USACO 2018 February Gold 题解

发表于 更新于 阅读次数： 本文字数： 5.9k 阅读时长 ≈ 5 分钟

概述

上次一月因为准备期末考试太忙而放弃，到了二月里的寒假就有时间做金组了。这次在我看来有两题数据结构，然而题解并非如此。我感觉比前几个月的金组简单多了。

此前的2017年十二月的月赛我从铜组升到金组，题解以后有兴趣考虑吧。

Snow Boots

大意

一条路上有$N$个格子编号$1 \dots N$，第$i$格有一定的深度的雪$f_i$，$1$和$N$都没有雪。有$B$双鞋，穿每双鞋最多能在$s_i$的雪中，每步最多走$d_i$格，求每双鞋是否能从$1$走到$N$。$1\le N,B\le 100,000$

样例
snowboots.in
1
2
3
4
5
6
7
8
9
8 7
0 3 8 5 6 9 0 0
0 5
0 6
6 2
8 1
10 1
5 3
150 7
snowboots.out
1
2
3
4
5
6
7
0
1
1
0
1
1
1

洛谷P4269 官方提交 官方题解

思路

可以每次$\mathcal O(N)$判断是否可行，复杂度$\mathcal O(BN)$。

考虑离线处理，将询问按照$s_i$排序，按照深度依次加入格子，用一个std::set维护，初始时只加入$1$和$N$。为了得到答案，还需要用堆维护最大的间隔，为了支持删除用std::set更方便，具体用two-pointers实现。视$\mathcal O(B)=\mathcal O(N)$，则复杂度$\mathcal O(N\log N)$。

换一种思维，考虑先加入所有格子，然后逐个删除。这样就简单很多了，不再需要大常数的std::set，只要一个双向链表即可，空隙一定是单调增的，用一个变量维护即可。这是官方题解的方法，简单很多。

查看代码 
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
#include <fstream>
#include <algorithm>
#include <set>
using namespace std;
ifstream fin("snowboots.in");
ofstream fout("snowboots.out");
const int N = 100005;
pair<int, int> snow[N];
struct boot_t
{
	int dep, step, id;
	bool operator<(const boot_t &rhs) const
	{
		return dep < rhs.dep;
	}
} boot[N];
bool ans[N];
int main()
{
	int n, m;
	fin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		fin >> snow[i].first;
		snow[i].second = i;
	}
	sort(snow + 2, snow + n);
	for (int i = 1; i <= m; i++)
	{
		fin >> boot[i].dep >> boot[i].step;
		boot[i].id = i;
	}
	sort(boot + 1, boot + m + 1);
	multiset<int> mn;
	mn.insert(n - 1);
	set<int> reach;
	reach.insert(1);
	reach.insert(n);
	for (int i = 1, j = 2; i <= m; i++)
	{
		for (; j < n && snow[j].first <= boot[i].dep; j++)
		{
			set<int>::iterator it1 = reach.insert(snow[j].second).first, it2 = it1;
			mn.erase(mn.find(*++it2 - *--it1));
			mn.insert(snow[j].second - *it1);
			mn.insert(*it2 - snow[j].second);
		}
		ans[boot[i].id] = boot[i].step >= *mn.rbegin();
	}
	for (int i = 1; i <= m; i++)
		fout << ans[i] << endl;
	return 0;
}

Directory Traversal

大意

有一个文件系统，求选定一个目录，使得表示所有文件相对路径的字符串长度和的最小。输入以邻接表形式输入。$N\le 100,000$

样例
dirtraverse.in
1
2
3
4
5
6
7
8
9
8
bessie 3 2 6 8
folder1 2 3 4
file1 0
folder2 1 5
file2 0
folder3 1 7
file3 0
file4 0
dirtraverse.out
1
42

最优情况选择folder1，相对路径为：

1
2
3
4
file1
folder2/file2
../folder3/file3
../file4

洛谷P4268 官方提交 官方题解

思路

文件系统是标准的树，只不过向下和向上的边权不同，向下为文件名长度+1，向上为3(…/)。我的简单想法是先选择根目录，得到每个文件的长度，然后再次dfs，向下走把子树内的长度减去文件名长度+1，子树外的加上3，更新最优解。这样求dfs序，再用线段树维护即可，时间复杂度$\mathcal O(N\log N)$。

更加简单的方法应该是树形DP，复杂度线性，但是暂时没有官方题解。

查看代码 
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
ifstream fin("dirtraverse.in");
ofstream fout("dirtraverse.out");
const int N = 100005;
vector<int> mat[N];
int a[N], leaf, into[N], outo[N], len[N];
long long ans;
struct node
{
	long long sum;
	int lazy;
} tree[N * 4];
void build(int id, int l, int r)
{
	if (l == r)
		tree[id].sum = len[l];
	else
	{
		int mid = (l + r) / 2;
		build(id * 2, l, mid);
		build(id * 2 + 1, mid + 1, r);
		tree[id].sum = tree[id * 2].sum + tree[id * 2 + 1].sum;
	}
}
inline void pushdown(int id, int l, int r)
{
	if (tree[id].lazy)
	{
		int mid = (l + r) / 2;
		tree[id * 2].sum += 1ll * (mid - l + 1) * tree[id].lazy;
		tree[id * 2].lazy += tree[id].lazy;
		tree[id * 2 + 1].sum += 1ll * (r - mid) * tree[id].lazy;
		tree[id * 2 + 1].lazy += tree[id].lazy;
		tree[id].lazy = 0;
	}
}
void modify(int id, int l, int r, int L, int R, int val)
{
	if (L <= l && R >= r)
	{
		tree[id].sum += 1ll * (r - l + 1) * val;
		tree[id].lazy += val;
	}
	else
	{
		pushdown(id, l, r);
		int mid = (l + r) / 2;
		if (L <= mid)
			modify(id * 2, l, mid, L, R, val);
		if (R > mid)
			modify(id * 2 + 1, mid + 1, r, L, R, val);
		tree[id].sum = tree[id * 2].sum + tree[id * 2 + 1].sum;
	}
}
void dfs(int k, int now)
{
	if (!mat[k].size())
		len[++leaf] = now;
	else
	{
		into[k] = leaf + 1;
		for (int i = 0; i < mat[k].size(); i++)
			dfs(mat[k][i], now + a[mat[k][i]] + (bool)mat[mat[k][i]].size());
		outo[k] = leaf;
	}
}
void dfs(int k)
{
	ans = min(ans, tree[1].sum);
	for (int i = 0; i < mat[k].size(); i++)
		if (mat[mat[k][i]].size())
		{
			if (into[mat[k][i]] > 1)
				modify(1, 1, leaf, 1, into[mat[k][i]] - 1, 3);
			modify(1, 1, leaf, into[mat[k][i]], outo[mat[k][i]], -a[mat[k][i]] - 1);
			if (outo[mat[k][i]] < leaf)
				modify(1, 1, leaf, outo[mat[k][i]] + 1, leaf, 3);
			dfs(mat[k][i]);
			if (into[mat[k][i]] > 1)
				modify(1, 1, leaf, 1, into[mat[k][i]] - 1, -3);
			modify(1, 1, leaf, into[mat[k][i]], outo[mat[k][i]], a[mat[k][i]] + 1);
			if (outo[mat[k][i]] < leaf)
				modify(1, 1, leaf, outo[mat[k][i]] + 1, leaf, -3);
		}
}
int main()
{
	int n;
	fin >> n;
	for (int i = 1; i <= n; i++)
	{
		string name;
		fin >> name;
		a[i] = name.length();
		int k;
		fin >> k;
		while (k--)
		{
			int v;
			fin >> v;
			mat[i].push_back(v);
		}
	}
	dfs(1, 0);
	build(1, 1, leaf);
	ans = tree[1].sum;
	dfs(1);
	fout << ans << endl;
	return 0;
}

Taming the Herd

大意

有一个计数器，每天如果发生事件则清零，否则加一。把连续$N$天的结果记录下来，但可能被篡改，其中第一天一定发生事件，求$\forall i\in 1\dots N$，若发生$i$次事件，则至少有几天被篡改。$N\le 100$

样例
taming.in
1
2
6
1 1 2 0 0 1
taming.out
1
2
3
4
5
6
4
2
1
2
3
4
事件次数 最优序列 差异
1 0 1 2 3 4 5 4
2 0 1 2 3 0 1 2
3 0 1 2 0 0 1 1

以此类推

洛谷P4267 官方提交 官方题解

思路

在fks的提醒下，这其实是简单的DP。用$f[i][j][k]$表示前$i$天，发生$j$次事件，计数器的值为$k$最少篡改次数。则有初始条件
$$f[1][1][0]=\begin{cases}0 & a[1]=0 \ 1 & \text{otherwise}\end{cases}$$

第$i+1$天的决策为
$$f[i+1][j][k+1]=\min f[i][j][k]+\begin{cases}0 & a[i+1]=k+1 \ 1 & \text{otherwise}\end{cases}$$
$$f[i+1][j+1][0]=\min f[i][j][k]+\begin{cases}0 & a[i+1]=0 \ 1 & \text{otherwise}\end{cases}$$

目标状态为
$$\min_{k\in 1\dots n} f[n][j][k]$$

复杂度$\mathcal O(N^3)$

查看代码 
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
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("taming.in");
ofstream fout("taming.out");
const int N = 105, INF = 1e9;
int a[N], f[N][N][N];
int main()
{
	int n;
	fin >> n;
	for (int i = 1; i <= n; i++)
		fin >> a[i];
	fill_n(&f[0][0][0], sizeof(f) / sizeof(int), INF);
	f[1][1][0] = (bool)a[1];
	for (int i = 1; i < n; i++)
		for (int j = 1; j <= i; j++)
			for (int k = 0; k < i; k++)
				if (f[i][j][k] < INF)
				{
					f[i + 1][j][k + 1] = min(f[i + 1][j][k + 1], f[i][j][k] + (a[i + 1] != k + 1));
					f[i + 1][j + 1][0] = min(f[i + 1][j + 1][0], f[i][j][k] + (bool)a[i + 1]);
				}
	for (int i = 1; i <= n; i++)
		fout << *min_element(f[n][i], f[n][i] + n) << endl;
	return 0;
}