2025省选模拟5
题目来源： 2024省选联测11
\(T1\) HZTG5843. Giao 徽的烤鸭 \(31pts\)
-
部分分
- \(20 \%\) ：爆搜。
- \(15 \%\) ：分讨菊花的三种情况。
点击查看代码
struct node { int nxt,to; }e[10010]; int head[5010],a[5010],b[5010],dis[5010][5010],vis[5010],cnt=0,ans=0; vector<int>col[510][510]; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void get_dis(int x,int fa,int rt) { col[rt][dis[rt][x]].push_back(x); for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa) { dis[rt][e[i].to]=dis[rt][x]+1; get_dis(e[i].to,x,rt); } } } int get_p(int x,int n) { for(int i=0;i<=n;i++) { for(int j=0;j<col[x][i].size();j++) { if(vis[col[x][i][j]]==0) return i-1; } } return n-1; } void dfs(int pos,int n,int sum) { if(pos==n+1) { for(int i=1;i<=n;i++) { if(vis[i]==1) { sum+=b[get_p(i,n)]; } } ans=max(ans,sum); return; } vis[pos]=1; dfs(pos+1,n,sum-a[pos]); vis[pos]=0; dfs(pos+1,n,sum); } int main() { #define Isaac #ifdef Isaac freopen("duck.in","r",stdin); freopen("duck.out","w",stdout); #endif int n,u,v,flag=1,sum=0,i; cin>>n; for(i=1;i<=n;i++) cin>>a[i]; for(i=0;i<=n-1;i++) cin>>b[i]; for(i=1;i<=n-1;i++) { cin>>u>>v; add(u,v); add(v,u); flag&=(u==i+1&&v==1); } if(flag==1) { for(i=2;i<=n;i++) sum+=max(b[0]-a[i],0); ans=max(ans,sum); sum=-a[1]; for(i=2;i<=n;i++) sum+=max(b[1]-a[i],0); ans=max(ans,b[0]+sum); sum=-a[1]; for(i=2;i<=n;i++) sum+=b[n-1]-a[i]; ans=max(ans,b[n-1]+sum); } else { for(i=1;i<=n;i++) get_dis(i,0,i); dfs(1,n,0); } cout<<ans<<endl; return 0; } -
正解
- 设 \(f_{x,i}\) 表示以 \(x\) 为根的子树内离 \(x\) 距离 \(\ge i\) 的点都办会员卡的最大利润。
- 转移时为保证 \(v_{i}\) 正确地加入决策集合需保证 \(i_{fa},i_{y} \ge i_{x}-1\) ，化简得到 \(i_{x}-1 \le i_{y} \le i_{x}+1\) 。
- 为方便不办会员卡时的转移，整体将下标右移一位，令 \(f_{x,0}\) 表示 \(x\) 不办会员卡的最大利润。
点击查看代码
struct node { ll nxt,to; }e[10010]; ll head[5010],a[5010],b[5010],f[5010][5010],cnt=0,n; void add(ll u,ll v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(ll x,ll fa) { for(ll i=1;i<=n;i++) f[x][i]=b[i-1]-a[x]; f[x][n+1]=-0x3f3f3f3f3f3f3f3f; for(ll i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa) { dfs(e[i].to,x); f[x][0]+=max(f[e[i].to][0],f[e[i].to][1]); for(ll j=1;j<=n;j++) { f[x][j]+=max({f[e[i].to][j-1],f[e[i].to][j],f[e[i].to][j+1]}); } } } } int main() { #define Isaac #ifdef Isaac freopen("duck.in","r",stdin); freopen("duck.out","w",stdout); #endif ll u,v,ans=0,i; cin>>n; for(i=1;i<=n;i++) cin>>a[i]; for(i=0;i<=n-1;i++) cin>>b[i]; for(i=1;i<=n-1;i++) { cin>>u>>v; add(u,v); add(v,u); } dfs(1,0); for(i=0;i<=n;i++) ans=max(ans,f[1][i]); cout<<ans<<endl; return 0; }
\(T2\) HZTG5844. A Dance of Fire and Ice \(20pts\)
- 原题： Gym103428C Assign or Multiply
- 观察到每次赋值相互独立，只需要处理乘法的情况。
- 部分分
-
\(20pts\) ：背包 \(O(np)\) 转移。
点击查看代码
ll pd[1000010],a[1000010],op,p; bitset<200010>ans,f[2]; void add(ll x) { op^=1; f[op]=f[op^1]; for(ll i=f[op^1]._Find_first();i<=p;i=f[op^1]._Find_next(i)) f[op][i*x%p]=1; } void mul(ll x) { for(ll i=f[op]._Find_first();i<=p;i=f[op]._Find_next(i)) ans[i*x%p]=1; } int main() { #define Isaac #ifdef Isaac freopen("dance.in","r",stdin); freopen("dance.out","w",stdout); #endif ll n,i; scanf("%lld%lld",&p,&n); a[0]=f[op][1]=1; for(i=1;i<=n;i++) { scanf("%lld%lld",&pd[i],&a[i]); if(pd[i]==1) add(a[i]); } for(i=0;i<=n;i++) { if(pd[i]==0) mul(a[i]); } printf("%lld\n",ans.count()); return 0; } -
\(60pts\) ：使用巴雷特约减优化上述取模过程。
点击查看代码
#include "MATH/Barrett.h"// oldyan 的 CP-template-main #endif int pd[1000010],a[1000010],op,p; bitset<200010>ans,f[2]; int main() { #define Isaac #ifdef Isaac freopen("dance.in","r",stdin); freopen("dance.out","w",stdout); #endif int n,i,j; scanf("%d%d",&p,&n); OY::Barrett32 brt(p); a[0]=f[op][1]=1; for(i=1;i<=n;i++) { scanf("%d%d",&pd[i],&a[i]); if(pd[i]==1) { op^=1; f[op]=f[op^1]; for(j=f[op^1]._Find_first();j<=p;j=f[op^1]._Find_next(j)) { f[op][brt.multiply(j,a[i])]=1; } } } for(i=0;i<=n;i++) { if(pd[i]==0) { for(j=f[op]._Find_first();j<=p;j=f[op]._Find_next(j)) { ans[brt.multiply(j,a[i])]=1; } } } printf("%d\n",ans.count()); return 0; }
-
- 正解
-
考虑通过原根及模意义下的对数将乘法转化为加法，然后在对数 \(\mod \varphi(p)\) 意义下进行背包 \(DP\) 转移。
-
使用
bitset加速，中途若转移后的状态与原状态相等则退出转移以此进行剪枝。点击查看代码
ll lg[200010],cnt[200010]; vector<ll>result; bitset<200010>f,g; void divide(ll n) { result.clear(); for(ll i=2;i*i<=n;i++) { if(n%i==0) { result.push_back(i); while(n%i==0) n/=i; } } if(n>1) result.push_back(n); } ll qpow(ll a,ll b,ll p) { ll ans=1; while(b) { if(b&1) ans=ans*a%p; b>>=1; a=a*a%p; } return ans; } bool check(ll x,ll p,ll phi) { if(qpow(x,phi,p)!=1) return false; for(ll i=0;i<result.size();i++) { if(qpow(x,phi/result[i],p)==1) return false; } return true; } ll min_pr(ll p,ll phi) { for(ll i=1;i<=p-1;i++) { if(check(i,p,phi)==true) return i; } return -1; } int main() { #define Isaac #ifdef Isaac freopen("dance.in","r",stdin); freopen("dance.out","w",stdout); #endif ll p,phi,n,pr,pd,x,ans=0,i,j; scanf("%lld%lld",&p,&n); phi=p-1; divide(phi); pr=min_pr(p,phi); for(i=0,x=1;i<=phi-1;i++,x=x*pr%p) lg[x]=i; for(i=1;i<=n;i++) { scanf("%lld%lld",&pd,&x); ans|=(x==0); if(pd==0) f[lg[x]]=1; else cnt[lg[x]]++; } f[0]=1; for(i=0;i<=phi-1;i++) { for(j=1;j<=cnt[i];j++) { g=f|(f<<i)|(f>>(phi-i)); if(f==g) break; f=g; } } for(i=0;i<=phi-1;i++) ans+=f[i]; printf("%lld\n",ans); return 0; } -
Gym103428C Assign or Multiply 上要求恰好 \(n\) 次操作，只需要记录一下 \(\prod\limits_{op_{i}=1} a_{i}\) 并在最后计入答案，需要加火车头优化。
点击查看代码
#pragma GCC optimize(3) #pragma GCC target("avx") #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") ll lg[200010],cnt[200010]; vector<ll>result; bitset<200010>f,g; void divide(ll n) { result.clear(); for(ll i=2;i*i<=n;i++) { if(n%i==0) { result.push_back(i); while(n%i==0) n/=i; } } if(n>1) result.push_back(n); } ll qpow(ll a,ll b,ll p) { ll ans=1; while(b) { if(b&1) ans=ans*a%p; b>>=1; a=a*a%p; } return ans; } bool check(ll x,ll p,ll phi) { if(qpow(x,phi,p)!=1) return false; for(ll i=0;i<result.size();i++) { if(qpow(x,phi/result[i],p)==1) return false; } return true; } ll min_pr(ll p,ll phi) { for(ll i=1;i<=p-1;i++) { if(check(i,p,phi)==true) return i; } return -1; } int main() { // #define Isaac #ifdef Isaac freopen("dance.in","r",stdin); freopen("dance.out","w",stdout); #endif ll p,phi,n,pr,pd,x,tmp=1,ans=0,i,j; scanf("%lld%lld",&p,&n); phi=p-1; divide(phi); pr=min_pr(p,phi); for(i=0,x=1;i<=phi-1;i++,x=x*pr%p) lg[x]=i; for(i=1;i<=n;i++) { scanf("%lld%lld",&pd,&x); ans|=(x==0); if(pd==0) f[lg[x]]=1; else { tmp=tmp*x%p; cnt[lg[x]]++; } } for(i=0;i<=phi-1;i++) { for(j=1;j<=cnt[i];j++) { g=f|(f<<i)|(f>>(phi-i)); if(f==g) break; f=g; } } if(tmp!=0) f[lg[tmp]]=1; for(i=0;i<=phi-1;i++) ans+=f[i]; printf("%lld\n",p-ans); return 0; } -
挂一下题解的做法。
-
\(T3\) HZTG5845. 挖掘机技术哪家强 \(60pts\)
-
部分分
- \(60pts\) ：建图后 Bron Kerbosch 求解最大团。
点击查看代码
int p[200010],R[80][200010],P[80][200010],ans=0; map<pair<int,int>,int> e; bool find(int u,int v) { return e.find(make_pair(u,v))!=e.end(); } void Bron_Kerbosch(int dep,int r,int p) { if(p==0||dep>75) { ans=max(ans,r); return; } int u=P[dep][1]; for(int i=1;i<=p;i++) { if(find(u,P[dep][i])==false) { for(int j=1;j<=r;j++) R[dep+1][j]=R[dep][j]; R[dep+1][r+1]=P[dep][i]; int np=0; for(int j=1;j<=p;j++) { if(find(P[dep][i],P[dep][j])==true) { np++; P[dep+1][np]=P[dep][j]; } } Bron_Kerbosch(dep+1,r+1,np); P[dep][i]=0; } } } int main() { #define Isaac #ifdef Isaac freopen("excavator.in","r",stdin); freopen("excavator.out","w",stdout); #endif int n,m,x,i; cin>>n>>m; for(i=1;i<=n;i++) p[i]=P[1][i]=i; for(i=1;i<=m;i++) { cin>>x; e[make_pair(p[x],p[x+1])]=e[make_pair(p[x+1],p[x])]=1; swap(p[x],p[x+1]); } Bron_Kerbosch(1,0,n); cout<<ans<<endl; return 0; } -
正解
总结
- \(T1\) 赛时以为保证 \(v_{i}\) 正确地加入决策集合需要换根分讨多种情况，没想到能直接把限制条件由儿子节点继承而来。
- \(T2\) 赛时瞪了 \(2h\) 才发现每次赋值相互独立的性质。
后记
- \(T1\) 输出 \(\max(0,\sum\limits_{i=1}^{n}v_{n-1}-w_{i})\) 即可通过此题。