又打了一场EDU，感觉这场比23难多了啊……
艹还是我太弱了。
A.
随便贪心一下。
#include<bits/stdc++.h> using namespace std; int n,sum=0,ans=-1,m; inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } int main(){ n=read();for(int i=1;i<=n;i++){int x=read();sum+=x;}m=read(); while(m--){ int l=read(),r=read(); if(r>=sum){ ans=max(l,sum);break; } } printf("%d ",ans); }
B.
预处理一下x,y的幂次就随便做了。
#include<bits/stdc++.h> using namespace std; typedef long long ll; vector<ll>a; ll x,y,l,r,ans=0; int main(){ ios::sync_with_stdio(false);cin>>x>>y>>l>>r; a.push_back(l-1);a.push_back(r+1); for(ll i=1;;i*=x){ for(ll j=1;;j*=y){ ll len=i+j; if(len>=l&&len<=r)a.push_back(i+j); if(j>r/y)break; } if(i>r/x)break; } sort(a.begin(),a.end()); for(ll i=1;i<a.size();i++)ans=max(ans,a[i]-a[i-1]-1); cout<<ans<<endl; }
C.
推一下结论就行了。
#include<bits/stdc++.h> #define N 200005 using namespace std; int da[N],db[N],head[N],tot=0,n,x,ans=0; struct Edge{int u,v,next;}G[N<<1]; inline void addedge(int u,int v){ G[++tot].u=u;G[tot].v=v;G[tot].next=head[u];head[u]=tot; G[++tot].u=v;G[tot].v=u;G[tot].next=head[v];head[v]=tot; } inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } void dfs(int u,int fa,int *d){ for(int i=head[u];i;i=G[i].next){ int v=G[i].v;if(v==fa)continue; d[v]=d[u]+1; dfs(v,u,d); } } int main(){ n=read();x=read(); for(int i=1;i<n;i++){ int u=read(),v=read(); addedge(u,v); } da[0]=db[0]=-1;dfs(1,0,da);dfs(x,0,db); for(int i=1;i<=n;i++)if(db[i]<da[i])ans=max(ans,2*da[i]); printf("%d ",ans); }
D.
按照官方题解做法dp一下就行。
#include<bits/stdc++.h> #define N 5010 using namespace std; int a[N],dp[N][N],cx[7],cy[100010],n,ans=0; inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } int main(){ n=read();for(int i=1;i<=n;i++)a[i]=read(); for(int i=0;i<=n;i++){ memset(cx,0,sizeof(cx));memset(cy,0,sizeof(cy)); for(int j=1;j<i;j++){ cx[a[j]%7]=max(cx[a[j]%7],dp[i][j]); cy[a[j]]=max(cy[a[j]],dp[i][j]); } for(int j=i+1;j<=n;j++){ dp[i][j]=dp[j][i]=max(max(cx[a[j]%7],dp[i][0]),max(cy[a[j]-1],cy[a[j]+1]))+1; ans=max(ans,dp[i][j]); cx[a[j]%7]=max(cx[a[j]%7],dp[i][j]); cy[a[j]]=max(cy[a[j]],dp[i][j]); } } printf("%d ",ans); }
E.
用动态开点线段树维护一下（因为值域过大）
#include<bits/stdc++.h> #define N 100005 using namespace std; int rt[N],a[N],cnt,n,k,m; int sumv[N*70],ls[N*70],rs[N*70]; queue<int>q[N]; void ins(int &x,int pre,int l,int r,int q,int v){ if(l>r)return;x=++cnt;sumv[x]=sumv[pre]+v; ls[x]=ls[pre];rs[x]=rs[pre];if(l==r)return; int mid=(l+r)>>1; if(q<=mid)ins(ls[x],ls[pre],l,mid,q,v); else ins(rs[x],rs[pre],mid+1,r,q,v); } int query(int o,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr)return sumv[o]; int ans=0,mid=(l+r)>>1; if(ql<=mid)ans+=query(ls[o],l,mid,ql,qr); if(qr>mid)ans+=query(rs[o],mid+1,r,ql,qr); return ans; } inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } int main(){ n=read();k=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++){ q[a[i]].push(i);ins(rt[i],rt[i-1],1,n,i,1); if(q[a[i]].size()>k){ int tmp=q[a[i]].front();q[a[i]].pop(); ins(rt[i],rt[i],1,n,tmp,-1); } } m=read();int ans=0; while(m--){ int l=read(),r=read(); l=(l+ans)%n+1;r=(r+ans)%n+1; if(l>r)swap(l,r); ans=query(rt[r],1,n,l,r); printf("%d ",ans); } }
F.
这tm做cf都能碰到原题，日哦。
bzoj4025。
可以分治并查集维护下（注意此时并查集不可以路径压缩）
或者直接LCT，参考2014集训队论文做法。
人懒就不码LCT了。
#include<bits/stdc++.h> #define N 500005 using namespace std; int n,m,t,fa[N],top,q[N<<2],d[N],a[N]; struct Edge{int x,y,l,r;}G[N]; inline int get(int x){ while(fa[x]!=x)x=fa[x]; return x; } inline int dis(int x){ int ret=0;while(fa[x]!=x)ret^=a[x],x=fa[x]; return ret; } inline void link(int x,int y,int v){ if(d[x]>d[y])swap(x,y);if(d[x]==d[y])d[y]++,q[++top]=y; fa[x]=y;a[x]=v;q[++top]=x; } inline void erase(int x){ for(;top>x;top--)if(q[top<0])d[-q[top]]--; else fa[q[top]]=q[top],a[q[top]]=0; } void solve(int l,int r,int k){ int mid=(l+r)>>1,now=top; for(int i=1;i<=k;i++)if(G[i].l<=l&&r<=G[i].r){ int u=get(G[i].x),v=get(G[i].y); if(u!=v)link(u,v,dis(G[i].x)==dis(G[i].y)); else if(dis(G[i].x)==dis(G[i].y)){ for(int i=l;i<=r;i++)puts("NO");erase(now);return; } swap(G[k--],G[i--]); } if(l==r)puts("YES"); else{ int i,j;for(i=1,j=0;i<=k;i++)if(G[i].l<=mid)swap(G[i],G[++j]); solve(l,mid,j); for(i=1,j=0;i<=k;i++)if(G[i].r>mid)swap(G[i],G[++j]); solve(mid+1,r,j); } erase(now); } map<int,int> mp[N]; inline int read(){ int f=1,x=0;char ch; do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9'); do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9'); return f*x; } int main(){ n=read();t=read(); for(int i=1;i<=t;i++){ int x=read(),y=read();if(x>y)swap(x,y); if(mp[x][y])G[mp[x][y]].r=i-1,mp[x][y]=0; else{ mp[x][y]=++m;G[m].x=x;G[m].y=y;G[m].l=i-1;G[m].r=t; } } for(int i=1;i<=m;i++)if(++G[i].l>G[i].r)i--,m--; for(int i=1;i<=n;i++)fa[i]=i,d[i]=1; solve(1,t,m); }
总结：
思维能力亟待加强，还要多多cf
edu的难度比较符合我目前的水平，找个空多补一补。