NOIP 2016 整理

Day 1

玩具谜题

描述

小南有一套可爱的玩具小人,它们各有不同的职业。

有一天,这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈,它们有的面朝圈内,有的面朝圈外。如下图:

这时 singer 告诉小南一个谜题:“眼镜藏在我左数第 $3$ 个玩具小人的右数第 $1$ 个玩具小人的左数第 $2$ 个玩具小人那里。”

小南发现,这个谜题中玩具小人的朝向非常关键,因为朝内和朝外的玩具小人的左右方向是相反的:面朝圈内的玩具小人,它的左边是顺时针方向,右边是逆时针方向;而面向圈外的玩具小人,它的左边是逆时针方向,右边是顺时针方向。

小南一边艰难地辨认着玩具小人,一边数着:

“singer 朝内,左数第 $3$ 个是 archer。
“archer 朝外,右数第 $1$ 个是 thinker。
“thinker 朝外,左数第 $2$ 个是 writer。
“所以眼镜藏在 writer 这里!”

虽然成功找回了眼镜,但小南并没有放心。如果下次有更多的玩具小人藏他的眼镜,或是谜题的长度更长,他可能就无法找到眼镜了。所以小南希望你写程序帮他解决类似的谜题。这样的谜题具体可以描述为:

有 $n$ 个玩具小人围成一圈,已知它们的职业和朝向。现在第 $1$ 个玩具小人告诉小南一个包含 $m$ 条指令的谜题,其中第i条指令形如“左数/右数第 $S_{i}$ 个玩具小人”。你需要输出依次数完这些指令后,到达的玩具小人的职业。

$n \leq 10^{5}, m \leq 10^{5}$

分析

其实我至今都没有想明白,去年在考场上我在想什么东西,以至于第一题都 WA 了。然后把考试的代码找出来改了一下,然后 A 了,debug 的时候找出来一堆奇奇怪怪的错误,我去年在干什么呀 qwq

大概思路就是 $\Theta(m)$ 模拟转圈的过程即可,注意细节。

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX = 100000 + 7;
int n, m;
struct Node {
int num;
char name[11];
}a[MAX];
int d[MAX], s[MAX];

int main()
{
// freopen("toy.in","r",stdin); freopen("toy.out","w",stdout);

n = readIn<int>(), m = readIn<int>();
for (int i = 0; i < n; i++) a[i].num = readIn<int>(), scanf("%s", a[i].name);

// for (int i = 0; i < n; ++i) printf("%d %d %s\n", i, a[i].num, a[i].name);

for (int i = 0; i < m; i++) d[i] = readIn<int>(), s[i] = readIn<int>();

int q = 0;
for (int i = 0; i < m; ++i) {
// printf("%d %d\n", d[i], s[i]);
if (d[i] == 0 && a[q].num== 0) {
q -= s[i];
if (q < 0) {
// q = n - s[i] + 1;
q = q + n;
}
}
else if (d[i] == 0 && a[q].num== 1) {
q += s[i];
if (q > n - 1) {
// q = q - n + 1;
q = q - n;
}
}
else if (d[i] == 1 && a[q].num == 0) {
q += s[i];
if (q > n - 1) {
// q = q - n + 1;
q = q - n;
}
}
else if (d[i] == 1 && a[q].num == 1) {
q -= s[i];
if (q < 0) {
// q = n - s[i] + 1;
q = q + n;
}
}
// printf("%s\n", a[q].name);
}

printf("%s\n", a[q].name);
return 0;
}

天天爱跑步

描述

小 C 同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。

这个游戏的地图可以看作一棵包含 $n$ 个结点和 $n−1$ 条边的树,每条边连接两个结点,且任意两个结点存在一条路径互相可达。树上结点编号为从 $1$ 到 $n$ 的连续正整数。

现在有 $m$ 个玩家,第 $i$ 个玩家的起点为 $S_{i}$,终点为 $T_{i}$。每天打卡任务开始时,所有玩家在第 $0$ 秒同时从自己的起点出发,以每秒跑一条边的速度,不间断地沿着最短路径向着自己的终点跑去,跑到终点后该玩家就算完成了打卡任务。(由于地图是一棵树,所以每个人的路径是唯一的)

小 C 想知道游戏的活跃度,所以在每个结点上都放置了一个观察员。在结点 $j$ 的观察员会选择在第 $W_{j}$ 秒观察玩家,一个玩家能被这个观察员观察到当且仅当该玩家在第 $W_{j}$ 秒也正好到达了结点 $j$。小 C 想知道每个观察员会观察到多少人?

注意:我们认为一个玩家到达自己的终点后该玩家就会结束游戏,他不能等待一段时间后再被观察员观察到。即对于把结点 $j$ 作为终点的玩家:若他在第 $W_{j}$ 秒到达终点,则在结点 $j$ 的观察员不能观察到该玩家;若他正好在第 $W_{j}$ 秒到达终点,则在结点 $j$ 的观察员可以观察到这个玩家。

$n \leq 299998, m \leq 299998$

分析

我去年大概是一个 zz,所以我连暴力都没有写出来qwq 然后今年作为模拟题来做的时候又用 25 分的暴力思想去做 40 分,然后 T 飞啦qwq(时间复杂度 $\Theta(n^{2})$)

好了现在进入正题,25 分的暴力分还是比较好拿到的,这里不详述。

这里考虑链的情况。因为是一条链所以每一条路劲都是唯一确定的,又因为链上的点依次为 $1, 2, 3, \cdots, n$ ,所以可以确定 $s \rightarrow t$ 是从编号小的点走向编号大的点还是编号大的点走向编号小的点。这里分开讨论:

  • 若 $(u, v) (u \leq v)$ ,那么点 $i$ 的观察员活跃度可以 $+1$ 当且仅当存在 $w_{i} = i - u$ ,$u \leq 0$ 的时候仍然成立。
  • 若 $(u, v)(u \geq v)$ ,那么点 $i$ 的观察员活跃度可以 $+1$ 当且仅当存在 $w_{i} = u - i$ ,$u > n$ 的时候也成立。

那么这里对于链的暴力,可以每次在 $u$ (开始的时候 $+1$),在 $v$ (结束时在开始处 $-1$),在路径结束之前,统计一下链上每一个点上等于 $i - w_{i} (u \leq v)$ 和 $w_{i} + i(u > v)$ 的数量。

对于 $s_{i} = 1$ 的部分分可以在每一个 $t_{i}$ 那里标记一下,然后 $\Theta(n)$ 一边遍历一边回溯累计一下答案即可。

那么到此为止,暴力分有 60 分了,如果有思路可以考虑 $t_{i} = 1$ 的情况。

至于剩下的正解部分呀,我决定暂且先不写,有时间来填坑。我并不觉得现在自己对这道题目的领悟比学长去年写的更深刻,所以呀,推荐你们去看学长的博客吧 qwq 链接戳我 qwq

代码

暴力

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
//  Created by ZJYelizaveta on 2017年11月08日 星期三 21时16分06秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 300000 + 3;
const int INF = 0x3f3f3f3f;
int n, m;
vector<int> G[MAX_N << 1];
int w[MAX_N];
int s[MAX_N], t[MAX_N];

inline void addEdge(int from, int to) {
G[from].push_back(to);
G[to].push_back(from);
}

namespace subtaskOne {
int cnt[1000];
inline void solve() {
memset(cnt, 0, sizeof cnt);
for (int i = 1; i <= n; ++i) if (w[s[i]] == 0) ++cnt[s[i]];
for (int i = 1; i <= n; ++i) printf("%d%c", cnt[i], i == n ? '\n' : ' ');
exit(0);
}
}

namespace subtaskTwo {
int cnt[1000];
inline void solve() {
memset(cnt, 0, sizeof cnt);
for (int i = 1; i <= n; ++i) if (s[i]) ++cnt[s[i]];
for (int i = 1; i <= n; ++i) printf("%d%c", cnt[i], i == n ? '\n' : ' ');
exit(0);
}
}

namespace subtaskThree {
int cnt[1000];

inline bool dfs(int u, int fa, int t, int timeStamp) {
bool flag = false;
if (u == t) flag = true;
else {
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (v == fa) continue;
flag = flag || dfs(v, u, t, timeStamp + 1);
}
}
if (flag && w[u] == timeStamp) ++cnt[u];
return flag;
}

inline void solve() {
for (int i = 1; i <= m; ++i) {
dfs(s[i], 0, t[i], 0);
}
for (int i = 1; i <= n; ++i) printf("%d%c", cnt[i], i == n ? '\n' : ' ');
exit(0);
}
}

namespace subtaskFour {
struct Events {
int s, t;
Events (int s, int t) : s(s), t(t){}
};
vector<Events> pre[100000], suf[100000];
int cnt[100000], ans[100000];

inline void calculate() {
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < (int)pre[i].size(); ++j) {
if (pre[i][j].s == i) ++cnt[i];
}

if (i - w[i] >= 1) ans[i] += cnt[i - w[i]];

for (int j = 0; j < (int)pre[i].size(); ++j) {
if (pre[i][j].t == i) --cnt[pre[i][j].s];
}
}

memset(cnt, 0, sizeof cnt);
for (int i = n; i >= 1; --i) {
for (int j = 0; j < (int)suf[i].size(); ++j) {
if (suf[i][j].s == i) ++cnt[i];
}

if (i + w[i] <= n) ans[i] += cnt[i + w[i]];

for (int j = 0; j < (int)suf[i].size(); ++j) {
if (suf[i][j].t == i) --cnt[suf[i][j].s];
}
}
}

inline void solve() {
for (int i = 1; i <= m; ++i) {
if (s[i] <= t[i]) {
pre[s[i]].push_back(Events(s[i], t[i]));
pre[t[i]].push_back(Events(s[i], t[i]));
}
else {
suf[s[i]].push_back(Events(s[i], t[i]));
suf[t[i]].push_back(Events(s[i], t[i]));
}
}

calculate();
for (int i = 1; i <= n; ++i) printf("%d%c", ans[i], i == n ? '\n' : ' ');
exit(0);
}
}

namespace subtaskFive {
int depth[MAX_N], cnt[MAX_N];

inline void dfs(int u, int fa) {
depth[u] = fa == 0 ? 0 : depth[fa] + 1;
for (int i = 0; i < (int)G[u].size(); ++i) {
if (G[u][i] == fa) continue;
dfs(G[u][i], u);
cnt[u] += cnt[G[u][i]];
// printf("%d %d\n", u, G[u][i]);
}
}

inline void solve() {
for (int i = 1; i <= m; ++i) ++cnt[t[i]];

dfs(1, 0);

for (int i = 1; i <= n; ++i) printf("%d%c", depth[i] == w[i] ? cnt[i] : 0, i == n ? '\n' : ' ');

exit(0);
}
}

int main()
{
n = readIn<int>(), m = readIn<int>();
for (int i = 1; i <= n - 1; ++i) {
int u = readIn<int>(), v = readIn<int>();
addEdge(u, v);
}
for (int i = 1; i <= n; ++i) w[i] = readIn<int>();
for (int i = 1; i <= m; ++i) s[i] = readIn<int>(), t[i] = readIn<int>();

if (n % 10 == 1 && m % 10 == 1) subtaskOne::solve();
if (n % 10 == 2 && m % 10 == 2) subtaskTwo::solve();
if (n % 10 == 3 && m % 10 == 3) subtaskThree::solve();
if (n % 10 == 4 && m % 10 == 4) subtaskFour::solve();
if (n % 10 == 5 && m % 10 == 5) subtaskFive::solve();

return 0;
}

$100 \%$

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 300000 + 3;
const int MAX_M = 300000 + 3;
const int INF = 0x3f3f3f3f;
int n, m;
int fa[MAX_N], rank[MAX_N], anc[MAX_N], w[MAX_N ], depth[MAX_N], cnt[2][MAX_N << 1];
int ans[MAX_N ];
bool vis[MAX_N];
vector<int> G[MAX_N << 1], start[2][MAX_N], end[2][MAX_N];
vector< pair<int, int> > q[MAX_N + 1];

int find(int x) {
return fa[x] ? fa[x] = find(fa[x]) : x;
}

inline void merge(int x, int y) {
int lx = find(x), ly = find(y);
if (rank[ly] > rank[lx]) swap(lx, ly);
fa[ly] = lx;
rank[lx] += rank[lx] == rank[ly];
}

inline void lca(int u, int p) {
anc[u] = u;
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (v == p) continue;
depth[v] = depth[u] + 1;
lca(v, u); merge(u, v);
anc[find(u)] = u;
}
vis[u] = true;
for (int i = 0; i < (int)q[u].size(); ++i) {
pair<int, int> p = q[u][i];
int v = p.first == u ? p.second : p.first;
if (vis[v]) {
int a = anc[find(v)], len = depth[u] + depth[v] - 2 * depth[a];
int s = depth[p.first], t = depth[p.second] - len + n;

start[0][p.first].push_back(s); start[1][p.second].push_back(t);
end[0][a].push_back(s); end[1][a].push_back(t);
}
}
}

inline void dfs(int u, int p) {
ans[u] -= cnt[0][depth[u] + w[u]] + cnt[1][depth[u] - w[u] + n];
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (v == p) continue;
dfs(v, u);
}

for (int i = 0; i <= 1; ++i) {
for (int j = 0; j < (int)start[i][u].size(); ++j) ++cnt[i][start[i][u][j]];
}
for (int j = 0; j < (int)end[1][u].size(); ++j) --cnt[1][end[1][u][j]];
ans[u] += cnt[0][depth[u] + w[u]] + cnt[1][depth[u] - w[u] + n];
for (int j = 0; j < (int)end[0][u].size(); ++j) --cnt[0][end[0][u][j]];
}

int main()
{
// freopen("test.in", "r", stdin);

n = readIn<int>(), m = readIn<int>();
for (int i = 0; i < n - 1; ++i) {
int u = readIn<int>(), v = readIn<int>();
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = 1; i <= n; ++i) w[i] = readIn<int>();
for (int i = 0; i < m; ++i) {
pair<int, int> p;
p.first = readIn<int>(), p.second = readIn<int>();
q[p.first].push_back(p);
if (p.first != p.second) q[p.second].push_back(p);
}

lca(1, 0);
dfs(1, 0);

for (int i = 1; i <= n; ++i) printf("%d%c", ans[i], i == n ? '\n' : ' ');
return 0;
}

换教室

描述

对于刚上大学的牛牛来说,他面临的第一个问题是如何根据实际情况申请合适的课程。

在可以选择的课程中,有 $2n$ 节课程安排在 $n$ 个时间段上。在第 $i (1 \leq i \leq n)$ 个时间段上,两节内容相同的课程同时在不同的地点进行,其中,牛牛预先被安排在教室 $c_{i}$ 上课,而另一节课程在教室 $d_{i}$ 进行。

在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的 $n$ 节安排好的课程。如果学生想更换第 $i$ 节课程的教室,则需要提出申请。若申请通过,学生就可以在第 $i$ 个时间段去教室 $d_{i}$ 上课,否则仍然在教室 $c_{i}$上课。

由于更换教室的需求太多,申请不一定能获得通过。通过计算,牛牛发现申请更换第 $i$ 节课程的教室时,申请被通过的概率是一个已知的实数 $k_{i}$,并且对于不同课程的申请,被通过的概率是互相独立的。

学校规定,所有的申请只能在学期开始前一次性提交,并且每个人只能选择至多 $m$ 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室,而不能根据某些课程的申请结果来决定其他课程是否申请;牛牛可以申请自己最希望更换教室的 $m$ 门课程,也可以 不用完 这 $m$ 个申请的机会,甚至可以一门课程都不申请。

因为不同的课程可能会被安排在不同的教室进行,所以牛牛需要利用课间时间从一间教室赶到另一间教室。

牛牛所在的大学有 $v$ 个 教室,有 $e$ 条道路。每条道路连接两间教室,并且是可以 双向通行 的。由于道路的长度和拥堵程度不同,通过不同的道路耗费的体力可能会有所不同。当第 $i (1\leq i \leq n-1)$ 节课结束后,牛牛就会从这节课的教室出发,选择一条耗费体力最少的 路径 前往下一节课的教室。

现在牛牛想知道,申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的 期望值 最小,请你帮他求出这个最小值。

$1 \leq n \leq 2000,0 \leq m \leq 2000, 1 \leq v \leq 300, 0 \leq e \leq 90000。$

分析

去年呀,不懂数学期望,然后 GG 。

先预习一下定义:数学期望(或均值,亦简称期望)是试验中每次可能结果的概率乘以其结果的总和。

这里要求“因在教室间移动耗费的体力值的总和的 期望值 最小”,那么可以先用 floyd 预处理出点与点之间的最短路。然后根据期望的线性性,可以将其线性向后递推,故使用动规来求。

令 $dp[i][j][k]$ 为到了第 $i$ 节课,已经换了 $j$ 次教室之后的耗费体力之和的期望值最小(其中 $k$ 表示第 $i$ 节课是否换教室)。

那么此时有两种决策,其中不换教室则在 $c_{i}$ 上,换教室在 $d_{i}$ 上,第 $i$ 节课换教室的概率为 $p_{i}$ ,第 $i$ 点到 $j$ 的最短路为 $dis[i][j]$ :

  • 第 $i$ 节课不换教室,那么考虑第 $i - 1$ 节课是否换教室来计算这一次的期望(期望的线性性)

  • 第 $i$ 节课换教室,一样考虑第 $i - 1$ 次是否换教室,转移方程如下

写转移方程的时候仔细一点就行了,然后没有了 qwq

记几个处理二进制位的内置函数:

  • __builtin_popcount(x):$x$ 中 1 的个数。
  • __builtin_ctz(x):$x$ 末尾 0 的个数。$x=0$ 时结果未定义。
  • __builtin_clz(x):$x$ 前导 0 的个数。$x=0$ 时结果未定义。
  • __builtin_ffs(x):返回 $x$ 中最后一个为 1 的位是从后向前的第几位。

代码

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
//  Created by ZJYelizaveta on 2017年11月06日 星期一 11时20分48秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 2000 + 3;
const int MAX_V = 300 + 3;
const int INF = 0x3f3f3f3f;
const double inf = 1e16;
int n, m, v, e; // vertex, edge
int c[MAX_N], d[MAX_N]; // classroom, another classroom
double p[MAX_N]; // 概率
int dis[MAX_V][MAX_V];
double dp[MAX_N][MAX_N][2];

inline void floyd() {
for (int k = 1; k <= v; ++k) {
for (int i = 1; i <= v; ++i) {
for (int j = 1; j <= v; ++j) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
/*
printf("\n");
for (int i = 1; i <= v; ++i) {
for (int j = 1; j <= v; ++j) printf("%d ", dis[i][j]);
printf("\n");
}
*/
}

inline void solve() {
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) dp[i][j][0] = dp[i][j][1] = inf;
}

dp[1][0][0] = dp[1][1][1] = 0.0;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j <= min(i, m); ++j) {
dp[i][j][0] = dp[i - 1][j][0] + dis[c[i - 1]][c[i]];
dp[i][j][0] = min(dp[i][j][0], dp[i - 1][j][1] + dis[d[i - 1]][c[i]] * p[i - 1] + dis[c[i - 1]][c[i]] * (1.0 - p[i - 1]));

if (j >= 1) {
dp[i][j][1] = dp[i - 1][j - 1][0] + dis[c[i - 1]][d[i]] * p[i] + dis[c[i - 1]][c[i]] * (1.0 - p[i]); //
dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j - 1][1] + dis[d[i - 1]][d[i]] * p[i - 1] * p[i]
+ dis[c[i - 1]][d[i]] * (1.0 - p[i - 1]) * p[i] + dis[d[i - 1]][c[i]] * p[i - 1] * (1.0 - p[i])
+ dis[c[i - 1]][c[i]] * (1.0 - p[i - 1]) * (1.0 - p[i]));
}
}
}

double ans = inf;
for (int i = 1; i <= min(n, m); ++i) {
ans = min(ans, min(dp[n][i][0], dp[n][i][1]));
}
ans = min(ans, dp[n][0][0]);
printf("%.2f\n", ans);
}

int main()
{
n = readIn<int>(), m = readIn<int>(), v = readIn<int>(), e = readIn<int>();
for (int i = 1; i <= n; ++i) c[i] = readIn<int>();
for (int i = 1; i <= n; ++i) d[i] = readIn<int>();
for (int i = 1; i <= n; ++i) scanf("%lf", &p[i]);

memset(dis, INF, sizeof dis);
for (int i = 0; i <= v; ++i) dis[i][i] = 0; //
for (int i = 1; i <= e; ++i) {
int u = readIn<int>(), v = readIn<int>(), w = readIn<int>();
dis[u][v] = dis[v][u] = min(min(dis[u][v], dis[v][u]), w);
}

floyd();
solve();

return 0;
}

Day 2

组合数问题

描述

组合数 $C_{n}^{m}$ 表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子,从 $(1, 2, 3)$ 三个物品中选择两个物品可以有 $(1, 2), (1, 3), (2, 3)$ 这三种选择方法。根据组合数的定义,我们可以给出计算组合数的一般公式:

其中 $n! = 1 \times 2 \times \cdots \times n$。

小葱想知道如果给定 $n, m$ 和 $k$ ,对于所有的 $0 \leq i \leq n, 0 \leq j <= min(i, m)$ 有多少对 $(i, j)$ 满足 $C_{i}^{j}$ 是 $k$ 的倍数。

$n \leq 2000, m \leq 2000, k = 21, t \leq 10^{4}$

分析

$\Theta(n^{2})$ 预处理 + $\Theta(nm)$ 计算有 70 分。

考虑正解,$t$ 组询问每次 $\Theta(nm)$ 的时间复杂度回答询问肯定是不行的,考虑优化。

这里依然是一个套路,用二维前缀和优化,这样回答的时间复杂度降为 $\Theta(1)$ 。

首先 $\Theta(n^{2})$ 根据杨辉三角的递推式计算 $C_{n}^{m}$ :

令 $sum[i][j]$ 为 $n = i, m = j$ 时 $C[a][b] \pmod k = 0(a \leq i, b \leq min(i, j))$ 的个数,那么 :

这样,$ans = sum[n][m]$ ;总时间复杂度为 $\Theta(n^{2} + nm + t)$ 。

代码

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
//  Created by ZJYelizaveta on Friday, November 03, 2017 AM08:44:04 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 2000 + 3;
const int INF = 0x3f3f3f3f;
int testCase;
int K, n, m;
int C[MAX_N][MAX_N], sum[MAX_N][MAX_N];
int ans;

inline void prepare() {
memset(C, 0, sizeof C);
memset(sum, 0, sizeof sum);

C[0][0] = 1;
for (int i = 1; i < MAX_N; ++i) {
C[i][0] = 1, C[i][i] = 1;
for (int j = 1; j < i; ++j) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % K;
}
}

for (int i = 1; i < MAX_N; ++i) {
for (int j = 1; j < MAX_N; ++j) {
sum[i][j] = (j <= i && C[i][j] == 0) + sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
}
}
}

int main()
{
testCase = readIn<int>(), K = readIn<int>();

prepare();

while (testCase--) {
n = readIn<int>(), m = readIn<int>();

printf("%d\n", sum[n][m]);
}

return 0;
}

蚯蚓

描述

本题中,我们将用符号 $\left \lfloor c \right \rfloor$ 表示对 $c$ 向下取整,例如:$\left \lfloor 3.0 \right \rfloor = \left \lfloor 3.1 \right \rfloor= \left \lfloor 3.9 \right \rfloor = 3$。

蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。

蛐蛐国里现在共有 $n$ 只蚯蚓($n$ 为正整数)。每只蚯蚓拥有长度,我们设第 $i$ 只蚯蚓的长度为 $a_{i}(i=1, 2, \cdots, n)$,并保证所有的长度都是非负整数(即:可能存在长度为 $0$ 的蚯蚓)。

每一秒,神刀手会在所有的蚯蚓中,准确地找到最长的那一只(如有多个则任选一个)将其切成两半。神刀手切开蚯蚓的位置由常数 $p$ (是满足 $0<p<l$ 的有理数)决定,设这只蚯蚓长度为 $x$ ,神刀手会将其切成两只长度分别为 $\left \lfloor px \right \rfloor$ 和 $x - \left \lfloor px \right \rfloor$ 的蚯蚓。特殊地,如果这两个数的其中一个等于 $0$ ,则这个长度为 $0$ 的蚯蚓也会被保留。此外,除了刚刚产生的两只新蚯蚓,其余蚯蚓的长度都会增加 $q$ (是一个非负整常数)。

蛐蛐国王知道这样不是长久之计,因为蚯蚓不仅会越来越多,还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物,但是救兵还需要 $m$ 秒才能到来…… ($m$ 为非负整数)

蛐蛐国王希望知道这 $m$ 秒内的战况。具体来说,他希望知道:

  • $m$秒内,每一秒被切断的蚯蚓被切断前的长度(有 $m$ 个数)

  • $m$ 秒后,所有蚯蚓的长度(有 $n + m$ 个数)。

蛐蛐国王当然知道怎么做啦!但是他想考考你……

$n = 10^{5}, m \leq 7 \times 10^{6}, t = 71, a_{i} \leq 10^{8}, v \leq 10^{9}, q \leq 200$

分析

直接用优先队列模拟题意大概有 20 分,加一点小 trick 就可以拿到 85 分qwq

具体来说是这样的:用优先队列来模拟的话,每次都要将除队首之外队列中的元素 $+q$ ,这样每次操作的时间复杂度为 $\Theta(2log(n + m))$ ,但是实际上我们不是每一次操作必须马上将队列中的元素 $+q$ 。我们只需要让每次操作之后所有蚯蚓的相对长度与将蚯蚓 $+ q$ 之后的蚯蚓的相对的长度保持一样,$m$ 次操作之后将每条蚯蚓的长度 $+mq$ 就行了。

这样一来时间复杂度为 $\Theta(m2log(n + m))$ ,可以拿到 85 分,但是在 $m$ 较大的时候一样会 TLE。

考虑正解。

考虑 $q = 0$ 的情况,那么每次取出的蚯蚓的长度一定单调不增。我们维护三个单调不降的队列,第一个队列是原序列,第二个队列值左半部分蚯蚓的序列,第三个队列是右半部分蚯蚓的序列。每次取出要被砍的蚯蚓是三个序列的队首最大值,然后将蚯蚓砍成左右两部分分别加入左半部分蚯蚓序列和右半部分蚯蚓序列的末尾即可。

那么对于 $q \neq 0$ 的情况呢?每次只有两只新蚯蚓不增加长度,那么我们可以将每只蚯蚓都 $+q$ ,然后将两只新蚯蚓 $-q$ ,这样蚯蚓的相对长度没有增加,依然满足单调性,沿用 $q = 0$ 的时候的算法。

其实这样的思路和 85 分的优先队列的思想是一样的,但是由于 STL 常数比较大,这里用三个队列模拟优先队列的过程,时间复杂度 $\Theta(n \ logn + m)$ 。

代码

$85 \%$

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
//  Created by ZJYelizaveta on Friday, November 03, 2017 AM11:51:23 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 100000 + 3;
const int MAX_M = 7000000 + 3;
const int MAX_T = 71 + 3;
const int INF = 0x3f3f3f3f;
int n, m, inc;
int u, v, t;
double p;
int len[MAX_N + MAX_M], add;

vector<int> ans;
priority_queue<int> q;
inline void solve() {
ans.clear(); add = 0;
memset(len, 0, sizeof len);

for (int i = 1; i <= m; ++i) {
int x = q.top(); q.pop();

x += add;
if (i % t == 0) ans.push_back(x);

add += inc;
int temp1 = (int)(floor(p * x) - add), temp2 = (int)(x - floor(p * x) - add);
q.push(temp1), q.push(temp2);
}
for (int i = 1; i <= n + m; ++i) {
int x = q.top(); q.pop();
len[i] = x + add;
}

for (int i = 0; i < (int)ans.size(); ++i) printf("%d ", ans[i]); printf("\n");
for (int i = 1; i <= n + m; i++) if (i % t == 0) printf("%d ", len[i]); printf("\n");
}

int main()
{
n = readIn<int>(), m = readIn<int>(), inc = readIn<int>();
u = readIn<int>(), v = readIn<int>(), t = readIn<int>();
for (int i = 1; i <= n; ++i) {
int x = readIn<int>();
q.push(x);
}
p = (double)u / (double)v;

solve();

return 0;
}

$100 \%$

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
//  Created by ZJYelizaveta on Friday, November 03, 2017 PM03:27:28 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 100000 + 3;
const int MAX_M = 7000000 + 3;
const int INF = 0x3f3f3f3f;
int n, m, inc;
int u, v, t;
double p;
int a[MAX_N];
int seq[3][MAX_M], l[3], r[3];

inline int findMax() {
int cur = INT_MIN, id = 0;
for (int i = 0; i < 3; ++i) {
if (r[i] - l[i] >= 1 && seq[i][l[i]] > cur) {
cur = seq[i][l[i]];
id = i;
}
}
return id;
}

vector<int> ans, res;
void solve() {
sort(a, a + n); reverse(a, a + n);
memcpy(seq[0], a, sizeof a);
memset(l, 0, sizeof l);
memset(r, 0, sizeof r);

// for (int i = 0; i < n; ++i) printf("%d ", seq[0][i]); printf("\n");

ans.clear();
r[0] = n;
for (int i = 0; i < m; ++i) {
int id = findMax(), cur = seq[id][l[id]++];
// printf("%d %d\n", id, cur);
int add = i * inc;

if ((i + 1) % t == 0) ans.push_back(cur + add);

int lft = (ll)(cur + add) * u / v, rht = (cur + add) - lft;
lft -= add, rht -= add;
seq[1][r[1]++] = lft - inc, seq[2][r[2]++] = rht - inc;
}

for (int i = 0; i < (int)ans.size(); ++i) printf("%d ", ans[i]); printf("\n");

res.clear();
int add = m * inc;
for (int i = 0; i < n + m; ++i) {
int id = findMax(), cur = seq[id][l[id]++];
if ((i + 1) % t == 0) res.push_back(cur + add);
}
for (int i = 0; i < (int)res.size(); ++i) printf("%d ", res[i]); printf("\n");
}

int main()
{
// freopen("earthworm.in", "r", stdin);
// freopen("earthworm.out", "w", stdout);

n = readIn<int>(), m = readIn<int>(), inc = readIn<int>();
u = readIn<int>(), v = readIn<int>(), t = readIn<int>();
for (int i = 0; i < n; ++i) a[i] = readIn<int>();

p = (double)u / (double)v;
solve();

return 0;
}

愤怒的小鸟

描述

Kiana 最近沉迷于一款神奇的游戏无法自拔。

简单来说,这款游戏是在一个平面上进行的。

有一架弹弓位于 $(0, 0)$ 处,每次 Kiana 可以用它向第一象限发射一只红色的小鸟,小鸟们的飞行轨迹均为形如 $y = ax^{2}+ bx$ 的曲线,其中 $a, b$ 是Kiana指定的参数,且必须满足$a < 0$。

当小鸟落回地面(即 $x$ 轴)时,它就会瞬间消失。

在游戏的某个关卡里,平面的第一象限中有 $n$ 只绿色的小猪,其中第 $i$ 只小猪所在的坐标为 $(x_{i}, y_{i})$ 。

如果某只小鸟的飞行轨迹经过了 $(x_{i}, y_{i})$ ,那么第 $i$ 只小猪就会被消灭掉,同时小鸟将会沿着原先的轨迹继续飞行;

如果一只小鸟的飞行轨迹没有经过 $(x_{i}, y_{i})$ ,那么这只小鸟飞行的全过程就不会对第 $i$ 只小猪产生任何影响。

例如,若两只小猪分别位于 $(1,3)$ 和 $(3,3)$ ,Kiana 可以选择发射一只飞行轨迹为 $y = -x^{2} + 4x$ 的小鸟,这样两只小猪就会被这只小鸟一起消灭。

而这个游戏的目的,就是通过发射小鸟消灭所有的小猪。

这款神奇游戏的每个关卡对 Kiana 来说都很难,所以 Kiana 还输入了一些神秘的指令,使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。

假设这款游戏一共有 $T$ 个关卡,现在 Kiana 想知道,对于每一个关卡,至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算,所以希望由你告诉她。

$n \leq 18, m = 2, T \leq 5$

分析

$n \leq 18$ ,很明显是状压dp的暗示。

令 $dp[S]$ 为打掉集合 $S$ 中所有的猪所需最少的次数。

每次发射一只鸟,要么打死一头猪,要么打死两头猪 $i$ 和 $j$ 。 $\Theta(2^{n}n^{2})$ 的时间复杂度枚举 $i$ 和 $j$ 然后判断一下:

  • $i = j$ ,那么包含 $i, j$ 的子集为 $S \otimes (1 << i)$
  • 若方程无解($a = 0$)或抛物线不符合条件($a > 0$),那么此时只能打一只猪,此时集合仍为 $S \otimes (1 << i)$
  • 否则,$\Theta(n)$ 的时间在集合 $S$ 中剔除这一次发射能够打掉的点。

这样一来时间复杂度为 $\Theta(2^{n}n^{3})$ 。

考虑优化。听说位运算优化掉一个 $n$ 之后,可以以 $\Theta(2^{n}n^{2})$ 的时间复杂度卡过去?

优化还是比较套路,首先我们还是预处理,预处理出 $sub_{i, j}$ 为打出一条经过猪 $i$ 和 $j$ 的抛物线,不能打掉的点的集合。

考虑集合中横坐标最小的点,在最优解中这个点早晚都会被打掉,那么可以固定 $i$ ,然后枚举 $j$ 即可。这样复杂度又可以优化一个 $n$ ,现在总时间复杂度为 $\Theta(2^{n}n)$ 。

从头到尾,都没有明白 $m$ 在这道题目里面是起什么作用的 qwq

然后对于暴力的部分,其实时间复杂度满打满算应该是 $\Theta(2^{n}n^{3})$ ,在 Luogu 上有 75,在 UOJ 上有 85 分,不明嚼栗 qwq

代码

暴力

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
//  Created by ZJYelizaveta on 2017年11月05日 星期日 15时35分32秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAXNODE = (1 << 18) + 3;
const int MAX_N = 18 + 3;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
int testCase;
int n, m;
double x[MAX_N], y[MAX_N];
int dp[MAXNODE];

inline bool calculate(double x1, double y1, double x2, double y2, double &a, double &b) {
double temp = (x1 * x1 * x2 - x2 * x2 * x1);
if (fabs(temp) < eps) return false;

a = (y1 * x2 - y2 * x1) / temp;
b = (y2 * x1 * x1 - y1 * x2 * x2) / temp;

return true;
}

inline int solve(int S, int i, int j) {
if (i == j) return (S ^ (1 << i)); //

double a, b;
if (!calculate(x[i], y[i], x[j], y[j], a, b) || a >= 0) return (S ^ (1 << i));

S = S ^ (1 << i) ^ (1 << j);
for (int k = 0; k < n; ++k) if (S & (1 << k)) { //
double sum = a * x[k] * x[k] + b * x[k];
if (fabs(sum - y[k]) < eps) S ^= (1 << k);
}

return S;
}

inline int count(int S) {
return __builtin_popcount(S);
}

inline int dfs(int S) {
if (S == 0) return 0;
if (count(S) == 1) return 1;
if (dp[S] < INF) return dp[S];

for (int i = 0; i < n; ++i) if (S & (1 << i)) {
for (int j = 0; j < n; ++j) if (S & (1 << j)) {
int sub = solve(S, i, j);

dp[S] = min(dp[S], dfs(sub) + 1);
}
}
return dp[S];
}

int main()
{
testCase = readIn<int>();

while (testCase--) {
n = readIn<int>(), m = readIn<int>();
for (int i = 0; i < n; ++i) scanf("%lf%lf", &x[i], &y[i]);

memset(dp, INF, sizeof dp);
int ans = dfs((1 << n) - 1);

printf("%d\n", ans);
}

return 0;
}

$100 \%$

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
//  Created by ZJYelizaveta on 2017年11月06日 星期一 09时17分10秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAXNODE = (1 << 18) + 3;
const int MAX_N = 18 + 3;
const int INF = 0x3f3f3f3f;
const double eps = 1e-10;
int testCase;
int n, m;
double x[MAX_N], y[MAX_N];
int dp[MAXNODE], sub[MAX_N][MAX_N];

inline bool calculate(double x1, double y1, double x2, double y2, double &a, double &b) {
double temp = (x1 * x1 * x2 - x2 * x2 * x1);
if (fabs(temp) < eps) return true;

a = (y1 * x2 - y2 * x1) / temp;
b = (y2 * x1 * x1 - y1 * x2 * x2) / temp;

if (a >= -eps) return true; // 注意精度
return false;
}

inline void prepare() {
double a, b;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (calculate(x[i], y[i], x[j], y[j], a, b)) {
sub[i][j] = (1 << n) - 1;
continue;
}
sub[i][j] = 0;

for (int k = 0; k < n; ++k) {
double temp = a * x[k] * x[k] + b * x[k];
if (fabs(temp - y[k]) > eps) sub[i][j] ^= (1 << k);
}
}
}
/*
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) printf("%d ", sub[i][j]);
printf("\n");
}
*/
}

inline int count(int x) {
return __builtin_popcount(x);
}

inline int findPos(int x) {
return __builtin_ctz(x);
}

inline int dfs(int S) {
if (S == 0) return 0;
if (count(S) == 1) return 1;
if (dp[S] < INF) return dp[S];

int i = findPos(S);
dp[S] = min(dp[S], dfs(S ^ (1 << i)) + 1);
for (int j = i + 1; j < n; ++j) if (S & (1 << j)) {
dp[S] = min(dp[S], dfs(S & sub[i][j]) + 1);
}
return dp[S];
}

int main()
{
// freopen("test.in", "r", stdin);

testCase = readIn<int>();

while (testCase--) {
n = readIn<int>(), m = readIn<int>();
for (int i = 0; i < n; ++i) scanf("%lf%lf", &x[i], &y[i]);

prepare();
memset(dp, INF, sizeof dp);
int ans = dfs((1 << n) - 1);
printf("%d\n", ans);
}

return 0;
}
Share