Codeforces Round #630 (Div. 2)

Codeforces Round #630 (Div. 2)

A. Exercising Walk

题意：给定abcd分别是从x，y向左右下上需要走的步数，不限次序。给定X1,X2,Y1,Y2,移动范围必须在他们的闭区间内。

脑子有坑上来就写复杂了还wa丢人o，贴出耻辱。

思路：二维坐标分别是-a，+b还有-c，+d。最小化坐标改变值，即d-c，b-a。当这两个个值介于x1-x&&x2-x之间、y1-y&&-y2-y之间时合法。特判两个为零的情况。

 
int main(){
    int t;
    cin>>t;
    LL a,b,c,d,x,y,x1,y1,x2,y2;
    int f1,f2;
    while(t--){
        f1=0;f2=0;
        cin>>a>>b>>c>>d;
        cin>>x>>y>>x1>>y1>>x2>>y2;
        if((a||b)&&(x2-x1)==0){puts3();continue;}
        if((c||d)&&(y2-y1)==0){puts3();continue;}
        b-=a;d-=c;x1-=x;x2-=x;y1-=y;y2-=y;
        if(b<=0){if(x1<=b) f1=1;}
        else{if(x2>=b) f1=1;}
        if(d<=0){if(y1<=d) f2=1;}
        else{if(y2>=d) f2=1;}
        if(f1&&f2) puts2();
        else puts3();
    }
    return 0;
}

B. Composite Coloring

题意：给定n个数字。要求用介于1~11之间的m个数字给他们着色。同种颜色的数字不互质。

思路：
给定ai范围1e3，168个质数，开头预处理用素数筛把数字都存起来放到vis中。每次看到一个数字就遍历vis中的所有素数，一旦有一个可以除断就以这个素数作为同一颜色的标记，放到vector中
最后遍历vector把答案放到ans中顺便统计一下颜色个数（要求1~m的颜色都要有），遍历输出

int a[maxn],vis[550],v[maxn];
int main(){
    int t=ird(),co=0;
    for(int i=2;i<=1000;i++){
        if(v[i]==0){
            v[i]=i;
            vis[++co]=i;
        }
        for(int j=1;j<=co;j++){
            if(vis[j]>v[i]||vis[j]>1000/i)break;
            v[i*vis[j]]=vis[j];
        }
    }//素数筛
    int n,ans,maxx,length;
    while(t--){
        n=ird();
        ans=0;
        maxx=0;
        vector<int> q[550];
        map<int,int>out;
        for(int i=1;i<=n;i++){
            a[i]=ird();
            for(int j=1;j<=co;j++){
                if(a[i]%vis[j]==0){
                    q[j].push_back(i);
                    break;
                }
            }
        }
        for(int i=1;i<300;i++){
            length=q[i].size();
            if(length!=0){
                ans++;
                for(int j=0;j<length;j++)
                    out[q[i][j]]=ans;
            }
        }
        cout<<ans<<endl;
        for(int i=1;i<=n;i++)
            cout<<out[i]<<" ";
        cout<<endl;
    }
    return 0;
}

C. K-Complete Word

题意：给定字符串s、周期k。要求将s变为回文串以周期k组成的字符串，输出最小改变字符个数。

u1s1这个还蛮顺的

思路：
题目保证了s的len是k的倍数，就可以将s分成n/k块，每块中的相同的序号字符都应该相同。考虑统计块间相同位置的26个字符出现次数，出现最多的保留（maxx），ans加上 n/k-maxx。
同时要求是以回文串组成的，在统计的时候直接把块内对称点处一起统计了，最后改成ans加上 2×（n/k）-maxx。
当k为奇数，就最后再单独考虑中间点。

string s;
int main(){
    int t,n,k,len,ans,maxx;
    cin>>t;
    while(t--){
        cin>>n>>k>>s;
        len=s.length();
        ans=0;
        for(int i=0;i<=k/2-1;i++){
            map<char,int> mp;
            maxx=0;
            int j=i;
            while(j<len){
                mp[s[j]]++;
                maxx=max(maxx,mp[s[j]]);
                j+=k;
            }
            j=k-1-i;//对称点
            while(j<len){
                mp[s[j]]++;
                maxx=max(maxx,mp[s[j]]);
                j+=k;
            }
            ans=ans+2*(n/k)-maxx;
        }
        if(k%2!=0){
            map<char,int> mp;
            maxx=0;
            int j=k/2;//注意不用+1
            while(j<len){
                mp[s[j]]++;
                maxx=max(maxx,mp[s[j]]);
                j+=k;
            }
            ans=ans+(n/k)-maxx;
        }
        cout<<ans<<endl;
    }
    return 0;
}

D. Walk on Matrix

这题是最气的啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊我都写出来了就是没输出nm找了半天我是sbbbbbbb气死我了气死我了气死我了

题意：给定k，还有一个程序。要求输出矩阵，使矩阵中路径（只能左/下走）所有数字&&操作后得到的ans中，最大值和程序输出的差值为k。
程序如下：
简单形容就是憨憨dp，没考虑位运算依次遍历了。

思路：看样例2基本上就清楚了。构造一个3 4大小的数组，统计k的最高1所在的位置记为co。让程序运行后旁边两条路大小分别是2^(co+1)和0，中间拐来拐去的一条路就是最大值k。
现在仔细想想矩阵大小可以直接缩小到2 3，路径只有三条的话就更easy了。憨憨也不会看不出没输出nm了？？？？？？好奇o

int ka[300];
int main(){
    int k=ird();
    int kk=k;
    int co=0;
    while(kk){
        if(kk%2)
            ka[co]++;
        kk/=2;
        co++;
    }
    if(ka[co]==0)
        co--;
    if(k==0){
        cout<<"1 1"<<endl<<1<<endl;
        return 0;
    }
    cout<<3<<" "<<4<<endl;
    for(int i=1;i<=3;i++){
        if(i==1){
            cout<<qpow(2,co+2)-1<<" "<<k<<" "<<k<<" "<<0<<endl;
        }
        if(i==2)
            cout<<qpow(2,co+1)<<" "<<qpow(2,co+2)<<" "<<k<<" "<<qpow(2,co+1)<<endl;
        if(i==3){
            for(int i=1;i<=3;i++)
                cout<<qpow(2,co+2)-1<<" ";
            cout<<k<<endl;
        }
    }
    return 0;
}

E. Height All the Same

题意：给定n×m的方格，每个格子有aij大小的数字。合法操作1：直接在aij上加2；合法操作2：在相邻方格各+1。现给定l、r要求aij大小在闭区间内。问能通过一系列合法操作使得所有格子大小一样的方格分布有几种

思路：
因为每次操作总数都加了2，不改变总的奇偶性，
而最后如果高度要达到一致，当n×m是奇数时，不论a的总和是多少，总是能找到一个高度，使得两者的差是偶数。得出结论1：n×m是奇数时是所有的情况，即（r-l+1）^（n×m）
当n×m是偶数时，偶数减去奇数还是偶数，没法对中间差值进行调节。所以对a的总和要求为非奇数
注意除2的时候用乘法逆元

LL n,m,l,r;
int main(){
    cin>>n>>m>>l>>r;
    LL ans=(n*m)%MOD;
    ans=(qpow(r-l+1,n*m))%MOD;
    LL ji=(r-l+1)/2,ou=(r-l+1)/2;
    if((r-l+1)%2){
        if(l%2)
            ji++;
        else
            ou++;
    }
    if(n*m%2){
        cout<<ans<<endl;
        return 0;
    }
    LL tt=(qpow(r-l+1,m*n)%MOD-qpow(ji-ou,m*n)%MOD+MOD)%MOD;
    tt=(tt*qpow(2,MOD-2))%MOD;
    ans=(ans-tt+MOD)%MOD;
    cout<<ans<<endl;
    return 0;
}