2020 ICPC 沈阳站 (Gym 103202) 训练记录
训练记录G. The Witchwood签到题。排序之后求最大的 $k$ 个数之和即可。
F. Kobolds and Catacombs签到题。等价于求这个序列有多少个前缀满足其中的数恰好为整个序列中最小的几个。
视写法不同，可能需要额外处理相同权值的边界情况。
D. Journey to Un’Goro对序列做前缀异或和，得到一个长度为 $n + 1$ 的新序列（第一个位置补 $0$）。显然为了最大化所求的对数需要让前缀和序列中 $0$ 和 $1$ 各自占一半。
由于只需要输出字典序最小的 $100$ 个，直接暴力 dfs 即可。
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
#include
using namespace std;
using LL = long long;
bool dfs(int it, int sum, int n0, int n1, int n, int &res, string &ans) {
bool valid = false;
if(n0 <= n / 2 && n1 <= (n + 1) / 2) {
valid = true;
}
if(n1 <= n / 2 && n0 <= (n + 1) / 2) {
valid = true;
}
if(!valid) {
return false;
}
if(it == n) {
cout << ans << "\n";
res--;
return res == 0;
}
ans.push_back('b');
if(dfs(it + 1, sum, n0 + (sum == 0), n1 + (sum == 1), n, res, ans)) {
return true;
}
ans.pop_back();
ans.push_back('r');
if(dfs(it + 1, sum ^ 1, n0 + (sum == 1), n1 + (sum == 0), n, res, ans)) {
return true;
}
ans.pop_back();
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
cout << (LL)((n + 1) / 2) * ((n + 2) / 2) << "\n";
int res = 100;
string ans;
dfs(1, 0, 1, 0, n + 1, res, ans);
return 0;
}
I. Rise of Shadows实际上是在求
$$
| (H - 1) x \bmod HM | \leq A
$$的解数。这里 $\bmod$ 取最小绝对剩余。
我们熟知对于给定的 $r$，同余方程
$$
(H - 1) x \equiv r \pmod {HM}
$$有解的充要条件是 $\gcd(H - 1, HM) | r$，且有解时解数为 $\gcd(H - 1, HM)$，由此可知答案为
$$
d \cdot \left( 2 \left\lfloor \frac{A}{d} \right\rfloor + 1 \right)
$$其中 $d = \gcd(H - 1, HM) = \gcd(H - 1, M)$。注意特判 $2A = HM$ 的情形。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include
using namespace std;
using LL = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int h, m;
LL a;
cin >> h >> m >> a;
if(a * 2 == (LL)h * m) {
cout << (LL)h * m << "\n";
return 0;
}
int d = __gcd(h - 1, m);
cout << (a / d * 2 + 1) * d << "\n";
return 0;
}
K. Scholomance Academy阅读理解题。注意到 AUC 的被积函数间断点取值一定为 negative 样本的估值，直接排序后暴力即可。
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
#include
using namespace std;
using LL = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(12);
int n;
cin >> n;
vector
while(n--) {
string op;
int val;
cin >> op >> val;
if(op == "+") {
pos.push_back(val);
} else {
neg.push_back(val);
}
}
sort(pos.begin(), pos.end());
sort(neg.begin(), neg.end(), greater
LL ans = 0;
for(size_t i = 0; i < neg.size(); ) {
size_t j = upper_bound(neg.begin(), neg.end(), neg[i], greater
size_t ff = upper_bound(pos.begin(), pos.end(), neg[i]) - pos.begin();
ans += (j - i) * (pos.size() - ff);
i = j;
}
cout << (long double)ans / (pos.size() * neg.size()) << "\n";
return 0;
}
H. The Boomsday Project注意到租借的总次数并不是很多，可以考虑用 $f_k$ 表示处理完时间最早的前 $k$ 次租借需要的最小花费。
转移就是枚举会员卡的类型，然后判断在满足次数和天数两个限制下最多能跳到哪一次。这一步需要二分。
时间复杂度 $O(n \log m \sum q)$，看上去卡满了铁 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
56
57
58
59
60
#include
using namespace std;
using LL = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, r;
cin >> n >> m >> r;
vector
for(int i = 1; i <= n; i++) {
int d, k, c;
cin >> d >> k >> c;
if((LL)k * r > c) {
cards.emplace_back(d, k, c);
}
}
map
for(int i = 1; i <= m; i++) {
int p, q;
cin >> p >> q;
rents[p] = q;
}
vector
map
for(auto [key, val] : rents) {
st_idx[key] = days.size();
while(val--) {
days.push_back(key);
}
}
st_idx[1000000001] = days.size();
vector
dp.assign(days.size(), numeric_limits
dp[0] = 0;
auto update = [] (LL &u, LL v) {
if(u > v) u = v;
};
for(size_t i = 0; i < dp.size() - 1; i++) {
update(dp[i + 1], dp[i] + r);
for(const auto &[d, k, c] : cards) {
size_t j = min(i + k, dp.size() - 1);
if(days[j] - days[i + 1] >= d) {
j = st_idx.lower_bound(days[i + 1] + d)->second - 1;
}
update(dp[j], dp[i] + c);
}
}
cout << dp.back() << "\n";
return 0;
}
M. United in Stormwind题目里要求 $n$ 个人中答案不同的无序对至少有 $k$ 个，这等价于答案相同的有序对至多 $n^2 - 2k$ 个。
由于每道题的选项只有两种，不妨把 A 看作 $0$，B 看作 $1$，那么对于两个答案分别为 $x$ 和 $y$ 的人来说，其答案相同的题目集为
$$
x \odot y
$$其中 $\odot$ 表示二进制同或（XNOR）运算。
记全体题目的集合为 $P$，我们可以统计每个人的答案，将其写成集合幂级数
$$
F(x) = \sum_{n \subset P} a_n x^n
$$那么 $F$ 和自身做同或卷积
$$
(F * F) (x) = \sum_{m, n \subset P} a_m a_n x^{m \odot n}
$$所得的结果的系数 $[x^s](F * F)$ 就是答案相同的问题集合恰好为 $s$ 的有序对的个数，而我们要求的实际上就是有多少个集合 $S \subset P$ 满足
$$
\sum_{S \subset T \subset P} [x^T](F * F) \leq n^2 - 2k
$$同或卷积可以由 FWT 求出，而后半部分的对超集求和可以通过逐元素枚举求出。两部分的时间复杂度均为 $O(m 2^m)$。
对于同或卷积，乃至于更加一般的二元运算的 FWT 变换矩阵的构造，可以参考 LOJ 548 的官方题解。
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
using namespace std;
using LL = long long;
void DFT(LL *A, int n, bool rev = false) {
if(n == 1) {
return;
}
int half = n / 2;
DFT(A, half, rev);
DFT(A + half, half, rev);
for(int i = 0; i < half; i++) {
LL u = A[i], v = A[half + i];
if(!rev) {
A[i] = u + v;
A[half + i] = -u + v;
} else {
A[i] = (u - v) / 2;
A[half + i] = (u + v) / 2;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
LL k;
cin >> n >> m >> k;
k = (LL)n * n - k * 2;
vector
for(int i = 1; i <= n; i++) {
string answer;
cin >> answer;
for(char &c : answer) {
c = (c == 'A') ? '0' : '1';
}
A[stoi(answer, 0, 2)]++;
}
DFT(A.data(), 1 << m);
for(LL &cur : A) {
cur = cur * cur;
}
DFT(A.data(), 1 << m, true);
for(int j = 0; j < m; j++) {
for(int i = (1 << m) - 1; i >= 0; i--) {
if((i >> j) & 1) {
A[i ^ (1 << j)] += A[i];
}
}
}
cout << count_if(A.begin(), A.end(), [&](LL u) { return u <= k; }) << "\n";
return 0;
}
C. Mean Streets of Gadgetzan由于每一个推断的条件都是正向的，所以当没有任何强制赋值的情况下全赋 False 显然是合法的。
我们可以通过 BFS 确定所有可确定的赋值，然后对其他的全部赋 False。
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
#include
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
cin.get();
vector
vector
vector
vector
// -1 -> conflict, 2 -> unchanged, 0/1 -> modified to 0/1
function
if(str[0] == '!') {
str[0] = '-';
}
int pos = stoi(str);
int val = pos > 0;
pos = abs(pos);
if(value[pos - 1] == (val ^ 1)) {
return -1;
}
if(value[pos - 1] == val) {
return 2;
}
return value[pos - 1] = val;
};
for(int i = 0; i < n; i++) {
string str;
getline(cin, str);
stringstream ss;
ss << str;
vector
while(ss >> str) {
items.push_back(str);
}
if(items.size() == 1) {
if(set_value(items[0]) == -1) {
puts("conflict");
return 0;
}
} else {
bool flag = false;
for(const string &s : items) {
if(s == "->") {
flag = true;
} else if(flag) {
consequence[i] = s;
} else {
in_conditions[stoi(s) - 1].push_back(i);
conditions_left[i]++;
}
}
}
}
queue
for(int i = 0; i < m; i++) {
if(value[i] == 1) {
que.push(i);
}
}
while(!que.empty()) {
int u = que.front();
que.pop();
for(int x : in_conditions[u]) {
if(--conditions_left[x] == 0) {
int ret = set_value(consequence[x]);
if(ret == -1) {
puts("conflict");
return 0;
}
if(ret == 1) {
que.push(stoi(consequence[x]) - 1);
}
}
}
}
for(int v : value) {
putchar(v == 1 ? 'T' : 'F');
}
return 0;
}
年后的第一次训练。开场 10min 不到队友 A 急性胃病发作去了医院，随后队友 B 也因为近期心态不好在和我一同做出 F 写过之后选择开摆。
只剩我一人也得硬着头皮打，没办法只能跟榜。所幸一路跟下来 DIKH 全是简单题，读完题就会做的那种，M 也是正好装在我技能歪脖子树上的 FWT。就这么莫名其妙三个半小时（几乎）单挑过了 7 题。
过了 M 之后打算继续做 C，又过了 10min 队友 A 从医院回来了，大致合计出做法之后我有点累就把代码扔给他写睡觉去了。
打完一看，8 题 1045 罚时，场内榜第八。这 tm 还是我几乎全程单挑的结果。只能说要不是当年一心想着死磕上海站说不定两年前我们就能去 WF 了（
补题记录咕