B:Circle
题目描述
现在我们要把1…n这n个数字首尾连接组成一个环，使得相邻元素互质的对数尽可能多。请输出最大对数。
输入描述:
一行一个整数n(1≤ n≤ 1000)。
输出描述:
一行一个整数表示答案。
输入
4
输出
4
说明
样例的一种构造方法为1 4 3 2。
题解：输入和输出题。i 和 i+1肯定互质，1和n肯定也互质，把1到n连成一串就可以了。输入即输出QAQ
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
printf("%d\n",n);
return 0;
}
C:Tree
题目描述
修修去年种下了一棵树，现在它已经有n个结点了。
修修非常擅长数数，他很快就数出了包含每个点的连通点集的数量。
澜澜也想知道答案，但他不会数数，于是他把问题交给了你。
输入描述:
第一行一个整数n (1≤ n ≤ 10^6)，接下来n-1行每行两个整数ai,bi表示一条边 (1≤ ai,bi≤ n)。
输出描述:
输出n行，每行一个非负整数。第i行表示包含第i个点的连通点集的数量对109+7取模的结果。
示例1
输入
6
1 2
1 3
2 4
4 5
4 6
输出
12
15
7
16
9
9
题解： 如果题目只要求求出每个点的子树内联通点集数量，那很显然是 所有儿子dp值加一 的积
当时往上衍生的方案数有点难处理，我们发现显然根结点的答案就是dp值
假设我们当前处理结点x，我们已知x的父节点的答案，那么很显然为那么往上面衍生的答案数很显然为temp: ans[fa]/(dp[x]+1)
，所以ans[x]=(temp+1)*dp[x] 但是这题还有一个坑点
如果之前乘上一个dp[x]+1的时候，dp[x]+1%mod恰好为0，如今想要将其贡献消除，乘上一个逆元是做不到的 可以采用暴力消除影响
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+100;
const ll mod=1e9+7;
ll fast(ll x,ll n) {
ll ans=1;
for(;n;n>>=1,x=x*x%mod)
if(n&1) ans=ans*x%mod;
return ans;
}
ll inv(ll x) {
return fast(x,mod-2);
}
vector<int>edge[N];
ll dp[N],ans[N],sta[N],f[N];
void dfs(int x,int fa) {
dp[x]=1;f[x]=fa;
for(auto &v:edge[x]) if(v!=fa) {
dfs(v,x);
dp[x]*=(dp[v]+1);
dp[x]%=mod;
}
}
void dfs2(int x,int fa) {
if(x!=1) {
if((dp[x]+1)%mod) {
sta[x]=ans[fa]*inv(dp[x]+1)%mod;
ans[x]=dp[x]*(1+sta[x])%mod;
}
else {
ll temp=sta[fa]+1;
for(auto v:edge[fa]) if(v!=x&&v!=f[fa])
temp=temp*(dp[v]+1)%mod;
sta[x]=temp;
ans[x]=(temp+1)*dp[x]%mod;
}
}
for(auto v:edge[x])
if(v!=fa) dfs2(v,x);
}
int main() {
int n;cin>>n;
for(int i=1;i<n;i++) {
int u,v;
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs(1,0);
ans[1]=dp[1];
dfs2(1,0);
for(int i=1;i<=n;i++) {
printf("%lld\n",ans[i]);
}
}
D:绝地求生pudg
示例1
输入
1
4 6
输出
Case 1: 12
示例2
输入
2
2147483647 2147483648
10000007 531233
输出
Case 1: 4611686016279904256
Case 2: 5312333718631
又是1条复杂的题目，头大QAQ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline void read(T &x) {
x=0;
T f=1;
char ch=getchar();
while(ch<'0' || ch>'9') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch<='9' && ch>='0') {
x=x*10+(ch-'0');
ch=getchar();
}
x*=f;
}
string multiple(string p,string q)
{
string s="";
int n,a[1000],b[1000],c[1000],la,lb,lc,temp;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
la=p.size();
lb=q.size();
for (int i=0; i<la; i++) a[la-i]=p[i]-'0';
for (int i=0; i<lb; i++) b[lb-i]=q[i]-'0';
lc=1;
temp=0;
for (int i=1; i<=la; i++) {
temp=0;
for (int j=1; j<=lb; j++) {
c[i+j-1]=a[i]*b[j]+temp+c[i+j-1];
temp=c[i+j-1]/10;
c[i+j-1]%=10;
}
c[i+lb]=temp;
}
lc=la+lb;
while(c[lc]==0 && lc>1) lc--;
for(int i=lc; i>=1; i--) s+=char(c[i])+'0';
return s;
}
ll L=110;
ll sub(ll *a,ll *b,ll La,ll Lb)
{
if(La<Lb) return -1;
if(La==Lb) {
for(int i=La-1; i>=0; i--) {
if(a[i]>b[i]) break;
else if(a[i]<b[i]) return -1;
}
}
for(int i=0; i<La; i++) {
a[i]-=b[i];
if(a[i]<0) a[i]+=10,a[i+1]--;
}
for(int i=La-1; i>=0; i--)
if(a[i]) return i+1;
return 0;
}
string div(string n1,string n2,ll nn)
{
string s,v;
ll a[L],b[L],r[L];
ll La=n1.size(),Lb=n2.size(),i,tp=La;
fill(a,a+L,0);
fill(b,b+L,0);
fill(r,r+L,0);
for(i=La-1; i>=0; i--) a[La-1-i]=n1[i]-'0';
for(i=Lb-1; i>=0; i--) b[Lb-1-i]=n2[i]-'0';
if(La<Lb || (La==Lb && n1<n2)) return n1;
ll t=La-Lb;
for(int i=La-1; i>=0; i--) {
if(i>=t) b[i]=b[i-t];
else b[i]=0;
}
Lb=La;
for(int j=0; j<=t; j++) {
ll temp;
while((temp=sub(a,b+j,La,Lb-j))>=0) {
La=temp;
r[t-j]++;
}
}
for(i=0; i<L-10; i++) r[i+1]+=r[i]/10,r[i]%=10;
while(!r[i]) i--;
while(i>=0) s+=r[i--]+'0';
i=tp;
while(!a[i]) i--;
while(i>=0) v+=a[i--]+'0';
if(v.empty()) v="0";
if(nn==1) return s;
if(nn==2) return v;
}
int T;
string a,b;
string gcd(string x,string y) {
string temp;
while(y!="0") {
temp=div(x,y,2);
x=y;
y=temp;
}
return x;
}
int main() {
read(T);
int pol=0;
while(T-- ) {
cin>>a>>b;
string t=multiple(a,b);
string y=gcd(a,b);
cout<<"Case "<<++pol<<": ";
cout<<div(t,y,1)<<endl;
}
return 0;
}
E:[水]悠悠碧波
题目描述
帕秋莉掌握了一种水属性魔法
这种魔法可以净化黑暗
帕秋莉发现对于一个黑暗的咒语s，可以使用这个水元素魔法净化它，净化的咒语是一个最长的字符串t，t满足以下条件：
它是s的前缀
它是s的后缀
除前缀和后缀外，它还在s中出现过至少一次
既然你都学会了，那么净化的工作就交给你了！
输入描述:
一行字符串 s ，代表黑暗咒语
输出描述:
一个字符串 t ，表示满足条件的最长净化咒语
输入
tqrwantoacthisproblembutqristooweaktodoitqr
输出
tqr
备注:
对于60%的数据，s长度≤100
对于100%的数据，s长度≤100,000
保证存在可行的净化咒语
题解：划分一下前缀、后缀和中间部分所在的区间，查找比对，if 判断就好了。
#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
cin>>s;
string t;
int n=s.size();
for(int i=1;i<=n/3;i++)
{
string a=s.substr(0,i);
string b=s.substr(i,n-2*i);
string c=s.substr(n-i,i);
if(a==c&&b.find(a)!=b.npos) t=a;
}
cout<<t<<endl;
}
本文地址：https://blog.csdn.net/Luoxiaobaia/article/details/107328542