AGC007 DEF 题解

First Post:

Last Update:

AGC007D

简单题，虽然对数轴上游走的题还是不太会。

一眼看出了状态，转移懒得编了（以后还是要编转移，现在编转移的能力有些弱）。

容易发现，路径一定是先往前走一段，再折回一段，再往前走，走了一段再折，再走。

说白了，一个点要么被经过一次，要么被经过三次。

那么设 表示收到前 个糖果的最小时间，此时人一定在 。

那么枚举位置 ， 中的点被一次折返收完，那么有转移

写出这个转移式子之后，优化非常简单，分类讨论那个 取到谁即可。因为 和 均不降，转移容易。

AGC007E

好题。

题意：给出一棵二叉树，每个节点只有 或 个儿子。

要求你从 走回 ，每天你可以从二叉树的一个叶子走到另一个叶子，或从 走到某个叶子，或从某个叶子走到 。要求你经过二叉树上的所有叶子，且每条边被经过恰好两次。

你的花费是最大的，从叶子到叶子的那一天经过的边的权值和，求最小花费。

。

首先二分答案，然后设 状态 表示从 开始游走，能否在第一天走过不超过 的距离，在第二天走过不超过 的距离。

那么有转移

交换 后再转移一遍即可。

当时只是觉得，这个转移形式有点双指针，然后想着能不能只记录一维，觉得挺假就没往下想了。

事实证明，确实需要双指针。

首先，对于同为 的状态 和 ，如果 ，那么后者完全无用。

所以你按 升序排序之后， 一定是降序的。

显然，对于每一个 都只需要考虑一个令 最小且满足转移式的 。所以，每一个 中的状态都只需要与一个对应的 转移到 中的唯一一个状态。所以，设左右子树的状态数分别为 ，那么一次转移只会增加最多 个状态（因为要把 交换后再转移一遍，所以要乘个 ）。

根据启发式合并的复杂度分析，总状态数是 的。

找到每个状态对应的状态可以使用双指针，总时间复杂度是 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 17) | 5;
typedef long long ll;
typedef pair<ll,ll> pll;
#define FI first
#define SE second
int n;
int son[N][2],w[N][2];

vector<pll> st[N]; // 状态集合
void DP(int x,ll mid)
{
	st[x].clear();
	if(!son[x][0]) {st[x].emplace_back(0,0);return;}
	DP(son[x][0],mid);DP(son[x][1],mid);
	ll tmp = mid - w[x][0] - w[x][1];
	vector<pll> vec;
	int num = 0;
	for(int d = 0;d < 2;d++)
	{
		int lc = son[x][d],rc = son[x][d ^ 1];
		for(int i = 0,j = 0;i < st[lc].size();i++)
		{
			while(j + 1 < st[rc].size() && st[rc][j + 1].FI + st[lc][i].SE <= tmp) ++j; //双指针
			if(j >= st[rc].size() || st[lc][i].SE + st[rc][j].FI > tmp) continue;
			vec.emplace_back(w[x][d] + st[lc][i].FI,w[x][d ^ 1] + st[rc][j].SE);
		}
		if(d == 0) num = vec.size();
	}
	inplace_merge(vec.begin(),vec.begin() + num,vec.end()); // 用归并来合并两个状态序列。用 sort 是 3 log 的。
	for(int i = 0;i < vec.size();i++) // 删去无用状态
	{
		if(st[x].size() && st[x].back().SE <= vec[i].SE) continue;
		st[x].push_back(vec[i]);
	}
}
inline bool Check(ll mid)
{
	DP(1,mid);
	return st[1].size() != 0;
}
int main()
{
	cin >> n;
	ll lef = 0,righ = 0;
	for(int i = 2;i <= n;i++)
	{
		int fa,v;
		cin >> fa >> v;righ += v;
		if(!son[fa][0]) son[fa][0] = i,w[fa][0] = v;
		else son[fa][1] = i,w[fa][1] = v;
	}
	while(lef < righ)
	{
		ll mid = lef + righ >>1;
		if(Check(mid)) righ = mid;
		else lef = mid + 1;
	}
	cout << lef << endl;
	return 0;
}

AGC007F

题意：

Shik 需要抄写一个字符串，一开始，纸面上有一个字符串 ，每次她写下字符串 的时候， 有可能与 相同，也可能与 相同。

Shik 希望抄写尽量少的字符串，就能使最后再纸上的字符串与 相同，具体地，她希望找到最小的整数 ，使得存在一种方案让 。

。

首先把图画出来， 中的一个字符肯定对应的是 中的一段区间。每个字符相当于在平面上向右或向下走。

当时的直觉是从后往前做，每个字符的匹配段都往右靠一定不劣，然后根据每个字符对应的区间设计 DP。

事实上，这样设计 DP 反倒会丢失路径信息。

考虑我们在不改变每个字符所对应区间的情况下，把中间走过的路径尽量往右靠，那么一定不劣。

而具体的策略就是：一直尽量右移，直到走到要覆盖的左边界，然后一直向下，最后横向覆盖。

有图如下（来自 @command_block）：

考虑从右往左，从一条折线变到另一条折线时的变化。

假设当前 要到达 （ 是区间左边界）

那么那些横坐标大于等于 的拐点要弹出。

然后，原来所有的拐点都会往左下方平移一格（因为新折线要尽量贴近原来的折线）。

最后，如果 ，那么在横坐标为 的地方会有一个拐点。

（上述所有拐点均不包括最后一行）。

我们可以用一个队列来维护拐点集合，队头是更加靠近目标串的，队尾是更加靠近 的。

上述操作都可以用队列维护。

核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
while(down)
{
	while(down > 1 && t[down - 1] == t[down]) --down;
	while(up >= 1 && (up > down || s[up] != t[down])) --up;
	if(!up) { puts("-1");return 0;}
	while(!Q.empty() && Q.front() - (int)Q.size() >= down) // 这里减去 Q.size 是因为，每加入一个拐点，已有的拐点都会往左下方平移一格，这是本题所维护的折线的性质。
		Q.pop();
	if(up != down) Q.push(up);
	ans = max(ans,(int)Q.size() + 1);
	--down;
}

答案是队列大小 +1 的历史最大值。

因为可以归纳证明，每条折线的拐点的横坐标都是连续的（即都位于连续的前几行）。

大致是说，这对于最右的折线显然成立，而其它的折线都会尽量往右靠。

一道思路比较清奇的题。

≡