| A | Phoenix and Balance |
题意：
把2^1,2^2,……2^n;分成两份，两份的差最小，保证n是偶数。
因为2^n=S(n-1)+2;
则最小的差即为Sn-2*(S(n-1)-S(n/2-1));
#include<iostream> #include<cstdio> #include<set> #include<queue> #include<stack> #include<vector> #include<bitset> #include<cstring> #include<string> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; const int MAXN=1e5+10; long long quick_power(int x, int y) { if(y==1)return x; if(y==0)return 1; long long res; if(y%2==0) { res=quick_power(x,y/2); res=res*res; } else { res=quick_power(x,y/2); res=res*res*x; } return res; } int main(){ int t; cin>>t; while(t--){ int n; cin>>n; int l=n/2-1,r=n-1; ll sl=2*(quick_power(2,l)-1),sr=2*(quick_power(2,r)-1); ll ss=2*(quick_power(2,n)-1); ll ans=ss-2*(sr-sl); cout<<ans<<endl; } return 0; }
| B | Phoenix and Beauty |
题意：
将所给的序列变成每k个数字的和相同的序列，不要求最小化。
思路：先在所给序列里面找到给的数字都有哪些，大于k个输出-1退出。再从1-n里面找一个没有出现过的数字；然后进行n次循环，每次先输出之前找到的数字，如果不够k个数字，把后来找的数组重复输出知道等于k个数字。
#include<iostream> #include<cstdio> #include<set> #include<queue> #include<stack> #include<vector> #include<bitset> #include<cstring> #include<string> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; const int MAXN=1e5+10; bool flag=false; int t,n,k,a[MAXN],s[150],MAX,tmp; int main(){ cin>>t; while(t--){ flag=false; cin>>n>>k; MAX=1; memset(s,0,sizeof(s)); int j=0; for(int i = 1;i<=n;i++){ int num; cin>>num; if(!s[num]){ s[num]=1; a[j++]=num; } } ll ccc=0; if(j>k){ cout<<"-1"<<endl; continue; } else if(j<k){ for(int i = 1;i<=n;i++){ if(s[i]==0){ s[i]=1; tmp=i; break; } } } cout<<n*k<<endl; int fla=0; for(int d =1;d<=n;d++){ for(int i = 0;i<j;i++){ if(fla) cout<<" "; cout<<a[i]; fla=1; } for(int i = 0;i<k-j;i++){ cout<<" "; cout<<tmp; } } cout<<endl; } return 0; }
| C | Road To Zero |
题意：把x,y都变成0。一共两种操作，第一种花费a元，令一个减一或加一，第二种，两个都加一或减一。
则有两种可能：1.先用第二种把a,b中最小的变为0，然后用第一种把剩下的数字变为0；2.直接都使用第一种。两种方案取最小值。
#include<iostream> #include<cstdio> #include<set> #include<queue> #include<stack> #include<vector> #include<bitset> #include<cstring> #include<string> #include<algorithm> using namespace std; typedef long long ll; const int MAXN=1e5+10; const ll MAX=1e18+10; inline int read(){ int x=0,y=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘){ y=-1; } ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*y; } ll x,y,a,b,t,ans; int main(){ cin>>t; while(t--){ ans=0; cin>>x>>y>>a>>b; ans+=b*min(x,y); ans+=a*(max(x,y)-min(x,y)); ans=min(ans,a*(x+y)); cout<<ans<<endl; } return 0; }
| D | Binary Period |
题意：给一个t字符串,找一个s字符串，保证字符循环周期最小，保证s为“0”，“1”组成，长度不会超过2|t|，且t为s的子序列：如果t可以通过删除零个或多个元素（任何）而不改变其余元素的顺序而从s导出，则t是s的子序列。
先判断，如果t是一个所有元素都相等的字符串，直接输出，不然的话，直接在相邻且相等元素的中间插入一个“0”或“1”分割开，这样可以令周期为2.且不会超过2倍的t的长度，t必是子序列。
#include<iostream> #include<cstdio> #include<set> #include<queue> #include<stack> #include<vector> #include<bitset> #include<cstring> #include<string> #include<algorithm> using namespace std; typedef long long ll; const int MAXN=1e5+10; const ll MAX=1e18+10; inline int read(){ int x=0,y=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘){ y=-1; } ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*y; } ll t; string ss; int main(){ cin>>t; while(t--){ cin>>ss; int flag=1; for(int i = 1;i<ss.length();i++){ if(ss[i]!=ss[i-1]){ flag=0;break; } } if(flag) cout<<ss<<endl; else{ for(int i = 1;i<ss.length();i++){ if(ss[i]==ss[i-1]&&ss[i-1]==‘0‘){ ss.insert(i,"1"); } if(ss[i]==ss[i-1]&&ss[i-1]==‘1‘){ ss.insert(i,"0"); } } cout<<ss<<endl; } } return 0; }
| E | Nastya and Rice |
题意，判断所有的有可能的谷子都否全部装进可能的袋子，直接判断最大和最小的关系：最多的谷子是否小于最小的袋子，最小的谷子是否大于最大的袋子为真输出“No”，不然输出“Yes”。
#include<iostream> #include<cstdio> #include<set> #include<queue> #include<stack> #include<vector> #include<bitset> #include<cstring> #include<string> #include<algorithm> using namespace std; typedef long long ll; const int MAXN=1e5+10; const ll MAX=1e18+10; inline int read(){ int x=0,y=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘){ y=-1; } ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*y; } ll t,n,a,b,c,d; string ss; int main(){ cin>>t; while(t--){ cin>>n>>a>>b>>c>>d; if(n*(a-b)>c+d||n*(a+b)<c-d) cout<<"No"<<endl; else cout<<"Yes"<<endl; } return 0; }
| F | Nastya and Door |
题意：找区间内最多的山顶，输出区间的山顶数+1和左顶点：
思路，先找一下山顶的索引，用两个数组记录下来，然后一个数组求前缀和，然后判断区间的山顶数最多的索引，注意边界也可能是山顶，所以要先减去边界的山顶再判#include<iostream>
#include<cstdio> #include<set> #include<queue> #include<stack> #include<vector> #include<bitset> #include<cstring> #include<string> #include<algorithm> using namespace std; typedef long long ll; const int MAXN=2e5+10; const ll MAX=1e18+10; inline int read(){ int x=0,y=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){ if(ch==‘-‘){ y=-1; } ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*y; } ll t,n,k,a[MAXN],s[MAXN],tt[MAXN]; string ss; int main(){ cin>>t; while(t--){ memset(s,0,sizeof(s)); memset(tt,0,sizeof(tt)); cin>>n>>k; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=2;i<n;i++){ if(a[i]>a[i-1]&&a[i]>a[i+1]) s[i]=1,tt[i]=1; s[i]+=s[i-1]; } s[n]+=s[n-1]; int maxPeak=-1,maxPeakIndex; for(int i = 1;i<=n-k+1;i++){ int num = s[i+k-1]-s[i-1]; if(tt[i]==1) num--; if(tt[i+k-1]==1) num--; if(num > maxPeak){
maxPeakIndex=i; maxPeak=num; } } cout<<maxPeak+1<<" "<<maxPeakIndex<<endl; } return 0; }
原文：https://www.cnblogs.com/aixiaodezsh/p/12924609.html