Codeforces Round #630 (Div. 2) A-D题解

鉴于自己太菜，E就不会做了（目测是2300+的组合数学）。因此仅写一下前四题题解。

A

题意：向左 $a$ 步，向右 $b$ 步，向下 $c$ 步，向上 $d$ 步。初始在 $(x,y)$ , 活动区域必须在 $(x1,y1)$ 和 $(x2,y2)$ 表示的矩形。问是否可能。
知识点：实现。
预估难度：1100
思路：首先特判 $x1=x2$ 以及 $y1=y2$ 这两种情况。如果是这样的情况则对应方向不允许有位移；否则代数和之后不超过边界即可。
代码：

#include<bits/stdc++.h>;
using namespace std;
#define ll long long
int main(){
    ll n,t,i,j,k,sum=0,cnt=0;
    ll a,b,c,d;
    cin>>t;
    while(t--){
        ll x,y,x1,y1,x2,y2;
        cin>>a>>b>>c>>d;
        cin>>x>>y>>x1>>y1>>x2>>y2;
        if(x1==x2&&(a||b)){
            cout<<"No\n";
            continue;
        }
        if(y1==y2&&(c||d)){
            cout<<"No\n";
            continue;
        }
        x+=b-a;
        y+=d-c;
        if(x>=x1&&x<=x2&&y>=y1&&y<=y2){
            cout<<"Yes\n";
        }
        else cout<<"No\n";
    }
}

B

题意：给一个长度不超过1000的数组，每个数不超过1000，让你对每个数染色，要求若两数不互质则颜色相同，且总颜色不超过11种。
知识点：数论，计数。
预估难度：1400
思路：由于前10个素数是 $2,3,5,7…29$ ，第11个素数是 $31$ ，发现 $31^2<1000$ 但是 $31*37>1000$ ，也就是说，用前10个颜色将前10个素数的倍数染色后，1000以内所有数均两两互素，得解。
该题的实现相对比较麻烦，不知道大佬有没有简单的实现方式。
代码：

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

int main(){
    ll n,t,i,j,k,sum=0,cnt=0;
    ll a[1111],p[22]={1,2,3,5,7,11,13,17,19,23,29,31},b,c,d;
    cin>>t;
    while(t--){
        cin>>n;
        int jud[22]={0};
        ll ma=0,jud1=0,jud2=0;
        for(i=1;i<=n;i++){
            cin>>a[i];
            for(j=1;j<=10;j++){
                if(a[i]%p[j]==0){jud[j]=1;break;}
            }
            if(j>10)jud1=1;
        }
        k=1;
        int out[11];
        for(j=0;j<11;j++){
            if(jud[j])out[j]=k++;
        }
        cout<<k+jud1-1<<endl;
        for(i=1;i<=n;i++){
            for(j=1;j<=10;j++){
                if(a[i]%p[j]==0){
                    cout<<out[j]<<" ";
                    break;
                }
            }
            if(j==11)cout<<k<<" ";
        }
        cout<<endl;

    }
}

C

题意：给一个长度为n的字符串，让你将它修改成n/k段相等的回文段。求最小的修改次数。
知识点：字符串，计数。
预估难度：1600
思路：我们先将字符串拆分：
{XXX...XX}{XXX...XX}...{XXX...XX}
可以发现，由于每一段都是相等的回文段，那么每一段里的第 $1$ 个和第 $k$ 个字符全部相等，第 $2$ 个和第 $k-1$ 个字符全部相等……以此类推。这样只需要统计对于这种要求相等的情况、出现次数最多的字母即可。注意特判k是奇数时，回文段中间字符的统计情况。
代码：

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

int main(){
    ll n,t,i,j,k,sum=0,cnt=0;
    ll a[1111],p[22]={1,2,3,5,7,11,13,17,19,23,29,31},b,c,d;
    cin>>t;
    while(t--){
        cin>>n>>k;
        string s;
        cin>>s;
        ll cnt=0;
        for(i=0;i<k/2;i++){
            ll tong[26]={0};
            ll ma=0;
            for(j=0;j<n/k;j++){
                tong[s[j*k+i]-'a']++;
                ma=max(ma,tong[s[j*k+i]-'a']);
                tong[s[j*k+(k-i-1)]-'a']++;
                ma=max(ma,tong[s[j*k+(k-i-1)]-'a']);
            }
            cnt+=n/k*2-ma;
        }
        if(k&1){
            ll tong[26]={0};
            ll ma=0;
            i=k/2;
            for(j=0;j<n/k;j++){
                tong[s[j*k+i]-'a']++;
                ma=max(ma,tong[s[j*k+i]-'a']);
            }
            cnt+=n/k-ma;
        }
        cout<<cnt<<endl;
    }
}

D

题意：给一个错误的dp法计算位与路径最大值的算法，对于一个矩阵而言，这个算法和正确答案相差为 $k$ 。现在输入 $k$ ，让你还原那个矩阵。
知识点：构造
预估难度：1700
思路：这个题本来是非常难的，但题目很良心的给了个样例2，所以我们就样例2展开讨论。
3 4
7 3 3 1
4 8 3 6
7 7 7 3
让我们把它的“错误算法”的dp矩阵写出来：
7 3 3 1
4 0 3 2
4 4 4 2
我们发现，关键的地方在于最后那一步：本来应该是在不断位与过程将3传递下去，但最后一行的倒数第二个位置出现了个4，导致3&4=0，因此发生了偏差。
我们还可以发现，第二列是对结果没任何影响的，因此构造时可以忽略。
那么现在矩阵可以构造成这样：

$2^p-1$ $2^{p-1}-1$ $1$
$2^{p-1}$ $2^{p-1}-1$ $?$
$2^{p}-1$ $2^{p}-1$ $2^{p-1}-1$
其中 $2^{p-1}$ 为大于 $k$ 第一个 $2$ 的幂。
现在还差一个位置没推出来。我们可以根据计算得出，要得到最终差为 $k$ ，只需要让 $2^{p-1}-1\&?和2^{p-1}-1$ 的差绝对值为 $k$ 即可。令 $?$ 为 $2^{p-1}-k$ 就可以了。

代码：

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

int main(){
    ll n,t,i,j,k,sum=0,cnt=0;
    cin>>k;
    if(!k)cout<<1<<" "<<1<<endl<<1;
    else{
        cout<<3<<" "<<3<<endl;
        int p=1;
        for(;p<k+1;p*=2);
        t=2*p-1;
        p--;
        cout<<t<<" "<<p<<" "<<p<<endl;
        cout<<p+1<<" "<<p<<" "<<p-k<<endl;
        cout<<t<<" "<<t<<" "<<p<<endl;

    }
}