题解：P15879 [ICPC 2026 NAC] Evil Judges
Calamity_Link
·
·
题解
Upd
5.10 初稿。
思路
观察发现交换 s_i 与 s_{i+1} 只会影响 s_i 与 s_{i-1} 这个子序列。因此答案即为操作 0 次时的序列中剩余合法的子序列的数量 -M。
注意因为操作 0 次时的序列中剩余合法的子序列的数量可能爆 int，所以要开 long long。
代码注释：
# AC Code
```cpp
#include<bits/stdc++.h>
using namespace std;
string s;
long long M,A[200000],C[200000],K[200000],cnt,i;
int main(){
cin>>s>>M;
if(s[0]=='A')
A[0]=1;
else if(s[0]=='C')
C[0]=1;
else
K[0]=1;
for(i=1;i<s.length();i++){
if(s[i]=='A')
A[i]=1;
else if(s[i]=='C')
C[i]=1;
else
K[i]=1;
A[i]+=A[i-1];
C[i]+=C[i-1];
K[i]+=K[i-1];
}
for(i=0;i<s.length()-1;i++)
if(s[i]=='A')
cnt+=C[s.length()-1]-C[i]+K[s.length()-1]-K[i];
if(cnt-M>0)
cout<<cnt-M;
else
cout<<0;
return 0;
}
```