Codeforces Round #630 (Div. 2)A~E题解

A. Exercising Walk题意：询问能否在给定的区域访问内走指定的步数。思路：特判区域宽度或高度为1的情况。其他用相对位移与区域大小比较代码：#include <iostream>#include <cstring>#include <cmath>#include <algorithm>#include <stri...

gzr2018

156人浏览 · 2020-04-02 12:46:09

gzr2018 · 2020-04-02 12:46:09 发布

A. Exercising Walk

题意：

询问能否在给定的区域访问内走指定的步数。

思路：

特判区域宽度或高度为1的情况。其他用相对位移与区域大小比较

代码：

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
int main() {
    int t;
    cin>>t;
    while (t--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        int x,y;
        int x1,x2,y1,y2;
        cin>>x>>y>>x1>>y1>>x2>>y2;
        if((x1==x2&&a*b!=0)||(y1==y2&&c*d!=0)){
            puts("No");
            continue;
        }
        x1 = x-x1;
        x2 = x-x2;
        y1 = y-y1;
        y2 = y-y2;
 
        int ab1 = b-a;
        int ab2 = d-c;
        if(abs(x1)<(a-b)||abs(x2)<(b-a)||abs(y1)<(c-d)||abs(y2)<(d-c)){
            puts("No");
        }
        else puts("Yes");
    }
    return 0;
}

B. Composite Coloring

题意：

给定n个合数，每个数小于1000，用 $m$ （ $m < = 11$ ）种颜色给n个数染色。两个数的gcd如果大于1，可以染成同一种颜色。(大概是这个题意…)

思路：

首先每个数都是合数，其次都是小于1000，所以每个数的最小质因子必定小于( $\sqrt{1000}\approx33$ ),而小于33的质因子为11个，所以可以满足 $m < = 11$ 上面条件。

代码：

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <string>
using namespace std;
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int n;
int a[1005];
int ans[1005];
int prime[11]={2,3,5,7,11,13,17,19,23,29,31};
int c[11];
int cnt;
int main() {
    int t;
    cin>>t;
    while (t--){
        cnt =0;
        cin>>n;
        memset(c,0,sizeof(c));
        for(int i=0;i<n;i++)cin>>a[i];
        for(int i=0;i<n;i++){
            for(int j=0;j<11;j++){
                if(a[i]%prime[j]==0){
                    if(c[j]==0)c[j]=++cnt;
                    ans[i]=c[j];
                    break;
                }
            }
        }
        cout<<cnt<<endl;
        for(int i=0;i<n;i++) {
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

C. K-Complete Word

题意：

Word $s$ of length $n$ is called $k$ -comlete if

$s$ is a palindrome
$s$ ha s period of $k$
给定一个word，要求改变最少的字符，使之变成 $k$ -comlete。

思路：

可以分析到，要求单词周期为 $k$ ，而且为回文串，分析可得每一个周期内也是回文串。所以暴力判断每一些位置哪个字母出现次数最多即可。处理的时候，特殊处理一下周期为计数的串。

代码：

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <string>
using namespace std;
const  int N=2e5+10;
char str[N];
int a[26];
int main() {
   int t;
   cin>>t;
   while(t--) {
       int n, k;
       cin >> n >> k;
       cin >> str;
       int ans = 0;
       for (int i = 0; i < k / 2; i++) {
           memset(a, 0, sizeof(a));
           for (int j = 0; j < n / k; j++) {
               a[str[j * k + i] - 'a']++;
               a[str[j * k + k - i - 1] - 'a']++;
           }
           int max_cnt = *max_element(a, a + 26);
           //cout<<"max:"<<max_cnt<<endl;
            ans += n/k*2-max_cnt;
       }
       memset(a,0,sizeof(a));
       if(k%2){
           for(int i=0;i<n/k;i++){
               a[str[k/2+i*k]-'a']++;
           }
           int max_cnt = *max_element(a, a + 26);
           //cout<<ans<<endl;
           ans += n/k-max_cnt;
       }
       cout<<ans<<endl;
   }
    return 0;
}

D. Walk on Matrix

题意：

构造一个矩阵，使得标准算法的答案与给定算法答案差距为k。

思路：

可以分析到，这个题这样dp是不行的。有大佬告诉我怎么求出标准答案吗？（嘤嘤嘤）
既然是构造题，就构造一个简单的矩阵，使得题目给定算法为0，标准答案为k即可。（大家真厉害，我怎么没有想到，嘤嘤嘤）

代码：

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <string>
using namespace std;
int k;
const  int N=505;
int a[N][N];
int main() {
    cin>>k;
    if(k==0){
        cout<<1<<" "<<1<<endl;
        cout<<1<<endl;
    }
    else{
        int temp=1;
        while (temp<=k)temp<<=1;
        cout<<"2 3"<<endl;
        cout<<temp+k<<" "<<k<<" "<<0<<'\n';
         cout<<temp<<" "<<temp+k<<" "<<k<<'\n';
    }
    return 0;
}

E. Height All the Same

题意：

现在有一个 $n * m$ 的方格，第i行第j列有 $a [i] [j]$ 个方块。

执行以下操作任意次：

1、选择 $(i, j)$ 使 $a [i] [j]$ 加上2。

2、选择两个相邻的方格(相邻的方格存在一条公共边)，将其方格数加上1。

现在问初始 $a [i] [j]$ 可以是 $[L, R]$ 中的任意数，有多少种初始方案可以通过任意次数的操作后使所有的 $a [i] [j]$ 相等。

思路：

这个题确实似曾相识。
由于操作1，可以加2，所以可以不断使用操纵1，使得不同数字相差1。使用只有数字的奇偶性有关。
给出结论：
奇数和偶数的个数都是奇数的方案是不行的，否则可行。
论证：
如果全部奇数和偶数个数都为偶数个（奇数等效），使用操作1即可满足条件
如果全部奇数和偶数分别为一奇一偶（易知一偶一奇等效）。可以使用操作2不断交换奇数和偶数所在的方格的位置，一旦两个偶数连接到一起，就可以使用操作2变成两个奇数，这样全部都变成奇数了。
总的方格数量 $S = m * n$

如果S为奇数，那么奇数的个数和偶数个数的至少一个为偶数，则所有初始状态都满足条件。 $ans =(R-L+1)^S$
如果S为偶数,设 $x$ 为 $[L, R]$ 中奇数个数， $y$ 为 $[L, R]$ 中偶数个数。
合法的方案只能是：奇数和偶数的个数都是偶数。所以可以得到下面的公式
$=\sum_{i=0,i+=2}^S(\binom{S}{i}*x^i*y^{S-i})$
公式的含义是：从S个方格中，选偶数个作为奇数，其他偶数个作为偶数。
这个公式等效于： $=\frac{(x+y)^S+(x-y)^S}{2}$ 。因为这样奇数项恰好抵消，偶数项计算了两次。
由于中途求mod了，所以不能直接除2，需要乘2关于mod的逆元。然后奇数和偶数的差的绝对值求法在代码中体现，比较简单。
（这样应该比较好理解，看到网上的有些博客在公式推倒处存在一点错误，这里和大家一同学习）

代码：

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <string>
using namespace std;
#define ll long long
const  ll mod = 998244353;
ll qpow(ll a,ll x){
    ll ans = 1;
    while(x>0){
        if(x&1){
            ans = ans*a%mod;
        }
        x>>=1;
        a=a*a%mod;
    }
    return ans%mod;
}
int main() {
    ll n,m,L,R;
    cin>>n>>m>>L>>R;
    if(n*m%2){
        cout<<qpow((R-L+1),m*n)<<endl;
    }
    else{
        ll ans = qpow(R-L+1,n*m)+qpow((R-L+2)/2-(R-L+1)/2,n*m);
        ans =ans%mod*qpow(2,mod-2)%mod;
        cout<<ans<<endl;
    }
    return 0;
}