荐 牛客算法周周练14题解

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