竞赛讨论区 > 【题解】2021年牛客寒假集训营第一场题解
头像
神崎兰子
编辑于 2021-02-01 19:10
+ 关注

【题解】2021年牛客寒假集训营第一场题解 精

Updated:B（括号）的数据已经加强，大家可以再次提交试试（不影响rating和排名）

Level 0 对答案一时爽

对标cf难度：900
知识点：贪心
签到题。最小值显然是0。最大值只需要找到有多少答案牛妹和牛牛是一样的，用题目总数加上这个数即可。

#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
int n;
int main(){
    int i,j;
    string a,b;
    cin>>n;
    cin.get();

    getline(cin, a, '\n');
    getline(cin, b, '\n');
    a.erase(remove_if(a.begin(), a.end(), ::isspace), a.end());
    b.erase(remove_if(b.begin(), b.end(), ::isspace), b.end());
    int cnt=0;
    for(i=0;i<n;i++)if(a[i]==b[i])cnt++;
    cout<<n+cnt<<" "<<0;

}

level 1 括号

对标cf难度：1300
知识点：构造、贪心
注意到题目要求字符串长度不超过，而大概是三万多不到4万，所以可以在8万以内完成构造。
一种简单的构造方式是这样：找到一个数，求出 的商和余数，那么则有 。所以先用个左括号，再用个右括号，构成的字符串有个括号对。之后在第个左括号的后面插入一个右括号，就正好增加了个括号对，符合题目要求。
大概长这个样子：
(((....((()((((...((())))....)))))
注意要特判k=0的情况，不要输出空串。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,i;
    cin>>n;
    if (n == 0) {
        cout << ")(" << endl;
    }
    else {
        int p=sqrt(n);
        int c=n/p,y=n%p;
        for(i=0;i<y;i++)printf("(");
        printf(")");
        for(;i<p;i++)printf("(");
        for(i=0;i<c;i++)printf(")");
    }
}

level 2 限制不互素对的排列

对标cf难度：1500
知识点：构造、数学
观察到不超过的一半，那么就简单了。
由于不大于的所有正整数***有个偶数（向下取整），那么如果k<n/2的话，直接取出k+1个偶数依次排列，再从开始从小到大即可。可以证明，后面的部分一定是相邻两两互素的。
如果k=n/2，那么有一个方法是，先取出所有的偶数，除了6以外依次排列，然后6后面接一个3（6和3显然不互素），然后3后面接1、5、7...依次从小到大。
举个例子，当n=10，k=5时，构造的结果是这样的：
2 4 8 10 6 3 1 5 7 9
要注意特判的情况，因为n=5，k=2的时候无法在6后面接一个3了（不存在正整数6），所以无解。
ps:如果 的时候怎么构造？

#include<bits/stdc++.h>
using namespace std;
int tong[100010];
int main(){
   // freopen("13.in","r",stdin);
   // freopen("13.out","w",stdout);
    int n,k,i;
    cin>>n>>k;
    if(n<6){
        if(k==n/2)cout<<-1;
        else{
            cout<<2;
            tong[2]=1;
            int i=4;
            while(k--)cout<<" "<<i,tong[i]=1,i+=2;
            for(i=1;i<=n;i++)if(!tong[i])cout<<" "<<i;
        }
    }
    else{
        if(k==n/2){
            for(i=2;i<=n;i+=2){
                if(i!=6)cout<<i<<" ",tong[i]=1;
            }
            cout<<6<<" "<<3<<" ";
            tong[6]=tong[3]=1;
            for(i=1;i<=n;i+=2){
                if(!tong[i])cout<<i<<" ",tong[i]=1;
            }
        }
        else{
            cout<<2;
            tong[2]=1;
            int i=4;
            while(k--)cout<<" "<<i,tong[i]=1,i+=2;
            for(i=1;i<=n;i++)if(!tong[i])cout<<" "<<i;
        }
    }
}

level 2 一群小青蛙呱蹦呱蹦呱

对标cf难度：1500
知识点：数论
我们可以发现，到最后剩余的数一定是不能表示为素数幂形式的数。
因此可以对每个素数对最终答案的贡献分别计算。
对于素数2而言，最大的贡献是（后面无法找到有个2的贡献）。
对于大于2的素数p而言，最大的贡献是（后面无法找到有个p的贡献）。
先线性筛出7.5e7以内的所有素数，然后统计每个素数的贡献后相乘即可。

#include<bits/stdc++.h>
using namespace std;
#define N 80010000
#define ll long long
int num[N], prim[5000060];
int pn = 0;
void table(){
    memset(num, -1, sizeof(num));
    for(int i = 2;i < N;i++){
        if(num[i]) prim[pn++] = i;
        for(int j = 0;j < pn && 1LL*i*prim[j] < N;j++){
            num[i*prim[j]] = 0;
            if(i % prim[j] == 0) break;
        }
    }
}
int main(){
    table();
    int i;
    int n;
    ll res=1,mod=1e9+7;
    cin>>n;
    if(n<6){cout<<"empty";return 0;}
    for(i=1;prim[i]<=n/2;i++){
        ll p=prim[i],temp=1;
        while(temp*p<=n/2)temp*=p;
        res=res*temp%mod;
    }
    ll temp2=1;
    while(temp2*2<=n/3)temp2*=2;
    res=res*temp2%mod;
    cout<<res;
}

level 3 点一成零

对标cf难度：1700
知识点：并查集
假设连通块数量为n，那么总方案数就是
每次操作有可能增加或减少连通块的数量，并改变连通块的大小，用并查集维护即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int fa[250010];
int kdm[250020];
string a[505];
int n;
int mod=1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll inv(ll x){
    return power(x,mod-2);
}
int f(int x){
    if(fa[x]==x)return x;
    return f(fa[x]);
}
void uni(int x,int y){
    int p=f(x),q=f(y);
    if(p==q)return;
    if(kdm[p]<kdm[q]){
        fa[p]=q;
        kdm[q]+=kdm[p]+1;
    }
    else {
        fa[q]=p;
        kdm[p]+=kdm[q]+1;
    }
}
int visited[505][505];
void dfs(int x,int y){
    visited[x][y]=1;
    if(x>0&&!visited[x-1][y]&&a[x-1][y]=='1')dfs(x-1,y);
    if(x<n-1&&!visited[x+1][y]&&a[x+1][y]=='1')dfs(x+1,y);
    if(y>0&&!visited[x][y-1]&&a[x][y-1]=='1')dfs(x,y-1);
    if(y<n-1&&!visited[x][y+1]&&a[x][y+1]=='1')dfs(x,y+1);
}
int main(){
   // freopen("10.in","r",stdin);
  //  freopen("10.out","w",stdout);
    int i,j;
    cin>>n;
    for(i=0;i<n;i++)cin>>a[i];
    for(i=0;i<n*n;i++)fa[i]=i;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if(j<n-1&&a[i][j]=='1'&&a[i][j+1]=='1'){
                uni(i*n+j,i*n+j+1);
            }
            if(i<n-1&&a[i][j]=='1'&&a[i+1][j]=='1'){
                uni(i*n+j,(i+1)*n+j);
            }
        }
    }
    int cnt=0;
    ll res=1;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if(a[i][j]=='1'&&!visited[i][j]){
                cnt++;
           //     cout<<kdm[f(n*i+j)]+1<<endl;
                res=res*(kdm[f(n*i+j)]+1)%mod;
                dfs(i,j);
            }
        }
    }
   // cout<<cnt<<endl;
    for(i=1;i<=cnt;i++)res=res*i%mod;
 //    cerr<<"RES:"<<res<<endl;
    int q;
    cin>>q;
    while(q--){
        int x,y;
        cin>>x>>y;
        if(a[x][y]=='1'){
            cout<<res<<endl;
        }
        else{
            int temp=1;
            cnt++;
            res=res*cnt%mod;
       //          cerr<<"RES:"<<res<<endl;
            a[x][y]='1';
            if(x>0&&a[x-1][y]=='1'&&f(n*(x-1)+y)!=f(n*x+y)){
                res=res*inv(kdm[f(n*(x-1)+y)]+1)%mod;
                temp+=kdm[f(n*(x-1)+y)]+1;
                uni(n*(x-1)+y,n*x+y);
                res=res*inv(cnt)%mod;
                cnt--;
            }
            //     cerr<<"RES:"<<res<<endl;
            if(x<n-1&&a[x+1][y]=='1'&&f(n*(x+1)+y)!=f(n*x+y)){
                res=res*inv(kdm[f(n*(x+1)+y)]+1)%mod;
             //   cout<<kdm[f(n*(x+1)+y)]+1<<endl;
                temp+=kdm[f(n*(x+1)+y)]+1;
                uni(n*(x+1)+y,n*x+y);
                res=res*inv(cnt)%mod;
                cnt--;
            }
          //       cerr<<"RES:"<<res<<endl;
            if(y>0&&a[x][y-1]=='1'&&f(n*x+y-1)!=f(n*x+y)){
                res=res*inv(kdm[f(n*x+y-1)]+1)%mod;
                temp+=kdm[f(n*x+y-1)]+1;
                uni(n*x+y-1,n*x+y);
                res=res*inv(cnt)%mod;
                cnt--;
            }
         //        cerr<<"RES:"<<res<<endl;
            if(y<n-1&&a[x][y+1]=='1'&&f(n*x+y+1)!=f(n*x+y)){
                res=res*inv(kdm[f(n*x+y+1)]+1)%mod;
                temp+=kdm[f(n*x+y+1)]+1;
                uni(n*x+y+1,n*x+y);
                res=res*inv(cnt)%mod;
                cnt--;
            }
            //  cout<<temp<<" "<<kdm[f(x*n+y)]+1<<endl;
            res=res*temp%mod;
            cout<<res<<endl;
        }
    }
}

level 3 红和蓝

对标cf难度：1700
知识点：树、搜索、dp
可以先树形dp预处理出每个节点子树的节点个数。那么当且仅当每个节点满足以下条件有解：

  • 若当前节点x与父节点颜色相同，那么它的子节点子树大小必须为偶数，子节点颜色和x不同。
  • 若当前节点x与父节点颜色不同，那么它的子节点子树大小一定有且仅有一个奇数、其他的均为偶数。x的“奇数大小子树”的那个子节点颜色和x相同，其他都和x不同。 
#include<bits/stdc++.h>
using namespace std;
vector<int>g[200020];
int dp[200020];
int su(int x,int pr){
    int i,sum=1;
    for(i=0;i<g[x].size();i++){
        if(g[x][i]!=pr){
            sum+=su(g[x][i],x);
        }
    }
    return dp[x]=sum;
}
char out[200020];
int jud=0;
char f(char c){
    if(c=='R')return 'B';
    return 'R';
}
void dfs(int x,int pr,char c){
    if(jud)return;
    out[x]=c;
    int cnt=0,i;
    for(i=0;i<g[x].size();i++){
        if(g[x][i]!=pr){
            cnt+=dp[g[x][i]]&1;
        }
    }
    if(out[x]==out[pr]){
        if(cnt!=0){jud=1;return;}
        for(i=0;i<g[x].size();i++){
            if(g[x][i]!=pr){
                dfs(g[x][i],x,f(c));
            }
        }
    }
    else {
        if(cnt!=1){jud=1;return;}
        for(i=0;i<g[x].size();i++){
        if(g[x][i]!=pr){
            if(dp[g[x][i]]&1)dfs(g[x][i],x,c);
                else dfs(g[x][i],x,f(c));
            }
        }
    }
}
int main(){
    int n,i;
    cin>>n;
    for(i=0;i<n-1;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dp[1]=su(1,-1);
   // for(i=1;i<=n;i++)cout<<dp[i]<<endl;
    out[0]='B';
    dfs(1,0,'R');
    if(jud)cout<<-1;
    else for(i=1;i<=n;i++)cout<<out[i];
}
/*
6
1 2
2 3
3 4
3 5
5 6
*/

level 4 幂塔个位数的计算

对标cf难度：2100
知识点：找规律、欧拉降幂（划掉）
计算a↑↑n

  • 当n为1时，直接输出a的个位数即可。
  • 当n=2时，如果a的个位数是2、3、7、8，那么需要观察a的十位数是奇数还是偶数。因为，而2、3、7、8的幂的个位数是4个一循环，所以只用观察a模4是2还是0就行。
    如果a的个位数是其他的，那么可以直接输出答案：a的个位数是0 1 5 6 9输出本身即可。a个位数是4则输出6。
  • 当n大于2时，由于，而如果a是偶数，模4的值是确定的，所以的个位数也是确定的。而如果a是奇数（特指个位数是3和7），那么模4取决于模4的值。如果模4为1，那么模4也是1，此时a的个位数是3和7的话，的个位数也是3和7，否则应为7和3。
    a的个位数是{0,1,2,3,4,5,6,7,8,9}时，对应的的个位数为{0,1,6,7,6,5,6,3,6,9}。

不过这道题也可以欧拉降幂直接秒掉，但由于我欧拉降幂不是很熟，所以这里就不讲解了，想学习的同学可以自行百度。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int out[10]={0,1,6,7,6,5,6,3,6,9};
int main(){
    ll a,b;
    string A,B;
    cin>>A>>B;
    if(B.length()==1&&B[B.length()-1]=='1'){
        cout<<A[A.length()-1];
        return 0;
    }
    a=(A[A.length()-1]-'0')%10;
    if(A[A.length()-1]=='3'||A[A.length()-1]=='7'){
        if(A.length()==1||(A[A.length()-2]-'0')%2==0){
            cout<<out[a];
        }
        else{
            cout<<a;
        }
        return 0;
    }


    if((a!=2&&a!=8)||(B.length()>1||B[B.length()-1]!='2')){
        cout<<out[a];

    }
    else{
        if(a==2){
        if(A.length()==1||(A[A.length()-2]-'0')%2==0){
            cout<<4;
        }
        else cout<<6;
        }
        else{
            if(A.length()==1||(A[A.length()-2]-'0')%2==0){
            cout<<6;
        }
        else cout<<4;
        }
    }
}

level 4 串

对标cf难度：2000
知识点：dp
定义dp[i]为长度为i且包含子序列"us"的字符串的数量。
那么对于长度i+1而言，包含子序列"us"的字符串有两类：
①前i个字符已经包含了子序列"us"，后面接任意一个字符。数量为dp[i]*26
②前i个字符包含字母u，但不包含子序列"us"。后面再接一个字符's'即可。数量为26^i-25^i-dp[i]。
两者相加即为dp[i+1]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int mod=1e9+7;
ll power(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
ll dp[1000100]={0};
int main(){
    dp[1]=0;
    dp[2]=1;
    int n,i;
    cin>>n;
    for(i=3;i<=1e6;i++)dp[i]=(power(26,i-1)-power(25,i-1)+25*dp[i-1]+mod)%mod;
    ll res=0;
    for(i=1;i<=n;i++)res=(res+dp[i])%mod;
    cout<<res;
    return 0;
}

level 4 三棱锥之刻

对标cf难度：2000
知识点：计算几何
根据r和a的关系一共分4类情况：
①染色面积为0
②染色面积为4个圆形
③染色面积为三棱锥的内表面减去12个小三角（不是三角形，而是一个三角形往内刨掉一个弓形）
④染色面积为三棱锥的内表面全体
分类讨论分别计算即可。

#include<bits/stdc++.h>
using namespace std;

int main(){
    double pi=acos(-1);
    double a,r=1;
    cin>>a>>r;
    double ma=sqrt(6)/4*a,mi=ma/3;
    double allar=sqrt(3)*a*a;

    double dd=sqrt(2)/4*a;
  //  cout<<"debug:"<<ma<<" "<<mi<<" "<<dd<<endl;
    if(r<mi)cout<<0<<endl;
    else if(r<dd){
        printf("%.5f\n",4*pi*(r*r-mi*mi));
    }
    else if(r<ma){
        //小等边三角形+小等腰三角形-扇形
        double temp=sqrt(r*r-mi*mi);
        double th=pi-asin(sqrt(3)/6*a/temp);
        double ntr=pi-th-pi/6;
   //     cout<<ntr<<endl;
        double d=sin(ntr)*temp*2;
      //  double d2=sin(ntr)*sqrt(3)/3*a/sin(th);
       // cout<<d<<endl;
        double h=sqrt(temp*temp-d*d/4);
        double ar=sqrt(3)/4*d*d+d*h/2-ntr*temp*temp;
        printf("%.5f\n",allar-12*ar);
    }
    else{
        printf("%.5f\n",allar);
    }


}

level ？ 好玩的数字游戏

对标cf难度：？
知识点：模拟
这道题并没有什么算法，模拟就完事了。
考验的是大家的码力和debug能力。

#include<bits/stdc++.h>
using namespace std;
long long f(long long x,int p){
    long long r=(x%p)*(x%p)/10%p;
    return (r^(1LL<<17)^(1LL<<57))%p;
}
int a[10][10];
int pp;
int cnt=0;
void gaow(int x){       //先移动，再合并，最后移动
    int i,j;
    for(i=1;i<4;i++){
        for(j=i-1;j>=0;j--){
            if(a[j][x]==0&&a[j+1][x])swap(a[j][x],a[j+1][x]),pp=1;
            else break;
        }
    }
    for(i=0;i<3;i++){
        if(a[i][x]==a[i+1][x]&&a[i+1][x]){
            pp=1;
            cnt+=a[i][x]*2;
            a[i][x]*=2;
            a[i+1][x]=0;
        }
    }
    for(i=1;i<4;i++){
        for(j=i-1;j>=0;j--){
            if(a[j][x]==0&&a[j+1][x])swap(a[j][x],a[j+1][x]),pp=1;
            else break;
        }
    }
}
void gaoa(int x){       //先移动，再合并，最后移动
    int i,j;
    for(i=1;i<4;i++){
        for(j=i-1;j>=0;j--){
            if(a[x][j]==0&&a[x][j+1])swap(a[x][j],a[x][j+1]),pp=1;
            else break;
        }
    }
    for(i=0;i<3;i++){
        if(a[x][i]==a[x][i+1]&&a[x][i]){
            pp=1;
            cnt+=a[x][i]*2;
            a[x][i]*=2;
            a[x][i+1]=0;
        }
    }
    for(i=1;i<4;i++){
        for(j=i-1;j>=0;j--){
            if(a[x][j]==0&&a[x][j+1])swap(a[x][j],a[x][j+1]),pp=1;
            else break;
        }
    }
}
void gaos(int x){       //先移动，再合并，最后移动
    int i,j;
    for(i=2;i>=0;i--){
        for(j=i+1;j<4;j++){
            if(a[j][x]==0&&a[j-1][x])swap(a[j][x],a[j-1][x]),pp=1;
            else break;
        }
    }
    for(i=2;i>=0;i--){
        if(a[i][x]==a[i+1][x]&&a[i][x]){
            pp=1;
            cnt+=a[i][x]*2;
            a[i+1][x]*=2;
            a[i][x]=0;
        }
    }
    for(i=2;i>=0;i--){
        for(j=i+1;j<4;j++){
            if(a[j][x]==0&&a[j-1][x])swap(a[j][x],a[j-1][x]),pp=1;
            else break;
        }
    }
}
void gaod(int x){       //先移动，再合并，最后移动
    int i,j;
    for(i=2;i>=0;i--){
        for(j=i+1;j<4;j++){
            if(a[x][j]==0&&a[x][j-1])swap(a[x][j],a[x][j-1]),pp=1;
            else break;
        }
    }
    for(i=2;i>=0;i--){
        if(a[x][i]==a[x][i+1]&&a[x][i]){
            pp=1;
            cnt+=a[x][i]*2;
            a[x][i+1]*=2;
            a[x][i]=0;
        }
    }
     for(i=2;i>=0;i--){
        for(j=i+1;j<4;j++){
            if(a[x][j]==0&&a[x][j-1])swap(a[x][j],a[x][j-1]),pp=1;
            else break;
        }
    }
}
void out(){
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}
int jud(){
    for(int i=0;i<4;i++){
        for(int j=0;j<4;j++){
            if(a[i][j]==0)return 0;
            if(i<3&&a[i][j]==a[i+1][j])return 0;
            if(j<3&&a[i][j]==a[i][j+1])return 0;
        }
    }
    return 1;
}
int main(){
    srand(time(0));
    int i,j,k,y;
    int x=10201,p,q;
    cin>>x>>p>>q;
    for(i=0;i<4;i++){
        for(j=0;j<4;j++){
            cin>>a[i][j];
        }
    }
    string s="";
 //   cout<<s<<endl;
    cin>>s;
    for(i=0;i<q*2;i+=2){
        pp=0;
        s[i+1]--;
        switch(s[i]){
            case 'W':gaow(s[i+1]-'0');break;
            case 'A':gaoa(s[i+1]-'0');break;
            case 'S':gaos(s[i+1]-'0');break;
            case 'D':gaod(s[i+1]-'0');break;
        }

        if(pp){
            while(1){
               // cout<<x%16/4<<" "<<x%4<<endl;
                if(a[x%16/4][x%4]==0){a[x%16/4][x%4]=2;x=f(x,p);break;}
                x=f(x,p);
            }

        }
        // out();

        if(jud())break;
    }
  //  out();
    cout<<cnt<<endl;
    if(i==q*2)cout<<"never die!";
    else cout<<i/2+1;
}
/*
10007 1000001 1
0 0 0 0
0 0 0 0
0 0 0 0
8 4 2 2
D4


*/
2024最新求职资料大礼包领取
真题
历年笔试真题附答案
搜狐畅游24届运营策划
2022年星环科技秋招笔试算法题
触宝科技2017秋季校招笔试客户端前端（第三批）
全部 >
面经
面试常考问题整理
0928携程笔试题解
硬件/IC/嵌入式高薪--你应该看看这些公司和岗位
22届-国企上岸经验分享
全部 >
内推
员工内推码获取
体验中心实习生招募 - 淘天集团
携程内推携程内推码
【美团】校招社招内推，简历免筛，所有岗位，进度可查，消息必回
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(22) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”