AGC029 解题记录

### A Irreversible operation
签到题，直接$for$一遍就好了

### B Powers of two
题意：给$n$个数字，要两两配对凑成和为$2^i$的数对，问最多凑多少个。

题解：感觉上排个序从大往小匹配卡不掉，也不会证。被自己菜到了。看看题解，发现是因为对于$x+y=2^i,x<y$，那么$y\le 2^i\le 2y$。因此符合条件的$x$只有一个，所以整个是个树形结构。

### C Lexicographic constraints
题意：你要构造一个由$N$个字符串组成的序列$S$，满足$S_i$长度为给定的$l_i$，且$S_i$字典序总是小于$S_{i+1}$，问字符集最小是多大。
题解：
我们考虑贪心策略的本质，显然如果$l_i > l_{i-1}$那么直接往后加字符$'a'$即可，如果$l_i \le l_{i-1}$。相当于：
1、$S_i=S_{i-1}$ 2、删除$(l_{i-1},l_i]$段 3、将末尾字符的字典序$+1$。
发现如果字符集$\alpha$大小一定，本质上就是在做稀奇古怪的$\alpha$进制加法。
那么我们二分$\alpha$，维护位数验证即可。
但是$a_i\in [1,10^9]$
一种想法是线段树，但是注意到$Atcoder$的题目都很小清新的。
我们可以只取前$100$位，因为后面的操作即使是在$\alpha=2$的情况下也不可能对验证答案产生影响。

### D Grid game

题意：有$H\times W$网格，网格上有$N$个障碍物。初始有一枚棋子在$(1,1)$。现在$A$和$B$轮流操作棋子，$A$先操作，$A$只能选择将棋子下移或者不动。$B$只能选择将棋子右移或不动。当一轮下来两个人都不动的时候，游戏结束。$A$想让回合数尽量多，$B$想让回合数尽量少，问最后会走多少轮。

题解：
那么意思就是$A$每一轮必须走，$B$可以自由发挥
我们枚举$B$在哪一列停就行了
模拟走动，中途查查后继，用个$set$就行

### E Wandering TKHS

题意：一棵带标号的树，你一开始在$x$，每一步进行如下操作：在与已经到达过的点相邻的点中标号最小的那个，并瞬移到该点。对于$x\in [1,n]$输出第一次到达$1$点的步数。
$n\le 2\times 10^5$

题解：容易发现如果存在$u$标号大于子树内所有节点，那么每个儿子所在的子树一定在内部走完。一开始想法是从大到小加入点，并且增量路径，加入点$u$的时候考虑更新点$u$子树下的所有路径到$u$，这样可以用$dfs$序加线段树维护。写了一下，写跪了。也不知道对不对。
不过进一步观察性(ti)质(jie)可以发现，实际上答案和每个点到根的最大值所在的点有关，设为$m_u$。(想象一下，路径一定被这些点分成不同的块)。具体来说，如果$u$是某个$m_x$，那么$u$的任意一个儿子$v$中的点要到$u$，都需要经过$v$子树内$m_i=u$的所有点$i$。那么可以用差分来做。
这里要考虑的只有这样的情况：从一个子树上到$u$，但是被$m_{fa_u}$挡住了，只能再下到其它子树中。
考虑一个点$v$到$m_v$以下的最大值$x$，设想如果$x<m_{fa_{m_v}}$，这个时候就会被$m_{fa_{m_v}}$挡住，下到$v$来。
那么我们只需要在这种情况下把贡献加到$m_v$，一般的情况把贡献加到点$v$到$m_v$以下的第一个点就可以了。
```
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 5;
struct edge {
	int v, next;
} e[maxn << 1];
int head[maxn], cnt, n, u, v, dt[maxn];
void adde(const int &u, const int &v) {
	e[++cnt] = (edge) {v, head[u]};
	head[u] = cnt;
}

int stk[maxn], pre[maxn], top;

void dfs(int u, int p, int mxp, int s) {
	stk[++top] = u, pre[top] = max(pre[top - 1], u);
	int ch = stk[mxp];
	if (mxp < top) {
		ch = stk[mxp + 1];
		if (pre[mxp - 1] > s) {
			ch = stk[mxp];
		}
	}
	//printf("#%d\n", s);
	++dt[ch];
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(v == p) continue;
		if(stk[mxp] > v) dfs(v, u, mxp, max(v, s));
		else dfs(v, u, top + 1, 0);
	}
	--top;
}

void dfs2(int u, int p) {
	for(register int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if(v == p) continue;
		dt[v] += dt[u];
		dfs2(v, u);
	}
}

int main() {
	scanf("%d", &n);
	for(register int i = 1; i < n; ++i)
		scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
	dt[1] = -1, dfs(1, 0, 1, 0);
	dfs2(1, 0);
	for(register int i = 2; i <= n; ++i)
		printf("%d ", dt[i]);
	return 0;
}
```

### F Construction of a tree
膜一膜题解Orz
有人曾经告诉我$2\times 10^5$的网络流跑不过？？？？
实际上就是网络流……
做法很神奇。
考虑一个有根树，如果我们定了根其它的点就有了父亲。
考虑找到一组点和点集的最大匹配，然后开始构造。
把没有被匹配到的点$x$看作根，
用一个队列，开始时只有元素$1$。
每次取出队首元素，看看在哪些集合中有
把匹配到这个集合的点全部入队，
并把父亲设为队首，
弹出队首元素。
我们可以充(gan)分(xing)证(li)明(jie)这个做法的正确性。

Rockdu's Blog

导航

最近发表

大佬们的友链