hahahaha我竟然没掉好高兴啊hahahaha

A - Grid game

我刚开始的时候想把上面两行放竖着的，下面两行放横着的，刚准备交，突然觉得没那么简单，如果一列的话也能消掉，怎么办啊我是智障！！！

然后才发现把下面的一行不放不就好了。。

#include
    
     using namespace std;char gc() {//  static char buf[100000],*p1,*p2;//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;    return getchar();}template
     
      int read(T &ans) {    T f=1;ans=0;    char ch=gc();    while(!isdigit(ch)) {        if(ch==EOF) return EOF;        if(ch=='-') f=-1;        ch=gc();    }    while(isdigit(ch))        ans=ans*10+ch-'0',ch=gc();    ans*=f;return 1;}template
      
       int read(T1 &a,T2 &b) {    return read(a)==EOF?EOF:read(b);}template
       
        int read(T1 &a,T2 &b,T3 &c) {    return read(a,b)==EOF?EOF:read(c);}typedef long long ll;const int Maxn=1100000;const int inf=0x3f3f3f3f;const ll mod=998244353;int vx[2][4]= {
    {1,1,1,1},{3,3,4,4}};int vy[2][4]= {
    {1,2,3,4},{1,3,1,3}};char s[Maxn];int main() {    scanf("%s",s);    int n=strlen(s);    int c0=0,c1=0;    for(int i=0;i
       
      
     
    

B - Game with modulo

想了半天。

首先，如果模数为1，那么可以一次判断出来。

然后，如果\(x\ \text{mod}\ a<2x\ \text{mod}\ a\)，那么一定有\(a<2x\)，那么就可以倍增了。

#include
    
     using namespace std;char gc() {//  static char buf[100000],*p1,*p2;//  return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin))?EOF:*p1++;    return getchar();}template
     
      int read(T &ans) {    T f=1;ans=0;    char ch=gc();    while(!isdigit(ch)) {        if(ch==EOF) return EOF;        if(ch=='-') f=-1;        ch=gc();    }    while(isdigit(ch))        ans=ans*10+ch-'0',ch=gc();    ans*=f;return 1;}template
      
       int read(T1 &a,T2 &b) {    return read(a)==EOF?EOF:read(b);}template
       
        int read(T1 &a,T2 &b,T3 &c) {    return read(a,b)==EOF?EOF:read(c);}typedef long long ll;const int Maxn=1100000;const int inf=0x3f3f3f3f;const ll mod=998244353;int vx[2][4]= {
    {1,1,1,1},{3,3,4,4}};int vy[2][4]= {
    {1,2,3,4},{1,3,1,3}};char s[Maxn];int main() {    scanf("%s",s);    while(s[0]=='s') {        int temp=1;        printf("? 0 1\n");        fflush(stdout);        scanf("%s",s);        if(s[0]=='y') {        for(;temp<=1000000000;temp<<=1) {            printf("? %d %d\n",temp,temp<<1);            fflush(stdout);            scanf("%s",s);            if(s[0]=='x') break;        }        for(int i=temp>>1;i;i>>=1) {            printf("? %d %d\n",temp,temp+i);            fflush(stdout);            scanf("%s",s);            if(s[0]=='x') continue;            temp+=i;        }        temp++;        }        printf("! %d\n",temp);        fflush(stdout);        scanf("%s",s);    }    return 0;}
       
      
     
    

C - Johnny Solving

首先构造一颗dfs树，如果树高大于等于n/k，那么直接输出路径即可。否则这棵树至少有k个叶子。

因为每个点度数至少为3，那么每一个叶子至少有两条返祖边。所以对于每一个叶子都至少能找到三个与它直接相连的祖先，按照深度依次记为i,j,k。

如果\(d_{i,j}\%3==1\)，那么这个环长度就是三的倍数，对于j,k同理。那么如果\(d_{i,j}\%3==1\text{且}d_{j,k}\%3==1\)，就有\(d_{i,k}\%3==2\)，所以一定能够找到不是三的倍数的环。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define qmin(x,y) (x=min(x,y))#define qmax(x,y) (x=max(x,y))#define vic vector
         
          #define vit vic::iterator#define pir pair
          
           #define fr first#define sc second#define mp(x,y) make_pair(x,y)#define rsort(x,y) sort(x,y),reverse(x,y)using namespace std;inline char gc() {// static char buf[100000],*p1,*p2;// return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; return getchar();}template
           
            int read(T &ans) { ans=0;char ch=gc();T f=1; while(!isdigit(ch)) { if(ch==EOF) return -1; if(ch=='-') f=-1; ch=gc(); } while(isdigit(ch)) ans=ans*10+ch-'0',ch=gc(); ans*=f;return 1;}template
            
             int read(T1 &a,T2 &b) { return read(a)!=EOF&&read(b)!=EOF?2:EOF;}template
             
              int read(T1 &a,T2 &b,T3 &c) { return read(a,b)!=EOF&&read(c)!=EOF?3:EOF;}typedef long long ll;const int Maxn=1100000;const int inf=0x3f3f3f3f;int to[Maxn],nxt[Maxn],first[Maxn],tot=1;int bj[Maxn],dep[Maxn],f[Maxn],a[4];int n,m,u,v,depmax,pos,k,cnt;inline void add(int u,int v) { to[tot]=v; nxt[tot]=first[u]; first[u]=tot++; to[tot]=u; nxt[tot]=first[v]; first[v]=tot++;}void dfs(int root) { if(dep[root]>depmax) { depmax=dep[root]; pos=root; } for(int i=first[root];i;i=nxt[i]) if(!dep[to[i]]) { f[to[i]]=root; dep[to[i]]=dep[root]+1; dfs(to[i]); }}signed main() {// freopen("test.in","r",stdin); read(n,m,k); for(int i=1;i<=m;i++) { read(u,v); add(u,v); } dep[1]=1; dfs(1); if(depmax>=n/k) { puts("PATH"); printf("%d\n",dep[pos]); for(int i=pos;i;i=f[i]) printf("%d ",i); } else { puts("CYCLES"); for(int i=1;i<=n;i++) bj[f[i]]=1; for(int i=1;i<=n;i++) if(!bj[i]) { cnt++; int num=0; for(int j=first[i];j;j=nxt[j]) { a[++num]=to[j]; if(num==3) break; } int x,y; if(dep[a[2]]>dep[a[1]]) swap(a[1],a[2]); if(dep[a[3]]>dep[a[2]]) swap(a[2],a[3]); if(dep[a[2]]>dep[a[1]]) swap(a[1],a[2]); if((dep[a[1]]-dep[a[2]])%3!=1) { x=a[1],y=a[2]; printf("%d\n%d %d",dep[a[1]]-dep[a[2]]+2,i,a[1]); } else if((dep[a[2]]-dep[a[3]])%3!=1) { x=a[2],y=a[3]; printf("%d\n%d %d",dep[a[2]]-dep[a[3]]+2,i,a[2]); } else { x=a[1],y=a[3]; printf("%d\n%d %d",dep[a[1]]-dep[a[3]]+2,i,a[1]); } do { x=f[x]; printf(" %d",x); } while(x!=y); putchar('\n'); if(cnt==k) break; } } return 0;}
             
            
           
          
         
        
       
      
     
    

D - Professional layer

首先求出所有数的gcd，然后分解质因数，质因数的个数不超过11个，记为m。

然后将每一个\(a_i\)只保留gcd分解出的质因数这些质因数，那么不同的\(a_i\)不会很多，记为M，实际上只有大约1w个。

对于每一种数，显然只要保留最小的m个数即可，因为不可能选超过m个数，其他的不会影响答案。

然后考虑对于每一个子集，显然对于这个子集，影响答案的还是最小的能够选出这个子集的m个数，那么对于每一个数都记下会影响答案的子集，然后对于每个数进行DP，这样保证每个数之多被选一次。这个过程其实就是枚举子集，那么这个复杂度就是\(O(mM2^m+m^23^m)\)。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include