2020-2021 ICPC Southeastern European Regional Programming Contest (SEERC 2020)
B. Reverse Game
对于所有操作，都是在把1往后移动，也就是使逆序对数量减少，当当前串 s 没有逆序对的时候，游戏结束。
对于四个操作（10, 110, 100, 1010 => 01,011,001,0101），分别可以使原串减少1、1、2、2个逆序对
并且对于一个01串，可以转化为只包含：10、110、100、1010四种情况，其余字符串都可以被转化为（例如100000000）只包含10、110、100、1010的字符串。
那我们只需要统计字符串中逆序对的数量，我们发现，对于逆序对的数量n，若n%3不为0，那么先手都可以利用操作使当前逆序对数量变为(n%3=0)的状态，为必胜态，反之则必败。
#include<bits/stdc++.h>
using namespace std;
int main(){
int cnt=0;
string s;
cin>>s;
long long ans=0;
for(int i=0;i<s.size();i++){
if(s[i]=='1') cnt++;
else ans+=cnt;
}
if(ans%3) puts("Alice");
else puts("Bob");
return 0;
}
定义一个数组的和为其中两两元素的乘机之和。
现在给定我们一个数组，让我们求其连续的子数组中满足和 \(s\)%3=0 的个数。
假设当前数组中有两个数字 \([x,y]\),则当前\(s=x*y\),我们往其中加入一个\(z\),
则\(s_1=x*y+x*z+y*z\) ,即：\(s_1=s+(x+y)*z\)
我们构造一个前缀和数组，则对于一个序列\([l,r]\),它的和\(w\)可以表示为：\(w=w_{l-1}*(s_r-s_{l-1})\)
由于答案只跟3有关，我们可以先把所有数模上3，这个时候考虑dp
\(dp[i][j][k]\)表示以\(a[i]\)为结尾的，权重为\(j\)，和为\(k\)的数组的个数。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500010;
int f[N][5][5];
int a[N];
ll s[N];
ll ans;
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]%=3;
f[i][0][a[i]]++;
}
for(int i=1;i<=n;i++){
for(int j=0;j<3;j++){
for(int k=0;k<3;k++){
f[i][(j+a[i]*k)%3][(k+a[i])%3]+=f[i-1][j][k];
}
}
for(int sum=0;sum<3;sum++) ans+=f[i][0][sum];
}
cout<<ans<<endl;
return 0;
}
By 泽浩巨巨