ToB企服应用市场:ToB评测及商务社交产业平台

标题: CF1943C Tree Compass [打印本页]

作者: 勿忘初心做自己 时间: 2024-8-13 22:18
标题: CF1943C Tree Compass
思路：

考虑往直径方向想，设直径的长度为 \(d\)。
首先可以留意到一个性质：

每次操作最多只会覆盖住直径的 \(2\) 个点，那么答案的下界即为 \(\lceil \frac{d}{2} \rceil\)。

分类讨论一下。
若 \(d\) 为奇数，则存在唯一的一个直径中心 \(u\)：

那么答案为 \((u,0),(u,1),\cdots,(u,\lceil \frac{d-1}{2} \rceil)\)。
最优次数是 \(\lceil \frac{d}{2} \rceil\) 次。

若 \(d\) 为偶数，则存在两个直径中心 \(u,v\)：

若 \(d \bmod 4 = 0\) 时：
- 那么答案为 \((u,1),(v,1),(u,3),(v,3),\cdots,(u,\frac{d}{2}-1),(v,\frac{d}{2}-1)\)。
- 最优次数是 \(\frac{d}{2}\)。
- 如许是两者是完全错开的。
若 \(d \bmod 4 = 2\) 时：
- 那么答案为 \((u,0),(u,1),\cdots,(u,\frac{2}{d})\)。
- 最优次数是 \(\frac{d}{2}+1\)。

这里证明一下为什么当 \(d \bmod 4 = 0\) 时不能取到答案的下界。
留意到若 \(x,y\) 能被同时取到当且仅当 \(\operatorname{dis}(x,y)\) 为偶数。
设 \(L\) 为直径的一个端点，那么 \(\operatorname{dis}(L,x)+\operatorname{dis}(L,y)\) 的奇偶性等价于 \(2*(奇数/偶数)+偶数=偶数\)。
由于 \(d \bmod 4 = 2\)，所以 \(\sum \operatorname{dis}(L,i) = \frac{d \times (d-1)}{2} \bmod 4 = 1\)，则这个和式一定不是偶数，故无法到达下界。

时间复杂度为 \(O(TN)\)。
完备代码：

[code]#include#define Add(x,y) (x+y>=mod)?(x+y-mod)

x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=2e3+10;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)