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