0%

4.17 杂题

T1 Replicate Replicate Rfplicbte

题意

有一个细胞自动机,对于每个格子,如果它周围(包含它)$9$个格子中$1$的个数为奇数,那么它就会变成$1$,否则变成$0$。

但是在变换的过程中这个自动机有一定几率会出错,每一轮变换之后可能有至多一个格子翻转,你并不知道是哪个格子。现在给出一个状态,你需要求出最小的初始状态使得它有可能达到这个终止状态。

容易发现最小化初始状态的行数时列数也会达到最小值。

题解

先考虑忽略变异的情况该怎么做。

容易发现每一回合这个自动机都会向外扩展一圈,那么我们可以知道这些格子在第$k-1$回合的时候必然全是$0$。那么我们可以从左上到右下通过第$k$回合每个位置的值倒推回第$k-1$回合。

具体来说,设$f_{i,j}$为第$k$回合的格子,$g_{i,j}$为第$k-1$回合的格子,当我们尝试计算$g_{i,j}$时,对于$i’\leq i,j’\leq j$的$g_{i’,j’}$,它已经计算完毕,因此我们可以通过$f_{i-1,j-1}$以及它周围除$i,j$以外的$8$个格子计算出$g_{i,j}$。

这时我们发现一件事情,由于第一行、最后一行、第一列、最后一列必然是$0$,我们没有用到这些地方的$f$。另外,这些位置的$g$也不需要计算,因此最后两行、两列的$f$是没有用到的。

考虑翻转一个$f$会对算出的$g$产生什么影响,我们可以画出这样一张图:

image-20210419201109553

左上角的$f$被翻转了,可以发现此时所有橙色格子计算出的$g$与实际上的$g$恰好相反。

image-20210419204925997

假设最后一行与最后一列为已经确定的$0$,那么可以发现黄色格子的$f$与当前计算出的$g$无法匹配,若最后一行或者最后一列恰好没有被翻转,那么倒数第二行或倒数第二列的黄色格子会无法匹配。

因此,只要我们找出所有失配的位置,对它们的$x$和$y$坐标分别取最小值,我们就能够得到变异的点的坐标。

将这个坐标的$f$翻转,重新计算$g$后再尝试找到变异点,如果仍然能找到变异点,说明变异的点不止一个,当前状态即为初始状态。

否则我们不断重复这个过程,直到行之差或者列之差小于等于$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
#include <bits/stdc++.h>
using namespace std;

int G[310][310], g[310][310];

typedef pair<int, int> P;

P get(int lx, int rx, int ly, int ry) {
memset(g, 0, sizeof(g));
for (int i = lx + 1; i < rx; i++)
for (int j = ly + 1; j < ry; j++) {
for (int t = 0; t <= 2; t++)
for (int p = 0; p <= 2; p++) if (t | p) g[i][j] ^= g[i - t][j - p];
g[i][j] ^= G[i - 1][j - 1];
}
P pos(rx + 1, ry + 1);
auto val = [&](int i, int j) {
int res = G[i][j];
for (int t = -1; t <= 1; t++)
for (int p = -1; p <= 1; p++) res ^= g[i - t][j - p];
return res;
};
for (int i = lx; i <= rx; i++)
for (int j = ly; j <= ry; j++)
if (val(i, j)) pos.first = min(pos.first, i), pos.second = min(pos.second, j);
return pos;
}

char s[310];

int main() {
int n, m; scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i++) {
scanf("%s", s + 1);
for (int j = 1; j <= m; j++) G[i][j] = s[j] == '#';
}
int lx = 1, rx = n, ly = 1, ry = m;
auto fuck = [&]() {
int a = 1e9, b = -1e9, c = 1e9, d = -1e9;
for (int i = lx; i <= rx; i++)
for (int j = ly; j <= ry; j++)
if (G[i][j]) a = min(a, i), b = max(b, i), c = min(c, j), d = max(d, j);
lx = a, rx = b, ly = c, ry = d;
};
for (; rx - lx > 1 && ry - ly > 1; memcpy(G, g, sizeof(g)), fuck()) {
auto res = get(lx, rx, ly, ry);
if (res.first == rx + 1) continue;
G[res.first][res.second] ^= 1;
auto tmp = get(lx, rx, ly, ry);
if (tmp.first == rx + 1) continue;
G[res.first][res.second] ^= 1; break;
}
for (int i = lx; i <= rx; i++, puts(""))
for (int j = ly; j <= ry; j++) putchar(G[i][j] ? '#' : '.');
}

T2 Winding polygonal line

题意

平面上有$n$个点,给定一个长度为$n-2$的字符串$s$,$s$由LR构成,你需要找到一种遍历所有点的方案,使得每次拐弯的方式与$s$相同。

题解

找到$y$坐标最小的点,这个点一定在凸包上,我们从这个点开始出发。

每次拿出一段极长的L或者R。假设现在有$k$个L连在一起,那么对于前$k-1$步,我们找到偏离当前方向最小的点,对于第$k$步,找到偏离当前方向最大的点,这样看起来就非常优秀。R的构造与L类似。

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

const int N = 2010;

typedef long long LL;

int x[N], y[N], vis[N], n;

LL cross(int x1, int y1, int x2, int y2) {
return (LL)x1 * y2 - (LL)y1 * x2;
}

int least1(int a, int b) {
int pos = 0;
for (int i = 1; i <= n; i++) if (!vis[i]) {
if (cross(x[b] - x[a], y[b] - y[a], x[i] - x[a], y[i] - y[a]) > 0) {
if (!pos) pos = i;
else if (cross(x[i] - x[b], y[i] - y[b], x[pos] - x[b], y[pos] - y[b]) > 0) pos = i;
}
}
return pos;
}

int least2(int a, int b) {
int pos = 0;
for (int i = 1; i <= n; i++) if (!vis[i]) {
if (cross(x[b] - x[a], y[b] - y[a], x[i] - x[a], y[i] - y[a]) < 0) {
if (!pos) pos = i;
else if (cross(x[i] - x[b], y[i] - y[b], x[pos] - x[b], y[pos] - y[b]) < 0) pos = i;
}
}
return pos;
}

int most1(int a, int b) {
int pos = 0;
for (int i = 1; i <= n; i++) if (!vis[i]) {
if (cross(x[b] - x[a], y[b] - y[a], x[i] - x[a], y[i] - y[a]) > 0) {
if (!pos) pos = i;
else if (cross(x[i] - x[b], y[i] - y[b], x[pos] - x[b], y[pos] - y[b]) < 0) pos = i;
}
}
return pos;
}

int most2(int a, int b) {
int pos = 0;
for (int i = 1; i <= n; i++) if (!vis[i]) {
if (cross(x[b] - x[a], y[b] - y[a], x[i] - x[a], y[i] - y[a]) < 0) {
if (!pos) pos = i;
else if (cross(x[i] - x[b], y[i] - y[b], x[pos] - x[b], y[pos] - y[b]) > 0) pos = i;
}
}
return pos;
}

char s[N];

void solve() {
memset(vis, 0, sizeof(vis));
vector<int> res;
int lst = 1, st = 0;
for (int i = 2; i <= n; i++)
if (y[i] < y[lst]) lst = i;
vis[lst] = 1, res.push_back(lst);
double mn = 1e9, mx = -1e9;
for (int i = 1; i <= n; i++) if (i != lst) {
double ang = atan2(y[i] - y[lst], x[i] - x[lst]);
if (s[1] == 'L') {
if (ang < mn) mn = ang, st = i;
} else {
if (ang > mx) mx = ang, st = i;
}
}
vis[st] = 1, res.push_back(st);
for (int t = 2; t < n; t++) {
int tmp = st;
if (s[t - 1] == s[t]) {
if (s[t - 1] == 'L') st = least1(lst, st);
else st = least2(lst, st);
} else {
if (s[t - 1] == 'L') st = most1(lst, st);
else st = most2(lst, st);
}
lst = tmp, vis[st] = 1, res.push_back(st);
}
for (auto t : res) if (!t) return;
for (auto t : res) printf("%d ", t);
exit(0);
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]);
scanf("%s", s + 1), solve();
// puts("-1");
}

T3 Distinctification

题意

有$n$个数对$(a_i,b_i)$,每次你可以选择一个数对,让它的$a_i$加一或者减一,但是需要满足如下条件:

  • 如果存在$j\neq i,a_i=a_j$,那么可以将$a_i$加一,花费$b_i$的代价。
  • 如果存在$j\neq i, a_j=a_i-1$,那么可以将$a_i$减一,花费$-b_i$的代价。

你希望使得最终所有$a_i$互不相同,且最小化花费的代价,容易发现这个代价可以是负的。你需要对于每个前缀求出这个最小的代价。

保证$b_i$互不相同。

题解

设$c_i$表示满足$a_j=i$的$j$的个数。

我们将极长的$[i,j]$使得$a\in [i,j]$均出现过成为一个连续段,容易发现最终每个连续段的左端点必然不变,右端点可以往外拓展。

具体来说,对于一段连续段$[i,j]$,它最终能够拓展到的区间为$[i,i+\sum_{k\in[i, j]} c_k]$。

如果某两端连续段拓展到的区间有交,那么最终这两个连续段必然会合并为一段。

对于一段连续段来说,最终它的最优状态必然是段内的所有数对按照$b_i$从大到小排序,这样花费的代价必然最小。

因此我们可以给每段开一棵线段树,以$b_i$为下标维护这个最小代价,合并两个连续段的时候就是线段树合并。

另外,我们需要开一个并查集维护连续段,每次在并查集上暴力向后跳,判断下一个连通块是否可以合并到当前连通块,容易发现这样的复杂度是$O(n\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
#include <bits/stdc++.h>
using namespace std;

const int N = 400010;

typedef long long LL;

struct node {
int ls, rs, sz; LL res, sum;
} T[N * 32];

int ncnt;

void pushup(int rt) {
int ls = T[rt].ls, rs = T[rt].rs;
T[rt].sum = T[ls].sum + T[rs].sum, T[rt].sz = T[ls].sz + T[rs].sz;
T[rt].res = T[ls].res + T[rs].res + (LL)T[rs].sz * T[ls].sum;
}

void update(int &rt, int l, int r, int x) {
if (!rt) rt = ++ncnt;
if (l == r) return T[rt].sum = T[rt].res = x, T[rt].sz = 1, void();
int mid = (l + r) >> 1;
if (x <= mid) update(T[rt].ls, l, mid, x);
else update(T[rt].rs, mid + 1, r, x);
pushup(rt);
}

void merge(int &x, int y, int l, int r) {
if (!x || !y) return x |= y, void();
assert(l != r);
int mid = (l + r) >> 1;
merge(T[x].ls, T[y].ls, l, mid), merge(T[x].rs, T[y].rs, mid + 1, r), pushup(x);
}

int rt[N], fa[N], sz[N]; LL res[N], sum[N];

int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}

set<int> s;

int main() {
int n; scanf("%d", &n);
LL ans = 0;
for (int i = 1; i <= n; i++) {
int a, b, f; scanf("%d%d", &a, &b);
auto pos = s.upper_bound(a);
if (pos == s.begin()) f = fa[a] = a, s.insert(a);
else {
pos--;
if (*pos + sz[*pos] >= a) f = *pos;
else f = fa[a] = a, s.insert(a);
}
ans -= T[rt[f]].res, update(rt[f], 1, n, b), ans += T[rt[f]].res;
LL tmp = (LL)(a - f + 1) * b; ans -= tmp, res[f] += tmp, sz[f]++, sum[f] += b;
while (233) {
int nxt = f + sz[f];
if (fa[nxt]) {
int t = find(nxt);
ans -= T[rt[f]].res + T[rt[t]].res, merge(rt[f], rt[t], 1, n), ans += T[rt[f]].res;
ans += res[f] + res[t], sz[f] += sz[t], fa[t] = f, s.erase(t);
res[f] += res[t] + (LL)(t - f) * sum[t], sum[f] += sum[t], ans -= res[f];
} else break;
}
printf("%lld\n", ans);
}
}

T4 博弈

题意

image-20210419213031935

题解

这道题正着做非常困难,考虑倒着递推。

我们称一个“终止状态”为一种分配方案,满足所有人都会同意这种方案。

显然,$n$个$0$是一个终止状态。考虑从这个状态往前推。

记录下当前提议的玩家编号,以及距离上一个终止状态剩余了多少金币可以分配(即每往前倒推一个玩家,金币数量$+k$)

如果当前剩余的金币数量$<n$,那么无论如何分配,必然有一个人分配到的金币数量与下一个终止状态相同,那么根据题意这个人会否决提议。

如果当前剩余的金币数量$\geq n$,那么最优的策略必然是这个人给所有人分配一枚金币,然后将剩下的所有金币全部留给自己。

因此我们得到了一个$80$分暴力:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

typedef long long LL;

int num[N];

int main() {
int n, m, k; cin >> n >> m >> k;
int turn = (m + k - 1) / k, pos = turn % n + 1, all = 0, tmp = m % k;
for (int i = turn + 1, nw = 0; i >= 1; i--) {
if (nw >= n) num[pos] += nw - n, all++, nw = 0;
if (pos == 1) pos = n; else pos--;
if (nw < tmp) nw = tmp, tmp = 0;
else nw += k;
}
for (int i = 1; i <= n; i++) printf("%d ", num[i] + all);
}

考虑优化这个暴力,可以发现两个终止状态中间相隔的轮数是一个定值(最后一次除外),而终止状态中分配的玩家是循环的,且由于只有$n$个人,因此循环节大小至多为$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
#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

typedef long long LL;

LL num[N];

int main() {
int n; LL m, k; cin >> n >> m >> k;
auto get = [&](int a, int t) {
int res = ((a - t) % n + n) % n;
return res ? res : n;
};
LL turn = m / k + 1, pos = (turn - 1) % n + 1, tmp = m % k, step = (n + k - 1) / k;
LL first = (n - tmp + k - 1) / k;
int t = get(pos, first);
if (first * k + tmp <= m) for (int i = 1; i <= n; i++) num[i]++;
num[t] += tmp + first * k - n, pos = get(t, step);
if ((first + step) * k + tmp > m) {
for (int i = 1; i <= n; i++) printf("%d ", num[i]);
return 0;
}
LL delta = step * k - n, all = ((m - tmp) / k - first) / step;
vector<LL> fuck = {pos}; LL nw = pos;
while (233) {
nw = get(nw, step);
if (nw == pos) break;
fuck.push_back(nw);
}
LL hh = all / fuck.size();
for (auto t : fuck) num[t] += delta * hh;
for (LL nw = pos, t = hh * fuck.size() + 1; t <= all; t++) {
num[nw] += delta;
nw = ((nw - step) % n + n) % n;
if (nw == 0) nw = n;
}
for (int i = 1; i <= n; i++) printf("%lld ", num[i] + all);
}