【题解】牛客寒假集训营第二场（C~J后八题）

牛牛与棋盘

https://ac.nowcoder.com/acm/contest/9982/H

Level 0 牛牛与棋盘

对标cf难度：700
知识点：模拟
签到题。按题意直接打印即可。

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

int main(){
    ll n,i,j,k,t,_=1;
   // cin>>_;
    while(_--){
        cin>>n;
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                if((i+j)%2==0)cout<<0;
                else cout<<1;
            }
            cout<<endl;
        }
    }

}

level 2 牛牛的“质因数”

对标cf难度：1600
知识点：dfs/dp，数论
我们可以根据x以及x的最小素因子k，推出 $F(x*p)$ 的值（p≤k）：等价于在 $F(x)$ 的前面添加一个p。这个用dfs搜索即可得出答案（需要先筛出4e6以内的素数）

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

#define N 4000600
int mod = 1e9+7;
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;
        }
    }
}

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 a[100010][2];
ll res=0,n;
ll gao(ll x){
    int cnt=0;
    while(x)x/=10,cnt++;
    return cnt;
}
void dfs(ll x,ll val,ll cnt,ll p){  //当前的值 当前的贡献 当前的位数 当前的最小素因子位置
    res=(res+val)%mod;
    for(int i=0;i<=p;i++){
        if(x*prim[i]<=n){
            dfs(x*prim[i],(val+power(10,cnt)*prim[i])%mod,cnt+gao(prim[i]),i);
        }
        else break;
    }
}
int main(){
    table();
    ll i,j,k,m,t,_=1;
   // cin>>_;
    while(_--){
        cin>>n;
        for(i=0;prim[i]<=n;i++){
            dfs(prim[i],prim[i],gao(prim[i]),i);
        }
        cout<<res;
    }

}

level 2 牛牛想要成为hacker

对标cf难度：1500
知识点：构造
前面用斐波那契数列填充，后面全部用1即可。

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

#define N 1000600
int mod = 1e9+7;
int num[N], prim[500060];
int pn = 0;
ll res=0,n;

ll a[100010];
int main(){
    a[0]=2;
    a[1]=3;
    ll i,j,k,m,t,_=1;
    for(i=2;i<=40;i++)a[i]=a[i-1]+a[i-2];
 //   cout<<a[40]<<endl;
   // cin>>_;
    while(_--){

        cin>>n;
        for(i=0;i<n;i++){
            if(i<40)cout<<a[i]<<" ";
            else {
                cout<<1<<" ";
               // cout<<a[i]<<" ";
            }
        }
    }

}

level 3 牛牛与交换排序

对标cf难度：1700
知识点：数据结构（双端队列）
这道题使用双端队列（deque）可以达到O(1)进行模拟翻转操作。
具体的方式是：正常情况下队列头进尾出，翻转后尾进头出，用一个变量记录是否翻转的状态即可。
由于k是固定的，并且翻转的区间单调递增，所以可以一次遍历 $O(n)$ 解决本题。

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

ll res=0,n;

ll a[100010],b[100010];
int main(){

    ll i,j,k,m,t,_=1;

   // cin>>_;
    while(_--){

        cin>>n;
        int m1=0;
        for(i=1;i<=n;i++){
            cin>>a[i];
        }
        for(i=1;i<=n;i++){
            if(a[i]!=i)break;
        }
        if(i==n+1){
            cout<<"yes\n1";
        }
        else{
            j=i;
            for(i=1;i<=n;i++)if(a[i]==j)break;
            int p=i,out=p-j+1;
            deque<int>q;
            for(i=j;i<p;i++)q.push_back(a[i]);
            int jud=0,temp=j,tt=1;
         //   cout<<p<<endl;
            for(i=p;i<=n;i++){
                if(tt){q.push_back(a[i]);}
                else q.push_front(a[i]);
                if(q.back()==temp){
                    q.pop_back();
                    tt=0;
                }
                else if(q.front()==temp){
                    q.pop_front();
                    tt=1;
                }
                else {jud=1;break;}
                temp++;
            }
            if(!jud){
                j=0;
                for(deque<int>::iterator it=q.begin();it!=q.end();it++){
                    b[j++]=(*it);
                //    cout<<(*it)<<endl;
                }
               // cout<<temp<<" "<<p<<endl;
                if(b[0]==temp){
                    for(i=0;i<j;i++){
                        if(b[i]!=temp+i)jud=1;
                    }
                }
                else{
                    for(i=0;i<j;i++){
                        if(b[i]!=n-i)jud=1;
                    }
                }
            }
            if(jud)cout<<"no";
          else   cout<<"yes"<<endl<<out;
        }
     //   cout<<a[i-1];
    }

}
/*
5
3 4 5 1 2
*/

level 3 牛牛与字符串border

对标cf难度：1800
知识点：字符串
分类讨论。
如果 $k*2≤n$ ，那么k、2k、...都要满足要求，在纸上画一下容易得出重复段长度为gcd(k,n)。
如果 $k*2>n$ ，可以发现重复段长度为 $n-k$ 即可。
用桶记录一下每个对应位置的次数，求出最大值。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m,i,j;
        string s;
        cin>>n>>m;
        cin>>s;
        string out="";
        int g=__gcd(n,m);
        if(n<m*2&&n!=m)g=n-m;
        for(i=0;i<g;i++){
            int tong[26]={0};
            for(j=i;j<n;j+=g){
                tong[s[j]-'a']++;
            }
            int ma=0,mi=0;
            for(j=0;j<26;j++){
                if(tong[j]>ma)ma=tong[j],mi=j;
            }
            out+='a'+mi;
        }
        for(i=0;i<n/g;i++)cout<<out;
        for(i=0;i<n%g;i++)cout<<out[i];
        cout<<endl;
    }
}

level 3 牛牛与整除分块

对标cf难度：1700
知识点：数论
将n/k分为两部分：若 $k\leq \sqrt{n}$ ，那么每个n/k都是不同的。否则每个n/k都是相同或连续的。
但需要注意特判一种特殊情况：若 $n=x^2-1=(x+1)*(x-1)$ ，那么 $k=\sqrt{n}=x-1$ ，这时n/x向下取整是x-1，和n/k=x+1相差为2，需要特判。
ps:这道题卡输入卡吐了。。不关同步cin会超时，关同步带endl会超时。
目前经过实验得出的结论是：关闭同步，并且不使用endl而是用'\n'是最快的，其次是scanf。不关同步或者使用endl都特别慢，遇到1e6级别的输入输出直接爆炸。。

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

#define N 1000600
int mod = 1e9+7;
int num[N], prim[500060];
int pn = 0;

ll res=0,n;

ll a[100010];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    a[0]=1;
    a[1]=1;
    ll i,j,k,m,t,_=1;

    scanf("%lld",&_);
   // cin>>_;
    while(_--){

        scanf("%lld%lld",&n,&k);
        if(k*k<=n)printf("%lld\n",k);
        else {
            ll cnt=sqrt(n);
            cnt+=5;
            while(cnt*cnt>n)cnt--;
            int jud=0;
            if(cnt*(cnt+2)==n)jud++;
            printf("%lld\n",cnt+(n/cnt-n/k)-jud);
        }
     //   cout<<a[i-1];
    }

}

level 4 牛牛与比赛颁奖

对标cf难度：2100
知识点：离散化、差分前缀和
这道题题意很明显，思路也很明显，按照题意模拟就行。注意数据范围到了1e9，这样离散化一下就变成1e5的数量级了。

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

#define N 1000600
int mod = 1e9+7;
int num[N], prim[500060];
int pn = 0;

ll res=0,n;

ll a[100010][2],lsh[300030],sum[300030],tong[100010];
map<int,int>mp;
int main(){

    ll i,j,k,m,t,_=1;

   // cin>>_;
    while(_--){

        cin>>n>>m;
        int c1=n/10+(n%10!=0),c2=n/4+(n%4!=0),c3=n/2+(n%2!=0);
        c1=max(c1,1);
        c1=max(c1,1);
        c1=max(c1,1);
        set<int>s;
        for(i=0;i<m;i++){
            int l,r;
            cin>>l>>r;
            a[i][0]=l;
            a[i][1]=r;
            s.insert(r+1);
            s.insert(l);
            s.insert(r);
        }
        j=1;
        for(set<int>::iterator it=s.begin();it!=s.end();it++){
            lsh[j]=(*it);
            mp[(*it)]=j++;
        }
        for(i=0;i<m;i++){
            int l=a[i][0],r=a[i][1];
            sum[mp[l]]++,sum[mp[r+1]]--;
        }

        for(i=1;i<300000;i++){
            sum[i]+=sum[i-1];
        }
        for(i=1;i<300000;i++){
            if(sum[i]){
                tong[sum[i]]+=lsh[i+1]-lsh[i];
            }
        }
     //   for(i=1;i<=m+1;i++)cout<<tong[i]<<endl;
      //  cout<<endl;
        int o1=0,o2=0,o3=0,temp=0;
   //     cout<<c1<<" "<<c2<<" "<<c3<<endl;
        int ou1=0,ou2=0,ou3=0;
        for(i=m;i>0;i--){
            temp+=tong[i];
          //  cout<<i<<" "<<temp<<endl;
            if(temp>=c1&&!o1)o1=i;
            if(temp>=c2&&!o2)o2=i;
            if(temp>=c3&&!o3)o3=i;
        }
        for(i=m;i>0;i--){
            if(i>=o1)ou1+=tong[i];
            else if(i>=o2)ou2+=tong[i];
            else if(i>=o3)ou3+=tong[i];
        }
        cout<<ou1<<" "<<ou2<<" "<<ou3<<endl;
       // cout<<tong[o3]<<" "<<tong[o2]<<" "<<tong[o1]<<endl;

    }

}

level 4 牛牛与跷跷板

对标cf难度：2000
知识点：最短路、双指针
看到这个题应该第一时间想到bfs求最短路，但怎么建图是个难点。
我的方法是:首先开1e5个vector。第i个vector存纵坐标为i的跷跷板（用结构体，存l、r以及跷跷板编号）。
然后对每个vector进行排序，这样在搞第i个vector的时候，可以用另外一个指针扫下一个vector，这样就能达成O(n)建图了。

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

#define N 1000600
int mod = 1e9+7;
int num[N], prim[500060];
int pn = 0;

ll res=0,n;

struct line{
    int l,r,i;
};
vector<line>a[100010];
vector<int>g[100010];
int dep[100010],visited[100010];
bool cmp(line a,line b){
    return a.l<b.l;
}
map<int,int>mp;
void out(){
    int i,j;
    for(i=0;i<4;i++){
        cout<<i<<":"<<endl;
        for(j=0;j<g[i].size();j++){
            cout<<g[i][j]<<" ";
        }
        cout<<endl;
    }
}
int main(){

    ll i,j,k,m,t,_=1;
   // table();
 //   cout<<a[40]<<endl;
   // cin>>_;
    while(_--){
        cin>>n;
        for(i=1;i<=n;i++){
            int y;
            line temp;
            cin>>y;
            cin>>temp.l>>temp.r;
            temp.i=i;
            a[y].push_back(temp);
        }

        for(i=0;i<=1e5;i++)sort(a[i].begin(),a[i].end(),cmp);
        for(i=0;i<=1e5;i++){

            k=0;
            for(j=0;j<a[i].size();j++){
                if(j<a[i].size()-1&&a[i][j].r==a[i][j+1].l){
                    int u=a[i][j].i,v=a[i][j+1].i;
                    g[u].push_back(v);
                    g[v].push_back(u);
                }
                if(i==1){
               //     cout<<a[i][0].l<<" "<<a[i+1][0].r<<endl;
                }
                while(k<a[i+1].size()&&a[i+1][k].r<=a[i][j].l)k++;
                while(k<a[i+1].size()&&a[i+1][k].l<a[i][j].r){
                    int u=a[i][j].i,v=a[i+1][k].i;

                    g[u].push_back(v);
                    g[v].push_back(u);
                    k++;
                }
                k--;
            }
        }
       // out();


        queue<int>q;
        q.push(1);
        visited[i]=1;
        while(!q.empty()){
            int temp=q.front();
            for(i=0;i<g[temp].size();i++){
                if(!visited[g[temp][i]]){
                    visited[g[temp][i]]=1;
                    dep[g[temp][i]]=dep[temp]+1;
                    q.push(g[temp][i]);
                }
            }
            q.pop();
        }
        cout<<dep[n];


    }

}
/*
4
1 2 5
0 0 4
1 0 1
2 0 3

*/

剩下的两道题一个数据结构，一个图论，都是我比较弱的部分（我有个数据结构和图论很强的队友，所以先不补了ww这两个题让队友补）
这场比赛的题目质量非常高，%%%%%%%智乃姐姐