【题解】Google Kick Start

老年人做点笔试题算了。

注:一切以 Hard 模式为准。

写在最前

文件头

有点长,就不重复贴了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cout << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
// -----------------------------------------------------------------------------

2019

Round E

Cherries Mesh

最小生成树。需要的边的条数是 n-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
const int N = 1e5 + 100;

int fa[N];
int findset(int x) { return fa[x] == -1? x : fa[x] = findset(fa[x]); }

int solve() {
int n, m; cin >> n >> m;
fill(fa, fa + n + 1, -1);
int cnt = 0;
FOR (_, 0, m) {
int u, v; scanf("%d%d", &u, &v);
int fu = findset(u), fv = findset(v);
if (fu != fv) {
++cnt;
fa[fu] = fv;
}
}
return 2 * (n - 1) - cnt;
}

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: %d\n", Ca, solve());
}
}

Code-Eat Switcher

判断点是否在凸包内。先不考虑把一个 time slot 分割的情况,肯定是按照某一方(比如 coding)的性价比排序,然后一侧全是 coding,另一侧全是 eating。每一个分界线的位置对应一个点,考虑所有点,把相邻的连起来,就是所有最优解构成的凸包。剩下的问题就是如何判断一个点是否在凸包内了,找出这个点 x 轴上附近的两个点(二分搜索),看是否在那两个点构成的直线的下方(叉积判正负)。

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
const int N = 1e5 + 100;
struct P {
LL c, e;
};
P p[N];

bool test(const P& a, const P& b, LL c, LL e) {
LL ax = a.c - c, ay = a.e - e;
LL bx = b.c - c, by = b.e - e;
return ax * by - bx * ay <= 0;
}

void solve() {
int D, S; cin >> D >> S;
FOR (i, 0, S) scanf("%lld%lld", &p[i].c, &p[i].e);
sort(p, p + S, [](const P& a, const P& b) {
return a.c * b.e > a.e * b.c;
}); // coding up, eating down
LL se = 0, sc = 0;
FOR (i, 0, S) se += p[i].e;
vector<P> c; c.push_back({sc, se});
FOR (i, 0, S) {
se -= p[i].e; sc += p[i].c;
c.push_back({sc, se});
}

FOR (i, 0, D) {
LL qe, qc; scanf("%lld%lld", &qc, &qe);
auto it = lower_bound(c.begin(), c.end(), P{qc, qe}, [](const P& a, const P& b) {
return a.c < b.c;
});
if (it == c.end()) { putchar('N'); continue; }
if (it == c.begin()) { putchar(it->e >= qe ? 'Y' : 'N'); continue; }
auto l = it, r = it;
--l;
putchar(test(*l, *r, qc, qe) ? 'Y' : 'N');
}
puts("");
}

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

Street Checker

数论题,求 [L, R] 区间内有多少数字的奇因子个数和偶因子个数差的绝对值不超过 2。

为了寻找满足要求的数,考虑一个数的 2 因子个数:

  • 如果个数为 0:那么这个数必须是素数,有且仅有两个奇因子。
  • 如果个数为 1:那么所有的奇因子乘 2 之后就能刚好对应一个偶因子,数量相等,满足要求。
  • 如果个数为 2:那么偶因子的数量是奇因子的两倍,奇因子数量可以为 1 或者 2,2 的时候这个数就是素数的 4 倍,1 的时候就是 4。
  • 如果个数为 3:那么这个数就是 8。

唯一的难点就是怎么求一个区间范围内的素数,方法是用 $\sqrt R$ 内的素数去筛。

注:一开始把 $R - L \le 10^5$ 看成 Test Set 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
const LL p_max = 1E6 + 100;
LL pr[p_max], p_sz;
void get_prime() {
static bool vis[p_max];
FOR (i, 2, p_max) {
if (!vis[i]) pr[p_sz++] = i;
FOR (j, 0, p_sz) {
if (pr[j] * i >= p_max) break;
vis[pr[j] * i] = 1;
if (i % pr[j] == 0) break;
}
}
}

const int N = 1E5 + 100;
bool f[N];
set<LL> S;

void count(LL L, LL R, LL multiplier = 1) {
if (L > R) return;
fill(f, f + R - L + 1, true);
FOR (i, 0, p_sz) {
LL p = pr[i];
if (p * p > R) break;
FOR (j, max((L + p - 1) / p, 2LL), R / p + 1) {
f[j * p - L] = false;
}
}
FOR (i, L, R + 1) if (f[i - L]) S.insert(i * multiplier);
}

void solve() {
S.clear();
LL L, R; cin >> L >> R;
count(L, R);
FOR (i, L, R + 1) if ((i & 3) == 2) S.insert(i);
count((L + 3) / 4, R / 4, 4);
if (L <= 4 && 4 <= R) S.insert(4);
if (L <= 8 && 8 <= R) S.insert(8);
dbg(S);
cout << S.size() << endl;
}


int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
get_prime();
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

Round F

Flattening

$f[i][k]$ 表示前 $i$ 个数中相邻不同的数量不超过 $k$ 的最少操作数,有转移式 $f[i][k] = \min_{j<i} f[j][k -1]+m(j+1,i)$,其中 $m(l, r)$ 表示把 $l$ 和 $r$ 之间的 $a[i]$ 变为相同需要的最小数,可以线性预处理。

还有一种思维复杂度和时间复杂度更高的做法,$f[i][k][last]$ 表示前 $i$ 个数相邻不同的数量小于 $k$ 且修改后 $a[i]$ 的值是 $last$ 的最小操作数,转移就有点复杂了。

官方题解中有一个观察,修改操作可以用删除替换,不过好像区别不大?官方题解中还提供了一种复杂度更低的做法,二分答案,然而我并不知道怎么判是否可行(我看了差不多十份代码也没找到用二分的)。

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
const int N = 100 + 5, M = 1000 + 5;
int a[N], f[N][N];
int d[M], m[N];

void up(int& x, int y) { x = min(x, y); }

void solve() {
int n, K; cin >> n >> K;
FOR (i, 0, n) scanf("%d", a + i);
memset(f, 0x3f, sizeof f);
FOR (i, 0, K + 1) f[0][i] = 0;
FOR (i, 1, n) {
int _m = 0;
FORD (j, i, -1) {
_m = max(_m, d[a[j]]++);
m[j] = (i - j) - _m;
}
FOR (j, 0, i + 1) --d[a[j]];
f[i][0] = m[0];
FOR (k, 1, K + 1) {
f[i][k] = f[i][k - 1];
FOR (j, 0, i)
up(f[i][k], f[j][k - 1] + m[j + 1]);
}
}
printf("%d\n", f[n - 1][K]);
}

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

Teach Me

考虑问题的反面,有多少对不能 mentor。对于一个人 x,y 不能 mentor 他的充要条件是 y 是 x 的子集。然后枚举子集,哈希后用 map 统计一下就好了。

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
const int N = 5E4 + 100;
map<LL, int> mp;

void solve() {
mp.clear();
vector<LL> a, x;

int n, S; cin >> n >> S;
FOR (i, 0, n) {
x.clear();
int k; scanf("%d", &k);
FOR (_, 0, k) { int t; scanf("%d", &t); x.push_back(t); }
sort(x.begin(), x.end());
FOR (j, 1, 1 << x.size()) {
LL v = 0;
FOR (k, 0, x.size()) if ((j >> k) & 1) v = v * 1001 + x[k];
++mp[v];
if (j == (1 << x.size()) - 1) a.push_back(v);
}
}
LL ans = 0;
for (LL& v: a) ans += n - mp[v];
cout << ans << endl;
}

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

Spectating Villages

经典树形 DP,f[u][0~2] 表示 u 这个节点:

  • 0 - 自己没选:可以从子节点的 0 或者 1 状态转移,无额外约束。
  • 1 - 被子节点选了:可以从子节点的 0 或者 1 或者 2 转移过来,但至少有一个 2。这个稍微有点 trick,先求出 012 状态的最大值以及从 012 坍缩成 2 的最小损失,计算时两者相减就好了。
  • 2 - 自己选了并导致父亲也要被选:从子节点 0 或者 1 或者 2 转移过来,0 需要额外累加该子节点权重。
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
const int N = 1e5 + 100;

int w[N];
vector<int> G[N];
LL f[N][3]; // 0 - 自己没选,1 - 被子节点选了,2 - 自己选了,导致父节点也被选

void go(int u, int fa) {
LL sum = 0, m1 = 1e18;
f[u][2] = w[u];
for (int& v: G[u]) {
if (v == fa) continue;
go(v, u);
LL s = max(f[v][0], max(f[v][1], f[v][2]));
m1 = min(m1, s - f[v][2]);
sum += s;
f[u][2] += max(f[v][0] + w[v], max(f[v][1], f[v][2]));
f[u][0] += max(f[v][0], f[v][1]);
}
f[u][1] = sum - m1 + w[u];
dbg(u, f[u][0], f[u][1], f[u][2]);
}

LL solve() {
int n; cin >> n;
FOR (i, 0, n + 1) {
f[i][0] = 0;
f[i][1] = f[i][2] = -1e18;
G[i].clear();
}

FOR (i, 1, n + 1) scanf("%d", w + i);
FOR (_, 1, n) {
int u, v; scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}

go(1, -1);
return *max_element(f[1], f[1] + 3);
}

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: %lld\n", Ca, solve());
}
}

Round G

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e02

Book Reading

考虑被撕掉的每一页,当询问是页数的因数时会减少对答案的贡献。预处理每个数的因数,统计一下就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N = 1E5 + 100;
vector<int> a[N];
int c[N], d[N];

int main() {
FOR (i, 1, N)
for (int j = i; j < N; j += i)
a[j].push_back(i);
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
int n, m, Q; cin >> n >> m >> Q;
FOR (i, 0, m) scanf("%d", d + i);
FOR (i, 0, m) for (int t: a[d[i]]) ++c[t];
LL ans = 0;
FOR (_, 0, Q) {
int x; scanf("%d", &x);
ans += n / x - c[x];
}
printf("%lld\n", ans);
FOR (i, 0, m) for (int t: a[d[i]]) --c[t];
}
}

The Equation

从高到低枚举答案二进制的每一位,如果枚举到的这一位能是 1,那么就放 1,否则只能放 0。判断某一位是不是能放 1,只要让剩下的那些没确定的位放最优(也就是能让异或和结果尽可能小的),再判断是否满足条件即可。

注意数据范围,不要在运算过程中爆 long long。

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
const int N = 1000 + 100, C = 50;
LL c[C], d[C];

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
memset(c, 0, sizeof c);
printf("Case #%d: ", Ca);
LL n, M; scanf("%lld%lld", &n, &M);
FOR (_, 0, n) {
LL t; scanf("%lld", &t);
FOR (i, 0, C) if ((t >> i) & 1) ++c[i];
}
FOR (i, 0, C) d[i] = min(c[i], n - c[i]) << i;
FOR (i, 1, C) d[i] += d[i - 1];
if (d[C - 1] > M) { puts("-1"); continue; }
LL ans = 0, S = 0;
FORD (i, C - 1, -1) {
if (S + ((n - c[i]) << i) + (i ? d[i - 1] : 0) <= M) {
ans += 1LL << i;
S += (n - c[i]) << i;
} else S += c[i] << i;
}
assert(S <= M);
printf("%lld\n", ans);
}
}

Shifts

$O(3^{20})$ 显然不怎么行,考虑两边相遇。分别处理 $O(3^{10})$,把每种组合看成坐标的一个点,对于左边的每一个点,需要知道在右边的某个矩形里的点的个数。做法就是按照一维排序,另一维用数据结构维护,代码中用了 pb_ds 里的平衡树,离散化用树状数组或者用 cdq 分治也行。

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
const int N = 20 + 10;
using VLL = vector<pair<LL, LL>>;
VLL L, R;
pair<LL, LL> a[N];

void go(const VLL& a, pair<LL, LL> s, VLL& ret, int k) {
if (k == a.size()) { ret.push_back(s); return; }
go(a, {s.first + a[k].first, s.second + a[k].second}, ret, k + 1);
go(a, {s.first, s.second + a[k].second}, ret, k + 1);
go(a, {s.first + a[k].first, s.second}, ret, k + 1);
}

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using Tree = tree<pair<LL, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
Tree t;

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
L.clear(); R.clear(); t.clear();
int n; LL H;
cin >> n >> H;
FOR (i, 0, n) scanf("%lld", &a[i].first);
FOR (i, 0, n) scanf("%lld", &a[i].second);
go(VLL(a, a + n / 2), {0, 0}, L, 0);
go(VLL(a + n / 2, a + n), {0, 0}, R, 0);
sort(L.begin(), L.end());
sort(R.begin(), R.end(), greater<>());
LL k = 0, ans = 0;
int clk = 0;
for (auto& x: L) {
while (k < R.size() && R[k].first + x.first >= H) t.insert({R[k++].second, clk++});
ans += k - t.order_of_key({H - x.second, -1});
}
cout << ans << endl;
}
}

Round H

H-Index

方法1:无脑模拟,相比起方法2代码复杂度高了一些,但是思维复杂度很低。需要有一个支持边插入边查询求第 K 大,或者求小于某个数的数量的数据结构。代码中使用了树状数组。

方法2:不需要高级数据结构的做法,搞一个普通平衡树或者优先队列(小根堆),维护属于 H-Index 内的东西,如果偏小则略过,较大则插入并根据情况增加 H-Index 并删除较小的部分。

方法3:题解里说可以线性。想了想,只需要把方法2中的优先队列改成数组或者哈希表就好了。

方法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
const int M = 1e5 + 100;
namespace bit {
LL c[M];
inline int lowbit(int x) { return x & -x; }
void add(int x, LL v) {
for (int i = x; i < M; i += lowbit(i))
c[i] += v;
}
LL sum(int x) {
LL ret = 0;
for (int i = x; i > 0; i -= lowbit(i))
ret += c[i];
return ret;
}
}

void solve() {
int n; cin >> n;
int h = 0;
vector<int> history;
FOR (i, 0, n) {
int v; scanf("%d", &v);
history.push_back(v);
bit::add(v, 1);
while (i + 1 - bit::sum(h) >= h + 1) h += 1;
printf("%d ", h);
}
for (int& v: history) bit::add(v, -1);
puts("");
}

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

方法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve() {
int n; cin >> n;
int h = 0;
priority_queue<int, vector<int>, greater<>> pq;
FOR (i, 0, n) {
int v; scanf("%d", &v);
if (v > h) pq.push(v);
h += pq.size() > h;
while (!pq.empty() && pq.top() <= h) pq.pop();
printf("%d ", h);
}
puts("");
}

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

方法3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve() {
int n; cin >> n;
int h = 0, sz = 0, cur = 0;
unordered_map<int, int> mp;
FOR (i, 0, n) {
int v; scanf("%d", &v);
if (v > h) { mp[v] += 1; ++sz; }
if (sz > h) sz -= mp[++h];
printf("%d ", h);
}
puts("");
}

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

Diagonal Puzzle

考虑这样一种转化,每一条对角线作为方程的一个未知量,如果翻转就是 1,不操作就是 0。对于每一个格子,如果当前是黑色的,那么对应的两条对角线对应的变量异或和为 0(也就是要么都取要么都不取),如果是白色,那么异或和为 1(必须一个取一个不取)。

对于大小为 n * n 的方阵,得到了一组未知数个数为 2 * (2 * n - 1),方程个数为 n * n 的异或方程组,最后需要在解空间内最小化所有未知量之和。

方法 2:如果光是求解的话,可以用 2-SAT 解决,现在需要最小化操作数。对于每一对强连通分量有两种选择,选择操作数较少的那种就好了。

方法 1:需要额外的观察,但不需要什么算法,实现起来也容易很多。这个方程组有一个特点,就是方程个数远大于未知数个数,如果假设其中某个(或者若干个)未知数的解的话,其它的未知数也迎刃而解,只需要考虑有没有矛盾就可以了。可以假定的未知量有很多,最合适的就是最长的对角线以及次长的对角线(同一方向),然后发现所有反向的对角线是否需要翻转就确定了,然后再检查一下光靠同向的其他对角线能否达到题目要求就行了,如果可以的话记录一下操作数。

方法 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
const int N = 100 * 2 + 5, INF = 1e5;
bool G[N][N];
bool GG[N][N];
char s[N];

int fix(int n, int x, int y) {
int cnt = 0, sum = 0;
while (x < n && y < n) {
cnt += 1; sum += G[x][y];
++x; ++y;
}
if (cnt == sum) return 0;
if (sum == 0) return 1;
return INF;
}

void flip(bool& f) { f = !f; }

int check(int n, int op1, int op2) {
memcpy(G, GG, sizeof G);
int ans = op1 + op2;
FOR (i, 0, n) {
if (op1) flip(G[i][i]);
if (!G[i][i]) {
++ans;
FOR (j, 0, i + i + 1) {
flip(G[j][i + i - j]);
}
}
}
FOR (i, 0, n - 1) {
if (op2) flip(G[i][i + 1]);
if (!G[i][i + 1]) {
++ans;
FOR (j, 0, i + i + 2) {
flip(G[j][i + i + 1 - j]);
}
}
}
FOR (i, 0, n) ans += fix(n, i, 0) + fix(n, 0, i);
return ans;
}

void solve() {
int n; cin >> n;
FOR (i, 0, n) {
scanf("%s", s);
FOR (j, 0, n) GG[i][j] = s[j] == '#';
}
int ans = INF;
FOR (op1, 0, 2) FOR (op2, 0, 2) ans = min(ans, check(n, op1, op2));
cout << ans << endl;
}

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

方法2

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
const int N = 100 * 2 * 2 * 2 + 10;
vector<int> G[N], rG[N], vs;
int used[N], cmp[N];

void add_edge(int from, int to) {
G[from].push_back(to);
rG[to].push_back(from);
}

void dfs(int v) {
used[v] = true;
for (int u: G[v]) {
if (!used[u])
dfs(u);
}
vs.push_back(v);
}

void rdfs(int v, int k) {
used[v] = true;
cmp[v] = k;
for (int u: rG[v])
if (!used[u])
rdfs(u, k);
}

int scc(int n) {
memset(used, 0, sizeof(used));
vs.clear();
for (int v = 0; v < n; ++v)
if (!used[v]) dfs(v);
memset(used, 0, sizeof(used));
int k = 0;
for (int i = (int) vs.size() - 1; i >= 0; --i)
if (!used[vs[i]]) rdfs(vs[i], k++);
return k;
}

char s[N];
int ans[N * 8], cnt[N * 8];
void solve() {
int n; cin >> n;
FOR (i, 0, n * 8) {
G[i].clear(); rG[i].clear();
}
// i, j
// /: (i + j) * 2 ^ ?
// \: (i - j + 3 * n) * 2 ^ ?
FOR (i, 0, n) {
scanf("%s", s);
FOR (j, 0, n) {
int u = (i + j) * 2, v = (i - j + 3 * n) * 2;
if (s[j] == '#') {
add_edge(u, v); add_edge(u ^ 1, v ^ 1);
add_edge(v, u); add_edge(v ^ 1, u ^ 1);
} else {
add_edge(u, v ^ 1); add_edge(u ^ 1, v);
add_edge(v, u ^ 1); add_edge(v ^ 1, u);
}
}
}
int k = scc(n * 8);
dbg(k);
memset(ans, 0, sizeof ans); memset(cnt, 0, sizeof cnt);
FOR (i, 0, n * 8) if (i % 2 == 0) {
if (G[i].empty()) continue;
assert(cmp[i] != cmp[i ^ 1]);
int kk = min(cmp[i], cmp[i ^ 1]);
dbg(i, cmp[i], cmp[i + 1]);
cnt[kk] += 1;
ans[kk] += cmp[i] > cmp[i ^ 1];
}
int res = 0;
FOR (i, 0, k) {
res += min(ans[i], cnt[i] - ans[i]);
}
cout << res << endl;
}

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

Elevanagram

我看了题解才知道大数据怎么做,虽然,明明是我擅长的数论。另外我觉得很奇怪,明明比第二题更难,而且分值更好,通过的人却比第二题多。

对于小数据:直接 dp,dp[i][delta][m] 表示前 i 个数字,取正和取负的数量差为 delta,这些数的和模 11 的余数是 m 是否可能。

对于大数据:显然需要一些观察,对于特定的情况(或者说自由度很高的情况),可以直接判为可行。一个条件就是任意两个数字数量都大于等于 10。证明也很简单,先让一个数字全正,另一个全负,然后一次次交换正负号,总共能操作 11 次。而两个数之差的两倍一定是与 11 互素的,所以一定会有余数为 0 的状态。这样的话,可能一个数字特别多,别的都小于 10,对于特别多的数字特别考虑一下。
题解中引入了三个数字的观察,使得可以不依赖 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
const int K = 10, M = 11, D = 20 * 10 + 10;
LL a[K];
bool f[K][D * 2][M];
bool solve() {
memset(f, 0, sizeof f);
FOR (i, 1, K) {
scanf("%lld", a + i);
}
LL s = accumulate(a, a + K, 0LL);
f[0][D][0] = true;
FOR (i, 1, K) {
FOR (j, 0, a[i] + 1) {
int delta = j - (a[i] - j);
FOR (d, 0, D * 2) if (0 <= d + delta && d + delta < D * 2) {
FOR (m, 0, M) {
f[i][d + delta][(m + (delta + 1111) * i) % 11] |= f[i - 1][d][m];
}
}
}
}
return f[K - 1][(s & 1) + D][0];
}

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
puts(solve() ? "YES" : "NO");
}
}

大数据

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
const int K = 10, M = 11, D = 20 * 10 + 10;
struct P { int v; int cnt; };
bool f[K][D * 2][M];
bool solve() {
memset(f, 0, sizeof f);
vector<P> p;
LL sum = 0;
FOR (i, 1, K) {
int t; scanf("%d", &t); sum += t;
p.push_back({i, t});
}
sort(p.begin(), p.end(), [](const P& a, const P& b){
return a.cnt > b.cnt;
});
if (p[1].cnt >= 10) return true;

f[0][D][0] = true;
FOR (i, 1, p.size()) {
FOR (j, 0, p[i].cnt + 1) {
int delta = j - (p[i].cnt - j);
FOR (d, 0, D * 2) if (0 <= d + delta && d + delta < D * 2) {
FOR (m, 0, M) {
f[i][d + delta][(m + (delta + 1111) * p[i].v) % 11] |= f[i - 1][d][m];
}
}
}
}

FOR (d, 0, D * 2) {
int dd = d - D + (sum & 1);
if (abs(dd) > p[0].cnt || (p[0].cnt + abs(dd)) % 2 != 0) continue;
if (f[p.size() - 1][d][(1111 + dd * p[0].v) % 11]) return true;
}
return false;
}

int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
puts(solve() ? "YES" : "NO");
}
}

2021

Round B

这场参加了,Rank 57。

Increasing Substring

题意:求字符串的最长严格上升子串。

题解:从头到尾扫一遍,如果满足严格递增就答案 +1,否则答案归 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve() {
int n; cin >> n;
string s; cin >> s;
int last = 33, ans = 0;
FOR (i, 0, n) {
int c = s[i] - 'A';
if (c <= last) ans = 1;
else ++ans;
last = c;
printf("%d%c", ans, i == _i - 1 ? '\n' : ' ');
}
}

int main() {
#ifdef zerol
freopen("in.txt", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

Longest Progression

题意:给定一个数组,至多替换一个元素,求可能的最长的等差数列的长度。

题解:只考虑差分数组,原来的修改操作相当于可以改相邻的两个元素(但是和必须不变),或者单独修改首尾元素,目标是使得数组中连续的相同数字最长。预处理一下每个位置向前和向后的最长相同元素长度,然后考虑对于每一对位置的修改,如果对答案有提升,肯定是把相邻的两个元素变为相同(因此元素和必须能被 2 整除),然后看一看向前向后能接多长(利用预处理的结果)。

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
const int N = 3e5 + 100;
LL a[N];
int f[N], rf[N];

void solve() {
int n; cin >> n;
FOR (i, 0, n) scanf("%lld", a + i);
--n;

FOR (i, 0, n) a[i] -= a[i + 1];
f[0] = 1;
FOR (i, 1, n) f[i] = a[i] == a[i - 1] ? f[i - 1] + 1 : 1;
rf[n - 1] = 1;
FORD (i, n - 2, -1) rf[i] = a[i] == a[i + 1] ? rf[i + 1] + 1 : 1;

int ans = *max_element(f, f + n);
if (ans < n) ++ans;

FOR (i, 0, n - 1) {
LL t = a[i] + a[i + 1];
if (t % 2 != 0) continue;
t /= 2;
int cur = 2;
if (i - 1 >= 0 && t == a[i - 1]) {
cur += f[i - 1];
}
if (i + 2 < n && t == a[i + 2]) {
cur += rf[i + 2];
}
ans = max(ans, cur);
}
cout << ans + 1 << endl;
}

int main() {
#ifdef zerol
freopen("in.txt", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

Consecutive Primes

题意:求不超过给定数字的,是相邻两个素数之积的最大的数。

题解:对于给定的数字 $Z$,考虑 $a < b < \sqrt Z \le c$,其中 $a, b, c$ 为相邻的素数,如果 $b \cdot c \le Z$,那么答案就是 $b \cdot c$,否则就是 $a \cdot b$。

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
bool check(LL x) {
FOR (i, 2, int(sqrt(x + 0.5)) + 1) {
if (x % i == 0) return false;
}
return true;
}


void solve() {
LL x; cin >> x;
LL o = sqrt(x + 0.5);
LL t1 = o;
while (!check(t1)) --t1;
LL t2 = t1 - 1;
while (!check(t2)) --t2;
++o;
while (!check(o)) ++o;
if (o * t1 <= x) cout << o * t1 << endl;
else cout << t1 * t2 << endl;
}

int main() {
#ifdef zerol
freopen("in.txt", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

Truck Delivery

题意:给一棵树,每条边都有一个 $L_i$ 和 $A_i$,然后很多次询问,需要回答从节点 1 到给定节点(必须简单路径),载货量为 $W$,支付的若干费用的 GCD(如果没支付过,记为 0)。费用是指,经过 $L_i < W$ 的边时,需要支付 $A_i$。

题解:离线计算,把边和询问按照 $L$ 和 $W$ 放在一起从小到大排序,按顺序加边或者回答询问。问题转换成了需要有个东西,支持加边,询问一个点到树根的路径边权的 GCD。再转化一下就是,支持给一棵子树批量 GCD 上一个东西,然后求一个点的值。配合 DFS 序,问题就成了区间 GCD,单点查询,然后就线段树了。

这题很没意思(套路题 + 模板题),kick start 不应该出这种题。

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
const int N = 1e5 + 100;
vector<int> G[N];
int clk = 0;
int fa[N];
int in[N], out[N];
int n;

const int maxn = N;
namespace sg {
struct Q {
LL setv;
explicit Q(LL setv = 0): setv(setv) {}
void operator += (const Q& q) { setv = __gcd(setv, q.setv); }
};
struct P {
LL g;
explicit P(LL g = 0): g(g) {}
void up(Q& q) { g = __gcd(g, q.setv); }
};
template<typename T>
P operator & (T&& a, T&& b) {
return P(__gcd(a.g, b.g));
}
P p[maxn << 2];
Q q[maxn << 2];
#define lson o * 2, l, (l + r) / 2
#define rson o * 2 + 1, (l + r) / 2 + 1, r
void up(int o, int l, int r) {
if (l == r) p[o] = P();
else p[o] = p[o * 2] & p[o * 2 + 1];
p[o].up(q[o]);
}
void down(int o, int l, int r) {
q[o * 2] += q[o]; q[o * 2 + 1] += q[o];
q[o] = Q();
up(lson); up(rson);
}
template<typename T>
void build(T&& f, int o = 1, int l = 1, int r = n) {
if (l == r) q[o] = f(l);
else { build(f, lson); build(f, rson); q[o] = Q(); }
up(o, l, r);
}
P query(int ql, int qr, int o = 1, int l = 1, int r = n) {
if (ql > r || l > qr) return P();
if (ql <= l && r <= qr) return p[o];
down(o, l, r);
return query(ql, qr, lson) & query(ql, qr, rson);
}
void update(int ql, int qr, const Q& v, int o = 1, int l = 1, int r = n) {
if (ql > r || l > qr) return;
if (ql <= l && r <= qr) q[o] += v;
else {
down(o, l, r);
update(ql, qr, v, lson); update(ql, qr, v, rson);
}
up(o, l, r);
}
}

void dfs(int u, int f) {
fa[u] = f; in[u] = ++clk;
for (auto& v: G[u]) {
if (v == f) continue;
dfs(v, u);
}
out[u] = clk;
}
struct P { int u, v, l; LL a; };
vector<P> edges;
struct Q { int idx, c, w; };
vector<Q> queries;
LL ans[N];

void solve() {
int Qn; cin >> n >> Qn;
FOR (i, 0, n + 1) G[i].clear();
edges.clear(); queries.clear(); clk = 0;
FOR (_, 1, n) {
int u, v, l; LL a; scanf("%d%d%d%lld", &u, &v, &l, &a);
G[u].push_back(v);
G[v].push_back(u);
edges.push_back({u, v, l, a});
}
dfs(1, -1);
assert(clk == n);
sort(edges.begin(), edges.end(), [](const P& a, const P& b){ return a.l < b.l; });
FOR (i, 0, Qn) {
int c, w; scanf("%d%d", &c, &w);
queries.push_back({i, c, w});
}
sort(queries.begin(), queries.end(), [](const Q& a, const Q& b){ return a.w < b.w; });
int cur = 0;
sg::build([](int){ return sg::Q(); });
for (Q& q: queries) {
while (cur < edges.size() && edges[cur].l <= q.w) {
auto& e = edges[cur++];
if (fa[e.u] != e.v) swap(e.u, e.v);
sg::update(in[e.u], out[e.u], sg::Q(e.a));
dbg("upd", in[e.u], out[e.u], e.a);
}
ans[q.idx] = sg::query(in[q.c], in[q.c]).g;
dbg("query", q.idx, in[q.c], ans[q.idx]);
}
FOR (i, 0, Qn) printf("%lld%c", ans[i], i == _i - 1 ? '\n' : ' ');
}

int main() {
#ifdef zerol
freopen("in.txt", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

Round C

这场参加了,第三题只做了 Test Set 1,Rank 60。

Smaller Strings

题意:给定一个字符集大小 K 和一个字符串,问字典序小于这个字符串的回文串的数量。

题解:考虑原始字符串的前半部分和后半部分,前半部分严格小于的回文串肯定符合条件,这部分统计类似于算 K 进制数。如果前半部分相同的情况下,只有后半部分比前半部分大才行。

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
const LL MOD = 1e9 + 7;
const int N = 1e5 + 100;
char s[N], ss[N];

void solve() {
int n, k; cin >> n >> k >> s;
int m = (n + 1) / 2;
FOR (i, 0, m) {
ss[i] = ss[n - 1 - i] = s[i];
}
bool f = strcmp(ss, s) >= 0;
LL ans = 0;
FOR (i, 0, m) {
dbg(i, s[i] - 'a');
ans = ans * k + (s[i] - 'a');
ans %= MOD;
}
cout << (ans + 1 - f) % MOD << endl;
}

int main() {
#ifdef zerol
freopen("in.txt", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

Alien Generator

题意:求有多少种的连续自然数之和恰好为 $G$。

题解:枚举连续自然数的项数就行了,项数一定是 $2G$ 的因数。

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
int ans = 0;

void check(LL x, LL k) {
LL u = x / k + 1 - k;
if (u >= 1 && u % 2 == 0) {
ans += 1;
}
}

void solve() {
LL x; cin >> x;
// x / n * 2 = k + k + n - 1
ans = 0;
x *= 2;
FOR (i, 1, LL(sqrt(x + 0.5) + 1)) {
if (i * i == x) {
check(x, i);
} else if (x % i == 0) {
check(x, i); check(x, x / i);
}
}
cout << ans << endl;
}

int main() {
#ifdef zerol
freopen("in.txt", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

Rock Paper Scissors

题意:石头剪刀布的交互题,题意有些复杂。每一天的得分规则不同,赢了得 W 分,平了得 E 分,其中 E 有四种可能的取值,为 $W, W / 2, W / 10, 0$。对手的策略是已知的,它出石头、剪刀、布的概率之比为那天之前你出的剪刀、布、石头的次数的比例,特别地,第一天视为等概率。目标是 200 天后(每天都是独立的),期望收益超过某个定值。

这题翻车了,我认定这是我擅长的构造题,四种情况分类讨论一下,然后凑出一个足够优的策略就好了。然后题意没读清楚把自己坑了,然后又凑了一通也没凑出来,最后只过了 Test Set 1。过 Test Set 1 的方案很简单,每天按照石头、剪刀、布的顺序出就行了。赛后看了题解,惊了,这竟然是 DP 题???

官方题解 for Test Set 2:随机生成策略,用随机优化算法来找到一个足够好的。

官方题解 for Test Set 3:$f[a][b][c]$ 为第 $a+b+c$ 天石头剪刀布分别出了 $a, b, c$ 次的最佳期望收益,最后把最优路径输出来就好了,状态转移也很简单。

其实四种情况的 DP 得到的某个最优解长这样,凭空构造还是太难了。

1
2
3
4
RSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSPRSP
SPPPPRRRRRRRRRRRRRRRSSSSSSSSSSSSSSSSSSSSSSSSSPPPPPPPPPPPPPPP
PRRRRRRRRRSSSSSSSSSSSSSSSSSSSSSSSSSSSPPPPPPPPPPPPPPPPPPPPPPP
PRRSSSSPPPPPPPPRRRRRRRRRRRRRRRRSSSSSSSSSSSSSSSSSSSPPPPPPPPPP

代码如下,包含 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
const int N = 60, M = N + 5;
int c[M];
int W, E;
double all;

void output() {
int cnt[3] = {0, 0, 0};
double rp[3] = {1.0 / 3, 1.0 / 3, 1.0 / 3};
double profit = 0;
FOR (i, 0, N) {
if (c[i] == 0) putchar('R');
if (c[i] == 1) putchar('S');
if (c[i] == 2) putchar('P');
profit += W * rp[(c[i] + 1) % 3] + E * rp[c[i]];
cnt[c[i]] += 1;
FOR (j, 0, 3) rp[(j + 2) % 3] = 1.0 * cnt[j] / (i + 1);
}
all += profit;
puts("");
}

pair<double, int> f[M][M][M];
int from[M][M][M];
void solve() {
cin >> W >> E;
f[1][0][0] = {0, 0}; f[0][1][0] = {0, 1}; f[0][0][1] = {0, 2};
int ii, jj, kk;
double ans = -1;
FOR (i, 0, N + 1) FOR (j, 0, N + 1) FOR (k, 0, N + 1) {
int s = i + j + k;
double ss = s - 1;
if (s <= 1 || s > N) continue;
f[i][j][k] = max({
make_pair(i ? f[i - 1][j][k].first + k * W / ss + j * E / ss : -1, 0),
make_pair(j ? f[i][j - 1][k].first + i * W / ss + k * E / ss : -1, 1),
make_pair(k ? f[i][j][k - 1].first + j * W / ss + i * E / ss : -1, 2),
});
if (s == N && f[i][j][k].first > ans) { ii = i; jj = j; kk = k; ans = f[i][j][k].first; }
}
dbg(ans);
FORD (i, N - 1, -1) {
c[i] = f[ii][jj][kk].second;
if (c[i] == 0) --ii; else if (c[i] == 1) --jj; else if (c[i] == 2) --kk;
}
output();
}


int main() {
#ifdef zerol
freopen("in.txt", "r", stdin);
#endif
int T, X; cin >> T >> X;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
dbg(all / 200);
}

Binary Operator

题意:定义一种新的二元运算,记号为 #,且为全函数。要求把若干包含 + * # 和超长数字的表达式划分为若干等价类。

题解:将 a#b 的结果定为随机整数参与运算(保证对于同样的 a 和 b,a#b 的结果一致),同时对素数取模。对于不同模数重复若干次,如果某两个表达式的值始终相同,那么它们就一定在一个等价类中。

这题其实有点套路,大概就是知道随机化算法的看了就知道,没见过的可能就想不出了。 另外只需要尝试很少几个模数就行了。

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
const int N = 100 + 5;
string s[N];
const int C = 100;
const vector<LL> M = {7883129, 9124553, 10415371, 11134633, 12214801, 15589333, 17148757, 17997457, 20278487, 27256133, 28678757, 38206199, 41337119, 47422547, 48543479, 52834961, 76993291, 85852231, 95217823, 108755593, 132972461, 171863609, 173629837, 176939899, 207808351, 227218703, 306112619, 311809637, 322711981, 330806107, 345593317, 345887293, 362838523, 373523729, 394207349, 409580177, 437359931, 483577261, 490845269, 512059357, 534387017, 698987533, 764016151, 906097321, 914067307, 954169327};
int m[N][N];
LL val[N];
map<pair<LL, LL>, LL> m2;
int ans[N];
LL MOD;

mt19937 mt(time(0));
auto rd = bind(uniform_int_distribution<LL>(), mt);

LL eval(const string& s) {
int cc = 0;
if (s[0] == '(') {
int n = s.length();
assert(s[n - 1] == ')');
FOR (i, 1, n - 1) {
if (s[i] == '(') ++cc;
else if (s[i] == ')') --cc;
else if (s[i] == '+' && cc == 0) {
return (eval(s.substr(1, i - 1)) + eval(s.substr(i + 1, n - 1 - (i + 1)))) % MOD;
} if (s[i] == '*' && cc == 0) {
return eval(s.substr(1, i - 1)) * eval(s.substr(i + 1, n - 1 - (i + 1))) % MOD;
} if (s[i] == '#' && cc == 0) {
LL x = eval(s.substr(1, i - 1)), y = eval(s.substr(i + 1, n - 1 - (i + 1)));
auto it = m2.find({x, y});
if (it == m2.end()) return m2[{x, y}] = rd() % MOD;
return it->second;
}
}
} else {
LL x = 0;
for (char c: s) {
x = x * 10 + c - '0';
x %= MOD;
}
return x;
}
assert(0);
}

void solve() {
memset(m, 0, sizeof m);
int n; cin >> n;
dbg(n);
FOR (i, 0, n) cin >> s[i];
for (auto x: M) {
MOD = x;
m2.clear();
FOR (i, 0, n) {
val[i] = eval(s[i]);
}
FOR (i, 0, n)
FOR (j, i + 1, n)
m[i][j] += val[i] == val[j];
}
memset(ans, -1, sizeof ans);
int cnt = 1;
FOR (i, 0, n) {
if (ans[i] != -1) continue;
ans[i] = cnt++;
FOR (j, i + 1, n)
if (m[i][j] == M.size())
ans[j] = ans[i];
}
FOR (i, 0, n) cout << ans[i] << ' ';
cout << endl;
}

int main() {
#ifdef zerol
freopen("in.txt", "r", stdin);
#endif
int T; cin >> T;
FOR (Ca, 1, T + 1) {
printf("Case #%d: ", Ca);
solve();
}
}

Round D

这场参加了,Rank 71,最后一题只做了小数据。这场 Google 评测出现了积压,测了几十分钟才能出结果,最后邮件中也对于这个问题道歉了。

Arithmetic Square

题意:给一个 3x3 的整数方阵(缺了中心的那个),中心任意填整数,问行列对角线(共八条)最多能形成多少等差数列。

题解:其中有四条是固定的,对于其他四条,求出中心填什么能形成等差数列,然后选择一个效果最好的。

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
const int N = 3;
int a[N][N];

int ck(int x, int y, int z) {
return y * 2 - x - z == 0;
}

map<int, int> mp;
void add(int x, int y) {
int v = x + y;
if (v % 2 == 0) mp[v] += 1;
}

void solve() {
mp.clear();
FOR (i, 0, N) FOR (j, 0, N) if (i != 1 || j != 1) {
scanf("%d", &a[i][j]);
}
int s = 0;
s += ck(a[0][0], a[0][1], a[0][2]);
s += ck(a[2][0], a[2][1], a[2][2]);
s += ck(a[0][0], a[1][0], a[2][0]);
s += ck(a[0][2], a[1][2], a[2][2]);
add(a[0][0], a[2][2]); add(a[0][2], a[2][0]);
add(a[0][1], a[2][1]); add(a[1][0], a[1][2]);
int m = 0;
for (auto it: mp) {
m = max(m, it.second);
}
printf("%d\n", s + m);
}

Cutting Intervals

题意:给若干个区间(可能重复,重叠),问砍 C 刀之后最多能形成几个区间(砍在端点上无效)。

题解 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
struct P {
LL v, d;
};
struct Q {
LL len, c;
};
vector<P> a;
vector<Q> b;

void solve() {
a.clear(); b.clear();
int n; LL C; cin >> n >> C;
FOR (i, 0, n) {
LL l, r; scanf("%lld%lld", &l, &r);
a.push_back({l, 1}); a.push_back({r, -1});
}
sort(a.begin(), a.end(), [](const P& a, const P& b){ return a.v < b.v; });
LL u = 0, last = -1;
LL cu = 0;
for (auto v: a) {
if (v.v != last) {
b.push_back({1, u + cu});
if (u) b.push_back({v.v - last - 1, u});
cu = 0;
}
if (v.d == 1) cu -= 1;
u += v.d; last = v.v;
}
sort(b.begin(), b.end(), [](const Q& a, const Q& b){ return a.c > b.c; });
LL ans = n;
for (auto v: b) {
LL c = max(0LL, min(C, v.len)); C -= c;
ans += c * v.c;
}
printf("%lld\n", ans);
}

题解 2(闭开区间):这种题就很适合闭开区间,你会发现就没有乱七八糟的边界和特殊情况了。代码上区别很小,就是把特殊处理端点处的部分去掉了。之前那个之所以是开开区间,是因为 [l, r] 中对答案有贡献的只有 [l + 1, r - 1],所以拿到的其实是两边开的区间。与之相对的,如果考虑的是 [l + 1, r],那么相当于是 [l + 1, r - 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
struct P {
LL v, d;
};
struct Q {
LL len, c;
};
vector<P> a;
vector<Q> b;

void solve() {
a.clear(); b.clear();
int n; LL C; cin >> n >> C;
FOR (i, 0, n) {
LL l, r; scanf("%lld%lld", &l, &r);
a.push_back({l + 1, 1}); a.push_back({r, -1});
}
sort(a.begin(), a.end(), [](const P& a, const P& b){ return a.v < b.v; });
LL u = 0, last = -1;
for (auto v: a) {
if (v.v != last) b.push_back({v.v - last, u});
u += v.d; last = v.v;
}
sort(b.begin(), b.end(), [](const Q& a, const Q& b){ return a.c > b.c; });
LL ans = n;
for (auto v: b) {
LL c = min(C, v.len); C -= c;
ans += c * v.c;
}
printf("%lld\n", ans);
}

用 map 写起来会方便一些:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct Q { LL len, c; };

void solve() {
int n; LL C; cin >> n >> C;
map<LL, int> mp;
FOR (i, 0, n) {
LL l, r; scanf("%lld%lld", &l, &r);
mp[l + 1]++; mp[r]--;
}
LL last = -1, u = 0;
vector<Q> b;
for (auto [x, v]: mp) {
if (u) b.push_back({x - last, u});
u += v; last = x;
}
sort(b.begin(), b.end(), [](const Q& a, const Q& b){ return a.c > b.c; });
LL ans = n;
for (auto v: b) {
LL c = min(C, v.len); C -= c;
ans += c * v.c;
}
printf("%lld\n", ans);
}

Final Exam

转换后的题意:给一些不重叠的区间,要求支持查询离给定数字最近的数,以及删除一个数。

题解:拿一个 set 维护一下。(比较考验对于 lower_bound 和 upper_bound 的理解。)

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
const int N = 1e5 + 100;
const LL INF = 1e18;
struct P { LL l, r; };
bool operator < (const P& a, const P& b) { return a.l < b.l; }
set<P> s;

void ins(LL l, LL r) { if (l <= r) s.insert({l, r}); }

void del(LL x) {
auto u = *--s.upper_bound({x, -1});
assert(u.l <= x && x <= u.r);
s.erase(u); ins(u.l, x - 1); ins(x + 1, u.r);
}

LL find_l(LL x) {
auto it = s.upper_bound({x, -1});
if (it == s.begin()) return -INF;
auto u = --it;
if (u->l <= x && x <= u->r) return x;
return u->r;
}

LL find_r(LL x) {
auto u = s.lower_bound({x, -1});
if (u == s.end()) return -INF;
return u->l;
}

void solve() {
s.clear();
int n, m; cin >> n >> m;
FOR (i, 0, n) {
LL l, r; scanf("%lld%lld", &l, &r);
s.insert({l, r});
}
FOR (i, 0, m) {
LL v; scanf("%lld", &v);
LL l = find_l(v), r = find_r(v);
LL ans = abs(l - v) <= abs(r - v) ? l : r;
del(ans);
printf("%lld ", ans);
}
puts("");
}

Primes and Queries

题意:给一个数组,要求支持两种操作,修改一个数,以及给定 $S, L, R$,求 $\sum_{i=L}^R V_p(A_i^S - (A_i \bmod P)^S)$,其中 $V_p(x)$ 表示 $x$ 中质因子 $p$ 的数量。

题解:肯定要搞个线段树维护些什么。对于小数据,有 $1 \le S\le 4$,那么只要对于每个可能的 $S$ 维护一下。对于大数据,需要维护一点什么,然后可以对于任意 $S$ 快速计算区间和。然后就需要一个数论公式,然后有几种情况需要讨论,维护一下。

Z: 这题很没意思,感觉完全没必要考这种东西,想考察什么,数论水平?有没有听说过某个公式或者搜索能力?还有线段树抄模板的水平?

懒得贴代码了。

Round F

这场参加了,Rank 39,AK 了。

Trash Bins

题意:给一个 01 串,求所有位置到最近的 1 的距离之和,保证存在 1。

题解:分别预处理左边最近的 1 和右边最近的 1,然后取 min 求和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve() {
int n; cin >> n;
string s; cin >> s;
int l[n], r[n];
memset(l, 0, sizeof l); memset(r, 0, sizeof r);
l[0] = s[0] == '1' ? 0 : 1e9;
r[n - 1] = s[n - 1] == '1' ? 0 : 1e9;
FOR (i, 1, n) l[i] = s[i] == '1' ? 0 : l[i - 1] + 1;
FORD (i, n - 2, -1) r[i] = s[i] == '1' ? 0 : r[i + 1] + 1;
LL ans = 0;
FOR (i, 0, n) ans += min(l[i], r[i]);
cout << ans << endl;
}

Festival

题意:给若干区间,每个区间对应一个值。找一个点,使得包含它的所有区间的值中任取 K 个之和最大,求这个最大值。

题解:转化为闭开区间,每个区间看做左端点插入和右端点删除两个操作,按顺序遍历,然后用两个 set 维护,同时保证第一个 set 中的最小值大于等于第二个 set 中的最大值且第一个 set 的大小不超过 K,答案就是第一个 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
multiset<int> a, b;
struct P { int h; bool start; };
void solve() {
int d, n, k; cin >> d >> n >> k;
map<int, vector<P>> mp;
FOR (i, 0, n) {
int h, s, e; cin >> h >> s >> e;
mp[s].push_back({h, true});
mp[e].push_back({h, false});
}
a.clear(); b.clear();
LL ans = -1, cur = 0;
for (auto& [_, v]: mp) {
for (P& p: v) {
if (p.start) {
a.insert(p.h); cur += p.h;
if (a.size() > k) {
cur -= *a.begin();
b.insert(*a.begin());
a.erase(a.begin());
}
} else {
if (b.count(p.h)) {
b.erase(b.find(p.h));
} else {
cur -= p.h;
a.erase(a.find(p.h));
if (!b.empty()) {
a.insert(*b.rbegin());
cur += *b.rbegin();
b.erase(--b.end());
}
}
}
}
assert(a.size() <= k);
ans = max(ans, cur);
}
cout << ans << endl;
}

Star Trappers

题意:给 300 个点以及一个目标点,选择若干点构成包含目标点的多边形,求最小的可能周长。

题解:首先这个多边形一定是凸多边形,其次它的边数至多为 4(如果更多的话总能砍掉一个不包含目标点的角)。然后分两种情况:

  • 三角形:直接枚举三角形的三个顶点
  • 四边形:四边形不能砍掉一个角变成三角形的唯一一种可能性在于,目标点落在四边形对角线的交点上。对于这种情况,枚举所有线段,如果目标点在这个线段上,再在线段的两侧分别找一个距离最近的点构成四边形。

另:题解中处理四边形的方法是极角排序,最先想到的也是这个,但感觉会比较难写。

代码(用了模板,有一些没用到的东西,还有一些东西不需要浮点数运算):

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
typedef double LD;
const LD eps = 1E-10;
int sgn(LD x) { return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1); }
struct L;
struct P;
typedef P V;
struct P {
LD x, y;
explicit P(LD x = 0, LD y = 0): x(x), y(y) {}
explicit P(const L& l);
};
struct L {
P s, t;
L() {}
L(P s, P t): s(s), t(t) {}
};

P operator - (const P& a, const P& b) { return P(a.x - b.x, a.y - b.y); }

LD dist(const P& p) { return sqrt(p.x * p.x + p.y * p.y); }
LD dot(const V& a, const V& b) { return a.x * b.x + a.y * b.y; }
LD det(const V& a, const V& b) { return a.x * b.y - a.y * b.x; }
LD cross(const P& o, const P& s, const P& t) { return det(s - o, t - o); }
// --------------------------------------------
bool p_on_seg(const P& p, const L& seg) {
P a = seg.s, b = seg.t;
return !sgn(det(p - a, b - a)) && sgn(dot(p - a, p - b)) < 0;
}

bool in_triangle(P p1, P p2, P p3, P o) {
if (sgn(cross(p1, p2, p3)) == 0) return false;
if (sgn(cross(p1, p2, p3)) < 0) return in_triangle(p1, p3, p2, o);
return sgn(cross(p1, p2, o)) > 0 && sgn(cross(p2, p3, o)) > 0 && sgn(cross(p3, p1, o)) > 0;
}

void solve() {
int n; cin >> n;
vector<P> v;
FOR (i, 0, n) {
int x, y; cin >> x >> y;
v.emplace_back(x, y);
}
P p; cin >> p.x >> p.y;
double ans = 1e18;
FOR (i, 0, n)
FOR (j, i + 1, n)
FOR (k, j + 1, n) {
P &a = v[i], &b = v[j], &c = v[k];
if (in_triangle(a, b, c, p)) {
ans = min(ans, dist(a - b) + dist(b - c) + dist(a - c));
}
}

FOR (i, 0, n) FOR (j, i + 1, n) if (p_on_seg(p, L(v[i], v[j]))) {
double d1 = 1e18, d2 = 1e18;
FOR (k, 0, n) if (k != i && k != j) {
if (sgn(cross(v[k], v[i], v[j])) > 0) {
d1 = min(dist(v[k] - v[i]) + dist(v[k] - v[j]), d1);
}
if (sgn(cross(v[k], v[i], v[j])) < 0) {
d2 = min(dist(v[k] - v[i]) + dist(v[k] - v[j]), d2);
}
}
ans = min(ans, d1 + d2);
}

if (ans > 1e17) puts("IMPOSSIBLE");
else printf("%.6f\n", ans);
}

Graph Travel

题意 & 题解:状态压缩 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
const int N = 16, M = 1 << N;
LL f[M], sum[M];
bool G[N][N];
LL l[N], r[N], a[N];
void solve() {
LL n, m, K; cin >> n >> m >> K;
memset(f, 0, sizeof f); memset(G, 0, sizeof G);
FOR (i, 0, n) cin >> l[i] >> r[i] >> a[i];
FOR (_, 0, m) {
int x, y; cin >> x >> y;
G[x][y] = G[y][x] = true;
}
FOR (i, 0, 1 << n) {
LL s = 0;
FOR (k, 0, n) if ((i >> k) & 1) s += a[k];
sum[i] = s;
}
FOR (i, 0, n) f[1 << i] = 1;
FOR (u, 1, 1 << n) {
if (__builtin_popcount(u) == 1) continue;
FOR (k, 0, n) if ((u >> k) & 1) {
int v = u ^ (1 << k);
if (sum[v] < l[k] || sum[v] > r[k]) continue;
bool can = false;
FOR (z, 0, n) can |= ((v >> z) & 1) && G[z][k];
if (can) f[u] += f[v];
}
}
LL ans = 0;
FOR (i, 0, 1 << n) if (sum[i] == K) {
ans += f[i];
}
cout << ans << endl;
}