USACO 2018 February Gold 题解

概述

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

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

Snow Boots

大意

一条路上有NN个格子编号 ,第ii格有一定的深度的雪fif_i11NN都没有雪。有BB双鞋,穿每双鞋最多能在sis_i的雪中,每步最多走did_i格,求每双鞋是否能从11走到NN1N,B100,0001\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 官方提交 官方题解

思路

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

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

大意

有一个文件系统,求选定一个目录,使得表示所有文件相对路径的字符串长度和的最小。输入以邻接表形式输入。N100,000N\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序,再用线段树维护即可,时间复杂度O(NlogN)\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

大意

有一个计数器,每天如果发生事件则清零,否则加一。把连续NN天的结果记录下来,但可能被篡改,其中第一天一定发生事件,求 ,若发生ii次事件,则至少有几天被篡改。N100N\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]f[i][j][k]表示前ii天,发生jj次事件,计数器的值为kk最少篡改次数。则有初始条件

f[1][1][0]={0a[1]=01otherwisef[1][1][0]=\begin{cases}0 & a[1]=0 \\ 1 & \text{otherwise}\end{cases}

i+1i+1天的决策为

f[i+1][j][k+1]=minf[i][j][k]+{0a[i+1]=k+11otherwisef[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]=minf[i][j][k]+{0a[i+1]=01otherwisef[i+1][j+1][0]=\min f[i][j][k]+\begin{cases}0 & a[i+1]=0 \\ 1 & \text{otherwise}\end{cases}

目标状态为

复杂度O(N3)\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;
}