AtCoder Regular Contest 153

A. AABCDDEFE

找形如 AABCDDEFE 的第 \(k\) 大数。

个数只有 \(10^6\) 个,枚举(甚至可以排序)找第 \(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
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

inline ll rd() {
ll 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;
}

vector<int> s;

int main() {
for (int i = 1, x = 0; i <= 9; ++i) {
x = i * 110000000; s.push_back(x);
for (int j = 0; j <= 99; ++j) {
if (j) {x = x / 100000 * 100000 + 100000; s.push_back(x);}
for (int k = 0; k <= 9; ++k) {
if (k) {x = x / 100000 * 100000 + k * 11000; s.push_back(x);}
for (int l = 0; l <= 9; ++l) {
if (l) {x = x / 1000 * 1000 + l * 101; s.push_back(x);}
for (int r = 1; r <= 9; ++r)
if (r) {x += 10; s.push_back(x);}
}
}
}
}
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());
int n = rd();
printf("%d\n", s[n - 1]);
return 0;
}

B. Grid Rotations

一个字符矩阵 \((W\times H\le 5\times 10^5)\)\(n\ (n\le 2\times 10^5)\) 次操作,最后输出整个矩阵。

每次操作给一个点,把矩阵划分成四个矩形,将四个矩形各自旋转 \(180^\circ\) (放在原位)。

容易发现交换不会改变同行同列关系,因此可以对行列坐标分别维护对应的变化,每次翻转某点分开的前后两个区间。

直接平衡树显然是可以做的,赛中就用 rope 水过去了(同时维护正反两个链表)。

1
2
3
4
5
inline void inv(int p) { // reverse first p elements and last n - p elements
tmp = s;
s = r.substr(n - p, p) + r.substr(0, n - p);
r = tmp.substr(p, n - p) + tmp.substr(0, p); // reversed sequence
}

正经结论是:如果把排列看成环,那么每次操作不会改变任意两数之间的相邻关系。

所以最多只有 \(2n\) 个排列(原始正反 + shift),每次直接找是哪个就行了,可以用 1 和 2 的位置确定。

最终复杂度 \(O(HW + 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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll rd() {
ll 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;
}

int main() {
int H = rd(), W = rd();
vector<int> r(H, 0), c(W, 0);
vector<vector<char>> a(H, vector<char>(W));
for (int i = 0; i < H; ++i)
for (int j = 0; j < W; ++j) {
char c = getchar();
while (!isalpha(c)) c = getchar();
a[i][j] = c;
}
int n = rd(), r0 = 0, r1 = 1, c0 = 0, c1 = 1;
auto upd = [&](int &pos, int m, int p) {pos = (pos > p) * m + p - pos;};

for (int i = 1; i <= n; ++i) {
int x = rd() - 1, y = rd() - 1;
upd(r1, H, x); upd(r0, H, x);
upd(c1, W, y); upd(c0, W, y);
}

if (r1 == (r0 + 1) % H) for (int i = 0; i < H; ++i) r[(r0 + i) % H] = i;
else for (int i = 0; i < H; ++i) r[(r0 + H - i) % H] = i;

if (c1 == (c0 + 1) % W) for (int i = 0; i < W; ++i) c[(c0 + i) % W] = i;
else for (int i = 0; i < W; ++i) c[(c0 + W - i) % W] = i;

for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) putchar(a[r[i]][c[j]]);
puts("");
}
return 0;
}

D.

cf 上有一个二元版本 https://codeforces.com/contest/1188/problem/D