6-26
T1粉丝问我ctrl键在哪里
励志阿伟现在正处在一个冰火迷宫中，迷宫由 n 个格子组成，每个格子要么是冰之格，要么是火之格，励志阿伟刚开始可以选择从迷宫中任意一个开始走，走到第 i 个位置时会得到值为 ai 的积分。如果励志阿伟当前在冰之格，那么他可以选择一个编号大于当前格子的冰之格，跳到那里。如果励志阿伟当前在火之格，那么他可以选择一个编号大于当前格子的火之格，跳到那里。如果励志阿伟目前没有格子可以走，那么结束。励志阿伟想最大化他的得分，于是他学会了一个超能力，他能在比赛开始的时候改变最多 m 个格子的状态，即将一个格子从冰之格变成火之格或从火之格变成冰之格，改变第 i 个格子的状态会让励志阿伟的得分减少 pi 。 你能告诉励志阿伟他最多能得几分吗？（特别地，励志阿伟可以选择一个格子都不走积分为 0。
在考试时看错了题面，痛失80分，正解应为贪心，从第一个收益为正的冰/火各自开始，计算每个格子的收益并排序可得。
std:
#include<bits/stdc++.h> #define poly vector<int> #define IOS ios::sync_with_stdio(false) #define ll long long #define mp make_pair #define mt make_tuple #define pa pair < int,int > #define fi first #define se second #define inf 1e18 #define mod 998244353 #define int ll #define N 200005 using namespace std; map<int,int>dp[N],s[N]; int ts[N],tdp[N]; int son[N]; int dis[N]; int siz[N]; int n,m; poly G[N],P[N]; int sum[N]; int r[N],val[N]; void dfs(int k,int fa) { siz[k]+=1; for (auto u:G[k]) { if (u==fa) continue; dfs(u,k); if (siz[u]>siz[son[k]]) son[k]=u; siz[k]+=siz[u]; } siz[k]+=P[k].size(); } void dfs1(int k,int fa) { if (son[k]) { dfs1(son[k],k); swap(s[k],s[son[k]]); swap(dp[k],dp[son[k]]); ts[k]=ts[son[k]]; tdp[k]=tdp[son[k]]; ts[k]++; s[k][(0)-ts[k]]=s[k][(1)-ts[k]]; tdp[k]--; dp[k].erase((-1)-tdp[k]); } int zson=0; int mx=0; for (auto u:G[k]) { if (u==fa||u==son[k]) continue; dfs1(u,k); } for (auto u:G[k]) { if (u==fa||u==son[k]) continue; for (auto [j,v]:s[u]) { if (j+ts[u]<dp[k].size()) { dp[k][(j+ts[u])-tdp[k]]+=v; } } } for (auto u:G[k]) { if (u==fa||u==son[k]) continue; for (auto [j,v]:s[u]) { s[k][(j+1+ts[u])-ts[k]]+=v; } } for (auto u:G[k]) { if (u==fa||u==son[k]) continue; for (auto [ii,v]:dp[u]) { int i=ii+tdp[u]; int coef=0; if (s[u].count((i-1)-ts[u])) coef+=-s[u][(i-1)-ts[u]]; if (s[k].count((i)-ts[k])) coef+=s[k][(i)-ts[k]]; dp[k][(i-1)-tdp[k]]=max(dp[k][(i-1)-tdp[k]],v+coef); } } for (auto i:P[k]) { int ds=r[i]; int coef=0; if (s[k].count((ds+1)-ts[k])) coef=s[k][(ds+1)-ts[k]]; dp[k][ds-tdp[k]]=max(dp[k][ds-tdp[k]],coef+val[i]); } for (auto u:G[k]) if (u!=fa&&u!=son[k]&&s[u].count(-ts[u])) s[k][0-ts[k]]+=s[u][0-ts[u]]; if (dp[k].count(-tdp[k])) s[k][0-ts[k]]=max(s[k][0-ts[k]],dp[k][0-tdp[k]]); } void BellaKira() { cin>>n>>m; for (int i=1;i<n;i++) { int x,y; cin>>x>>y; G[x].push_back(y); G[y].push_back(x); } for (int i=1;i<=m;i++) { int pos; cin>>pos>>r[i]>>val[i]; P[pos].push_back(i); } dfs(1,0); dfs1(1,0); int ans=s[1][-ts[1]]; for (auto u:dp[1]) ans=max(ans,u.se); cout<<ans<<'\n'; } signed main() { IOS; cin.tie(0); int T=1; while (T--) { BellaKira(); } }
T2原神，启动
你需要构造一个 n × n 的矩阵，每个点填黑或白，使得相邻格子不同色的对数恰好为 m考试时只打了25分的部分分，被dp所限制了，正解是构造，可将整个表格不同色对数个数最大化，再解方程。
std：
#include<bits/stdc++.h> #define poly vector<int> #define IOS ios::sync_with_stdio(false) #define ll long long #define mp make_pair #define mt make_tuple #define pa pair < int,int > #define fi first #define se second #define inf 1e18 #define mod 998244353 // #define int ll #define N 1005 using namespace std; int n,m,a[N][N],b[N][N],col[N][N]; void BellaKira() { cin>>n>>m; if (n==1) { if (m==0) { cout<<"Possible\n0\n"; return; } cout<<"Impossible\n"; return; } if (n==2) { if (m==4) { cout<<"Possible\n01\n10\n"; return; } if (m==2) { cout<<"Possible\n01\n01\n"; return; } if (m==0) { cout<<"Possible\n00\n00\n"; return; } cout<<"Impossible\n"; return; } memset(a,-1,sizeof(a)); for (a[1][1]=0;a[1][1]<=1;a[1][1]++) for (a[n][1]=0;a[n][1]<=1;a[n][1]++) for (a[n][n]=0;a[n][n]<=1;a[n][n]++) for (a[1][n]=0;a[1][n]<=1;a[1][n]++) { int x=0,y=0,z=0,p=0; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { b[i][j]=a[i][j]; if ((i+j)%2==0&&b[i][j]==-1) b[i][j]=0; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if ((i+j)%2==1&&b[i][j]==-1) { int tt=0,pp=0; for (int dx=-1;dx<=1;dx++) for (int dy=-1;dy<=1;dy++) if (dx+dy&&(dx==0||dy==0)&&i+dx>=1&&i+dx<=n&&j+dy>=1&&j+dy<=n) { tt+=1; pp+=b[i+dx][j+dy]; } if (tt==4) x++,col[i][j]=1; else if (pp==0) y++,col[i][j]=2; else p++,col[i][j]=3+pp; } for (int i=1;i<=n;i++) for (int j=1;j<n;j++) if (b[i][j]!=-1&&b[i][j+1]!=-1) z+=b[i][j]!=b[i][j+1]; for (int i=1;i<n;i++) for (int j=1;j<=n;j++) if (b[i][j]!=-1&&b[i+1][j]!=-1) z+=b[i][j]!=b[i+1][j]; int X=-1,Y=-1,Z=-1; // assert(p<=4); for (int j=0;j<=y;j++) for (int k=0;k<=p;k++) if ((m-(z+j*3+k*1+(p-k)*2))%4==0 &&(m-(z+j*3+k*1+(p-k)*2))/4<=x &&(m-(z+j*3+k*1+(p-k)*2))/4>=0) { X=(m-(z+j*3+k*1+(p-k)*2))/4,Y=j,Z=k; } if (X!=-1) { cout<<"Possible\n"; for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { if (b[i][j]==-1) { if (col[i][j]==1) { b[i][j]=(X>0); X--; } else if (col[i][j]==2) { b[i][j]=(Y>0); Y--; } else if (col[i][j]==4) { if (Z) { Z--; b[i][j]=0; } else b[i][j]=1; } else if (col[i][j]==5) { if (Z) { Z--; b[i][j]=1; } else b[i][j]=0; } } cout<<b[i][j]; } cout<<'\n'; } return; } } cout<<"Impossible\n"; } signed main() { IOS; cin.tie(0); int T=1; cin>>T; while (T--) { BellaKira(); } }
T3雨田天宇
定义一个长度为 n 的序列 a 的权值为所有重排 a 之后的新序列 a ′ 的 ∑ni=1 |a ′ i −a ′ n−i+1| 的最大值。求所有长度为 n 的每个数取值在 [1, m] 的序列的权值的和，对 998244353 取模。
考虑拆开看贡献，首先显然排序过后的 a 是最优解之一。考虑横着算贡献，也就是枚举 i，枚举 j，使得 j 个数小于 i，n − j 个数大于等于i，然后算一下这一行对答案的贡献就行了。
std：
// Problem: Sum Over All Arrays // Contest: CodeChef - START86 // URL: https://www.codechef.com/problems/SUMOVERALL // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> #define poly vector<int> #define IOS ios::sync_with_stdio(false) #define ll long long #define mp make_pair #define mt make_tuple #define pa pair < int,int > #define fi first #define se second #define inf 1e18 #define mod 998244353 #define int ll #define N 5005 using namespace std; int n,m,C[N][N],pw[N][N]; void BellaKira() { int ans=0; cin>>n>>m; int t=0; for (int i=0;i<=n;i++) for (int j=1;j<=m;j++) { int coef=0; if (i<=(n+1)/2) coef=min(i,n/2); else coef=min(i,n/2)-(i-(n+1)/2); ans=(ans+coef*C[n][i]%mod*pw[m-j+1][i]%mod*pw[j-1][n-i]%mod)%mod; } cout<<ans*2%mod<<'\n'; } signed main() { C[0][0]=1; for (int i=1;i<N;i++) { C[i][0]=1; for (int j=1;j<=i;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; } for (int i=0;i<N;i++) { pw[i][0]=1; for (int j=1;j<N;j++) pw[i][j]=pw[i][j-1]*i%mod; } IOS; cin.tie(0); int T=1; while (T--) { BellaKira(); } }
T4安排 r
定义一个长度为 n 的序列 a 后缀和序列为另一个长度为 n 的序列 b 使得对于所有 i都有 定义将一个序列一般化指把序列中的每个数都跟 bi = ∑n j=i aj。 1018 取 min，然后跟 −1018 取 max。现在给你一个长度为 n 的序列，你可以执行以下三种操作：1：将序列中所有数取反。2：选取一个区间 [l, r](1 ≤ l ≤ r ≤ n)，将 [l, r] 这个区间变为这个区间的前缀和序列，然后将 a 一般化。3：选取一个区间 [l, r](1 ≤ l ≤ r ≤ n)，将 [l, r] 这个区间变为这个区间的后缀和序列，然后将 a 一般化。你需要花费最少的次数使得序列中每个数都是非负整数。
先把只需要操作零次和操作一次判掉，操作一次只需要操作整个序列即可，可以证明一定不劣。有如下结论：操作次数不超过 3。这是因为我们发现对一个区间 [l, r] 做前缀和本质上是从 al , al+1, ..., ar 变成 sl −sl−1, sl+1−sl−1, ..., sr−sl−1。做后缀和本质上是从 al , al+1, ..., ar 变成 sr−sl−1, sr−sl , ..., sr−sr−1。所以如果我们找到 s 最小的位置 x 与 s 最大的位置 y，若 x ≤ y，则能在两次之内完成，否则我们把序列取反，两个位置就会反一反，也能在三次之内完成。再考虑分治，动态维护凸壳
std：
#include<bits/stdc++.h> #define poly vector<int> #define IOS ios::sync_with_stdio(false) #define ll long long #define mp make_pair #define mt make_tuple #define pa pair < int,int > #define fi first #define se second #define inf ((int)1e18) #define mod 998244353 #define int ll #define N 500005 using namespace std; int n,m,a[N],s[N]; int ss[N]; int Tmp[N]; int tmpa[N]; int pre[N],suf[N]; vector<pair<int,pa>>ans; int chk() { { bool bl=1; for (int i=1;i<=n;i++) bl&=(a[i]>=0); if (bl) { return 1; } { bl=1; int x=0; for (int i=1;i<=n;i++) { x=min(inf,a[i]+x),x=max(-inf,x); bl&=(x>=0); } if (bl) { ans.push_back(mp(2,mp(1,n))); return 1; } } { bl=1; int x=0; for (int i=n;i>=1;i--) { x=min(inf,a[i]+x),x=max(-inf,x); bl&=(x>=0); } if (bl) { ans.push_back(mp(3,mp(1,n))); return 1; } } { bl=1; int x=0; for (int i=1;i<=n;i++) bl&=(a[i]<=0); if (bl) { ans.push_back(mp(1,mp(0,0))); return 1; } } } return 0; } void outp() { cout<<ans.size()<<endl; for (auto [u,v]:ans) { cout<<u; if (v.fi) cout<<" "<<v.fi<<" "<<v.se; if (u==1) { for (int i=1;i<=n;i++) Tmp[i]=-Tmp[i]; }else if (u==2) { for (int i=v.fi+1;i<=v.se;i++) Tmp[i]+=Tmp[i-1],Tmp[i]=max(Tmp[i],-inf),Tmp[i]=min(Tmp[i],inf); } else { for (int i=v.se-1;i>=v.fi;i--) Tmp[i]+=Tmp[i+1],Tmp[i]=max(Tmp[i],-inf),Tmp[i]=min(Tmp[i],inf); } cout<<endl; } // for (int i=1;i<=n;i++) // cout<<Tmp[i]<<" "; // cout<<endl; for (int i=1;i<=n;i++) assert(Tmp[i]>=0); exit(0); } void chklf(){ for (int i=1;i<=n;i++) tmpa[i]=a[i]; int now=1; __int128 all=0; while (ans.size()<=2){ while (now<=n&&all+tmpa[now]>=0){ all+=tmpa[now]; now++; } ans.push_back(mp(2,mp(1,now-1))); for (int i=1;i<now;i++) tmpa[i]=(tmpa[i-1]+tmpa[i]),tmpa[i]=min(tmpa[i],inf),tmpa[i]=max(tmpa[i],-inf); all=0; for (int i=1;i<now;i++) all+=tmpa[i]; bool bl=1; for (int i=1;i<=n;i++) bl&=(tmpa[i]>=0); if (bl) break; } if (ans.size()==2) outp(); ans.clear(); } void chkrt(){ for (int i=1;i<=n;i++) tmpa[i]=a[i]; int now=n; __int128 all=0; while (ans.size()<=2){ while (now>=1&&all+tmpa[now]>=0) { all+=tmpa[now]; now--; } ans.push_back(mp(3,mp(now+1,n))); for (int i=n;i>now;i--) tmpa[i]=(tmpa[i+1]+tmpa[i]),tmpa[i]=min(tmpa[i],inf),tmpa[i]=max(tmpa[i],-inf); all=0; for (int i=n;i>now;i--) all+=tmpa[i]; bool bl=1; for (int i=1;i<=n;i++) bl&=(tmpa[i]>=0); if (bl) break; } if (ans.size()==2) outp(); ans.clear(); } pa sta[N]; int tp; int p[N]; int cnt; int alltag; pa Rt[N]; int rev; int Mn[N]; int L=-1,R=-1; inline pa sub(pa x,pa y) { return mp(x.fi-y.fi,x.se-y.se); } inline pa addy(pa x,int del) { return mp(x.fi,x.se+del); } inline int mul(pa x,pa y) { return x.fi*y.se-x.se*y.fi; } namespace lct { struct node { int k,b; node(pa x) { k=x.fi,b=x.se; } node(int x,int y) { k=x,b=y; } node() { k=b=0; } inline int val(int x) { return k*x+b; } }tr[N<<2]; int lson[N<<2]; int rson[N<<2]; int tot=0; int rt=0; void update(int &k,int l,int r,node x) { if (!k) { k=++tot; assert(tot<(N<<2)); tr[k]=x; lson[k]=0,rson[k]=0; return; } int mid=l+(r-l)/2; if (tr[k].val(mid)>x.val(mid)) swap(tr[k],x); if (l==r) return; if (tr[k].k<x.k) { update(lson[k],l,mid,x); } else update(rson[k],mid+1,r,x); } int query(int k,int l,int r,int L) { if (!k) return inf; int mid=l+(r-l)/2; if (L<=mid) return min(tr[k].val(L),query(lson[k],l,mid,L)); return min(tr[k].val(L),query(rson[k],mid+1,r,L)); } void clr() { rt=0; tot=0; } } void work(int l,int r) { if (l==r) return; int mid=l+(r-l)/2; // cout<<"work "<<l<<" "<<r<<endl; work(l,mid); work(mid+1,r); tp=0; cnt=0; alltag=0; for (int i=mid+1;i<=r;i++) { int mx=-inf; alltag+=a[i]; alltag-=s[i]; pa now=mp(r-i+1,-s[n]-alltag); while (tp>1&&mul(sub(addy(sta[tp],alltag),addy(now,alltag)), sub(addy(sta[tp-1],alltag),addy(now,alltag)))>=0) { tp--; } sta[++tp]=now; if (suf[i+1]) { int L=2,R=tp; int pos=tp; pa zero=mp(r-i,0); while (L<=R) { int mid=L+(R-L)/2; if (mul(sub(addy(sta[mid],alltag),zero),sub(addy(sta[mid-1],alltag),zero))>=0) { pos=mid-1; R=mid-1; } else { L=mid+1; } } int lim=(sta[pos].se+alltag-0)/(sta[pos].fi-r+i); if (sta[pos].se+alltag>0) lim=(sta[pos].se+alltag+(sta[pos].fi-r+i)-1)/(sta[pos].fi-r+i); Rt[++cnt]=mp(lim,i); } } lct::clr(); for (int i=mid;i>=l;i--) { int sm=(-s[i-1])*(mid-i+1)+ss[mid]-ss[i-1]; Mn[i]=min(sm+s[i-1]+pre[i-1],inf); lct::update(lct::rt,-n,n,lct::node(mid-i+1,ss[mid]-ss[i-1])); Mn[i]=min(Mn[i],lct::query(lct::rt,-n,n,-s[i-1])); p[i]=i; } sort(p+l,p+mid+1,[&](int x,int y) { return -s[x-1]<-s[y-1]; }); lct::clr(); sort(Rt+1,Rt+cnt+1); int pos=1; for (int ii=l;ii<=mid;ii++) { int i=p[ii]; // cout<<"!!"<<i<<" "<<-s[i-1]<<endl; while (pos<=cnt&&-s[i-1]>=Rt[pos].fi) { // cout<<"ins "<<Rt[pos].se<<endl; lct::update(lct::rt,-n,n, lct::node(-(Rt[pos].se-mid),-(ss[Rt[pos].se]-ss[mid]+s[n]-s[Rt[pos].se]))); pos++; } int mx=-lct::query(lct::rt,-n,n,-s[i-1]); if (mx+Mn[i]>=0) { for (int j=1;j<pos;j++) { lct::node now= lct::node(-(Rt[j].se-mid),-(ss[Rt[j].se]-ss[mid]+s[n]-s[Rt[j].se])); if (now.val(-s[i-1])==-mx) { if (rev==0) ans.push_back(mp(2^rev,mp(i,Rt[j].se))); else ans.push_back(mp(2^rev,mp(n-Rt[j].se+1,n-i+1))); ans.push_back(mp(3^rev,mp(1,n))); outp(); } } } } // cout<<"work "<<l<<" "<<r<<endl; } void BellaKira() { cin>>n>>m; for (int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i],Tmp[i]=a[i]; if (chk()) { outp(); } ans.push_back(mp(1,mp(0,0))); for (int i=1;i<=n;i++) a[i]=-a[i]; if (chk()) { outp(); } for (int i=1;i<=n;i++) a[i]=-a[i]; ans.clear(); int mn=0,mx=0; for (int i=1;i<=n;i++) { if (s[i]>=s[mx]) mx=i; if (s[i]<s[mn]) mn=i; } if (mn>=mx) { pre[0]=inf,suf[n+1]=1; for (int i=1;i<=n;i++) pre[i]=min(pre[i-1],-s[i-1]); for (int i=n;i>=1;i--) suf[i]=suf[i+1]&(s[n]-s[i-1]>=0); for (int i=1;i<=n;i++) ss[i]=ss[i-1]+s[i]; chklf(); chkrt(); work(1,n); rev=1; reverse(a+1,a+n+1); for (int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; pre[0]=inf,suf[n+1]=1; for (int i=1;i<=n;i++) pre[i]=min(pre[i-1],-s[i-1]); for (int i=n;i>=1;i--) suf[i]=suf[i+1]&(s[n]-s[i-1]>=0); for (int i=1;i<=n;i++) ss[i]=ss[i-1]+s[i]; work(1,n); reverse(a+1,a+n+1); ans.push_back(mp(1,mp(0,0))); for (int i=1;i<=n;i++) a[i]=-a[i],s[i]=s[i-1]+a[i]; mn=0,mx=0; for (int i=1;i<=n;i++) { if (s[i]>=s[mx]) mx=i; if (s[i]<s[mn]) mn=i; } ans.push_back(mp(2,mp(mn+1,n))); ans.push_back(mp(3,mp(1,mx))); outp(); } else { ans.push_back(mp(2,mp(mn+1,n))); ans.push_back(mp(3,mp(1,mx))); outp(); } } signed main() { IOS; cin.tie(0); int T=1; while (T--) { BellaKira(); } }