A. Prison Break
很明显是n*m
B. Restore Modulo
乱搞搞过得去的，讨论了一下增情况和减情况这样。
wa了两发
#include<bits/stdc++.h> #define inf 1e18 #define ll long long #define MAX 1000001 const ll N = 1e5+7; const ll mod = 1e18; using namespace std; ll a[N]; int main(){ ll t;cin>>t; while(t--){ ll n,m,maxx=-1,ff=0;cin>>n; ll d=0,z=0,flag=0; for(int i=1;i<=n;++i){ cin>>a[i]; maxx=max(a[i],maxx); } for(int i=2;i<=n;++i){ ll x=a[i]-a[i-1]; if(x>0){ if(d==0)d=x; else if(x!=d) ff=1; } else if(x<0){ if(z==0)z=x; else if(x!=z) ff=1; } else{ flag=1; } } if(ff==1){ printf("-1 "); continue; } if(flag==1&&(d>0||z<0)){ printf("-1 "); continue; } if(d>0&&z<0){ m=d-z; if(m<maxx){ printf("-1 "); } else{ printf("%lld %lld ",m,d); } } else{ printf("0 "); } } return 0; }
C. Basic Diplomacy
题意：给定n个人和m天
每天会给一些人可以选
要求最多被选的人的次数不超过 向上取整m/2
有一些天只能选一个。
如果这些被迫选的人的其中某个已经过要求了，那直接出NO
如果这些被迫选的人已经占据了是k天。0≤k≤ （向上取整m/2）
剩下的m-k天还没选，每天都至少有两个人可以选。
极端化情况，k天都是A占据的，剩下两天都只有A和B。测试最困难的情况。
此时
A 占据 k天 0 ≤ k ≤ (m+1)/2 A/B 共同占据(m-k)天
先设A= (m+1)/2天，不关k的情况，k小就往共同里面填，A不够了填B= m-(m+1)/2 < (m+1)/2
这样构造满足k的任意情况，证明结束。
如果可以的话，也可以试试网络流
#include<bits/stdc++.h> #define inf 1e18 #define ll long long #define MAX 1000001 const ll N = 1e5+7; const ll mod = 1e18; using namespace std; int vis[N],vis2[N],n,m,maxx,ans[N]; vector<int>G[N]; int main(){ ll t;cin>>t; while(t--){ int flag=0;cin>>n>>m; for(int i=1;i<=n;++i)vis[i]=vis2[i]=0; for(int i=1;i<=m;++i)G[i].clear(),ans[i]=0; maxx=(m+1)/2; for(int i=1;i<=m;++i){ int x;scanf("%d",&x); for(int j=1;j<=x;++j){ int q;scanf("%d",&q); G[i].push_back(q); } if(x==1){ vis[G[i][0]]++; if(vis[G[i][0]]>maxx) flag=1; ans[i]=G[i][0]; vis2[G[i][0]]++; } } if(flag==1)printf("NO "); else{ for(int i=1;i<=m;++i){ if(ans[i]) continue; //避免vis2的重复计算 for(int j=0;j<G[i].size();++j){ if(vis2[G[i][j]]<maxx){ ans[i]=G[i][j]; vis2[G[i][j]]++; break; } } } printf("YES "); for(int i=1;i<=m;++i) printf("%d ",ans[i]); printf(" "); } } return 0; } //之前那样写会出现 前面有别的选择但是已经取了但是后面只能取然后超过的情况。
D. Playlist
参考了某位大佬的代码
并查集维护循环删除过程中，每个人的下一个。
但是因为路径压缩优化的原因，我们只能存下一个的左边那一个。
然后队列维护删除的情况。
因为新的情况只会在改变之后出现在原来的位置上。
----
线段树+循环列表也能维护这个东西
#include<bits/stdc++.h> #define inf 1e18 #define ll long long #define MAX 1000001 const ll N = 1e5+7; const ll mod = 1e18; using namespace std; int del[N],a[N],n,fa[N]; vector<int> ans; int nxt(int x){ return x%n+1; } int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); } int main(){ int t;cin>>t; while(t--){ ans.clear(); scanf("%d",&n); for(int i=1;i<=n;++i){ scanf("%d",&a[i]); fa[i]=i;del[i]=0; } queue<int>qe; for(int i=1;i<=n;++i) if(__gcd(a[i],a[nxt(i)])==1)qe.push(i); while(!qe.empty()){ int x=qe.front(); qe.pop(); if(del[x]) continue; int y=nxt(find(x)); fa[x]=find(y);del[y]=1; ans.push_back(y); if(__gcd(a[x],a[nxt(fa[x])])==1) qe.push(x); } printf("%d ",ans.size()); for(int i=0;i<ans.size();++i) printf("%d ",ans[i]); puts(""); } return 0; }
E. Skyline Photo
推荐阅读
https://blog.csdn.net/Brian_Pan_/article/details/115065320
#include<bits/stdc++.h> #define inf 1e18 #define ll long long #define MAX 1000001 const ll N = 3e5+7; const ll mod = 1e18; using namespace std; ll f[N],a[N],b[N],c[N],n; struct node{ ll l,r; ll maxn,addv; }tr[N<<2]; void build(ll o,ll l,ll r){ tr[o].l=l;tr[o].r=r; if(l==r){ return ; } ll mid=l+r>>1; build(o<<1,l,mid); build(o<<1|1,mid+1,r); } void pushup(ll o){ tr[o].maxn=max(tr[o<<1].maxn,tr[o<<1|1].maxn); } void pushdown(ll o){ if(tr[o].addv==0) return ; tr[o<<1].addv+=tr[o].addv; tr[o<<1].maxn+=tr[o].addv; tr[o<<1|1].addv+=tr[o].addv; tr[o<<1|1].maxn+=tr[o].addv; tr[o].addv=0; } void update_seg(ll o,ll a,ll b,ll k){ if(a<=tr[o].l&&tr[o].r<=b){ tr[o].addv=tr[o].addv+k; tr[o].maxn=tr[o].maxn+k; return ; } pushdown(o); ll mid=tr[o].r+tr[o].l>>1; if(a<=mid) update_seg(o<<1,a,b,k); if(b>mid) update_seg(o<<1|1,a,b,k); pushup(o); } void update_pos(ll o,ll pos, ll v){ if(tr[o].l==tr[o].r){ tr[o].maxn=v; return ; } ll mid=tr[o].r+tr[o].l>>1; if(pos<=mid) update_pos(o<<1,pos,v); else update_pos(o<<1|1,pos,v); pushup(o); } ll query(ll o,ll a,ll b){ if(a<=tr[o].l&&tr[o].r<=b) return tr[o].maxn; pushdown(o); ll ans=-inf; ll mid=tr[o].l+tr[o].r>>1; if(a<=mid) ans=query(o<<1,a,b); if(b>mid) ans=max(ans,query(o<<1|1,a,b)); return ans; } int main(){ scanf("%lld",&n); build(1,0,n); for(int i=1;i<=n;++i)scanf("%lld",&a[i]); for(int i=1;i<=n;++i)scanf("%lld",&b[i]); a[0]=-1;f[1]=0; int cnt=1; for(int i=1;i<=n;++i){ while(a[c[cnt]]>=a[i] && cnt){ update_seg(1,c[cnt-1],c[cnt]-1,-b[c[cnt]]); //c[cnt-1]到c[cnt]-1减去b[c[cnt]] --cnt; } update_seg(1,c[cnt],i-1,b[i]); //c[cnt]到i-1加上b[i] f[i]=query(1,0,i-1); update_pos(1,i,f[i]); //单点修改 maxx i为fi c[++cnt]=i; } printf("%lld ",f[n]); return 0; }