HZOJ NOIP2025模拟7
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | 100 | - | - | 200 | 6/27 |
别笑，你来你也只能过第二关。
—— Dyk
A. Imbalance
理论上是2025CSP-S模拟赛57 C 的原，但完全忘了。
对于双 \(\log\) 做法，路径计数考虑点分治，对于当前子树的两条根链，相当于要满足一个二维偏序，容斥+二维数点即可。理论 \(70pts\)，实则 \(100pts\)（
考虑如果在链上怎么做，建出小根笛卡尔树和大根笛卡尔树，相当于要求两个点在两棵树上分别满足「祖先-后代」/「后代-祖先」关系，在一棵树上跑出 dfn，再在另一棵树上用树状数组数点即可。
而如果在树上，那建 kruskal 重构树即可。
放个点分治代码吧实则是懒得写重构树
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
#define pii pair<int,int>
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace asbt{
namespace IO{const int bufsz=1<<20;char ibuf[bufsz],*p1=ibuf,*p2=ibuf;#define getchar() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,bufsz,stdin),p1==p2)?EOF:*p1++)il int read(){char ch=getchar();while(ch<'0'||ch>'9'){ch=getchar();}int x=0;while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x;}#undef getchar
}
using IO::read;
const int maxn=5e5+5;
int n,rt,tot,sz[maxn],mxs[maxn],cmx,cmn;
ll ans;
bool ban[maxn];
pii vmx[maxn],vmn[maxn];
vector<int> e[maxn];
il void dfs1(int u,int fa){sz[u]=1,mxs[u]=0;for(int v:e[u]){if(v==fa||ban[v]){continue;}dfs1(v,u);sz[u]+=sz[v];mxs[u]=max(mxs[u],sz[v]);}if(!rt||max(mxs[u],tot-sz[u])<max(mxs[rt],tot-sz[rt])){rt=u;}
}
il void dfs2(int u,int fa,int mx,int mn){if(u>mx){mx=u;vmx[++cmx]=mp(mx,mn);}if(u<mn){mn=u;vmn[++cmn]=mp(mx,mn);}for(int v:e[u]){if(v==fa||ban[v]){continue;}dfs2(v,u,mx,mn);}
}
struct{#define lowbit(x) (x&-x)int tr[maxn];il void add(int p){for(;p<=n;p+=lowbit(p)){tr[p]++;}}il int query(int p){int res=0;for(;p;p-=lowbit(p)){res+=tr[p];}return res;}il void clear(int p){for(;p<=n;p+=lowbit(p)){tr[p]=0;}}#undef lowbit
}F;
il void solve(int u){
// cout<<u<<' ';rt=0,dfs1(u,0),u=rt,dfs1(u,0);
// cout<<u<<' '<<ans<<' ';ban[u]=1,cmx=cmn=0;for(int v:e[u]){if(ban[v]){continue;}int smx=cmx+1,smn=cmn+1;dfs2(v,0,u,u);int tmx=cmx,tmn=cmn;sort(vmx+smx,vmx+tmx+1);sort(vmn+smn,vmn+tmn+1);int p=smn;for(int i=smx;i<=tmx;i++){while(p<=tmn&&vmn[p].fir<vmx[i].fir){F.add(vmn[p++].sec);}ans-=F.query(vmx[i].sec-1);}for(int i=smn;i<=tmn;i++){F.clear(vmn[i].sec);}}int tmx=cmx,tmn=cmn;sort(vmx+1,vmx+tmx+1);sort(vmn+1,vmn+tmn+1);int p=1;for(int i=1;i<=tmx;i++){if(vmx[i].sec==u){ans++;}while(p<=tmn&&vmn[p].fir<vmx[i].fir){F.add(vmn[p++].sec);}ans+=F.query(vmx[i].sec-1);}for(int i=1;i<=tmn;i++){if(vmn[i].fir==u){ans++;}F.clear(vmn[i].sec);}
// cout<<ans<<'\n';for(int v:e[u]){if(!ban[v]){tot=sz[v],solve(v);}}
}
int main(){freopen("imbalance.in","r",stdin);freopen("imbalance.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0);n=read();for(int i=1,u,v;i<n;i++){u=read(),v=read();e[u].pb(v),e[v].pb(u);}tot=n,solve(1);cout<<ans;return 0;
}
}
int main(){return asbt::main();}
B. 原子
一个合法构造是，枚举步长，再枚举步长的剩余系作为开头，一直跳到不能跳为止。此时的答案为 \(\lfloor\frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil\)，考虑证明。
显然若 \([a,b)\cap[c,d)\ne\varnothing\)，则不可能在一轮内解决。
考虑找出一堆两两有非空交的区间，设它们组成集合 \(S\)，最大化 \(|S|\)。显然 \(S=\{[l,r)\mid l\le a,r\ge b,a<b\}\)。于是 \(|S|_{\max}=\lfloor\frac{n}{2}\rfloor\cdot\lceil\frac{n}{2}\rceil\)。于是答案至少为这个值。于是构造正确。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=2e3+5;
int n;
struct node{int s,d;
};
vector<node> ans;
int main(){freopen("atom.in","r",stdin);freopen("atom.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0);cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){if(j+i>n){break;}ans.pb((node){j,i});}}cout<<ans.size()<<'\n';for(node x:ans){int s=x.s,d=x.d;cout<<(n-s)/d+(s>1)<<' ';if(s>1){cout<<s-1<<' ';}while(s+d<=n){cout<<d<<' ';s+=d;}cout<<'\n';}return 0;
}
}
int main(){return asbt::main();}
C. 旅行计划
考虑树形 DP，在路径的 LCA 处对答案进行贡献。
设 LCA 为 \(u\)，考虑路径的形态，必然是从 \(u\) 的子树中的某个点 \(v\) 开始走到 \(u\)，然后在子树内绕一大圈，再走到 \(u\) 子树内的某个点 \(v'\)。
于是设 \(f_{u,0/1/2}\)：
- \(f_{u,0}\)：从 \(u\) 开始走出去的一条链的最大长度。
- \(f_{u,1}\)：从 \(u\) 开始走一圈回到 \(u\) 的最大长度。
- \(f_{u,2}\)：以 \(u\) 为 LCA 的最长路径。
于是对于 \(u\) 的每个儿子，我们可以转移：
\[w>1:f_{u,1}\gets f_{v,1}+\lfloor\frac{w}{2}\rfloor\\
f_{u,0/2}\gets f_{u,1}\\[3mm]
f_{u,0/2}\gets\begin{cases}
\begin{aligned}
&f_{v,0}+\lfloor\frac{w-1}{2}\rfloor+1&w>1\\
&f_{v,0}+1&w=1
\end{aligned}
\end{cases}
\]
但这样并没有转移完整。考虑从起点 \(x\) 开始走，走到它的某个祖先 \(v\)（注意不是 \(u\)，而是它的某个后代），再一直往上走到 \(u\)，再走回到 \(v\)，最后走到 \(v\) 子树中的某个点 \(x'\)。这样 LCA 也是 \(u\)，但上面的转移并未考虑到。于是还有转移：
\[w>1:f_{u,2}\gets f_{v,2}+(f_{u,1}-f_{v,1})
\]
答案即为 \(\max\limits_{u=1}^{n}\{f_{u,2}\}\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
#define fir first
#define sec second
#define pii pair<int,int>
#define mp make_pair
using namespace std;
namespace asbt{
const int maxn=1e6+5;
int T,n;
ll f[maxn][3],ans;
vector<pii> e[maxn];
il void dfs(int u,int fa){f[u][0]=f[u][1]=f[u][2]=0;ll mx1=0,mx2=0;for(pii i:e[u]){int v=i.fir,w=i.sec;if(v==fa){continue;}dfs(v,u);if(w>1){f[u][1]+=f[v][1]+w/2*2;ll x=f[v][0]-f[v][1]+(w&1?1:-1);if(x>mx1){mx2=mx1,mx1=x;}else if(x>mx2){mx2=x;}}else{ll x=f[v][0]+1;if(x>mx1){mx2=mx1,mx1=x;}else if(x>mx2){mx2=x;}}}f[u][0]=f[u][1]+mx1,f[u][2]=f[u][0]+mx2;for(pii i:e[u]){int v=i.fir,w=i.sec;if(v==fa){continue;}if(w>1){f[u][2]=max(f[u][2],f[v][2]+f[u][1]-f[v][1]);}}ans=max(ans,f[u][2]);
}
il void solve(){cin>>n;for(int i=1,u,v,w;i<n;i++){cin>>u>>v>>w;e[u].pb(mp(v,w));e[v].pb(mp(u,w));}ans=0,dfs(1,0);cout<<ans<<'\n';for(int i=1;i<=n;i++){e[i].clear();}
}
int main(){freopen("plan.in","r",stdin);freopen("plan.out","w",stdout);ios::sync_with_stdio(0),cin.tie(0);cin>>T;while(T--){solve();}return 0;
}
}
int main(){return asbt::main();}