A题
排序输出答案即可
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=4e5+10; const int inf=1e9; int a[N]; int main(){ ios::sync_with_stdio(false); int i; int t; cin>>t; while(t--){ int n; cin>>n; for(i=1;i<=n;i++){ cin>>a[i]; } reverse(a+1,a+1+n); for(i=1;i<=n;i++) cout<<a[i]<<" "; cout<<endl; } return 0; }
B题
用两个vector，分类讨论情况求和
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=4e5+10; const int inf=1e9; int a[N]; vector<int> pos; vector<int> ne; int main(){ ios::sync_with_stdio(false); int t; cin>>t; while(t--){ int n; cin>>n; int i; pos.clear(); ne.clear(); for(i=1;i<=n;i++){ cin>>a[i]; if(a[i]>0){ pos.push_back(i); } if(a[i]<0){ ne.push_back(i); } } if(n==1){ cout<<0<<endl; continue; } int l=0,r=0; int n1=(int)pos.size()-1,n2=(int)ne.size()-1; while(l<=n1&&r<=n2){ if(pos[l]>ne[r]){ r++; continue; } if(a[pos[l]]==-a[ne[r]]){ a[pos[l]]=0; l++,r++; } else if(a[pos[l]]>-a[ne[r]]){ a[pos[l]]+=a[ne[r]]; r++; } else if(a[pos[l]]<-a[ne[r]]){ a[ne[r]]+=a[pos[l]]; a[pos[l]]=0; l++; } } ll ans=0; for(i=0;i<=n1;i++){ ans+=a[pos[i]]; } cout<<ans<<endl; } return 0; }
C题
经典套路，可以观察到modk相等的数有共性，之后判断一下非法情况
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=4e5+10; const int inf=1e9; string s; int main(){ ios::sync_with_stdio(false); int t; cin>>t; while(t--){ int n,k; cin>>n>>k; int i; cin>>s; int cnt1=0; int cnt2=0; int flag=1; for(i=k;i<n;i++){ if(s[i]=='?'||s[i]==s[i%k]) continue; if(s[i%k]=='?') s[i%k]=s[i]; else{ flag=0; } } for(i=0;i<k;i++){ if(s[i]=='0') cnt1++; if(s[i]=='1') cnt2++; } if(!flag||cnt1>k/2||cnt2>k/2) cout<<"NO"<<endl; else{ cout<<"YES"<<endl; } } return 0; }
D题
思维题，关注一下有哪些输赢关系
1.dis(a,b)<=da，显然，一步就能抓到
2.直径小于2*da，这是本题解题的核心，我们发现alice站在直径的终点就稳赢
3.如果直径大于2*da，我们证明当2*da>=db的时候alice赢，否则bob赢
首先因为我们不在情况2，所以一定可以找到一个点使得这个点与alice相离da+1个位置，并且我们发现如果db>2*da，那么bob永远可以走到这个位置，就是稳赢
如果2*da>=db，alice可以采取策略不断往bob所在子树逼近，因为bob不能跳出掌控的范围，所以bob是必输的
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+100; int t; int n,a,b,da,db; vector<int> g[maxn]; int d; int dp[2][maxn]; int dis[maxn]; void dfs (int u,int pre) { for (int v:g[u]) { if (v==pre) continue; dis[v]=dis[u]+1; dfs(v,u); if (dp[0][v]+1>dp[0][u]) { dp[1][u]=dp[0][u]; dp[0][u]=dp[0][v]+1; } else if (dp[0][v]+1>dp[1][u]) { dp[1][u]=dp[0][v]+1; } } d=max(dp[0][u]+dp[1][u],d); } int main () { scanf("%d",&t); while (t--) { scanf("%d%d%d%d%d",&n,&a,&b,&da,&db); d=0; for (int i=0;i<=n;i++) dis[i]=0,g[i].clear(),dp[0][i]=0,dp[1][i]=0; for (int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } dfs(a,0); //printf("%d ",d); //d--; if (dis[b]<=da) { printf("Alice "); continue; } if (da>=db) { printf("Alice "); continue; } else { if (da*2>=d) { printf("Alice "); continue; } else if (db<=da*2) { printf("Alice "); } else { printf("Bob "); } } } }
E题
第一点可以想到的是，对于某个位置i上的数，他能不能被删除只和前面的数的能不能删除掉-(a[i]-i)的数有关。前提是他要a[i]-i小于0
现在的问题是，因为他有很多询问，因为左区间的限定，我们对每个询问需要知道每个i对于当前左区间l-i之间能删除多少个数，这样我们才能知道对于当前区间这个点能不能删除。
因此我们想到每个左区间的端点都是十分重要的，因此我们考虑维护一个线段树，每个点的意义都是以i为左区间能删除的数的大小。
对于每个点，我们在线段树上二分查询到离他最近的能满足条件的位置，把点的贡献加到对应位置上，这样做是最优的。
另外，这需要对询问排序，因为我们不能让后面的点对当前位置的答案产生错误的贡献
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e5+10; int n,q; int a[N]; struct Q{ int l,r; int id; }s[N]; struct node{ int l,r; int sum; }tr[N<<2]; bool cmp(Q a,Q b){ return a.r>b.r; } void build(int u,int l,int r){ if(l==r){ tr[u]={l,r,0}; } else{ tr[u]={l,r,0}; int mid=l+r>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); } } void modify(int u,int l,int x){ if(tr[u].l==tr[u].r){ tr[u].sum+=x; return ; } int mid=tr[u].l+tr[u].r>>1; if(l<=mid) modify(u<<1,l,x); else modify(u<<1|1,l,x); tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum; } int query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r){ return tr[u].sum; } int mid=tr[u].l+tr[u].r>>1; int ans=0; if(l<=mid){ ans+=query(u<<1,l,r); } if(r>mid) ans+=query(u<<1|1,l,r); return ans; } int ans[N]; int get(int u,int l){ if(tr[u].l==tr[u].r){ return tr[u].l; } int mid=tr[u].l+tr[u].r>>1; if(tr[u<<1|1].sum>=l){ return get(u<<1|1,l); } else{ return get(u<<1,l-tr[u<<1|1].sum); } } int main(){ cin>>n>>q; int i; for(i=1;i<=n;i++){ cin>>a[i]; a[i]-=i; } for(i=1;i<=q;i++){ int x,y; cin>>x>>y; s[i]={x,y,i}; } sort(s+1,s+1+q,cmp); int cur=1; int tot=0; build(1,1,n); for(i=1;i<=q;i++){ while(cur<=n-s[i].r){ if(a[cur]==0) modify(1,cur,1),tot++; else if(a[cur]<0&&-a[cur]<=tot){ modify(1,get(1,-a[cur]),1); tot++; } cur++; } ans[s[i].id]=query(1,s[i].l+1,n-s[i].r); } for(i=1;i<=q;i++) cout<<ans[i]<<endl; return 0; }