代碼

#include<bits/stdc++.h>using namespace std;const int N=1e5+10;int ans[N];void solve()
{//輸入字符串長度和字符串int n;string s;cin>>n>>s;//下面說的修改操作是進行異或操作//k表示前后對稱位置不相等的字符的對數//m表示前后對稱位置相等的字符的對數int k=0,m=0;//字符長度是奇數的情況//該情況最中間的字符可選擇性修改if(n&1){//表示的是最中間字符的下標int mid=n/2;//下面是模擬出前后位置不相等和相等的字符的對數int l=mid-1,r=mid+1;while(l>=0&&r<=n-1){if(s[l]!=s[r])k++;elsem++;l--,r++;}//不相等的字符一定需要修改，才可以實現回文串的要求//回文串需要的是，前后對稱位置的字符完全相等//前后位置不相等的元素，可以修改，也可以不修改//修改的話是提供兩次貢獻，有 m 對//最多提供 2m 次貢獻//所以修改的區間是 k-k+2m+1for(int i=0;i<=n;i++)if(i>=k&&i<=k+2*m+1)cout<<1;elsecout<<0;cout<<endl;return;}//下面表示的是字符串長度是偶數的情況//最好找一個樣例看一下下標的情況是否符合條件//下標很容易寫錯int mid=n/2;int l=mid-1,r=mid;//這里和上面板塊一摸一樣，直接復制過來的while(l>=0&&r<=n-1){if(s[l]!=s[r])k++;elsem++;l--,r++;}//cout<<k<<" "<<m<<endl;//字符串長度是偶數的話，沒有一個最中間的元素//一定需要修改 k 次以上//上限是 k+2m 次，并且每一次修改都是 k 次加 2 的整數次修改//前后對稱位置相等的時候，修改需要把兩個元素都修改for(int i=0;i<=n;i++)if(i>=k&&(i-k)%2==0&&i<=k+2*m)ans[i]=1;elseans[i]=0;for(int i=0;i<=n;i++)cout<<ans[i];cout<<endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin>>t;while(t--)solve();return 0;
}

簡短代碼

#include<bits/stdc++.h>using namespace std;void solve()
{int n;string s;cin>>n>>s;int cnt=0;for(int i=0;i<n/2;i++)if(s[i]!=s[n-i-1])cnt++;string ans(n+1,'0');for(int i=cnt;i<=n-cnt;i+=(n&1?1:2))ans[i]='1';cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin>>t;while(t--)solve();return 0;
}

#include<bits/stdc++.h>using namespace std;void solve()
{int n;string s;cin>>n>>s;//假設字符串長度是奇數，那么n/2表示的是最中間的位置的下標//假設是偶數，表示的是最中間兩個元素里面靠右邊的那個元素的//下標//cnt 統計的是前后對稱位置不相等元素的對數int cnt=0;for(int i=0;i<n/2;i++)if(s[i]!=s[n-i-1])cnt++;//初始化答案為全 0，學一下這種寫法string ans(n+1,'0');//判斷奇數和偶數的兩種情況，用 ? 這種語句簡短表示for(int i=cnt;i<=n-cnt;i+=(n&1?1:2))ans[i]='1';cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin>>t;while(t--)solve();return 0;
}

字符串

該題題目意思比較難懂，意思是說，把一個給定的字符串修改成回文串，修改的操作是用一個等長的字符串和原來的字符串進行異或操作，這兩個字符串都是 01 串

尋找的這個字符串中 1 的個數是需要統計的答案

最后輸出的答案是一個字符串，這個比較奇怪的輸出方式，字符串的下標表示的是前面說的統計出來的 1 的個數，假設符合條件就把該位置標記為 1 ，不符合條件就把這個位置標記為 0

解法是把前后對稱位置的不相等的元素的對數統計出來

我們知道，回文串的要求是前后對稱位置的元素相等，所以我們需要進行的操作就是把對稱位置不相等的進行一次修改，隨便修改一個即可，算一次操作，但是不可以對同一個元素修改兩次，不符合題意，兩個位置修改哪一個都不影響答案，答案只需要統計使用的 1 的數目

對稱位置相等的元素，可以進行修改，每一次修改需要把兩個元素都進行修改，要變一起變，大概這種，所以每一次對答案的貢獻值是 2

假設字符串長度是奇數的話，最中間的元素可以任意修改，也就是說可以不修改也可以修改一次

以上就是全部的思路，字符串長度是奇數的話，答案就是 k-k+2m+1，k 表示的是前后對稱位置的不相等元素的對數，m 表示的是前后對稱位置相等元素的對數

偶數的話，首先需要 k 次，然后每一次都是 +2 ,最大值是 k+2m