H題Genta Game
題意：首先給定n和m，n為字串長度，接著給定字串，m次操作，問m次操作中有多少次會出現回文串
思路：因為給的資料范圍是1e5,所以時間復雜度應該控制在O（nlogn）以內，首先先把給定的字串預處理一下，查詢字串中有多少個不回文的部分，之后的每一次操作中，操作結束時判斷不回文的部分是否為0，如果是，結果加一，
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char a[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
int res=0;
int ans=0;
int n,m;
cin>>n>>m;
cin>>a;
int len=strlen(a);
for(int i=0,j=len-1;i<=j;i++,j--)
{
if(a[i]!=a[j])
res++;
}
for(int i=0;i<m;i++)
{
int x;
char c;
cin>>x>>c;
if(n%2==1&&x==n/2+1&&res==0)//特殊情況判定
ans++;
x--;
if(a[x]!=a[n-1-x])
{
if(a[n-1-x]==c)
{
res--;
}
}
else
{
if(a[x]!=c)
{
res++;
}
}
a[x]=c;
if(res==0)
ans++;
}
cout<<ans<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/272273.html
標籤：其他
上一篇：ios證書申請，最簡單的申請方法