题解：CF1970D3 Arithmancy (Hard)

写了一个不需要打表的程序，以

9843 \operatorname{ms}

获得了全球最劣解。

记号说明：

$f(i,j)$ 为第 $i$ 个与第 $j$ 个字符串拼接后的本质不同的子串个数。

D1 只需要随便打几个字符串就可以了。但 D2 就无法像这样直接随机。经过我的尝试，我的程序最多只能随机出

n=25

的解。这引导我们去想更好的随机方式。

容易发现，我们如果每一次随机都重新计算

n

个字符串，速度会很慢。于是我们可以考虑递推。每一次先构造好前面的字符串，再随机当前的字符串，直到当前字符串与前面的字符串的

f

，与前面都不同。

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

2

个方面：

每一次计算 $f$ 的速度比较慢（ $O(n \log n)$ ）。
字符串的格式不确定，随机状态非常多。

这

2

点都启发我们找到一个固定的字符串的格式，使得

f

的计算也很方便。

当

\text{X}

和

\text{O}

都很多的时候，

f

显然不方便计算，于是我们可以考虑比较极端的构造，例如全部都是

\text{X}

或全部都是

\text{O}

。但是显然不满足条件。于是我们可以只改一个字符，从而使字符串都是形如

\text{XO}

后面跟上一堆

\text{X}

。

对于这种字符串，我们容易检验

n

比较小的时候是可以递推的，于是大胆猜测

n=1000

时递推不会错。

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

f

？

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

设第

i

个字符串的长度为

x

，第

j

个字符串的长度为

y

。那么：

f(i,j)=\begin{cases} x(y+2)-1 & x \ge y \\ (x+3)(y-1)-1 & \text{otherwise} \end{cases}

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

f

值存到答案里，否则就尝试更长的字符串。

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

CPP

#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。

题解：CF1970D3 Arithmancy (Hard)

文章操作

相关推荐

评论

题解：CF1970D3 Arithmancy (Hard)