联盟场-提高组-R5 ZYZSC-S-Round 9

2026/10/29 2:10:53

AT_abc475_d [ABC475D] Alphametic Prime

原题链接：[ABC475D] Alphametic Prime

分析

呃，这个原题没有要求最小值，题目要求了，只是多取一步而已……不知道为啥之前打ABC的时候这个卡了那么久……

正解

#include<bits/stdc++.h>usingnamespacestd;constintN=10000005;boolflag[N];string s;set<char>st;inttot;vector<int>pr;voidEuler(){for(inti=2;i<N;i++){if(!flag[i]){tot++;pr.push_back(i);}for(intj=1;j<=tot&&i*pr[j-1]<N;j++){flag[i*pr[j-1]]=true;if(i%pr[j-1]==0)break;}}}charc[30];intcnt=0;intans=0x3f3f3f3f;map<char,int>buc;boolvis[15];voiddfs(intp){if(p==cnt+1){intres=0;for(inti=0;i<(int)s.length();i++){res=res*10+buc[s[i]];}if(!flag[res])ans=min(ans,res);return;}if(c[p]==s[0]){for(inti=1;i<=9;i++){if(!vis[i]){buc[c[p]]=i;vis[i]=true;dfs(p+1);vis[i]=false;}}}else{for(inti=0;i<=9;i++){if(!vis[i]){buc[c[p]]=i;vis[i]=true;dfs(p+1);vis[i]=false;}}}}signedmain(){// freopen("alphametic.in", "r", stdin);// freopen("alphametic.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>s;for(autov:s){st.insert(v);}if(st.size()==1&&s.length()>2){cout<<-1;return0;}flag[0]=true;flag[1]=true;Euler();for(autov:st){c[++cnt]=v;buc[v]=0;}dfs(1);if(ans==0x3f3f3f3f)cout<<-1;elsecout<<ans;}

LGP17437 「LWLV Round 1」Young

原题链接：「LWLV Round 1」Young

分析

哎呀！
差一步😭
就是说，我们发现，我们尽可能使得最小的子树最小，然后，剩下的分为两个，然后你记录一个最大，一次次大不久可以更新答案了吗？
哎呀😭
这个没想到真的不应该！

另一个解法是二分答案：

代码放到这里了。不过这个写法常数巨大，甚至逼近了O ( n n ) O(n\sqrt{n})O(nn)，在5 e 5 5e55e5中显然需要卡常。

正解

#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=500005;constintinf=0x3f3f3f3f3f3f3f3f;intn,w[N];vector<int>e[N];intmx[N],mx_id[N];intmmx[N];intmn[N],mn_id[N];intmmn[N];intsz[N],sum[N],de[N];intson[N];intans=-inf;intget_mid(intx,inty,intz){vector<int>a;a.push_back(x);a.push_back(y);a.push_back(z);sort(a.begin(),a.end());returna[1];}voiddfs(intu,intfa){mx[u]=mmx[u]=-inf;mn[u]=mmn[u]=inf;sz[u]=1;de[u]=de[fa]+1;sum[u]=w[u];for(autov:e[u]){if(v==fa)continue;dfs(v,u);son[u]++;sz[u]+=sz[v];sum[u]+=sum[v];inttmp1=max(mx[v],sum[v]);inttmp2=min(mn[v],sum[v]);if(tmp1>mx[u]){mmx[u]=mx[u];mx[u]=tmp1;mx_id[u]=v;}elseif(tmp1>mmx[u]){mmx[u]=tmp1;}if(tmp2<mn[u]){mmn[u]=mn[u];mn[u]=tmp2;mn_id[u]=v;}elseif(tmp2<mmn[u]){mmn[u]=tmp2;}}}voidsolve(intu,intfa,intMx,intMn){for(autov:e[u]){if(v==fa)continue;inttmp1,tmp2;if(son[u]>1){if(mx_id[u]==v){tmp1=max(Mx,mmx[u]);tmp2=min(Mn,mmn[u]);}else{tmp1=max(Mx,mx[u]);tmp2=min(Mn,mn[u]);}}else{tmp1=max(Mx,-inf);tmp2=min(Mn,inf);}inttmp=sum[1]-sum[v];if(n-sz[v]>1){ans=max(ans,get_mid(tmp-tmp1,tmp1,sum[v]));ans=max(ans,get_mid(tmp-tmp2,tmp2,sum[v]));}if(sz[v]>1){ans=max(ans,get_mid(tmp,sum[v]-mx[v],mx[v]));ans=max(ans,get_mid(tmp,sum[v]-mn[v],mn[v]));}solve(v,u,max(tmp1,tmp),min(tmp2,tmp));}}signedmain(){// freopen("young.in", "r", stdin);// freopen("young.out", "w", stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(inti=1;i<=n;i++){cin>>w[i];}for(inti=1,u,v;i<n;i++){cin>>u>>v;e[u].push_back(v);e[v].push_back(u);}dfs(1,0);solve(1,0,-inf,inf);cout<<ans;}

LGP17432 [LBA-OI R5 B] 彼方的她

原题链接：[LBA-OI R5 B] 彼方的她

分析

大概就是一遍最短路，然后bfs的同时DP。

我也不想写了……

LGP7707 「Wdsr-2.7」百花齐放的太阳花田

原题链接：P7707 「Wdsr-2.7」百花齐放的太阳花田

分析

这是啥啊😭
思考离线怎么做……
发现，这个离线就是h i h_ihi排序之后开始扫描。然后对于一段区间我们用[ 1 , r ] − [ 1 , l − 1 ] [1,r]-[1,l-1][1,r]−[1,l−1]即为答案。
进一步发现，每一段产生的贡献相当于找到当前位置前一个小于等于它的，这个可以做单调栈。
又由于这个是可差分的，所以，放到主席树上直接做就行了。