Znzryb's Blog
0%

2025牛客WC4-C-Tokitsukaze and Balance String (hard)

Posted on Edited on

思路讲解

https://www.luogu.com/article/wa8c5zfe 还有一种差分想法，更加简洁，挺好的

10就是在差分数组中有一个-1，01就是差分数组中有一个1，把差分数组加起来，就能得到01数量-10数量的值，然后根据差分的结论，我们就知道差分总值只和首项和末项有关。

首先根据上题，我们需要发现两个结论：
1） 首尾相同的字符串一定是平衡的。
2） 首尾不相同的字符串一定是不平衡的。

这是为什么那？

直接证明这个结论比较难，可以这么想，大家可以想象一个都是0序列，将里面的0变为1（通过这一操作可以生成任何序列）会对10，01数量造成什么变化那？（其实我也不是很会证明，大家就随便看看吧）

image

我们发现，只有在对空情况的操作时，才会产生不平衡这样的问题

而且对空情况的左右两种镜像情况分别为一组，这两组中的任意两对都是互相抵消的（比如10++ && 01++ 就会使数列平衡）

那么其实就完成了，头尾都是0的情况嘛所有操作都使数列保持平衡，头尾都是1的情况对空操作也就抵消了，那么就得到了上述的结论。

有了这个结论以后剩下的就简单了，剩下的就看代码吧，关键地方有注释，然后注意特判只有单个字母的情况。

AC代码

AC

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75411197

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// Problem: Tokitsukaze and Balance String (hard)
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/95336/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3,mod=static_cast<ll>(1e9)+7;

ll N,T;
char S[MAXN];//Sd[MAXN];
ull ans=0,pow2[MAXN];

inline void solve(){
	cin>>N;
	ans=0;
	ll cnt=0;
	FOR(i, 1, N){
		cin>>S[i];
		if(S[i]=='?') ++cnt;
		// Sd[i]=S[i];
	}
	if(N==1){
		if(S[1]!='?') cout<<1<<'\n';
		else cout<<2<<'\n';
		return;
	}
	if(S[1]=='?' && S[N]=='?'){
		ans+=2*pow2[cnt-2]*(N-2);	// ?为0，0 1，1的情况
		//cerr<<ans<<'\n';
		ans%=mod;
		ans+=4*pow2[cnt-2];	// ?,? 1,0 0,1的情况(两种情况，每种情况有两种位置，所以*4)
		//cerr<<ans<<'\n';
		ans%=mod;
	}else if(S[1]=='?' || S[N]=='?'){
		ans+=pow2[cnt-1]*(N-2);
		ans%=mod;
		ans+=2*pow2[cnt-1];
		ans%=mod;
	}else{
		if(S[1]!=S[N]){
			ans=2*pow2[cnt];
			ans%=mod;
		}else{
			ans=pow2[cnt]*(N-2);
			ans%=mod;
		}
	}
	cout<<ans%mod<<'\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	pow2[0]=1;
	FOR(i,1,MAXN-5){
		pow2[i]=(pow2[i-1]*2)%mod;
	}
	while(T--){
		solve();
	}
	return 0;
}
/*
AC

*/

心路历程（WA，TLE，MLE……）