CF1970D1 Arithmancy (Easy) 题解

FFTotoro · 2024-05-05 19:50:41 · 题解

点这里前往游记。

拿到这个题全场首杀。

记 f(s) 为字符串 s 本质不同的子串个数。对于一个字符串 s，可以借助 AtCoder Library 快速计算 f(s)（什么你说 CF 不带 AT Library？你把他们代码粘贴进你的代码即可）。

显然对于询问的一个 f(x)，要能唯一地对应回去那两个字符串 s,t(s+t=x)，这里 + 表示连接。又由于还要确定两个字符串的顺序（即 s+t 和 t+s 是不同的），所以构造 \texttt{O}，\texttt{OO}，\texttt{OOOO} 这样简单的构造是不行的。

这个时候考虑乱搞。因为 D1 中 n\le 3（以下就拿 n=3 举例），而字符串长度限制是 30n=90，所以可以在键盘上面乱敲或者直接随机 3 个字符串，然后判断是否对于所有的 (i,j,k,l)(1\le i,j,k,l\le n) 满足 f(w_i+w_j)\neq f(w_k+w_l)。事实证明因为字符串数量很少而长度又很大，所以这 3\times 3=9 个数做到两两不同是很容易的。

对于 D2，我们需要一些更加进阶的技巧：D2 题解。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  if(n==1){
    cout<<"O"<<endl;
    int q; cin>>q;
    while(q--){
      int x,a,b; cin>>x;
      switch(x){
        case 2:a=1,b=1; break;
      }
      cout<<a<<' '<<b<<endl;
    }
  }
  if(n==2){
    cout<<"XOX\nOOOXXX"<<endl;
    int q; cin>>q;
    while(q--){
      int x,a,b; cin>>x;
      switch(x){
        case 14:a=1,b=1; break;
        case 34:a=1,b=2; break;
        case 33:a=2,b=1; break;
        case 51:a=2,b=2; break;
      }
      cout<<a<<' '<<b<<endl;
    } // 直接打表就行了
  }
  if(n==3){
    cout<<"XOX\nOOOXXX\nOOOOOOOOXXXXXXXXOXO"<<endl;
    int q; cin>>q;
    while(q--){
      int x,a,b; cin>>x;
      switch(x){
        case 14:a=1,b=1; break;
        case 34:a=1,b=2; break;
        case 183:a=1,b=3; break;
        case 33:a=2,b=1; break;
        case 51:a=2,b=2; break;
        case 240:a=2,b=3; break;
        case 180:a=3,b=1; break;
        case 237:a=3,b=2; break;
        case 483:a=3,b=3; break;
      }
      cout<<a<<' '<<b<<endl;
    }
  }
  return 0;
}