CF1970D2 Arithmancy (Medium) 题解

FFTotoro · 2024-05-05 20:28:43 · 题解

点这里前往游记。

场切了这个 \color{Red}*2600，太舒服了。自从来了某学校，卡时、假算、乱搞能力显著增强；不过这题乱搞似乎就是真算。

建议先阅读 D1 题解。

我们沿用 D1 的做法，考虑随机一堆字符串然后打表。但是因为 n 比较大，所以 f(w_i+w_j) 有极大的概率会重复一些。由于这题 n\le 30，下文若无特殊说明则将 n 视为 30。

但是题面有说，交互库的询问方式是每次均匀随机选择两个下标 (i,j)(1\le i,j\le n) 问。于是可以得出，只要重复的 (i,j) 的数量不太多，1000 次询问是可以过去的。

考虑均匀随机地生成那些字符串。这样直接干肯定是过不去的，于是我们考虑加入如下的若干技巧，使得随机可以通过题目：

• 虽然说长度限制为 900，但是并不是让每个字符串长度都达到 900，这样反而不优：我们控制每个字符串的长度在 [450,900] 之间即可——如果 n<30 就类似地把长度控制在 [15n,30n] 之间；
• 时限很长，有 5\mathrm{s}，所以考虑卡时（前面卡时部分放个 4.8\mathrm{s} 比较合适，后面 1000 组交互 0.2\mathrm{s} 绰绰有余）：具体地，上面的字符串不止生成一组，一直随机若干组字符串，每次如果不同的 f(w_i+w_j) 的数量比上一次多那么就继承当前次的答案；
• 这种做法看起来不错，但是会在 n 不大不小（大约是 [7,18] 这个范围）的时候出错：因为在这个时候字符串不长，可供询问的 (i,j) 也不多，所以可能多重复几个 f(w_i+w_j) 就寄了；考虑每一位 \dfrac{1}{2} 概率为 \texttt{O} 或 \texttt{X} 生成的字符串有什么弊端——它的所有段内字符都相等的极长连续段不会太长，这样能产生的本质不同的子串个数必然也不是很多；于是我们将生成字符串的方式改一改——每次以 p\left(p>\dfrac{1}{2}\right) 的概率将该位的字符设为和前一位相等的字符，1-p 的概率设为和前一位不相等的，这样可以产生更多的本质不同的子串，经试验取 p=\dfrac{3}{5} 可以通过此题。

自此我们用乱搞切掉了一道 \color{Red}\mathrm{*2600}。

代码里面的 AtCoder Library 部分请自行补全，或使用 AtCoder Custom Test 测试样例。

放代码（GNU C++17, with AtCoder Library）：

#include<bits/stdc++.h>
#include<atcoder/string>
#define int long long
using namespace std;
mt19937 g(time(0));
int lst; inline bool get(){
  if(g()%5<=3)return lst;
  return lst=!lst;
} // 特殊的生成方式——3/5 的概率继承上一个
inline int f(string s){
  int n=s.length(),c=n*(n+1)>>1;
  for(int i:atcoder::lcp_array(s,atcoder::suffix_array(s)))c-=i;
  return c;
} // 计算本质不同的子串个数
main(){
  ios::sync_with_stdio(false);
  int n,bs=0,st=clock(); cin>>n;
  vector<string> v;
  map<int,pair<int,int> > mp;
  mt19937 g(time(0));
  uniform_int_distribution<> l(n*15,n*30);
  while(1.0*(clock()-st)/CLOCKS_PER_SEC<4.8){
    vector<string> a(n);
    for(int j=0;j<n;j++){
      int x=l(g);
      for(int k=0;k<x;k++)
        a[j]+=(get()?'X':'O');
    } // 随机生成字符串
    vector c(n,vector<int>(n));
    set<int> s;
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        s.emplace(c[i][j]=f(a[i]+a[j]));
    // 计算种类数，如果种类数大于当前最优解就更新
    if(s.size()>bs){
      bs=s.size(),v=a;
      for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
          mp[c[i][j]]=make_pair(i+1,j+1);
    } // 打表
  } // 卡时进行贪心
  for(int i=0;i<n;i++){
    cout<<v[i];
    if(i<n-1)cout<<'\n';
    else cout<<endl;
  } // 给出方案
  int q; cin>>q;
  while(q--){
    int x; cin>>x;
    auto [a,b]=mp[x];
    cout<<a<<' '<<b<<endl;
  } // 回答询问
  return 0;
}