2023年第十四届蓝桥杯大赛软件类省赛C&C++研究生组真题（包含代码&完整题解）

#include<bits/stdc++.h> #include<set> #include<vector> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; #define ll long long #define pii pair<int,int> #define debug1(x) cout<<x<<" " #define debug2(x) cout<<x<<endl #define rep1(a,b,c) for (int a = (b) ; a < (c) ; a+=1) #define rep2(a,b,c) for (int a = (b) ; a < (c) ; a+=2) const int INF = 0x3f3f3f3f; const int maxn = 1e6+10; const int mod = 998244353; vector<int> prime; bool is_prime[maxn]; //埃氏筛法 void Eratosthenes(int n) { is_prime[0] = is_prime[1] = false; for (int i = 2; i <= n; ++i) is_prime[i] = true; for (int i = 2; i <= n; ++i) { if (is_prime[i]) { prime.push_back(i); if ((ll)i * i > n) continue; for (int j = i * i; j <= n; j += i) is_prime[j] = false; } } } //快速求逆元 int inv(int a){ int b = mod-2, ans = 1; while(b){ if(b&1) ans = (ll) ans*a%mod; a = (ll) a*a%mod; b >>= 1; } return ans; } char T[maxn], new_T[2*maxn]; int num_1[2*maxn], p[2*maxn], n, m=0; void Manacher(char* str,char* new_str,int* p){ new_str[m++]='$'; new_str[m++]='#'; for(int i=0;i<n;i++) new_str[m++]=str[i], new_str[m++]='#'; new_str[m]='\0'; int mx=0,id=1,ans = 0; for(int i=1;i<m;i++){ p[i] = id<mx ? min(p[2*id-i],mx-i) : 1; while(new_str[i+p[i]]==new_str[i-p[i]]) p[i]++; if(i+p[i]>mx) mx=i+p[i], id=i; } return ; } void solve(){ scanf("%s",T); n=strlen(T); Manacher(T,new_T,p); num_1[0] = (new_T[0]=='1'); rep1(i,0,2*n+2) num_1[i] = num_1[i-1]+(new_T[i]=='1'); int ans = num_1[2*n+1], res = ans; // vector<int> res; res.push_back(ans); rep1(i,0,2*n+2) if(p[i]>2){ if(new_T[i]=='1' && (p[i]-1)%2==1) continue; int s = i-(p[i]-1), e = i+(p[i]-1); res = min(res, ans-(num_1[e]-num_1[s]+1)/2); // res.push_back(ans-(num_1[e]-num_1[s]+1)/2); } // sort(res.begin(),res.end()); printf("%d\n",res); return ; } int main(){ ios::sync_with_stdio(false) ; cin.tie(0); cout.tie(0) ; // int N; scanf("%d",&N); while(N--) solve(); return 0; }