题解：CF1970D3 Arithmancy (Hard)

lgx57 · 2025-02-07 14:30:09 · 题解

写了一个不需要打表的程序，以 9843 \operatorname{ms} 获得了全球最劣解。

记号说明：

D1 只需要随便打几个字符串就可以了。但 D2 就无法像这样直接随机。经过我的尝试，我的程序最多只能随机出 n=25 的解。这引导我们去想更好的随机方式。

容易发现，我们如果每一次随机都重新计算 n 个字符串，速度会很慢。于是我们可以考虑递推。每一次先构造好前面的字符串，再随机当前的字符串，直到当前字符串与前面的字符串的 f，与前面都不同。

但是即使这样，直接随机字符串依然很困难，这主要体现在 2 个方面：

1. 每一次计算 f 的速度比较慢（O(n \log n)）。

2. 字符串的格式不确定，随机状态非常多。

这 2 点都启发我们找到一个固定的字符串的格式，使得 f 的计算也很方便。

当 \text{X} 和 \text{O} 都很多的时候，f 显然不方便计算，于是我们可以考虑比较极端的构造，例如全部都是 \text{X} 或全部都是 \text{O}。但是显然不满足条件。于是我们可以只改一个字符，从而使字符串都是形如 \text{XO} 后面跟上一堆 \text{X}。

对于这种字符串，我们容易检验 n 比较小的时候是可以递推的，于是大胆猜测 n=1000 时递推不会错。

现在只要处理的问题就是：如何快速计算 f？

可以通过尝试小的例子来找出规律:

设第 i 个字符串的长度为 x，第 j 个字符串的长度为 y。那么：

然后代码的实现是非常简单的。我们使用一个 map 来存储答案，每一次递推求答案的时候新开一个 map 来判断当前这个字符串放进答案中是否可行。如果可行，就把这个字符串与前面字符串的 f 值存到答案里，否则就尝试更长的字符串。

最后的询问只要输出 map 里储存的两个字符串的编号即可。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define endl '\n'
#define pb push_back
#define ls(p) ((p)<<1)
#define rs(p) ((p)<<1|1)
#define lowbit(x) ((x)&(-(x)))
#define abs(x) ((x)>0?(x):(-(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define gc getchar
#define pc putchar
#define sz(v) ((int)(v.size()))
using namespace std;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
inline int read(){
    int x=0,f=1;
    char ch=gc();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=gc();}
    return x*f;
}
inline void print(int x){
    if (x<0) pc('-'),x*=-1;
    if (x<10) pc(x+'0');
    else print(x/10),pc(x%10+'0');
}
int work(int x,int y){// f 函数
    return x>=y?x*(y+2)-1:(x+3)*(y-1)-1;
}
int n;
unordered_map<int,pii> ans;
unordered_map<int,bool> mp;
const int N=1005;
int b[N];// b_i=len(a_i)
string a[N];
void init(){
    int now=1;
    for (int i=1;i<=n;i++){
        bool f=1;
        do{
            now++;//增加长度
            f=1;
            mp.clear();
            int cnt=work(now,now);
            if (ans.count(cnt)){
                f=0;
                continue;
            }
            mp[cnt]=1;
            for (int _=1;_<i;_++){
                cnt=work(b[_],now);
                if (ans.count(cnt)||mp.count(cnt)){
                    f=0;
                    continue;
                }
                mp[cnt]=1;
                cnt=work(now,b[_]);
                if (ans.count(cnt)||mp.count(cnt)){
                    f=0;
                    continue;
                }
                mp[cnt]=1;
            }
            if (f){// 如果可以，把当前字符串与前面的字符串的 f 值放进 ans 中
                ans[work(now,now)]={i,i};
                for (int _=1;_<i;_++){
                    ans[work(b[_],now)]={_,i};
                    ans[work(now,b[_])]={i,_};
                }
            }
        }while (!f);
        a[i]="XO";
        for (int _=1;_<=now-2;_++) a[i]+='X';//存储答案
        b[i]=now;
    }
}
void sol(){
    for (int i=1;i<=n;i++) cout<<a[i]<<endl;
    int q;
    cin>>q;
    while (q--){
        int x;
        cin>>x;
        cout<<ans[x].fi<<' '<<ans[x].se<<endl;
    } 
}
signed main(){
    cin>>n;
    init();
    sol();
    return 0;
}

温馨提示：如果你 TLE on #15，请不要使用 map，改成 unordered_map。