A. Dr. TC
有n次翻轉，從1到n，0->1,1->0，每次統計1的數量，設cnt1是字符串1的數量，n次就是n*cnt1，
但每個1都會被翻轉一次減去一個cnt1,再統計cnt0，每個被翻轉一次,答案就是(n-1)*cnt1+cnt0
#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N = 1e4 + 10;
void solve()
{int n;cin>>n;string s;cin>>s;int cnt1=0,cnt0=0;for(int i=0;i<n;i++){if(s[i]=='1')cnt1++;else cnt0++;}cout<<(n-1)*cnt1+cnt0<<endl;
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin>>t;while (t--){solve();}return 0;
}B. St. Chroma?
給一個排列，從1到n依次做mex操作，讓x出現次數最多?，要出現x，要先排0~x-1，再放x后面的數字，最后再放x
#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N = 1e4 + 10;
void solve()
{int n,x;cin>>n>>x;vector<int>ans(n);for(int i=0;i<x;i++)ans[i]=i;for(int i=x;i<n-1;i++)ans[i]=i+1;ans[n-1]=x==n?x-1:x;for(int i=0;i<n;i++)cout<<ans[i]<<" ";cout<<endl;
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin>>t;while (t--){solve();}return 0;
}C. Cherry Bomb?
給出a和b數組，當對應和都相等，就是互補數組，b中有缺失，求方案數
先找無解，那就是給出的對應和有多個?，或憑借b的范圍無法湊出對應和
有解的話就是1個，或b全是-1，有多個，找a的最小值與最大值，即可求
#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N = 1e4 + 10;
void solve()
{int n,k;cin>>n>>k;ll maxx=-2,minn=1e18;ll sum=-1;vector<ll>a(n+1),b(n+1);for(int i=1;i<=n;i++){cin>>a[i];maxx=max(maxx,a[i]);minn=min(minn,a[i]);}bool tag=true;for(int i=1;i<=n;i++){cin>>b[i];if(b[i]!=-1){if(sum==-1)sum=a[i]+b[i];else{if(a[i]+b[i]!=sum)tag=false;}}}if(!tag){cout<<0<<endl;}else if(sum!=-1){bool flag=true;for(int i=1;i<=n&&flag;i++){if(b[i]==-1){if(a[i]+k<sum||a[i]>sum)flag=false;}}if(flag)cout<<1<<endl;else cout<<0<<endl;}else{ll up=minn+k;if(up<maxx)cout<<0<<endl;else cout<<up-maxx+1<<endl;}
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin>>t;while (t--){solve();}return 0;
}D. Flower Boy?
在a中找出一個長為m的序列，讓對應ai都大于bi，也可刪去b中一個再找
不操作有解直接輸出
操做的話，考慮枚舉刪去的b，對a做前綴和與后綴和，pre[i]表示前i個元素可匹配b中前多少個，suf[i]同理
枚舉b的過程中，到i，表示要找i-1個先匹配，再找n-i個在后面匹配，二分pre數組，看suf是否合法
#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N = 1e4 + 10;
void solve()
{int n,m;cin>>n>>m;vector<ll>a(n+1),b(m+1);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++)cin>>b[i];int pos=1;for(int i=1;i<=n;i++){if(pos!=m+1&&a[i]>=b[pos])pos++;}if(pos==m+1){cout<<0<<endl;return;}vector<int>pre(n+1,0),suf(n+3,0);int t=1;for(int i=1;i<=n;i++){int k=0;if(a[i]>=b[t])t++,k=1;pre[i]=pre[i-1]+k;}//for(int i=1;i<=n;i++)cout<<pre[i]<<" ";//cout<<endl;t=m;for(int i=n;i>=0;i--){int k=0;if(a[i]>=b[t])t--,k=1;suf[i]=suf[i+1]+k;}ll ans=1e18;for(int i=1;i<=m;i++){int pos=lower_bound(pre.begin(),pre.end(),i-1)-pre.begin();//cout<<pos<<endl;if(pos>n)continue;if(pre[pos]==i-1&&suf[pos+1]>=m-i)ans=min(ans,b[i]);}if(ans==1e18)cout<<-1<<endl;else cout<<ans<<endl;
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin>>t;while (t--){solve();}return 0;
}
/*
2
5 5
7 7 6 7 7
7 7 7 7 7
*/?E. Wolf
給出一個排列，有q次詢問，詢問l到r中能否二分到x，不可輸出-1，可的話找最小操作數
可做的操作是對數組除x以外的數任意調換順序，找調換順序的最小個數
可用st數組記錄每個元素的位置
#1.當mid<st[x],且p[mid]>x需要操作，將p[mid]換成小于x的
#2.當mid>st[x]，且p[mid]<x需要操作，將p[mid]換成大于x的
注意到1與2，之間可以直接交換使其都合法
模擬二分過程，記錄mid>x的次數，和mid>x并且合法次數
記錄mid<x次數，和mid<x合法次數
于是就得到了mid<x與>x的不合法次數，抵消到有剩余，判斷剩余的有沒有對應剩余的可抵消
?
#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N = 1e4 + 10;
void solve()
{int n,q;scanf("%d%d",&n,&q);vector<int>p(n+1),st(n+1);for(int i=1;i<=n;i++){cin>>p[i];st[p[i]]=i;}vector<int>ans;while(q--){int l,r,x;scanf("%d%d%d",&l,&r,&x);if(st[x]<l||st[x]>r){ans.push_back(-1);continue;}if(l==r){if(p[l]==x)ans.push_back(0);else ans.push_back(-1);continue;}int L=0,R=0,LL=0,RR=0;while(l<r){int mid=(l+r)/2;if(p[mid]==x)break;if(mid<st[x]){ L++;if(p[mid]<x)LL++;l=mid+1;}else{R++;if(p[mid]>x)RR++;r=mid-1;}//cout<<l<<endl;}//cout<<l<<" "<<r<<endl;//cout<<cnt<<" "<<ok<<endl;if(L>x-1||R>n-x)ans.push_back(-1);else{L-=LL;R-=RR;if(L>=R){ll tmp=L-R;if(x-1>=tmp+LL+R)ans.push_back(2ll*R+2ll*(L-R));else ans.push_back(-1);}else{ll tmp=R-L;if(n-x>=tmp+RR+L)ans.push_back(2ll*L+2ll*(R-L));else ans.push_back(-1);}}}for(auto y:ans)printf("%d ",y);printf("\n");
}
int main()
{int t = 1;scanf("%d",&t);while (t--){solve();}return 0;
}
/*
3
13 1
12 13 10 9 8 4 11 5 7 6 2 1 3
1 13 2
*/F. Goblin?
與a題共享題面，但問的不同，n次操作后，我們需要找出這n*n的方格中?最大連通0的數量
考慮dp
注意到每次操作的數形成了主對角線
對于每個字符i，它在aii處翻轉，其余保持不變
我們一列一列的添加，發現出現了四種狀態轉移
0->1,0->0,1->0,1->1
并且在一列一列添加的過程中，場上0的聯通塊數量不會大于2
因為如果s[i]是0,中間有1，其余為0，將其隔開有兩個連通塊，如s[i+1]是0，它的上連通塊和下聯通塊會繼承s[i]的
如果s[i+1]是1，一個0隔開上列1和下列1，它會將上連通塊截止，繼承上一個的下連通塊
設置狀態dp[i][0]表示到第i列，上連通塊0的數量
dp[i][1]表示到第i列，下連通塊0數量
?
#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N = 1e4 + 10;
void solve()
{int n;cin>>n;string s;cin>>s;s="#"+s;vector<vector<ll>>dp(n+1,vector<ll>(2,0));if(s[1]=='0')dp[1][1]=n-1;else dp[1][1]=1;ll ans=0;for(int i=2;i<=n;i++){if(s[i-1]=='0'&&s[i]=='1'){ans=max(ans,dp[i-1][0]);dp[i][1]=dp[i-1][1]+1;}else if(s[i-1]=='0'&&s[i]=='0'){dp[i][0]=dp[i-1][0]+i-1;dp[i][1]=dp[i-1][1]+n-i;}else if(s[i-1]=='1'&&s[i]=='0'){dp[i][0]=dp[i-1][1]+i-1;dp[i][1]=n-i;}else{ans=max(ans,dp[i-1][1]);dp[i][1]=1;}}ans=max(ans,dp[n][0]);ans=max(ans,dp[n][1]);cout<<ans<<endl;
}
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin>>t;while (t--){solve();}return 0;
}?
?
)
