A题
循环构造bac即可，因为题目是小于等于，我看成了等于所以构造的复杂了点
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int main(){ ios::sync_with_stdio(false); int t; cin>>t; while(t--){ int n,k; cin>>n>>k; string res=""; int i; for(i=0;i<k;i++){ res+='a'; } n-=k; int x=0; for(i=0;i<n;i++){ if(x%3==0){ res+='b'; } else if(x%3==1){ res+='c'; } else{ res+='a'; } x++; } cout<<res<<endl; } }
B题
直接枚举三维加上一些剪枝，复杂度能够接受
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; int sum[1010][1010]; string s[N]; int main(){ ios::sync_with_stdio(false); int t; cin>>t; while(t--){ int n,m; cin>>n>>m; int i,j; memset(sum,0,sizeof sum); for(i=1;i<=n;i++){ cin>>s[i]; s[i]=" "+s[i]; } for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ sum[i][j]=sum[i][j-1]+(s[i][j]=='*'); } } int ans=0; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ for(int k=i;k<=n;k++){ if(j+k-i>m||j-k+i<1) break; if(sum[k][j+k-i]-sum[k][j-k+i-1]!=2*(k-i)+1) break; ans++; } } } cout<<ans<<endl; } }
C题
容斥思想，找到后缀中最前面的使得后面都是按序，这样答案就是1-前面都不符合的情况
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; int a[N]; int p[N]; int main(){ //ios::sync_with_stdio(false); int t; cin>>t; while(t--){ int n,m; cin>>n>>m; int i; for(i=1;i<=n;i++){ scanf("%d",&a[i]); } int last=n+1; for(int i=n;i>0;i--){ if(a[i]==i){last=i;} else break; } double ans=1; for(i=1;i<=m;i++){ int pos; double cnt; scanf("%d%lf",&pos,&cnt); if(pos>=last-1){ ans=ans*(1-cnt); } } int sign=0; for(i=2;i<=n;i++){ if(a[i]-a[i-1]!=1){ sign=1; } } if(!sign){ cout<<"1.000000"<<endl; } else printf("%.6f ",1-ans); } }
D题
首先排序，那么之后就是一种分治的思想，根据mid不断往两边，用一个map存所有的可能性，这里需要二分一下边界，之后判断所有情况即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; int n,q; int a[N]; int b[N]; map<ll,int> m1; ll sum[N]; vector<int> num; void solve(int l,int r){ if(l>r) return ; if(l==r){ m1[a[l]]=1; return ; } int mid=(a[l]+a[r])/2; int l1=l,r1=r; while(l1<r1){ int tmp=l1+r1+1>>1; if(a[tmp]<=mid) l1=tmp; else r1=tmp-1; } m1[(sum[l1]-sum[l-1])]=1; m1[(sum[r]-sum[l1])]=1; if(a[l1]!=a[l]||(l1==l)) solve(l,l1); if(a[l1+1]!=a[r]||(l1+1==r)) solve(l1+1,r); } int main(){ ios::sync_with_stdio(false); int t; cin>>t; while(t--){ m1.clear(); cin>>n>>q; int i; for(i=1;i<=n;i++){ cin>>a[i]; sum[i]=0; } sum[n+1]=0; for(i=1;i<=q;i++){ cin>>b[i]; } sort(a+1,a+1+n); for(i=1;i<=n;i++){ sum[i]=a[i]+sum[i-1]; } solve(1,n); m1[sum[n]]=1; for(i=1;i<=q;i++){ if(m1[b[i]]){ cout<<"Yes"<<endl; } else{ cout<<"No"<<endl; } } } }
E题
观察到数据范围这么大，一般都会有规律在里面，首先比较容易想到的是分类讨论
分x和y的关系，x>y容易讨论，现在重点讨论x<y
第一步的贪心比较好想，因为y>x所以我们要防止的就是不要溢出，因为所有的小于下界都可以通过先+y，再-x控制
那么贪心的思路就是不断-x,在不能减的时候+y，这样是最不可能溢出的情况。
但是问题是现在的数据有点大，所以肯定有突破口，观察数据范围，x只有1e6，并且我们每次都是一直-x到不行
所以可以按x的模数分类，到达过已经判定合法的状态的情况下，那么一定是yes
剩下就是讨论溢出的问题了
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10; int st[N]; int main(){ ios::sync_with_stdio(false); ll k,l,r,t,x,y; cin>>k>>l>>r>>t>>x>>y; if(x>y){ if(k+y>r){ t--; k-=x; } if(k<l){ cout<<"No"<<endl; return 0; } ll tmp=(k-l)/(x-y); if(t<=tmp){ cout<<"Yes"<<endl; } else{ cout<<"No"<<endl; } } else{ while(1){ if(st[k%x]){ cout<<"Yes"<<endl; return 0; } t-=(k-l)/x; if(t<=0){ cout<<"Yes"<<endl; return 0; } k=k-((k-l)/x*x); st[k%x]=1; k+=y; if(k>r){ cout<<"No"<<endl; return 0; } if(k-x<l){ cout<<"No"<<endl; return 0; } } } }
F题
参考的某谷的思路，首先肯定是分类讨论，其他的讨论都比较简单，主要是+*的情况
这种情况下，我们可以根据0划分成独立贡献
那么再根据1讨论情况，对于这里要使用dp，但是普通dp一个是超时一个是炸ll
因此肯定要有什么方法解决他，普通的dp思路很清晰，也很有道理，所以我们思考是否有一些约束性条件
只要乘积和大于1e9，那么这段全部的肯定是乘法，这样就能降低复杂度了
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10; int pre[N],pl[N],pr[N],pm[N]; int a[N]; map<char,int> m1; int ans[N]; ll f[N]; void solve(int l,int r){ int lst=l-1; ll sign=1; int i; int idx=0; for(i=l;i<=r;i++){ if(a[i]==1){ if(lst+1<=i-1) pl[++idx]=lst+1,pr[idx]=i-1,pm[idx]=sign; sign=1; lst=i; } else{ sign*=a[i]; if(sign>1e9) sign=1e9; } } if(lst!=r){ pl[++idx]=lst+1,pr[idx]=r,pm[idx]=sign; } pr[0]=l-1; for(i=1;i<=idx;i++){ f[i]=0; } sign=1; for(i=1;i<=idx;i++){ sign*=pm[i]; if(sign>1e9){ sign=1e9; break; } } if(sign==1e9){ pre[idx]=1; } else{ for(int i=1;i<=idx;i++){ ll mul=1; for(int j=i;j>=1;j--){ mul*=pm[j]; if(f[i]<f[j-1]+pl[j]-pr[j-1]-1+mul){ f[i]=f[j-1]+pl[j]-pr[j-1]-1+mul; pre[i]=j; } } } } for(int i=l;i<pl[1];i++) ans[i]=1; for(int i=pr[idx];i<r;i++) ans[i]=1; int cur=idx; while(cur){ int t=pre[cur]; for(int i=pr[t-1];i<pl[t];i++) ans[i]=1;cur=t-1; } } int main(){ ios::sync_with_stdio(false); int n; cin>>n; int i; for(i=1;i<=n;i++){ cin>>a[i]; } m1['+']=0,m1['-']=1,m1['*']=2; string s; cin>>s; s=" "+s; int sign=0; for(i=1;i<(int)s.size();i++){ sign|=(1<<m1[s[i]]); } if(sign==1||sign==2||sign==4){ for(int i=1;i<=n;i++){ cout<<a[i];if(i!=n) cout<<s[1]; } } else if(sign==3){ for(int i=1;i<=n;i++){ cout<<a[i];if(i!=n) cout<<"+"; } } else if(sign==6){ bool hav=0;cout<<a[1]; for(int i=2;i<=n;i++){ if(!a[i]&&!hav) hav=1,cout<<"-"; else cout<<"*"; cout<<a[i]; } } else{ for(i=1;i<=n;i++){ if(!a[i]){ if(i!=1) ans[i-1]=1; if(i!=n) ans[i]=1; } } int lst=0; for(i=1;i<=n;i++){ if(!a[i]){ solve(lst+1,i-1),lst=i; } } solve(lst+1,n); for(i=1;i<n;i++){ cout<<a[i]; if(ans[i]){ cout<<"+"; } else{ cout<<"*"; } } cout<<a[n]<<endl; } }