「BJWC 2018」所有题目【题解】

题目列表

  • T1. Kakuro
  • T2. Cross sums
  • T3. Kreuzsummen

简要题解

题目背景

首先介绍一下 Kakuro\text{Kakuro} ((カックロ)) 这个游戏。游戏规则为:

  • 方形空格中填入 191 \sim 9 的整数。
  • 被斜线分开的方格中,右上角的数字等于其右侧邻接之连续方格中数字之和,左下角的数字等于其下方邻接之连续方格中数字之和。
  • 无论是横向还是纵向,连续方格中的数字不能重复。

左边为一个 Kakuro 游戏,右边为这个游戏的唯一解

我们称一开始给出的数字为线索,称需要填入数字的地方为空格。如果一个格子包含线索那么就不需要填入数字。保证每一个空格恰好被两个线索包含,且至少有一个空格。

注意在以下题目中的游戏规则可能会有所不同,请认真阅读在每个题目下的规则

T1. Kakuro

题目大意:本题的游戏规则如下:

  • 空格中填入正整数。
  • 被斜线分开的方格中,右上角的数字等于其右侧邻接之连续方格中数字之和,左下角的数字等于其下方邻接之连续方格中数字之和。

你在空格里面填上了一些数字,称这个为一个局面,即包含了谜题一开始给出的线索和后面填入的数字。有些数字 ((包括线索和空格)) 是可以修改的,将这个数字 ±1\pm 1 都得付出这个数字对应的代价。

你希望用最少的代价让这个局面变得合法,如果不可能输出 1-1。保证谜题的大小 30×30\leqslant 30 \times 30

思路分析:先将所有空格赋为 11 并预先支付费用 ((这样修改时就只会增加数字)),然后跑费用流 ((空格本质上是连接两个线索的边)),当费用 0\geqslant 0 时停止。

有一个小问题,如何判断答案是否是 1-1?可以将不能修改的数字代价设为 ++\infty,最后看有没有边权为 ++\infty 的边有流量。

还有一种使用反流的官方做法,可以参考 殊途同归二则 (by EntropyIncreaser)

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

typedef long long ll;
const int maxn = 2010, INF = 0x3f3f3f3f;
int n, m, cnt, tot, head[maxn], incf[maxn], pre[maxn], inq[maxn];
int tp[35][35], a[35][35][2], lf[35][35], up[35][35], id[35][35][2];
ll ans, dist[maxn], c[35][35][2];
queue<int> q;
struct edge { int to, cap, nxt; ll cost; } e[100010];

void add(int from, int to, int cap, ll cost) {
if (cap <= 0) return;
e[cnt] = (edge){to, cap, head[from], cost}, head[from] = cnt++;
e[cnt] = (edge){from, 0, head[to], -cost}, head[to] = cnt++;
}

bool spfa(int s, int t) {
memset(dist, 0x3f, sizeof(dist));
q.push(s), dist[s] = 0, incf[s] = INF;
while (!q.empty()) {
int v = q.front(); q.pop(), inq[v] = 0;
for (int i = head[v], u; ~i; i = e[i].nxt) {
if (e[i].cap && dist[u = e[i].to] > dist[v] + e[i].cost) {
dist[u] = dist[v] + e[i].cost, pre[u] = i;
incf[u] = min(incf[v], e[i].cap);
if (!inq[u]) q.push(u), inq[u] = 1;
}
}
}
return dist[t] < 0;
}

void upd(int s, int t) {
for (int i = t; i ^ s; i = e[pre[i] ^ 1].to) {
e[pre[i]].cap -= incf[t], e[pre[i] ^ 1].cap += incf[t];
}
ans += incf[t] * dist[t];
}

int main() {
memset(head, -1, sizeof(head));
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &tp[i][j]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (tp[i][j] & 1 || tp[i][j] == 4) scanf("%d", &a[i][j][0]);
if (tp[i][j] & 2) scanf("%d", &a[i][j][1]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (tp[i][j] & 1 || tp[i][j] == 4) scanf("%lld", &c[i][j][0]);
if (c[i][j][0] == -1) c[i][j][0] = 1e15;
if (tp[i][j] & 2) scanf("%lld", &c[i][j][1]);
if (c[i][j][1] == -1) c[i][j][1] = 1e15;
}
}
int s = 0, t = n * m * 2 + 1;
for (int i = 1; i <= n; i++) {
for (int j = 1, k; j <= m; j++) if (tp[i][j] & 1) {
for (k = i + 1; tp[k][j] == 4; k++) up[k][j] = i;
int x = k - i - 1;
add(s, id[i][j][0] = ++tot, INF, c[i][j][0]);
add(s, id[i][j][0], a[i][j][0] - x, -c[i][j][0]);
ans += c[i][j][0] * abs(a[i][j][0] - x);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1, k; j <= m; j++) if (tp[i][j] & 2) {
for (k = j + 1; tp[i][k] == 4; k++) lf[i][k] = j;
int x = k - j - 1;
add(id[i][j][1] = ++tot, t, INF, c[i][j][1]);
add(id[i][j][1], t, a[i][j][1] - x, -c[i][j][1]);
ans += c[i][j][1] * abs(a[i][j][1] - x);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (tp[i][j] ^ 4) continue;
int x = id[up[i][j]][j][0], y = id[i][lf[i][j]][1];
add(x, y, INF, c[i][j][0]);
add(x, y, a[i][j][0] - 1, -c[i][j][0]);
ans += c[i][j][0] * abs(a[i][j][0] - 1);
}
}
while (spfa(s, t)) upd(s, t);
for (int i = 0; i < cnt; i++) {
if (e[i].cost == 1e15 && e[i ^ 1].cap) printf("-1\n"), exit(0);
}
printf("%lld\n", ans);
return 0;
}

T2. Cross sums ()(\star)

题目大意:本题的游戏规则如下:

  • 空格中填入正整数。
  • 被斜线分开的方格中,右上角的数字等于其右侧邻接之连续方格中数字之异或和,左下角的数字等于其下方邻接之连续方格中数字之异或和。
  • 所有空格中填入的整数都不能重复。

Rimbaud\text{Rimbaud} 让你求解一个 Kakuro\text{Kakuro} 谜题,使得谜题的解中每个数字都不超过 26012^{60} - 1,若无解输出 1-1。保证谜题的大小 200×200\leqslant 200 \times 200,数据组数 5\leqslant 5

思路分析:把约束看作一个二分图,相当于要让每个点的点权 ((定值)) 等于它的出边异或和。

考虑先求出一棵生成树,然后随机地生成非树边的权值并修改点权,这样就唯一确定了树边的边权,DFS\text{DFS} 一遍即可。时间复杂度为 O(nm)O(nm)

:这个思路是一个很通用的做法,可以解决一般图上的问题 ((它并没有用到二分图的性质))

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

typedef long long ll;
int T, n, m, tot, cnt, flag, vis[100010];
int tp[210][210], head[100010], lf[210][210], up[210][210];
ll w[100010], ans[210][210]; set<int> S;
struct edge { int to, nxt, r, c; ll w; bool vis, tr; } e[200010];
ll get() { return rand() ^ ((ll)rand() << 16) ^ ((ll)rand() << 28); }

void add(int from, int to, int r, int c) {
e[cnt] = (edge){to, head[from], r, c, 0, 0, 0}, head[from] = cnt++;
e[cnt] = (edge){from, head[to], r, c, 0, 0, 0}, head[to] = cnt++;
}

void dfs1(int v) {
vis[v] = 1;
for (int i = head[v], u; ~i; i = e[i].nxt) {
if (e[i].vis) continue;
e[i].vis = e[i ^ 1].vis = 1;
if (!vis[u = e[i].to]) {
e[i].tr = e[i ^ 1].tr = 1, dfs1(u);
} else {
S.insert(e[i].w = e[i ^ 1].w = get());
w[v] ^= e[i].w, w[u] ^= e[i].w;
}
}
}

void dfs2(int v) {
for (int i = head[v], u; ~i; i = e[i].nxt) {
if (!e[i].tr) continue;
e[i].tr = e[i ^ 1].tr = 0, dfs2(u = e[i].to);
e[i].w = e[i ^ 1].w = w[u];
if (!w[u] || S.count(w[u])) flag = 1;
S.insert(w[u]), w[v] ^= w[u];
}
}

int main() {
scanf("%d", &T), srand(time(0));
while (T--) {
memset(vis, 0, sizeof(vis)), tot = flag = 0;
memset(head, -1, sizeof(head)), cnt = 0;
scanf("%d %d", &n, &m), S.clear();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &tp[i][j]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1, k; j <= m; j++) {
if (tp[i][j] & 1) {
scanf("%lld", &w[++tot]);
for (k = i + 1; tp[k][j] == 4; k++) up[k][j] = tot;
}
if (tp[i][j] & 2) {
scanf("%lld", &w[++tot]);
for (k = j + 1; tp[i][k] == 4; k++) lf[i][k] = tot;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (tp[i][j] == 4) add(up[i][j], lf[i][j], i, j);
}
}
for (int i = 1; i <= tot; i++) {
if (!vis[i]) dfs1(i), dfs2(i), flag |= w[i];
}
if (flag) { printf("-1\n"); continue; }
for (int i = 0; i < cnt; i += 2) {
ans[e[i].r][e[i].c] = e[i].w;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (tp[i][j] == 4) printf("%lld ", ans[i][j]);
}
printf("\n");
}
}
return 0;
}

T3. Kreuzsummen

题目大意:本题的游戏规则如下:

  • 空格中填入 1k1 \sim k 的整数。
  • 被斜线分开的方格中,右上角的数字等于其右侧邻接之连续方格中数字之和,左下角的数字等于其下方邻接之连续方格中数字之和。
  • 无论是横向还是纵向,连续方格中的数字不能重复。

定义对于每个空格的候选数为 ((更详细的定义请参考原始题面))

只考虑这个格子在初始谜题下对应的行和列线索数字不能重复的条件下可以填的数字集合。

求所有的空格的候选数个数之和。保证谜题的大小 105×105\leqslant 10^5 \times 10^5,线索个数 105\leqslant 10^5

思路分析:分类讨论后每个限制对应 020 \sim 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
#include <bits/stdc++.h>
#define mid (l + r >> 1)
using namespace std;

typedef long long ll;
const int maxn = 50010;
int n, m, K, T, tot, rt[maxn]; ll s, ans;
struct seg { int l, r, k; };
typedef pair<seg, int> P;
vector<P> G[maxn], Q[maxn];
struct node { int l, r, tag; ll s; } t[4000000];

seg get(ll len, ll s, ll m) {
if (len > m) return (seg){-1, 0, 0};
ll lb = len * (len + 1) / 2, rb = len * (m + m - len + 1) / 2;
ll l = max(1LL, m - len + 1 + s - rb), r = min(m, len + s - lb);
if (s < lb || s > rb) return (seg){-1, 0, 0};
if (s == lb + 1) return (seg){1, len + 1, len};
if (s == rb - 1) return (seg){m - len, m, m - len + 1};
if (m == len + 1 && s > lb && s < rb) return (seg){l, r, m - len + rb - s};
if (len == 2 && s / 2 <= m && s % 2 == 0) return (seg){l, r, s / 2};
return (seg){l, r, 0};
}

void add(int &k, int l, int r, int ql, int qr, int v) {
if (!k) k = ++tot;
t[k].s += (min(r, qr) - max(l, ql) + 1) * v;
if (l >= ql && r <= qr) { t[k].tag += v; return; }
if (mid >= ql) add(t[k].l, l, mid, ql, qr, v);
if (mid < qr) add(t[k].r, mid + 1, r, ql, qr, v);
}

ll sum(int k, int l, int r, int ql, int qr) {
if (!k || l >= ql && r <= qr) return t[k].s;
ll s = 0;
if (mid >= ql) s += sum(t[k].l, l, mid, ql, qr);
if (mid < qr) s += sum(t[k].r, mid + 1, r, ql, qr);
return s + 1LL * t[k].tag * (min(r, qr) - max(l, ql) + 1);
}

void upd(int x, seg t, int v) {
if (t.l < 0) return;
for (; x <= n; x += x & -x) {
add(rt[x], 1, K, t.l, t.r, v);
if (t.k > 0) add(rt[x], 1, K, t.k, t.k, -v);
}
}

ll query(int x, seg t) {
if (t.l < 0) return 0;
ll s = 0;
for (; x; x -= x & -x) {
s += sum(rt[x], 1, K, t.l, t.r);
if (t.k > 0) s -= sum(rt[x], 1, K, t.k, t.k);
}
return s;
}

int main() {
scanf("%d %d %d %d", &n, &m, &K, &T);
for (int i = 1, op, x, y1, y2; i <= T; i++) {
scanf("%d %d %d %d %lld", &op, &x, &y1, &y2, &s);
seg t = get(y2 - y1 + 1, s, K);
if (!op) G[y1].push_back(P(t, x)), G[y2 + 1].push_back(P(t, -x));
else Q[x].push_back(P(t, 1 - y1)), Q[x].push_back(P(t, y2));
}
for (int i = 1; i <= m; i++) {
for (int j = 0; j < G[i].size(); j++) {
upd(abs(G[i][j].second), G[i][j].first, G[i][j].second > 0 ? 1 : -1);
}
for (int j = 0; j < Q[i].size(); j++) {
ans += query(abs(Q[i][j].second), Q[i][j].first)
* (Q[i][j].second > 0 ? 1 : -1);
}
}
printf("%lld\n", ans);
return 0;
}