10/12, Rank 5. 这个比赛居然需要自己加上文件 IO，有点离谱

A. Alex Origami Squares

只有三种情况：hh 等分三份、中间切出一个 2×22\times 2 然后取三个、ww 等分三份。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using ld = long double;

ld a, b;

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::freopen("alex.in", "r", stdin);
    std::freopen("alex.out", "w", stdout);

    std::cin >> a >> b;
    ld op1 = std::min(a / 3, b);
    ld op2 = std::min(a, b / 3);
    ld op3 = std::min(a / 2, b / 2);
    std::cout << std::setprecision(20) << std::fixed << std::max({op1, op2, op3}) << "\n";
}

B. Black and White

不妨设 b<wb\lt w。我们只需要两列，先 b−1b-1 次黑白交替 B,W,B,W,…\tt B,W,B,W,\dots 行，然后填 2(w−(b−1))2(w-(b-1)) 行黑格，再在其中挖出 w−(b−1)w-(b-1) 个白格。

AC Code
 
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
#include <bits/stdc++.h>
constexpr int N = 2000;

int b, w;
bool reverse;
char g[N][N];

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);

    std::freopen("black.in", "r", stdin);
    std::freopen("black.out", "w", stdout);

    std::cin >> b >> w;
    if (b > w) {
        std::swap(b, w);
        reverse = true;
    }

    for (int i = 1; i <= 2 * w; i++) g[i][1] = g[i][2] = '@';
    for (int i = 1; i <= b - 1; i++) g[i * 2][1] = g[i * 2][2] = '.';

    for (int i = 1, o = 2 * (b - 1); i <= w - (b - 1); i++) g[i * 2 + o][1] = '.';

    std::cout << 2 * w << " " << 2 << "\n";
    auto rev = [&](char v) -> char { return reverse ? '@' + '.' - v : v; };
    for (int i = 1; i <= 2 * w; i++) std::cout << rev(g[i][1]) << rev(g[i][2]) << "\n";
}

C. Concatenation

正难则反，考虑有多少个字符串会重复：考察两个字符串里相同的字符 ai=bja_i = b_j，那么这两个字符串会重复：

a[1,i]+b[j+1,m]a[1,i−1]+b[j,m] a[1, i]+b[j+1, m] \\ a[1,i-1]+b[j, m]

所以会扣去一次。于是令 Ki,cK_{i,c} 表示字符串 ii 里 cc 出现的次数，LiL_i 是字符串长度，那么答案就是

L1L2−∑c=’a’’z’K1,c⋅K2,c L_1L_2-\sum_{c=\texttt{'a'}}^{\texttt{'z'}} K_{1,c}\cdot K_{2,c}

但要注意的是，由于 a1,bma_1,b_m 是必须取的，所以在统计 KK 的时候，不能把 a1,bma_1,b_m 算入 KK. 时间复杂度 O(n+m)O(n+m)

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
constexpr int V = 30;

std::string a, b;
int n, m;
int c[V];
long long ans{0};

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);
    std::freopen("concatenation.in", "r", stdin);
    std::freopen("concatenation.out", "w", stdout);

    std::cin >> a >> b;
    n = a.length(), m = b.length();
    for (int i = 0; i < m - 1; i++) c[b[i] - 'a']++;
    ans = 1ll * n * m;

    for (int i = 1; i < n; i++) ans -= c[a[i] - 'a'];
    std::cout << ans << "\n";
}

D. Distribution in Metagonia

不是我写的，先 pass

E. Easy Arithmetic

如果是正数项直接不管，对于负数项，首先第一位必须跟在负号后面，对于 d2d3…dmd_2d_3\dots d_m，把所有前导零都剥离出来，然后全部加上正号。

实现比较麻烦（队友就挂了几次

AC Code
 
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
#include <bits/stdc++.h>

struct term {
    std::string sign{""};
    std::string val, tf;
};

std::string a;
int n;
std::vector<term> t;

bool isdigit(char c) { return '0' <= c && c <= '9'; }

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);
    std::freopen("easy.in", "r", stdin);
    std::freopen("easy.out", "w", stdout);

    std::cin >> a, n = a.length();

    for (int i = 0; i < n;) {
        term tmp;
        int j = i;
        while (j < n && !isdigit(a[j])) j++;
        if (i != j) tmp.sign = a[i];

        int t1 = j;
        while (j < n && isdigit(a[j])) j++;
        tmp.val = a.substr(t1, j - t1);

        i = j;
        t.push_back(tmp);
    }

    for (auto &v : t) {
        if (v.sign != "-") {
            v.tf = v.val;
            continue;
        }

        int m = v.val.length();
        v.tf.push_back(v.val[0]);
        for (int i = 1; i < m; i++) {
            if (v.val[i] == '0') {
                v.tf.push_back('+');
                v.tf.push_back(v.val[i]);
            } else {
                v.tf += "+";
                v.tf += v.val.substr(i, m - i);
                break;
            }
        }
    }

    for (auto v : t) std::cout << v.sign << v.tf;
    std::cout << "\n";
}

F. Fygon

还能这么搞？

因为最多 66 个循环，所以最终的多项式最多为 66 次多项式。故我们取 77 个点（分别是 n∈[0,6]n\in [0,6]）进行拉格朗日插值

怎么算对应的 f(n)f(n) 呢？诶，Python 大法好，直接 exec()\tt exec() 完美解决。

注意实现时还需要实现一个分数类。

AC Code
 
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
from functools import reduce
import math
from itertools import combinations

file = "fygon.in"
# file = "1.in"
with open(file, "r") as f:
    code = "\n" + f.read() + "\n"

code = code.replace("lag", "lag += 1")


res = []
cont = []
for n in range(7):
    lag = 0
    exec(code)
    res.append(lag)


class Fraction:
    def __init__(self, a: int = 1, b: int = 1):
        g = math.gcd(a, b)
        self.up, self.lo = a // g, b // g

    def __add__(self, o):
        if o.up == 0:
            return self
        nlo = math.lcm(self.lo, o.lo)
        nup = nlo // self.lo * self.up + nlo // o.lo * o.up
        return Fraction(nup, nlo)

    def __mul__(self, o):
        if isinstance(o, Fraction):
            return Fraction(self.up * o.up, self.lo * o.lo)
        else:
            return Fraction(self.up * o, self.lo)

    def __repr__(self) -> str:
        return f"{self.up}/{self.lo}"

    def __str__(self):
        return self.__repr__()


def add(p):
    upper = res[p]
    lower = reduce(lambda x, y: x * y, [p - j for j in range(7) if p != j])

    rest = [k for k in range(7) if k != p]
    apply = lambda f: reduce(lambda x, y: x * y, f)
    gTerms = lambda r: combinations(rest, r)
    mapped = lambda s: [apply(c) for c in gTerms(s)]

    fac = [1] + [
        reduce(lambda x, y: x + y, mapped(k)) * (1 if k % 2 == 0 else -1)
        for k in range(1, 7)
    ]

    ans = [Fraction(upper, lower) * v for v in fac]
    return ans


ans = []
final = [Fraction(0, 1)] * 7
for i in range(7):
    fac = add(i)
    for j, fj in enumerate(fac):
        final[j] += fj

for i, f in enumerate(final):
    if f.up == 0:
        continue

    ans.append(f"{f}" + "".join([f"*n" for _ in range(6 - i)]))

output = "fygon.out"
with open(output, "w") as f:
    print("+".join(ans), file=f)

G. Graph

也不是我写的，待补

H. Hash Code Hacker

因为模数很小，所以如果 si←si+31,si−1←si−1−1s_i\gets s_i+31, s_{i-1}\gets s_{i-1}-1，那么就可以满足了。

并且因为 kk 比较小，可以直接 DFS\tt DFS.

AC Code
 
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
#include <bits/stdc++.h>
constexpr int L = 50;

std::vector<std::string> ans;
int k;

bool isvalid(char c) { return ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z'); }

void display() {
    for (auto &s : ans) std::cout << s << "\n";
}

void dfs(int which, int index) {
    if (ans.size() >= k) return;
    for (int i = index; i >= 1; i--) {
        if (ans.size() >= k) return;
        std::string f = ans[which];
        if (isvalid(f[i] + 31) && isvalid(f[i - 1] - 1)) {
            f[i] += 31;
            f[i - 1] -= 1;
            ans.push_back(f);
            dfs(ans.size() - 1, i);
        }
    }
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);

    std::freopen("hash.in", "r", stdin);
    std::freopen("hash.out", "w", stdout);

    std::cin >> k;
    std::string init = "";
    for (int i = 1; i <= L; i++) init.push_back('M');
    ans.push_back(init);

    dfs(0, L - 1);

    assert(ans.size() == k);
    display();
}

I. Insider’s Information

emmm, 怎么说呢，看到只需要满足 m2\frac{m}{2} 的条件即可，感觉比较像概率期望什么的，所以联想到随机化算法。

先随机一个 permutation，然后进行如下操作直到有 m2\frac{m}{2} 的条件满足：

  1. 维护所有不满足的条件和已经尝试过的 swap；随机一个条件 (a,b,c)(a,b,c)，然后随机交换 pa,pbp_a,p_b 或者 pb,pcp_b,p_c
  2. 对于交换后的 permutation，检查满足的条件数是不是变多了。没有的话回退操作，并且记录这个 swap

注意一下输出格式，要求的是第 ii 个数字表示是几号大学。

反正就是跑得很快（

AC Code
 
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
99
100
101
102
103
104
105
106
107
108
109
110
#include <algorithm>
#include <bits/stdc++.h>
constexpr int N = 1e5 + 10;

struct tpl {
    int a, b, c;
} tp[N];
int n, m;
int f[N], ok[N];
std::vector<int> left[N], mid[N], right[N];
std::mt19937 rng(std::random_device{}());
int satis = 0;
std::set<std::pair<int, int>> du;

int get(int s) { return rng() % s + 1; }
bool ck(int a, int b, int c) { return (f[a] < f[b] && f[b] < f[c]) || (f[a] > f[b] && f[b] > f[c]); }

void alter() {
    int which = get(m);
    while (ok[which]) which = get(m);
    tpl x = tp[which];
    int i = x.b, j = x.c;
    if (rng() % 2 == 1) i = x.a, j = x.b;
    std::tie(i, j) = std::pair{std::min(i, j), std::max(i, j)};
    if (du.count({i, j})) return;

    std::swap(f[i], f[j]);
    int rt = satis;
    auto maintain = [&](std::vector<int> &vi) {
        for (auto id : vi) {
            auto &[a, b, c] = tp[id];
            rt -= ok[id];
            ok[id] = ck(a, b, c);
            rt += ok[id];
        }
    };
    maintain(left[i]), maintain(mid[i]), maintain(right[i]);
    maintain(left[j]), maintain(mid[j]), maintain(right[j]);

    if (rt < satis) {
        std::swap(f[i], f[j]), du.insert({i, j});
        maintain(left[i]), maintain(mid[i]), maintain(right[i]);
        maintain(left[j]), maintain(mid[j]), maintain(right[j]);
    } else satis = rt, du.clear();
}

int data[N];
void gendata() {
    n = get(1e5);
    m = get(1e5);
    for (int i = 1; i <= n; i++) data[i] = i;
    std::shuffle(data + 1, data + 1 + n, rng);

    for (int i = 1; i <= m; i++) {
        int l, mid, r;
        while (true) {
            l = get(n);
            if (l > n - 2) continue;
            mid = get(n - l) + l;
            if (mid > n - 1) continue;
            r = get(n - mid) + mid;

            if (l <= mid && mid <= r) break;
        }
        tp[i] = {l, mid, r};
    }
}

int main() {
    // gendata();
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);
    // std::freopen("insider.in", "r", stdin);
    // std::freopen("insider.out", "w", stdout);

    std::cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        auto &[a, b, c] = tp[i];
        std::cin >> a >> b >> c;
        left[a].push_back(i);
        mid[b].push_back(i);
        right[c].push_back(i);
    }
    for (int i = 1; i <= n; i++) f[i] = i;
    std::shuffle(f + 1, f + 1 + n, rng);

    for (int i = 1; i <= m; i++) {
        auto &[a, b, c] = tp[i];
        ok[i] = ck(a, b, c);
        satis += ok[i];
    }

    auto disp = [&](int c = 0) {
        std::cout << satis << "\n";
        if (c) {
            for (int i = 1; i <= m; i++) std::cout << ok[i] << " \n"[i == m];
            for (int i = 1; i <= n; i++) std::cout << f[i] << " \n"[i == n];
        }
        std::cout << "\n";
    };
    // disp(1);
    while (satis * 2 < m) {
        alter();
        // disp(1);
    }
    for (int i = 1; i <= n; i++) data[f[i]] = i;
    for (int i = 1; i <= n; i++) std::cout << data[i] << " \n"[i == n];
    // disp(1);
    // disp(0), std::cout << satis * 2 << ", m = " << m << "\n";
}

J. Journey to the “The World’s Start”

挺板的题。首先发现 车票距离 和 需要花费的时间 之间有单调性：车票距离 rr 越大，因为再不济可以用 r−1r-1 的方案，而且距离为 rr 有可能有更快的方案。所以可以使用二分找出 possible min⁡r\min r

考虑怎么检查 rr 是否合法。令 dpidp_i 表示走到车站 ii、出站再入站的最小时间，这里有另一个观察：不会往回走。比如说往回走了 i→j→k→⋯→n,i<k<ji\to j\to k \to \dots \to n, i\lt k\lt j. 那么我们完全可以直接从 i→ki\to k 跳过 jj（ii 都能跳到 jj 了那么一定可以跳到 kk）

所以有 dp\tt dp 转移式子

dpi=min⁡j∈[i−r,i−1](dpj+i−j+di)=i+di+min⁡j∈[i−r,i−1](dpj−j) \begin{aligned} dp_i &=\min_{j\in [i-r, i-1]} (dp_j+i-j+d_i) \\ &=i+d_i+\min_{j\in [i-r,i-1]} (dp_j-j) \end{aligned}

所以可以 O(n)O(n) 用单调队列做，也可以用 O(nlog⁡n)O(n\log n) 线段树做，维护 dpj−jdp_j-j 即可。总时间复杂度为 O(nlog⁡n)O(n\log n) 或者 O(nlog⁡2n)O(n\log^2 n)

AC Code
 
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
#include <bits/stdc++.h>
#include <random>
using ll = long long;
constexpr int N = 5e4 + 10;
constexpr ll V = 1e6;

int n;
ll t, p[N], d[N];
ll tree[N * 5], dp[N];

std::mt19937 rng{std::random_device{}()};

void pushup(int p) { tree[p] = std::min(tree[p << 1], tree[p << 1 | 1]); }
void set(int pos, ll v, int p = 1, int l = 1, int r = n) {
    if (l == r) {
        tree[p] = v;
        return;
    }
    int mid = l + ((r - l) >> 1);
    if (pos <= mid) set(pos, v, p << 1, l, mid);
    else set(pos, v, p << 1 | 1, mid + 1, r);
    pushup(p);
}
ll rquery(int ql, int qr, int p = 1, int l = 1, int r = n) {
    if (ql > r || qr < l) return (1e18);
    if (ql <= l && r <= qr) return tree[p];
    int mid = l + ((r - l) >> 1);
    return std::min(rquery(ql, qr, p << 1, l, mid), rquery(ql, qr, p << 1 | 1, mid + 1, r));
}

bool check(int distance) {
    for (int i = 1; i <= n; i++) {
        dp[i] = 0;
        set(i, 1e18);
    }
    set(1, -1);

    for (int i = 2; i <= n; i++) {
        int l = std::max(1, i - distance);
        dp[i] = rquery(l, i - 1) + i;
        set(i, dp[i] + d[i] - i);
    }

    return dp[n] <= t;
}

int bf() {
    for (int i = 1; i <= n - 1; i++)
        if (check(i)) return i;
    assert(false);
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0);

    std::freopen("journey.in", "r", stdin);
    std::freopen("journey.out", "w", stdout);

    std::cin >> n >> t;

    for (int i = 1; i <= n - 1; i++) {
        std::cin >> p[i];
    }
    for (int i = 2; i <= n - 1; i++) {
        std::cin >> d[i];
    }

    int l = 0, r = n;
    while (l + 1 < r) {
        int mid = l + ((r - l) >> 1);
        if (check(mid)) r = mid;
        else l = mid;
    }

    ll ans = 1e18;
    for (int i = r; i <= n - 1; i++) ans = std::min(ans, p[i]);

    std::cout << ans << "\n";
}

K. Kingdom Trip

几何题，但是我没做出来 ;w;

L. Lucky Chances

也不是我写的，不过是签到，待补（

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

const int N = 1e2;

int r, c;
int a[N+5][N+5];

int cn(int x, int y)
{
    int cnt = 4;
    for (int i=1; i<x; i++)
    {
        if (a[i][y] >= a[x][y]) 
        {
            cnt--;
            break;
        }
    }

    for (int j=1; j<y; j++)
    {
        if (a[x][j] >= a[x][y]) 
        {
            cnt--;
            break;
        }
    }

    for (int i=x+1; i<=r; i++)
    {
        if (a[i][y] >= a[x][y])
        {
            cnt--;
            break;
        }
    }

    for (int j=y+1; j<=c; j++)
    {
        if (a[x][j] >= a[x][y]) 
        {
            cnt--;
            break;
        }
    }

    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    freopen("lucky.in", "r", stdin);
    freopen("lucky.out", "w", stdout);

    cin >> r >> c;
    for (int i=1; i<=r; i++)
    {
        for (int j=1; j<=c; j++) cin >> a[i][j];
    }

    int res = 0;
    for (int i=1; i<=r; i++)
    {
        for (int j=1; j<=c; j++)
        {
            res += cn(i, j);
        }
    }

    cout << res;
}
ICPC/NTU Training
License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。