【题解】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");
}
}