又打了一场EDU，感觉这场比23难多了啊……
艹还是我太弱了。
A.
随便贪心一下。
#include<bits/stdc++.h>
using namespace std;
int n,sum=,ans=-,m;
inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
int main(){
n=read();for(int i=;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\n",ans);
}
B.
预处理一下x,y的幂次就随便做了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>a;
ll x,y,l,r,ans=;
int main(){
ios::sync_with_stdio(false);cin>>x>>y>>l>>r;
a.push_back(l-);a.push_back(r+);
for(ll i=;;i*=x){
for(ll j=;;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=;i<a.size();i++)ans=max(ans,a[i]-a[i-]-);
cout<<ans<<endl;
}
C.
推一下结论就行了。
#include<bits/stdc++.h>
#define N 200005
using namespace std;
int da[N],db[N],head[N],tot=,n,x,ans=;
struct Edge{int u,v,next;}G[N<<];
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=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
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]+;
dfs(v,u,d);
}
}
int main(){
n=read();x=read();
for(int i=;i<n;i++){
int u=read(),v=read();
addedge(u,v);
}
da[]=db[]=-;dfs(,,da);dfs(x,,db);
for(int i=;i<=n;i++)if(db[i]<da[i])ans=max(ans,*da[i]);
printf("%d\n",ans);
}
D.
按照官方题解做法dp一下就行。
#include<bits/stdc++.h>
#define N 5010
using namespace std;
int a[N],dp[N][N],cx[],cy[],n,ans=;
inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
int main(){
n=read();for(int i=;i<=n;i++)a[i]=read();
for(int i=;i<=n;i++){
memset(cx,,sizeof(cx));memset(cy,,sizeof(cy));
for(int j=;j<i;j++){
cx[a[j]%]=max(cx[a[j]%],dp[i][j]);
cy[a[j]]=max(cy[a[j]],dp[i][j]);
}
for(int j=i+;j<=n;j++){
dp[i][j]=dp[j][i]=max(max(cx[a[j]%],dp[i][]),max(cy[a[j]-],cy[a[j]+]))+;
ans=max(ans,dp[i][j]);
cx[a[j]%]=max(cx[a[j]%],dp[i][j]);
cy[a[j]]=max(cy[a[j]],dp[i][j]);
}
}
printf("%d\n",ans);
}
E.
用动态开点线段树维护一下（因为值域过大）
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int rt[N],a[N],cnt,n,k,m;
int sumv[N*],ls[N*],rs[N*];
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)>>;
if(q<=mid)ins(ls[x],ls[pre],l,mid,q,v);
else ins(rs[x],rs[pre],mid+,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=,mid=(l+r)>>;
if(ql<=mid)ans+=query(ls[o],l,mid,ql,qr);
if(qr>mid)ans+=query(rs[o],mid+,r,ql,qr);
return ans;
}
inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
int main(){
n=read();k=read();
for(int i=;i<=n;i++)a[i]=read();
for(int i=;i<=n;i++){
q[a[i]].push(i);ins(rt[i],rt[i-],,n,i,);
if(q[a[i]].size()>k){
int tmp=q[a[i]].front();q[a[i]].pop();
ins(rt[i],rt[i],,n,tmp,-);
}
}
m=read();int ans=;
while(m--){
int l=read(),r=read();
l=(l+ans)%n+;r=(r+ans)%n+;
if(l>r)swap(l,r);
ans=query(rt[r],,n,l,r);
printf("%d\n",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<<],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=;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<])d[-q[top]]--;
else fa[q[top]]=q[top],a[q[top]]=;
}
void solve(int l,int r,int k){
int mid=(l+r)>>,now=top;
for(int i=;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=,j=;i<=k;i++)if(G[i].l<=mid)swap(G[i],G[++j]);
solve(l,mid,j);
for(i=,j=;i<=k;i++)if(G[i].r>mid)swap(G[i],G[++j]);
solve(mid+,r,j);
}
erase(now);
}
map<int,int> mp[N];
inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
int main(){
n=read();t=read();
for(int i=;i<=t;i++){
int x=read(),y=read();if(x>y)swap(x,y);
if(mp[x][y])G[mp[x][y]].r=i-,mp[x][y]=;
else{
mp[x][y]=++m;G[m].x=x;G[m].y=y;G[m].l=i-;G[m].r=t;
}
}
for(int i=;i<=m;i++)if(++G[i].l>G[i].r)i--,m--;
for(int i=;i<=n;i++)fa[i]=i,d[i]=;
solve(,t,m);
}
总结：
思维能力亟待加强，还要多多cf
edu的难度比较符合我目前的水平，找个空多补一补。