Codeforces Round #777 (Div. 2） 简训

导语涉及的知识点题目

A Madoka and Math DadB Madoka and the Elegant GiftC Madoka and Childish PranksD Madoka and the Best School in Russia 参考文献

日常训练，官方题解写的好麻烦…

思维，模拟，数论，分类

链接：Codeforces Round #777 (Div. 2)

题目大意：给出一个正整数n，构造出一个正整数x，x每一位不为0，相邻两位不相同，并且x尽量大

思路：与其让位上的数大，不如让位数更多，直接拆成1和2即可

代码

#include 
#define int long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e5+5;
int n,t;
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>t;
    while(t--) {
        cin >>n;
        int ans=n/3,res=n%3;//拆成多个1+2
        if(res==1)//如果剩下的是1，那么12循环
            while(ans--)cout <<12;
        else//否则21循环
            while(ans--)cout <<21;
        if(res)cout < 
B Madoka and the Elegant Gift 
题目大意：略
 
思路：直接判断每个2×2的矩阵里是不是恰好有3个黑，如果有则一定不行
 
代码
 
#include 
#define int long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e5+5;
int n,t,m,Next[4][2]= {0,1,0,-1,1,0,-1,0};
char maze[121][121];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>t;
    while(t--) {
        cin >>n>>m;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                cin >>maze[i][j];
        bool flag=0;
        for(int i=1; i<=n-1; i++)
            for(int j=1; j<=m-1; j++) {
                int ans=0;
                for(int k=i; k<=i+1; k++)
                    for(int p=j; p<=j+1; p++)
                        if(maze[k][p]=='1')
                            ans++;
                if(ans==3)flag=1;
            }
        flag?cout <<"NOn":cout <<"YESn";
    }
    return 0;
}
 
C Madoka and Childish Pranks 
题目大意：略
 
思路：贪心的想，每次拿上白下黑或者左白右黑的2×2即可，一开始想着从上向下涂，但是不行，因为这样最后一个块就无法修正了，因此从最后一行最后一个开始向前涂，因为前一个是可以通过一个单独的白修正的
 
代码
 
#include 
#define int long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e5+5;
int n,t,m,x1[maxn],y1[maxn],x2[maxn],y2[maxn];
char maze[121][121],op[121][121];
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>t;
    while(t--) {
        cin >>n>>m;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++) {
                cin >>maze[i][j];
                op[i][j]='0';
            }
        if(maze[1][1]=='1') {//只有左上角为黑的时候才无解
            cout <<-1<=1; i--)//从最后一行开始填
            for(int j=m; j>=1; j--) {
                if(op[i][j]==maze[i][j])continue;//如果一样就跳过
                if(op[i][j]=='0'&&maze[i][j]=='1') {//如果要白变黑
                    if(j==1) {//第一个，只能向上一个拓展
                        op[i][j]='1';
                        op[i-1][j]='0';
                        x1[++ans]=i-1;
                        y1[ans]=j;
                        x2[ans]=i;
                        y2[ans]=j;
                    } else {//否则向左拓展
                        op[i][j]='1';
                        op[i][j-1]='0';
                        x1[++ans]=i;
                        y1[ans]=j-1;
                        x2[ans]=i;
                        y2[ans]=j;
                    }
                } else if(op[i][j]=='1'&&maze[i][j]=='0') {//黑变白直接赋值即可
                    op[i][j]='0';
                    x1[++ans]=i;
                    y1[ans]=j;
                    x2[ans]=i;
                    y2[ans]=j;
                }
            }
        cout < 
D Madoka and the Best School in Russia 
题目大意：给出相关定义：如果一个数是d的倍数，那么这个数被认为是好数，如果一个数是好数并且不能被表示为两个好数的乘积，那么这个数就是美数，现在给出一个关于d的好数x，判断它是否至少有两种分解方式表示为多个美数的乘积（不同的定义为使用的数字集合不同）
 
思路：分多种情况讨论，假设
    
     
      
       
        x
       
       
        =
       
       
        b
       
       
        ×
       
       
        
         d
        
        
         a
        
       
       
        ,
       
       
        b
       
       
        %
       
       
        d
       
       
        ≠
       
       
        0
       
      
      
       x=b×d^a,b%d≠0
      
     
    x=b×da,b%d​=0
 

     
      
       
        
         a
        
        
         =
        
        
         1
        
       
       
        a=1
       
      
     a=1，此时
     
      
       
        
         x
        
       
       
        x
       
      
     x只能分成
     
      
       
        
         b
        
        
         ×
        
        
         d
        
       
       
        b×d
       
      
     b×d，或者把
     
      
       
        
         b
        
       
       
        b
       
      
     b拆分，显然不管是
     
      
       
        
         b
        
       
       
        b
       
      
     b还是拆分后的
     
      
       
        
         b
        
       
       
        b
       
      
     b都不是好数，则输出
     
      
       
        
         N
        
        
         O
        
       
       
        NO
       
      
     NO
     
      
       
        
         b
        
       
       
        b
       
      
     b为合数且
     
      
       
        
         a
        
        
         >
        
        
         1
        
       
       
        agt 1
       
      
     a>1，显然可以将
     
      
       
        
         b
        
       
       
        b
       
      
     b拆成几个数之积，每个数分配一个
     
      
       
        
         d
        
       
       
        d
       
      
     d，并且有多种拆分和分配方式，输出
     
      
       
        
         Y
        
        
         E
        
        
         S
        
       
       
        YES
       
      
     YES
     
      
       
        
         d
        
       
       
        d
       
      
     d为质数（
     
      
       
        
         b
        
       
       
        b
       
      
     b为质数），显然没办法拆，和第一种情况一样，输出
     
      
       
        
         N
        
        
         O
        
       
       
        NO
       
      
     NO
     
      
       
        
         d
        
       
       
        d
       
      
     d为合数且不为质数的幂数（
     
      
       
        
         b
        
       
       
        b
       
      
     b为质数），如果
     
      
       
        
         a
        
        
         =
        
        
         2
        
       
       
        a=2
       
      
     a=2，那么还是只能拆成
     
      
       
        
         b
        
        
         ×
        
        
         d
        
       
       
        b×d
       
      
     b×d和
     
      
       
        
         d
        
       
       
        d
       
      
     d，输出
     
      
       
        
         N
        
        
         O
        
       
       
        NO
       
      
     NO，否则若
     
      
       
        
         a
        
        
         >
        
        
         2
        
       
       
        a>2
       
      
     a>2，那么一定可以将一个
     
      
       
        
         d
        
       
       
        d
       
      
     d分解成
     
      
       
        
         p
        
        
         ×
        
        
         q
        
        
         （
        
        
         g
        
        
         c
        
        
         d
        
        
         (
        
        
         p
        
        
         ,
        
        
         q
        
        
         )
        
        
         =
        
        
         1
        
        
         ）
        
       
       
        p×q（gcd(p,q)=1）
       
      
     p×q（gcd(p,q)=1），将
     
      
       
        
         d
        
       
       
        d
       
      
     d与
     
      
       
        
         b
        
        
         ,
        
        
         q
        
        
         ,
        
        
         p
        
       
       
        b,q,p
       
      
     b,q,p等进行配对与组合即可，一定有多种方式（例如
     
      
       
        
         a
        
        
         =
        
        
         3
        
       
       
        a=3
       
      
     a=3，可以得到
     
      
       
        
         q
        
        
         ×
        
        
         b
        
        
         ×
        
        
         d
        
       
       
        q×b×d
       
      
     q×b×d和
     
      
       
        
         p
        
        
         ×
        
        
         d
        
       
       
        p×d
       
      
     p×d）输出
     
      
       
        
         Y
        
        
         E
        
        
         S
        
       
       
        YES
       
      
     YES
     
      
       
        
         d
        
       
       
        d
       
      
     d为合数且为质数的幂数（
     
      
       
        
         b
        
       
       
        b
       
      
     b为质数），假设
     
      
       
        
         d
        
        
         =
        
        
         
          p
         
         
          k
         
        
       
       
        d=p^k
       
      
     d=pk，情况就变得复杂起来，只有
     
      
       
        
         d
        
        
         =
        
        
         
          p
         
         
          2
         
        
        
         ,
        
        
         x
        
        
         =
        
        
         
          p
         
         
          7
         
        
       
       
        d=p^2,x=p^7
       
      
     d=p2,x=p7时是
     
      
       
        
         N
        
        
         O
        
       
       
        NO
       
      
     NO，具体解释如下，如果
     
      
       
        
         a
        
        
         >
        
        
         2
        
        
         ,
        
        
         k
        
        
         >
        
        
         1
        
       
       
        a>2,k>1
       
      
     a>2,k>1，那么可以将
     
      
       
        
         
          d
         
         
          a
         
        
        
         =
        
        
         
          p
         
         
          
           a
          
          
           k
          
         
        
       
       
        d^a=p^{ak}
       
      
     da=pak分成
     
      
       
        
         
          p
         
         
          
           2
          
          
           k
          
          
           −
          
          
           1
          
         
        
        
         ,
        
        
         
          p
         
         
          
           k
          
          
           +
          
          
           1
          
         
        
        
         ,
        
        
         
          p
         
         
          k
         
        
        
         ,
        
        
         …
        
       
       
        p^{2k-1},p^{k+1},p^k,dots
       
      
     p2k−1,pk+1,pk,…，即
     
      
       
        
         
          p
         
         
          
           k
          
          
           −
          
          
           1
          
         
        
        
         d
        
        
         ,
        
        
         p
        
        
         d
        
        
         ,
        
        
         d
        
        
         ,
        
        
         …
        
       
       
        p^{k-1}d,pd,d,dots
       
      
     pk−1d,pd,d,…，如果
     
      
       
        
         k
        
        
         >
        
        
         2
        
        
         (
        
        
         a
        
        
         >
        
        
         2
        
        
         )
        
       
       
        k>2(a>2)
       
      
     k>2(a>2)，即使
     
      
       
        
         b
        
        
         =
        
        
         p
        
       
       
        b=p
       
      
     b=p，则原式=
     
      
       
        
         
          p
         
         
          
           a
          
          
           k
          
          
           +
          
          
           1
          
         
        
       
       
        p^{ak+1}
       
      
     pak+1仍然可以分成至少两种：
     
      
       
        
         
          p
         
         
          k
         
        
        
         ,
        
        
         
          p
         
         
          
           k
          
          
           −
          
          
           1
          
         
        
        
         
          p
         
         
          k
         
        
        
         ,
        
        
         b
        
        
         p
        
        
         
          p
         
         
          k
         
        
        
         ,
        
        
         …
        
       
       
        p^k,p^{k-1}p^k,bpp^k,dots
       
      
     pk,pk−1pk,bppk,…和
     
      
       
        
         
          p
         
         
          k
         
        
        
         ,
        
        
         
          p
         
         
          
           k
          
          
           −
          
          
           2
          
         
        
        
         
          p
         
         
          k
         
        
        
         ,
        
        
         b
        
        
         
          p
         
         
          2
         
        
        
         
          p
         
         
          k
         
        
        
         ,
        
        
         …
        
       
       
        p^k,p^{k-2}p^k,bp^2p^k,dots
       
      
     pk,pk−2pk,bp2pk,…，但是，当
     
      
       
        
         k
        
        
         =
        
        
         2
        
        
         ,
        
        
         a
        
        
         =
        
        
         3
        
        
         ,
        
        
         b
        
        
         =
        
        
         p
        
       
       
        k=2,a=3,b=p
       
      
     k=2,a=3,b=p时，无论如何都无法拆分出两种方案，输出
     
      
       
        
         N
        
        
         O
        
       
       
        NO
       
      
     NO，其余为
     
      
       
        
         Y
        
        
         E
        
        
         S
        
       
       
        YES
       
      
     YES
 
那么第5,6其实可以合并得到：d为合且a=2不行，k=2,a=3,b=p不行其余都行
 
代码
 
#include 
#define int long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=5e5+5;
int t,x,d;
int prime(int x) {
    if(x==2)return -1;
    if(x%2==0)return 2;
    for(int i=3; i<=x/i; i+=2)
        if(x%i==0)return i;
    return -1;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >>t;
    while(t--) {
        cin >>x>>d;
        int cnt=0;
        while(x%d==0) {
            ++cnt;//获得a
            x/=d;
        }
        if(cnt==1) {//a=1
            cout <<"NOn";
            continue;
        }
        if(prime(x)!=-1) {//b为合数且a>1
            cout <<"YESn";
            continue;
        }
        if(prime(d)!=-1&&d==prime(d)*prime(d))//d为合数且k=2
            if(x==prime(d)&&cnt==3) {//b=p,a=3
                cout <<"NOn";
                continue;
            }
        if(cnt>2&&prime(d)!=-1) {//a>2且d为合数
            cout <<"YESn";
            continue ;
        }
        cout <<"NOn";//d为质数
    }
    return 0;
}
 
参考文献 
Tutorial