C.回文串處理：https://codeforces.com/contest/1512/problem/C

題意

給一個字串s和兩個數字a和b，s由‘0’，‘1’和‘？’組成，要求將s中的‘？’替換成‘1’或者‘0’，同時要求s中的‘0’的個數嚴格等于a，s中國‘1’的個數嚴格等于b，請問是否存在這樣的回文串s，如果存在就輸出處理好的回文串s，不存在就輸出-1，

思路

雙指標兩頭遍歷，然后判斷是不是回文串已經a和b是否用完，

代碼

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int t, n, k, a, b, l; cin>>t;
	while(t--){
		cin>>a>>b;
		string str; cin>>str;
		n = a+b;
		for(int i=0; i<n; i++){
  			//如果兩邊都是'?'就不變
     		//如果一邊是'?'就變成另一邊的字符
       		//這樣字串中就沒有不對稱的'?'了
			if(str[i]=='?')str[i] = str[n-i-1];
		}
		//對a和b減去字串中已有的'0'和'1'的個數
		a -= count(str.begin(), str.end(), '0');
		b -= count(str.begin(), str.end(), '1');
		for(int i=0; i<=n/2; i++){
  			//如果有對稱的'?'就用剩有多于1個的'0'或者'1'來代替
			if(i!=n-i-1 && str[i]=='?'){
				if(a>1)str[i]=str[n-i-1]='0', a-=2;
				else if(b>1)str[i]=str[n-i-1]='1', b-=2;
			}
   			//如果是奇數長度，那么正中間如果是'?'，就用剩的'0'或者'1'來代替   			
			else if(str[i]=='?'){
				if(a)str[i]='0',a--;
				else str[i]='1',b--;
			}
		}
		
		string vec=str;
  		//檢驗是否是回文串
		reverse(vec.begin(), vec.end());
  		//檢驗a和b是否恰好用完
		if(vec==str && a==0 && b==0)cout<<str<<'\n';
		else cout<<"-1"<<endl;
	}
}

E.找連續正整數序列：https://codeforces.com/contest/1512/problem/E

題意

給四個數n，l，r和s，n表示有一個正整數序列從1到n，問這個序列（無序的）中的下標閉區間[l,r]的值的和能不能等于s，如果存在這樣的閉區間滿足就輸出這個序列，沒有就輸出-1，

思路

考慮1到n這樣一個數集，找一個大小為r-l+1的子集使得子集元素和為s，設len=r-l+1，可以抽象為有len個箱子，往里面一共放入s個小球且每個箱子放的小球數不一樣，假設第i個箱子放i個小球，那么一共可以放k = len*(len+1)/2個小球，根據抽屜原理，這時第i個箱子最少要放(s-k)/len+i個小球，同時如果(s-k)%len!=0，那么需要在后面的箱子里面補小球（不在前面補是避免后面的箱子和前面的箱子小球數相同），這時需要補m=(s-k)%len個小球，就在len-m+1的位置開始補，

代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int tt,n,l,r,s;
int vis[N];
int main()
{
    scanf("%d",&tt);
    while(tt--)
	{
		scanf("%d%d%d%d",&n,&l,&r,&s);
		memset(vis,0,sizeof vis);
		
		int len = r-l+1,x = len*(len+1)/2;
		if(s<len*(len+1)/2||s>(n+n-len+1)*len/2) cout<<-1<<endl;
		else
		{
			int k = s-x;
			for(int i=1;i<=len;i++)
			{
				//抽屜原理
    			int h = k/len+i;
       			//補小球
				if(k%len&&k%len>len-i) h++;
				vis[h] = 1;
			}
			int t = 1,f = 1;
			for(int i=1;i<=n;i++)
			{
				if(i<l||i>r)
				{
					while(f<=n&&vis[f]==1) f++;
					printf("%d ",f++);
				}
				else
				{
					while(t<=n&&vis[t]==0) t++;
					printf("%d ",t++);
				}
			}
			puts("");
		}
		
	}
    return 0;
}

F.買電腦：https://codeforces.com/contest/1512/problem/F

題意

給兩個數n和c，兩個陣列a[n]，b[n-1]，c表示電腦的價格，a[i]表示在第i個職位一天可以賺多少錢，b[i]表示想要去第i+1個職位需要花的用來學習的錢，求最少多少天可以攢夠c塊錢去買電腦，

思路

模擬+暴力，從第1個職位開始遍歷，用rem存手上剩下的錢，p存天數，ans存答案，在第i個職位先判斷錢夠不夠買電腦，如果夠的話算一下ans=min(ans,p)，如果不夠的話假如我不學習，之后一直在這個職位需要多少天才能買到電腦，也就是ans = min(ans,p+(c-rem)/a[i]+((c-rem)%a[i]!=0))，如果已經到了第n個職位就可以退出回圈了，因為這里上面一直在這個職位這一步處理了，接下來模擬，如果剩的錢大于學習開銷，就學習然后去下一個職位，如果不夠就計算需要打工多少天才夠，也就是p += (b[i]-rem)/a[i]+((b[i]-rem)%a[i]!=0)，然后再更新剩的錢，

代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 200010;
LL ans,t,p,rem,a[N],b[N],n,c;
int main()
{
	cin>>t;
    while(t--)
    {
    	cin>>n>>c;
    	p = -1,rem = 0,ans = 1e9+10;
    	for(int i=1;i<=n;i++) scanf("%d",a+i);
    	for(int i=1;i<n;i++) scanf("%d",b+i);
    	int k = 1;
    	for(int i=1;i<=n;i++)
    	{
    		p++;
    		if(c<=rem) ans = min(ans,p);
    		else ans = min(ans,p+(c-rem)/a[i]+((c-rem)%a[i]!=0));
    		
    		if(i==n) break;
    		
    		if(rem>=b[i])
    		{
    			rem-=b[i];
    			continue;
			}
    		
    		p += (b[i]-rem)/a[i]+((b[i]-rem)%a[i]!=0);
    		
    		if((b[i]-rem)%a[i]!=0) rem = a[i]-(b[i]-rem)%a[i];
    		else rem = 0;
		}
    	cout<<ans<<endl;
	}
    return 0;
}

G.因數和：https://codeforces.com/contest/1512/problem/G

題意

給一個數c，使數n滿足n所有因數的和等于c，問這樣的n最小是多少，

思路

打表，類似于篩質數，開一個陣列yz[]，將每個數的對應倍數位置加上這個數，等回圈到這個位置的時候恰好它存的數就是這個位置所有因數的和，然后用ans[]陣列來把下標為因數和的位置存為這個數，

代碼

#include <bits/stdc++.h>
using namespace std;
const int N=1e7;
int t, n, yz[N], ans[N];
int main() {
	for(int i=1; i<=N; ++i) {
		for(int j=i; j<=N; j+=i)
			yz[j]+=i;
		if(yz[i]<=N&&!ans[yz[i]])
			ans[yz[i]]=i;
	} cin>>t;
	while(t--) {
		cin>>n;
		cout<<(ans[n]==0?-1:ans[n])<<endl;
	} return 0;
}