至今头条

2024.02 别急记录

2024-02-06 10:30 由 KiharaTouma 发表于 #后端开发

1. WC/CTSC2024 - 水镜 [省选/NOI-]

设 \(2L=T\)，我们可以发现相邻两项之间的大小关系有四种：

  • \(h_i<h_{i+1}\)；
  • \(h_i<T-h_{i+1}\) 即 \(h_i+h_{i+1}<T\)；
  • \(T-h_i<T-h_{i+1}\) 即 \(h_i>h_{i+1}\)；
  • \(T-h_i<h_{i+1}\) 即 \(h_i+h_{i+1}>T\)。

那么由 1,2 可得若 \(h_i\geq h_{i+1},h_i+h_{i+1}\geq T\) 则一定会取 \(T-h_i\)。

类似地总共四条：

  • 若 \(h_i\geq h_{i+1},h_i+h_{i+1}\geq T\) 则一定会取 \(T-h_i\)；
  • 若 \(h_i\geq h_{i+1},h_i+h_{i+1}\leq T\) 则一定会取 \(T-h_{i+1}\)；
  • 若 \(h_i\leq h_{i+1},h_i+h_{i+1}\geq T\) 则一定会取 \(h_{i+1}\)；
  • 若 \(h_i\leq h_{i+1},h_i+h_{i+1}\leq T\) 则一定会取 \(h_i\)。

那么我们接着考虑 \(h_{i-1},h_i,h_{i+1}\) 三者的关系，可得若 \(h_{i-1},h_i\) 满足上述条件 2，\(h_i,h_{i+1}\) 满足上述条件 4，则 \(h_i\) 既要取 \(h_i\) 又要取 \(T-h_i\)，所以这个 \(T\) 对于 \(h_i\) 不可行。

那么我们就可以对于每个 \(i\) 求出 \((L_i,R_i)\) 表示区间里有这个 \(i\) 会对 \(T\) 产生的限制：

  • 若 \(h_i\geq\max(h_{i-1},h_{i+1}),T\geq \min(h_{i-1}, h_{i+1}) + h_i\)；
  • 若 \(h_i\leq\min(h_{i-1},h_{i+1}),T\leq \max(h_{i-1}, h_{i+1}) + h_i\)；

那么一个区间合法当且仅当 \(\max L_i < \min R_i\)。可以枚举左端点并二分右端点求解。

点击查看代码 
const int N = 5e5 + 10;
ll lw[20][N], up[20][N], h[N];
int n;

bool chk(int L, int R){
	if(L > R){
		return 1;
	}
	int k = 31 ^ __builtin_clz(R-L+1);
	ll Lm = max(lw[k][L], lw[k][R-(1<<k)+1]);
	ll Rm = min(up[k][L], up[k][R-(1<<k)+1]);
	return Lm < Rm;
}

void solve(){
	read(n);
	for(int i = 1; i <= n; ++ i){
		read(h[i]);
	}
	lw[0][1] = lw[0][n] = -1e18;
	up[0][1] = up[0][n] = 1e18;
	for(int i = 2; i < n; ++ i){
		lw[0][i] = -1e18;
		up[0][i] = 1e18;
		if(h[i-1] <= h[i] && h[i] >= h[i+1]){
			lw[0][i] = min(h[i-1], h[i+1]) + h[i];
		}
		if(h[i-1] >= h[i] && h[i] <= h[i+1]){
			up[0][i] = max(h[i-1], h[i+1]) + h[i];
		}
	}
	for(int i = 1; i < 20; ++ i){
		for(int j = 1; j + (1 << i) - 1 <= n; ++ j){
			lw[i][j] = max(lw[i-1][j], lw[i-1][j+(1<<i-1)]);
			up[i][j] = min(up[i-1][j], up[i-1][j+(1<<i-1)]);
		}
	}
	ll ans = 0;
	for(int i = 1; i <= n; ++ i){
		int l = i, r = n;
		while(l < r){
			int mid = l + r + 1 >> 1;
			if(chk(i + 1, mid - 1)){
				l = mid;
			} else {
				r = mid - 1;
			}
		}
		ans += l - i;
	}
	println(ans);
}

2. CTSC2017 - 吉夫特 [省选/NOI-]

简单题啊。

一个经典结论是 \(\dbinom nm \equiv [n\operatorname{AND} m=m]\pmod 2\)

proof

根据卢卡斯定理有 \(\dbinom nm\equiv \dbinom{n/p}{m/p}\dbinom{n\bmod p}{m\bmod p}\)。

然后我们观察到如果 \(n\) 最低位是 \(0\) 而 \(m\) 最低位是 \(1\)，那么这个就是 \(0\) 了。

否则这个不会变为 \(0\) 就是 \(1\)。

然后就能写出转移方程：\(f_i=\sum_{a_i\operatorname{AND}a_j=a_i}\{f_j+1\}\)，使用枚举子集即可 \(O(3^{\log V})\) 转移。

点击查看代码 
const int N = 262144 + 10;
const ll P = 1e9 + 7;
int n, a[N], p[N];
ll f[N], ans;

void solve(){
	read(n);
	memset(p, 0x3f, sizeof(p));
	for(int i = 1; i <= n; ++ i){
		read(a[i]);
		p[a[i]] = i;
	}
	for(int i = 0; i <= n; ++ i){
		int s = 262143 - a[i];
		for(int j = s; j > 0; j = (j - 1) & s){
			f[a[i]] = (f[a[i]] + (p[a[i]+j] < i ? f[a[i]+j]+1 : 0)) % P;
		}
		ans = (ans + f[a[i]]) % P;
	}
	println(ans);
}

3. CF1918G - Permutation of Given [*2700]

无聊构造题。

首先 \(n=3,5\) 是无解的。

proof 当 $n=3$ 时，设序列为 $\{a,b,c\}$，变化后为 $\{b,a+c,b\}$，显然二者总和不等，故无解。

当 \(n=5\) 时，设序列为 \(\{a,b,c,d,e\}\)，变化后为 \(\{b,a+c,b+d,c+e,d\}\)，\(b=b\)，\(d=d\)，\(a+c\neq a,c\) 只能 \(=e\)，\(c+e=a\)，所以 \(b+d=c\)；又二者总和相减得 \(b+c+d=0\)，所以 \(c=0\)，无解。

然后考虑一个合法的长度为 \(n-2\) 的序列，设其最后两项为 \(a,b\)，变化后的最后两项为 \(t,a\)。

那么若在序列末尾添加 \(x,y\)，则 \(\{a,b,x,y\}=\{t,a+x,b+y,x\}\)，解得可取 \(x=-b,y=a-b\)。

那么我们只用找到 \(n=2\) 和 \(n=7\) 时的解即可。

\(n=2\) 很好找：\(\{1,2\}\)。

\(n=7\) 打表可得 \(\{-3,-3,2,1,-1,1,-2\}\)。

点击查看代码 
const int N = 1e6 + 10;
int n, a[N];

void solve(){
	read(n);
	if(n == 3 || n == 5){
		println_cstr("NO");
	} else if(n & 1){
		println_cstr("YES");
		a[1] = a[2] = -3;
		a[3] = 2;
		a[4] = a[6] = 1;
		a[5] = -1;
		a[7] = -2;
		for(int i = 8; i <= n; i += 2){
			a[i] = - a[i-1];
			a[i+1] = a[i-2] - a[i-1];
		}
		for(int i = 1; i <= n; ++ i){
			printk(a[i]);
		}
	} else {
		println_cstr("YES");
		a[1] = 1;
		a[2] = 2;
		for(int i = 3; i <= n; i += 2){
			a[i] = - a[i-1];
			a[i+1] = a[i-2] - a[i-1];
		}
		for(int i = 1; i <= n; ++ i){
			printk(a[i]);
		}
	}
}

4. COCI2018-2019#4 - Akvizna [NOI/NOI+/CTSC]

wqs 二分+斜率优化。

首先考虑如果没有 \(k\) 的限制该怎么做：倒着做，设 \(f_i\) 表示赢后 \(i\) 个选手的最多奖金，有转移：

\(f_i=\max\{f_j+\dfrac{i-j}j\}=\max\{\dfrac 1i * j + f_j - 1\}\)

可以斜率优化。具体地，用单调队列维护 \((j,f_j-1)\) 的上凸壳，斜线斜率是 \(\dfrac 1i\) 由大到小，故凸壳斜率递减。

然后加上 \(k\) 的限制就是 wqs 二分。二分斜率 \(k_0\)，用这条直线去切答案下凸壳，切到的点是 \((k,f_{n,k})\) 即可取答案。二分后的答案应尽量大，所以当可行时 \(mid\to l\)。

点击查看代码 
const int N = 1e5 + 10;
const double eps = 1e-16;
int n, k, q[N], g[N];
double f[N];

double slp(int x, int y){
	return (f[x] - f[y]) * 1.0 / (x - y);
}

bool chk(double x){
	int l = 1, r = 0;
	q[1] = 0;
	memset(g, 0, sizeof(g));
	for(int i = 1; i <= n; ++ i){
		while(l < r && slp(q[l+1], q[l]) > 1.0 / i + eps){
			++ l;
		}
		f[i] = f[q[l]] + (i - q[l]) * 1.0 / i - x;
		g[i] = g[q[l]] + 1;
		while(l < r && slp(q[r], q[r-1]) + eps < slp(i, q[r])){
			-- r;
		}
		q[++r] = i;
	}
	return g[n] >= k;
}

void solve(){
	scanf("%d%d", &n, &k);
	double l = 0, r = 1e6;
	while(l + eps < r){
		double mid = (l + r) / 2;
		if(chk(mid)){
			l = mid;
		} else {
			r = mid;
		}
	}
	printf("%.9lf\n", f[n] + l * k);
}

5. LuoguP5633 - 最小度限制生成树 [省选/NOI-]

wqs 二分。

考虑给每条连接到 \(s\) 的边 \(-x\)，然后二分最小生成树中 \(s\) 度数 \(\geq k\) 的最小 \(x\)。

无解情况：\(s\) 本身度数 \(<k\)；图不连通；\(x=-inf\) 时度数仍 \(>k\)。

点击查看代码 
const int N = 1e5 + 10, M = 5e5 + 10;
int n, m, s, k, deg, fa[N], tx, ty;
ll res;
struct edge{
	int u, v, w;
} e[M], E[M];
bool cmp(edge x, edge y){
	return x.w < y.w;
}
int gf(int x){
	return x == fa[x] ? x : fa[x] = gf(fa[x]);
}

int chk(int x){
	for(int i = 1; i <= n; ++ i){
		fa[i] = i;
	}
	ll ans = 0, cnt = 0, i = 1, j = 1;
	while(i <= tx || j <= ty){
		if(i <= tx && (e[i].w < E[j].w - x || j > ty)){
			if(gf(e[i].u) != gf(e[i].v)){
				fa[gf(e[i].u)] = gf(e[i].v);
				ans += e[i].w;
			}
			++ i;
		} else {
			if(gf(E[j].u) != gf(E[j].v)){
				fa[gf(E[j].u)] = gf(E[j].v);
				ans += E[j].w - x;
				++ cnt;
			}
			++ j;
		}
	}
	res = ans;
	return cnt;
}

void solve(){
	read(n, m, s, k);
	for(int i = 1; i <= n; ++ i){
		fa[i] = i;
	}
	for(int i = 1; i <= m; ++ i){
		int u, v, w;
		read(u, v, w);
		fa[gf(u)] = gf(v);
		if(u == s || v == s){
			++ deg;
			E[++ty] = { u, v, w };
		} else {
			e[++tx] = { u, v, w };
		}
	}
	sort(e + 1, e + tx + 1, cmp);
	sort(E + 1, E + ty + 1, cmp);
	int cnt = 0;
	for(int i = 1; i <= n; ++ i){
		if(gf(i) == i){
			++ cnt;
		}
	}
	if(deg < k || cnt > 1 || chk(-1e5) > k){
		println_cstr("Impossible");
		return;
	}
	int l = -1e5, r = 1e5;
	while(l < r){
		int mid = l + r >> 1;
		if(chk(mid) >= k){
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	chk(l);
	println(res + k * l);
}

6. POI2014 - PAN-Solar Panels [提高+/省选-]

显然可以四维数论分块。

但是发现对于 \(\lfloor\dfrac bx\rfloor,\lfloor\dfrac dx\rfloor\) 相同的 \(x\in[l,r]\)，\(x=r\) 一定是其中最优的。于是可以二维数论分块解决。

点击查看代码 
int T, a, b, c, d;

void solve(){
	read(T);
	while(T--){
		read(a, b, c, d);
		if(b > d){
			swap(a, c);
			swap(b, d);
		}
		int ans = 0;
		for(int l = 1, r; l <= b; l = r + 1){
			r = min(b / (b / l), d / (d / l));
			if((a-1) / r < b / r && (c-1) / r < d / r){
				ans = max(ans, r);
			}
		}
		println(ans);
	}
}

7. Ynoi ER 2021 - TEST_152 [省选/NOI-]

考虑从左往右执行操作的同时使用树状数组记录：第 \(i\) 位记录最后一次操作是操作 \(i\) 的所有位置的值之和。然后把询问离线并绑定到右端点，执行完操作 \(r\) 后询问 \([l,r]\) 的答案即为树状数组的 \([l,r]\) 之和。

接着考虑如何快速操作：使用 set 维护序列连续段及其值、最后修改的时间，然后每次修改找到那些与之有交的序列段进行修改。可以发现每次至多增加两段，故总段数是 \(O(n)\) 的。注意找序列段的实现。

复杂度 \(O(n\log n)\)。

点击查看代码 
const int N = 5e5 + 10;
int n, m, q, L[N], R[N], v[N];
vector<pair<int, int> > qr[N];
tuple<int, int, int> seq[N];
ll bit[N], ans[N];

void add(int x, ll v){
	++ x;
	while(x <= n + 1){
		bit[x] += v;
		x += x & -x;
	}
}
ll ask(int x){
	++ x;
	ll rs = 0;
	while(x){
		rs += bit[x];
		x -= x & -x;
	}
	return rs;
}
ll ask(int l, int r){
	return ask(r) - ask(l-1);
}

void solve(){
	read(n, m, q);
	for(int i = 1; i <= n; ++ i){
		read(L[i], R[i], v[i]);
	}
	for(int i = 1; i <= q; ++ i){
		int l, r;
		read(l, r);
		qr[r].emplace_back(l, i);
	}
	set<int> st;
	st.insert(1);
	seq[1] = { n, 0, 0 };
	for(int i = 1; i <= n; ++ i){
		while(true){
			auto it = st.upper_bound(R[i]);
			if(it == st.begin()){
				break;
			}
			-- it;
			int l = (*it), r, cl, vl;
			tie(r, cl, vl) = seq[l];
			if(L[i] <= l && r <= R[i]){
				add(cl, -(ll)vl * (r-l+1));
				st.erase(it);
			} else if(L[i] <= l && R[i] < r && l <= R[i]){
				add(cl, -(ll)vl * (R[i]-l+1));
				st.erase(it);
				st.insert(R[i]+1);
				seq[R[i]+1] = { r, cl, vl };
			} else if(l < L[i] && r <= R[i] && L[i] <= r){
				add(cl, -(ll)vl * (r-L[i]+1));
				seq[l] = { L[i]-1, cl, vl };
				break;
			} else if(l < L[i] && R[i] < r){
				add(cl, -(ll)vl * (R[i]-L[i]+1));
				seq[l] = { L[i]-1, cl, vl };
				st.insert(R[i]+1);
				seq[R[i]+1] = {r, cl, vl};
				break;
			} else {
				break;
			}
		}
		st.insert(L[i]);
		seq[L[i]] = { R[i], i, v[i] };
		add(i, (ll)v[i] * (R[i]-L[i]+1));
		for(auto j : qr[i]){
			ans[j.second] = ask(j.first, i);
		}
	}
	for(int i = 1; i <= q; ++ i){
		println(ans[i]);
	}
}

8. CF627F - Island Puzzle [*3400]

思路不难的逆天角盒题！

首先考虑不加边的情况，容易发现将 \(0\) 的位置由起始一步一步移动到目标是唯一的操作方法。那么就先这样进行一下操作，如果已经完成目标就是不用加边的最短步骤；否则一定需要加边。

那么将 \(0\) 放对位置后，还剩下若干 \(a\neq b\) 的位置。我们可以发现 \(0\) 在环上绕圈相当于其他位置进行一个轮换。那么求出这些点的 lca \(p\)。若 \(p\) 与这些点构成一条链，那么就要把链加一条边连成环；否则无解。然后如果环上除掉 \(p\) 以外的点 \(a,b\) 不构成轮换，无解；否则，步骤为 \(0\) 初始位置 \(\to 0\) 目标位置 \(\to p\)，然后顺时针或逆时针绕圈，最后返回 \(0\) 目标位置。

但是，有可能有的路径可以省去！比如 \(p\) 在 \(0\) 初始位置 \(\to 0\) 目标位置上，就不用先到 \(0\) 目标位置，而是直接去绕圈。这个对于顺时针和逆时针两种情况分别判一下，因为第一圈的某些步一样可以省去，最后取最小值即可。

点击查看代码 
const int N = 2e5 + 10;
int n, a[N], b[N], a0, b0;
vector<int> g[N];

int st[N], tp;
bool dfs1(int x, int fa){
	st[++tp] = x;
	if(x == b0){
		return 1;
	}
	for(int i : g[x]){
		if(i != fa){
			if(dfs1(i, x)){
				return 1;
			}
		}
	}
	-- tp;
	return 0;
}

int nd[N], dep[N], fat[N], ind[N];
void dfs2(int x, int fa){
	fat[x] = fa;
	dep[x] = dep[fa] + 1;
	for(int i : g[x]){
		if(i != fa){
			dfs2(i, x);
		}
	}
}

int stt[N], tpp, as[N], bs[N], so[N];
bool dfs3(int x, int fa, int gl){
	stt[++tpp] = x;
	if(x == gl){
		return 1;
	}
	for(int i : g[x]){
		if(i != fa && nd[i]){
			if(dfs3(i, x, gl)){
				return 1;
			}
		}
	}
	-- tpp;
	return 0;
}

void solve(){
	read(n);
	for(int i = 1; i <= n; ++ i){
		read(a[i]);
		if(a[i] == 0){
			a0 = i;
		}
	}
	for(int i = 1; i <= n; ++ i){
		read(b[i]);
		if(b[i] == 0){
			b0 = i;
		}
	}
	for(int i = 1; i < n; ++ i){
		int u, v;
		read(u, v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	dfs1(a0, 0);
	for(int i = 1; i < tp; ++ i){
		swap(a[st[i]], a[st[i+1]]);
	}
	bool flg = 1;
	for(int i = 1; i <= n; ++ i){
		if(a[i] != b[i]){
			flg = 0;
			break;
		}
	}
	if(flg){
		println(0, tp - 1);
		return;
	}
	
	dfs2(b0, 0);
	int p = 0;
	bool ok = 1;
	for(int i = 1; i <= n; ++ i){
		if(a[i] != b[i]){
			nd[i] = 1;
		}
	}
	for(int i = 1; i <= n; ++ i){
		if(nd[i]){
			if(!p || dep[p] >= dep[i]){
				p = fat[i];
			}
		}
	}
	
	nd[p] = 1;
	for(int i = 1; i <= n; ++ i){
		for(int j : g[i]){
			if(i < j && nd[i] && nd[j]){
				++ ind[i];
				++ ind[j];
			}
		}
	}
	int c = 0;
	for(int i = 1; i <= n; ++ i){
		if(ind[i] == 1){
			++ c;
		} else if(nd[i] && ind[i] != 2){
			ok = 0;
			break;
		}
	}
	if(c != 2){
		ok = 0;
	}
	if(!ok){
		println(-1);
		return;
	}
	
	int u = 0, v = 0;
	for(int i = 1; i <= n; ++ i){
		if(ind[i] == 1){
			if(u){
				v = i;
			} else {
				u = i;
			}
		}
	}
	dfs3(u, 0, v);
	int psp = 0;
	for(int i = 1, q = 0; i <= tpp; ++ i){
		if(stt[i] != p){
			as[++q] = a[stt[i]];
			bs[q] = b[stt[i]];
		} else {
			psp = i;
		}
	}
	int dy = 0;
	for(int i = 1; i < tpp; ++ i){
		if(as[1] == bs[i]){
			dy = i;
			for(int j = 1, k = i; j < tpp; ++ j, ++ k){
				if(k == tpp){
					k = 1;
				}
				if(as[j] != bs[k]){
					ok = 0;
					break;
				}
			}
			break;
		}
	}
	if(dy == 0){
		ok = 0;
	}
	if(!ok){
		println(-1);
		return;
	}
	
	int tmp = p;
	while(tmp != b0){
		so[fat[tmp]] = tmp;
		tmp = fat[tmp];
	}
	ll ac = 2, rc = 2;
	ac += tp - 1 + (dep[p] - 1) * 2;
	rc += tp - 1 + (dep[p] - 1) * 2;
	ac += (dy - 1) * 1ll * tpp;
	rc += (tpp - dy) * 1ll * tpp;
	
	int np = b0, nq = b0, fl = tp, pr = 0;
	while(true){
		if(np == nq){
			-- rc;
			-- rc;
		}
		if(np == a0 || nq == stt[tpp]){
			break;
		}
		-- fl;
		np = st[fl];
		if(nq == p){
			pr = psp;
		}
		if(!pr){
			nq = so[nq];
		} else {
			++ pr;
			nq = stt[pr];
		}
	}
	np = b0, nq = b0, fl = tp, pr = 0;
	while(true){
		if(np == nq){
			-- ac;
			-- ac;
		}
		if(np == a0 || nq == stt[1]){
			break;
		}
		-- fl;
		np = st[fl];
		if(nq == p){
			pr = psp;
		}
		if(!pr){
			nq = so[nq];
		} else {
			-- pr;
			nq = stt[pr];
		}
	}
	
	println(u, v, min(ac, rc));
}

9. COCI2021-2022#2 - Osumnjičeni [省选/NOI-]

双指针+线段树可以求出对于每个人，最右边能选到哪个人。然后倍增即可。

点击查看代码 
const int N = 2e5 + 10, M = 4e5 + 10;
int n, q, l[N], r[N], pl[M], tp, t[M*4], tag[M*4], f[N][20];

void psd(int p){
	if(tag[p] == -1){
		return;
	}
	t[p<<1] = t[p<<1|1] = tag[p<<1] = tag[p<<1|1] = exchange(tag[p], -1);
}
void add(int p, int l, int r, int ql, int qr, int v){
	if(qr < l || r < ql){
		return;
	} else if(ql <= l && r <= qr){
		t[p] = tag[p] = v;
	} else {
		int mid = l + r >> 1;
		psd(p);
		add(p<<1, l, mid, ql, qr, v);
		add(p<<1|1, mid+1, r, ql, qr, v);
		t[p] = max(t[p<<1], t[p<<1|1]);
	}
}
int qry(int p, int l, int r, int ql, int qr){
	if(qr < l || r < ql){
		return 0;
	} else if(ql <= l && r <= qr){
		return t[p];
	} else {
		int mid = l + r >> 1;
		psd(p);
		return max(qry(p<<1, l, mid, ql, qr), qry(p<<1|1, mid+1, r, ql, qr));
	}
}

void solve(){
	read(n);
	memset(tag, -1, sizeof(tag));
	for(int i = 1; i <= n; ++ i){
		read(l[i], r[i]);
		pl[++tp] = l[i];
		pl[++tp] = r[i];
	}
	sort(pl + 1, pl + tp + 1);
	tp = unique(pl + 1, pl + tp + 1) - pl - 1;
	for(int i = 1; i <= n; ++ i){
		l[i] = lower_bound(pl + 1, pl + tp + 1, l[i]) - pl;
		r[i] = lower_bound(pl + 1, pl + tp + 1, r[i]) - pl;
	}
	int L = 1, R = 0;
	while(R < n && qry(1, 1, tp, l[R+1], r[R+1]) == 0){
		add(1, 1, tp, l[R+1], r[R+1], 1);
		++ R;
	}
	f[1][0] = R + 1;
	for(L = 2; L <= n; ++ L){
		add(1, 1, tp, l[L-1], r[L-1], 0);
		while(R < n && qry(1, 1, tp, l[R+1], r[R+1]) == 0){
			add(1, 1, tp, l[R+1], r[R+1], 1);
			++ R;
		}
		f[L][0] = R + 1;
	}
	f[n+1][0] = n + 1;
	for(int i = 1; i < 20; ++ i){
		for(int j = 1; j <= n + 1; ++ j){
			f[j][i] = f[f[j][i-1]][i-1];
		}
	}
	read(q);
	while(q--){
		int x, y, ans = 0;
		read(x, y);
		for(int i = 19; i >= 0; -- i){
			if(f[x][i] <= y){
				ans += (1 << i);
				x = f[x][i];
			}
		}
		println(ans + 1);
	}
}

10. BJOI2014 - 想法 [省选/NOI-]

非常厉害！

发现直接做不好做。我们考虑给每个 \([1,m]\) 之间的点附一个随机权值，然后求每个点所能到达的最小权值，设其为 \(s\)，则 \(s\) 的期望为 \(\dfrac{RAND\_MAX}{k+1}\)，其中 \(k\) 为所能到达点的数量。那么我们就可以多跑几次来估计出 \(k\)。

点击查看代码 
const int N = 2e6 + 10, T = 100;
int c[N][2], f[N][T], n, m;
double ans[N];

void solve(){
	read(n, m);
	for(int i = m + 1; i <= n; ++ i){
		read(c[i][0], c[i][1]);
	}
	for(int p = 0; p <= 2; ++ p){
		for(int i = 1; i <= m; ++ i){
			for(int j = 0; j < T; ++ j){
				f[i][j] = rand();
			}
		}
		for(int i = m + 1; i <= n; ++ i){
			for(int j = 0; j < T; ++ j){
				f[i][j] = min(f[c[i][0]][j], f[c[i][1]][j]);
				ans[i] += f[i][j];
			}
		}
	}
	for(int i = m + 1; i <= n; ++ i){
		println((int)(RAND_MAX / ans[i] * T * 3 - 0.5));
	}
}

热门相关：庶子风流   懒散初唐   走私大明   万古第一帝   虎狼之师