Google Code Jam to I/O for Women 2022

A. Inversions Organize

给你一个 \(2n\times 2n\) 的 01 矩阵,问你最少反转多少个位置,能够做到上下两半1的个数相同,左右两半1的个数相同。

以中点为原点,设最后四个象限的 1 的个数分别为 \(a,b,c,d\)

需要满足:\(a+b=b+c=c+d=d+a\) ,可以推出 \(a=c,b=d\)

因此把一三象限 1 的个数调整到相同、二四象限 1 的个数调整到相同即可。

答案就是 \(|cnt_1-cnt_3|+|cnt_2-cnt_4|\) ,复杂度 \(\mathcal O(n^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
#include <bits/stdc++.h>
using namespace std;

inline int gc() {
char c = getchar();
while (!isalpha(c)) c = getchar();
return c == 'I';
}

int testcase;

inline void work() {
printf("Case #%d: ", ++testcase);
int n;
cin >> n;
int m = n * 2;
int a = 0, b = 0;
for (int i = 1; i <= m; ++i)
for (int j = 1; j <= m; ++j) {
int x = gc();
if (i <= n && j <= n) a += x;
else if (i <= n && j > n) b += x;
else if (i > n && j <= n) b -= x;
else a -= x;
}
printf("%d\n", abs(a) + abs(b));
}

int main() {
int t;
cin >> t;
for (; t; t--) work();
return 0;
}


B. Ingredient Optimization

\(n\) 批货物,第 \(i\) 批货物有 \(L_i\) 个,\(M_i\) 时刻送达,\(M_i+E_i\) 时刻起就不能再用了。

\(q\) 个订单,第 \(i\) 个在 \(O_i\) 时刻 \((O_{i-1}<O_i)\) ,需要 \(U\) 个货物制作。

某一次做不了商店就倒闭了(后面订单都不做),问最优策略下能完成多少个订单。

贪心即可,扫描订单,每次先把当前可用的集合用一个堆维护一下。

然后优先取用最早过保质期的商品即可,处理需要一些细节,复杂度 \(\mathcal{O}((n+q)\log n)\)

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

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 107
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define pii pair<int, int>

vector<pii> q;

int testcase, a[N], b[N];

struct node {
int id;
inline bool operator < (const node &obj) const{
return b[id] > b[obj.id];
}
};

priority_queue<node> s;

inline void work() {
q.clear();
while (!s.empty()) s.pop();
printf("Case #%d: ", ++testcase);
int n = rd(), m = rd(), u = rd();
for (int i = 1; i <= n; ++i) {
int t = rd();
a[i] = rd();
b[i] = t + rd();
q.pb(mp(t, i));
q.pb(mp(b[i], -i));
}
sort(q.begin(), q.end());
int ans = 0, fl = 1;
for (int i = 1, ptr = 0; i <= m; ++i) {
int t = rd();
while (ptr < 2 * m && q[ptr].fr <= t) {
if (q[ptr].sc < 0) a[-q[ptr].sc] = 0;
else s.push((node){q[ptr].sc});
++ptr;
}
int tmp = u;
while (tmp && !s.empty()) {
int id = s.top().id;
int del = min(a[id], tmp);
tmp -= del; a[id] -= del;
if (a[id] == 0) s.pop();
}
if (tmp) fl = 0;
ans += fl;
}
printf("%d\n", ans);
}

int main() {
int t;
cin >> t;
for (; t; t--) work();
return 0;
}


C. Interesting Outing

给一棵树,有边权,求一个最短的路径,使得所有点都至少被访问到一次。

定义 \(f_{i,0/1}\) 表示 \(i\) 的子树全部访问完,回到 / 不回到 \(i\) 的最短路径长度,答案就是 \(f_{root,1}\)

转移方程:设 \(w_{i, son}\) 表示 \(i\) 和儿子 \(son\) 之间的边权。

\(f_{i,0}=\sum_{son}(f_{son,0}+w_{i, son})\)\(f_{i,1}=f_{i,0}-\max_{son}(f_{son,0}-f_{son,1} + w_{i,son})\)

复杂度 \(\mathcal{O}(n)\)

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

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

#define N 1007

int testcase, hd[N], tot;

struct edge {int to, nxt, w;}e[N << 1];

ll f[N][2];

void dfs(int u, int fa) {
ll mx = 0;
for (int i = hd[u], v; i; i = e[i].nxt)
if ((v = e[i].to) != fa) {
dfs(v, u);
f[u][0] += f[v][0] + 2 * e[i].w;
mx = max(mx, f[v][0] - f[v][1] + e[i].w);
}
f[u][1] = f[u][0] - mx;
}

inline void work() {
printf("Case #%d: ", ++testcase);
tot = 0;
memset(hd, 0, sizeof(hd));
int n = rd();
for (int i = 1; i < n; ++i) {
int u = rd(), v = rd(), w = rd();
e[++tot].to = v; e[tot].w = w; e[tot].nxt = hd[u]; hd[u] = tot;
e[++tot].to = u; e[tot].w = w; e[tot].nxt = hd[v]; hd[v] = tot;
}
ll ans = 1e18;
for (int i = 1; i <= n; ++i) {
memset(f, 0, sizeof(f));
dfs(i, i);
ans = min(ans, min(f[i][0], f[i][1]));
}
printf("%lld\n", ans);
}

int main() {
for (int t = rd(); t; --t) work();
return 0;
}


D. Inventor Outlasting

给定一个 \(R\times C\) 的地图,上面有黄色和绿色的点。

两个人博弈,每次可以选择一个黄色的点操作,不能操作的人输。

操作就是把这个点染黑,然后从个点按照 X 形发散染黑。具体的,就是从这个点开始按照四个 \(45^\circ\) 方向扩展把所有点染黑,直到碰到边界,或当前要染的格子已经被染黑后,不继续往这个方向扩展。

问先手第一步有多少种不同的下法保证必胜。

首先观察这个地图可以拆成两张,按照 \((\) 行号+列号 \()\) 的奇偶性可以把图分开,互不影响。

进一步的,如果把坐标系转 \(45^\circ\) ,可以发现每次操作就相当于把一个以黑色为边界的矩形横竖各切一刀。

所以其实是把当前的游戏转化成了四个子游戏的并,根据 SG 引理,当前状态的 SG 值就是四个子游戏的 SG 值的异或。

本质不同的游戏数取决于当前“矩形”在原地图中的位置,所以有 \(O(R^2\times C^2)\) 个。

每次枚举下一个操作的是哪个位置,复杂度 \(\mathcal{O}(R\times C)\) ,所以记忆化搜索 SG 函数总复杂度 \(\mathcal{O}(R^3\times C^3)\)

需要注意第一次的选择的时候,是把游戏划分为五种情况的并,除了四个子矩形,还有另外一张图(奇偶性不同)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
int x = 0;
bool f = 0;
char c = getchar();
for (; !isdigit(c); c = getchar()) f |= (c == '-');
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return f ? -x : x;
}

inline int gc() {
char c = getchar();
for (; c != '.' && c != 'X'; c = getchar());
return c == 'X';
}

#define N 107
#define pb push_back

bool a[2][N][N];

int testcase;

unordered_map<ll, int> sg;

inline ll hash_scope(ll id, ll a, ll b, ll c, ll d) {
return (((a * 200 + b) * 200 + c) * 200 + d) * 2 + id;
}

int dp(int id, int lx, int rx, int ly, int ry) {
if (lx > rx || ly > ry) return 0;
ll h = hash_scope(id, lx, rx, ly, ry);
if (sg.find(h) != sg.end()) return sg[h];
vector<int> nxt; nxt.clear();
for (int x = lx; x <= rx; ++x)
for (int y = ly; y <= ry; ++y)
if (a[id][x][y]) {
int a = dp(id, lx, x - 1, ly, y - 1);
int b = dp(id, lx, x - 1, y + 1, ry);
int c = dp(id, x + 1, rx, ly, y - 1);
int d = dp(id, x + 1, rx, y + 1, ry);
nxt.pb(a ^ b ^ c ^ d);
}
sort(nxt.begin(), nxt.end());
for (int i = 0, ptr = 0; ; ++i) {
if (ptr >= nxt.size() || nxt[ptr] > i) return sg[h] = i;
for (; ptr < nxt.size() && nxt[ptr] == i; ++ptr);
}
}

inline void work() {
sg.clear();
memset(a, 0, sizeof(a));
int r = rd(), c = rd();
int lx = 1e9, ly = 1e9;
int rx = -1e9, ry = -1e9;
for (int i = 1; i <= r; ++i)
for (int j = 1; j <= c; ++j) {
int id = ((i + j) & 1);
int x = (i + j) / 2;
int y = (i - j + 100) / 2;
if ((a[id][x][y] = gc())) {
lx = min(lx, x); rx = max(rx, x);
ly = min(ly, y); ry = max(ry, y);
}
}
int ans = 0;
for (int id = 0; id <= 1; ++id)
for (int x = lx; x <= rx; ++x)
for (int y = ly; y <= ry; ++y)
if (a[id][x][y]) {
int a = dp(id, lx, x - 1, ly, y - 1);
int b = dp(id, lx, x - 1, y + 1, ry);
int c = dp(id, x + 1, rx, ly, y - 1);
int d = dp(id, x + 1, rx, y + 1, ry);
ans += ((a ^ b ^ c ^ d ^ dp(id ^ 1, lx, rx, ly, ry)) == 0);
}
printf("Case #%d: %d\n", ++testcase, ans);
}

int main() {
for (int t = rd(); t; --t) work();
return 0;
}