Part 2: $[140, 180)$
acm.sgu.ru@CodeForces

140. Integer Sequences

给定一个行向量 $A,$ 构造列向量 $X$ 使得 $A \times X \equiv B \mod P$。
$P \leq 10000, A_i \leq 10 ^ 9$。

Sol

$\gcd$ 变化时暴力更新,复杂度是 $O(nd(n)) < O(n \log n)$ 的。
注意 $A_i > P$ 的情况。

#include <bits/stdc++.h>
using namespace std;

#define N 105
int n, P, B;
int a[N], X[N], q[10101], fr[10101];

void update(int v, int id) {
    int h = 0, t = 0;
    for (int i = 0; i < P; i++) {
        if (fr[i] != -1) {
            q[t++] = i;
        }
    }
    while (h < t) {
        int x = q[h++];
        int y = (x + v) % P;
        if (fr[y] == -1) {
            fr[y] = id;
            q[t++] = y;
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &P, &B);
    for (int i = 1; i <= n; i++) scanf("%d", a + i), a[i] %= P;
    memset(fr, -1, sizeof fr);
    fr[0] = 0;
    int g = P;
    for (int i = 1; i <= n && fr[B] == -1; i++) {
        int ng = __gcd(g, a[i]);
        if (ng != g) {
            g = ng;
            update(a[i], i);    
        }
    }
    if (fr[B] == -1) return puts("NO") * 0;
    puts("YES");
    int x = B;
    while (x) {
        X[fr[x]] ++;
        x = (x + P - a[fr[x]]) % P;
    }
    for (int i = 1; i <= n; i++) {
        printf("%d%c", X[i], i == n ? '\n' : ' ');
    }
}

141. Jumping Joe

$$
P_1x_1 – N_1x_1 + P_2x_2 – N_2x_2 = P
P_1 + N_1 + P_2 + N_2 = K
$$ 给定 $x_1, x_2, P, K$,解方程。

Sol

exgcd,然后找找最小的解就好了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) return x = 1, y = 0, a;
    LL t = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return t;
}

LL a, b, P, K;

void chk(LL x, LL y) {
    LL d = abs(x) + abs(y);
    if (d <= K && d % 2 == K % 2) {
        LL c = (K - d) / 2;
        printf("YES\n%lld %lld %lld %lld\n", c + (x > 0 ? x : 0), c + (x < 0 ? -x : 0), y > 0 ? y : 0, y < 0 ? -y : 0);
        exit(0);
    }
}

int main() {
    cin >> a >> b >> P >> K;
    LL x, y, g = exgcd(a, b, x, y);
    if (P % g) return puts("NO") * 0;
    x *= P / g, y *= P / g;
    LL u = b / g, v = a / g;
    chk(x, y);
    for (LL i = -3, base = x / u; i <= 3; i++) {
        chk(x - (base + i) * u, y + (base + i) * v);
    }
    for (LL i = -3, base = y / v; i <= 3; i++) chk(x + (base + i) * u, y - (base + i) * v);
    puts("NO");
}

142. Keyword

询问最短的没有出现过的子串。

Sol
#include <bits/stdc++.h>
using namespace std;

#define N 500111

unordered_set <int> s;
int n;
char t[N];
bool check(int mid) {
    s.clear();
    for (int i = mid; i <= n; i++) {
        int cur = 0;
        for (int j = 0; j < mid; j++) {
            cur = cur * 2 + (t[i - j] == 'b');
        }
        s.insert(cur);
    }
    return s.size() < (1 << mid);
}

void output(int mid) {
    printf("%d\n", mid);
    for (int i = 0; ; i++) if (!s.count(i)) {
        for (int j = 0; j < mid; j++) {
            putchar('a' + i % 2);
            i /= 2;
        }
        putchar('\n');
        return;
    }
}

int main() {
    scanf("%d%s", &n, t + 1);
    int l = 1, r = min(20, n);
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    check(l);
    output(l);
}

143. Long Live the Queen

询问树上最大权连通块。

Sol
#include <bits/stdc++.h>
using namespace std;

#define N 16111

int n, a[N], c[N];
vector <int> E[N];

void dfs(int x, int y) {
    c[x] = a[x];
    for (auto v : E[x]) if (v != y) {
        dfs(v, x);
        c[x] += max(0, c[v]);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs(1, - 1);
    int ans = -1e9;
    for (int i = 1; i <= n; i++) ans = max(ans, c[i]);
    printf("%d\n", ans);
}

144. Meeting

#include <bits/stdc++.h>
using namespace std;
double X, Y, Z;
int main() {
    scanf("%lf%lf%lf", &X, &Y, &Z);
    double a = (Y - X) * 60;
    printf("%.7lf\n", ((a - Z) / a * 2 + Z / a) * Z / a);
}

145. Strange People

求 $k$ 短简单路,输出方案。

Sol

二分或者 A* 搞搞就好了。然而这题 SPJ 挂了。

146. The Runner

原来刻意卡精度自古有之。

#include <bits/stdc++.h>
using namespace std;

double L;
long long s, ll;
int n;
int main() {
    scanf("%lf%d", &L, &n);
    ll = L * 10000 + 0.5;
    while (n--) {
        long long x, y;
        scanf("%lld%lld", &x, &y);
        s += x * y * 10000;
        s %= ll;
    }
    printf("%.4lf\n", min(s, ll - s) / 10000.);
}

147. Black-white king

棋盘上有两个王要约会,有另一个王要阻止他们。然而那个坏人很憨,要求任意时刻他都在他的起点到当前点的最短路上,路径长度定义为步数。另外两个王会沿着某条最短路见面,见面定义为走到相邻的格子里。三个人依次行动,问坏人是否有可能抓到两个人中的一个,能的话输出最快的有可能的步数;否则输出两个王之间的距离。

Sol

感觉题意没啥营养,就不写题解了。

#include <bits/stdc++.h>
using namespace std;

int n;
int p[3], q[3];

bool inter(int x, int yl, int yr, int i) {
    x -= p[2];
    yl -= q[2], yr -= q[2];
    if (abs(x) == i && (yl <= i && yr >= -i)) return true;
    if (abs(x) <= i && ((yl <= -i && yr >= -i) || (yl <= i && yr >= i))) return true;
    return false;
}
int dis;
bool ok(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= n && max(abs(x - p[0]), abs(y - q[0])) + max(abs(x - p[1]), abs(y - q[1])) == dis;
}

int check() {
    dis = abs(p[0] - p[1]);
    int dir = p[0] > p[1] ? -1 : 1;
    int l0, r0, l1, r1;
    l0 = r0 = q[0], l1 = r1 = q[1];
    for (int i = 1; i <= dis / 2 - 1; i++) {
        int p0 = p[0] + dir * i, p1 = p[1] - dir * i;
        if (ok(p0, l0 - 1)) l0--;
        if (ok(p0, r0 + 1)) r0++;
        while (!ok(p0, l0)) l0++;
        while (!ok(p0, r0)) r0--;
        if (inter(p0, l0, r0, i)) return i;
        if (ok(p1, l1 - 1)) l1--;
        if (ok(p1, r1 + 1)) r1++;
        while (!ok(p1, l1)) l1++;
        while (!ok(p1, r1)) r1--;
        if (inter(p1, l1, r1, i)) return i;
    }
    return -1;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < 3; i++) scanf("%d%d", p + i, q + i);
    if ((p[0] == p[2] && q[0] == q[2]) || (p[1] == p[2] && q[1] == q[2])) return puts("YES\n0"), 0;
    if (abs(p[0] - p[1]) < abs(q[0] - q[1])) {
        for (int i = 0; i < 3; i++) swap(p[i], q[i]);
    }
    int ret = check();
    if (ret == -1) printf("NO\n%d\n", abs(p[0] - p[1]) - 1);
    else printf("YES\n%d\n", ret);
}

148. B-Station

每层车站现在有一些水,每层有一个容量上限。如果某层的水超过容量上限则这一层会被破坏掉,水会落入下一层;你也可以选择花费相应的代价炸掉一些层。询问破坏最后一层的最优解。

Sol

开始想了很久,还是被 sez 点了一下我才想通的,我好菜。
首先,我们一定会破坏一个后缀;那么破坏一层有两种方法,第一种是炸掉,第二种是淹没掉。显然,不同的后缀起点会导致每一层是炸还是淹没;而从每一层来观察,只要起点到他的水够了就会淹没,二分一下前缀和一下就没了。

#include <bits/stdc++.h>
using namespace std;
#define N 15111
int n;
int w[N], l[N], p[N], sum[N];
bool vis[N];
vector <int> c[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d%d", w + i, l + i, p + i);
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + w[i];
    for (int i = n; i; i--) {
        int L = 1, R = i;
        while (L < R) {
            int mid = (L + R) / 2;
            if (sum[i] - sum[mid - 1] <= l[i]) R = mid;
            else L = mid + 1;
        }
        c[L].push_back(i);
    }
    int su = 0, ans = 0x3f3f3f3f, id = 0;
    for (int i = 1; i <= n; i++) {
        for (auto v : c[i]) su += p[v];
        if (su < ans) ans = su, id = i;
        su -= p[i];
    }
    for (int i = 1; i <= id; i++) {
        for (auto v : c[i]) vis[v] = 1;
        if (i < id) vis[i] = 0;
    }
    for (int i = 1; i <= n; i++) if (vis[i]) printf("%d\n", i);
}

149. Computer Network

求树上每个点最远点距离。

Sol

传 统 艺 能

#include <bits/stdc++.h>
using namespace std;
#define N 10111
int n, a[N], c[N];
struct edge {
    int v, w;
};
vector <edge> E[N];
void dfs(int x) {
    for (auto v : E[x]) {
        dfs(v.v);
        c[x] = max(c[x], c[v.v] + v.w);
    }
}
void f(int x, int z) {
    a[x] = max(c[x], z);
    int ma = z, sma = -1e9;
    for (auto v : E[x]) { 
        int val = c[v.v] + v.w;
        if (val > ma) sma = ma, ma = val;
        else if (val > sma) sma = val;
    }
    for (auto v : E[x]) {
        int val = c[v.v] + v.w;
        f(v.v, v.w + (val == ma ? sma : ma));
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        E[u].push_back({i, v});
    }
    dfs(1);
    f(1, 0);
    for (int i = 1; i <= n; i++) printf("%d\n", a[i]);
}

150. Mr. Beetle II

从 $(x_1, y_1)$ 向 $(x_2, y_2)$ 画一条线,问线经过的第 $n$ 个格子是什么,无解输出无解。

Sol

暴力可过,但是我不想写暴力。
考虑在较长边(设为 $x$)上二分,这样每个 $x$ 的边对应至多两个 $y$,并且 $mid$ 个 $x$ 有 $$mid + \lfloor \frac {mid \Delta y } {\Delta x} \rfloor – \frac {mid} {\Delta x / \gcd (\Delta x, \Delta y)}$$ 个,枚举一下边界就做完了。我交换和调整了符号来减少代码量。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
    int x1, y1, x2, y2, n;
    cin >> x1 >> y1 >> x2 >> y2 >> n;
    if (x1 == x2 || y1 == y2) return puts("no solution") * 0; 
    int dx = x2 - x1, dy = y2 - y1;
    bool negx = 0, negy = 0, sw = 0;
    if (dx < 0) negx = 1, dx = -dx;
    if (dy < 0) negy = 1, dy = -dy; 
    if (dx < dy) sw = 1, swap(dx, dy);
    int g = __gcd(dx, dy);
    int totcell = dx + dy - g;
    if (totcell < n) return puts("no solution") * 0;
    int l = 0, r = dx;
    int xg = dx / g;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        int c = int(mid + (LL)dy * mid / dx - mid / xg);
        if (c < n) l = mid;
        else r = mid - 1;
    }
    int c = int(l + (LL)dy * l / dx - l / xg);
    int yy = int((LL)dy * l / dx);
    vector < pair<int, int> > ans;
    ans.push_back({l, yy});
    if (int((LL)dy * (l + 1) / dx) > yy && ((LL)dy * (l + 1) % dx)) {
        ans.push_back({l, yy + 1});
    }
    int ansx = ans[n - c - 1].first, ansy = ans[n - c - 1].second;
    if (sw) swap(ansx, ansy);
    if (negx) {
        ansx = -ansx - 1;
    }
    if (negy) {
        ansy = -ansy - 1;
    }
    ansx += x1; ansy += y1;
    printf("%d %d\n", ansx, ansy);
}

151. Construct a triangle

构造一个满足从一个顶点 $A$ 出发的两条边 $b, c$ 和中线 $m$ 为给定值的三角形。

Sol

取短边所在的非 $A$ 角,可以发现中线长度关于这个角度是凸的。算角度可能比较麻烦,枚举高的话需要考虑锐角和钝角两种情况。第一种取 $h = 0$ 和 $h = m$ 都太小了但是 $m < (b + c) / 2$ 的情况,可以尝试用第二种构造,否则不用。
BETTER: 把 $A, B$ 固定在 $(0, 0), (c, 0)$,然后就是一个二次方程。

#include <bits/stdc++.h>
using namespace std;

double c, b, m, lp, rp, mp;

double chk1(double h) {
    lp = -sqrt(c * c - h * h);
    rp = sqrt(b * b - h * h);
    mp = (lp + rp) / 2;
    double l = sqrt(mp * mp + h * h);
    return l - m;
}

double chk2(double h) {
    lp = sqrt(c * c - h * h);
    rp = sqrt(b * b - h * h);
    mp = (lp + rp) / 2;
    double l = sqrt(mp * mp + h * h);
    return l - m;
}

int main() {
    cin >> c >> b >> m;
    if (m > (b + c) / 2.) return puts("Mission impossible") , 0;
    double l = 0, r = min(m, min(b, c));
    auto chk = chk1;
    if (chk1(l) < 0 && chk1(r) < 0) chk = chk2;
    for (int t = 0; t < 100; t++) {
        double lmid = (l * 3 + r) / 4, rmid = (l + r * 3) / 4;
        if (chk(lmid) > chk(rmid)) l = lmid;
        else r = rmid;
    }
    if (chk(l) > 0) return puts("Mission impossible"), 0;
    if (chk(0) >= 0) l = 0, swap(l, r);
    else r = min(m, min(b, c));
    for (int t = 0; t < 100; t++) {
        double mid = (l + r) / 2;
        if (chk(mid) > 0) r = mid;
        else l = mid;
    }
    printf("%.5lf %.5lf\n", 0., l);
    printf("%.5lf %.5lf\n", lp, 0.);
    printf("%.5lf %.5lf\n", rp, 0.);
}

152. Making round

#include <bits/stdc++.h>
using namespace std;
#define N 10111
int n;
int a[N], b[N], c[N];
int main() {
    scanf("%d", &n);
    int sum = 0;
    for (int i = 1; i <= n; i++) scanf("%d", a + i), sum += a[i];
    int tot = 100;
    for (int i = 1; i <= n; i++) {
        b[i] = a[i] * 100 / sum;
        if (a[i] * 100 % sum) c[i] = 1;
        tot -= b[i];
    }
    for (int i = 1; i <= n; i++) if (c[i] && tot) b[i]++, tot--;
    for (int i = 1; i <= n; i++) printf("%d%c", b[i], i == n ? '\n' : ' ');
}

153. Playing with matches

给定 $n \leq 10 ^ 9$ 个石子,给定操作集合为一个 $[1, 9]$ 的子集,两人轮流取石子,取到最后一个的输掉,问必胜者。

Sol

一个直观的感受是,sg 函数存在循环节。我最初认为循环节是 $9!$ 的约数,但是是错的。循环节很小,最大的循环节由 4 7 8 取到 $25$, for 一下就行了。
注意网上很多题解假了,循环节可能存在一个第一段不一样的情况,需要特判。Hack:

2
1 2
6 9
6 2
6 9

应该输出

SECOND PLAYER MUST WIN
FIRST PLAYER MUST WIN
#include <bits/stdc++.h>
using namespace std;

const int N = 3000;

int K, n, m;

bool dp[N + 1];
vector <int> a;
int ma;
void work() {
    scanf("%d%d", &n, &m);
    a.clear();
    for (int i = 0; i < m; i++) {
        int x; scanf("%d", &x);
        a.push_back(x);
    }
    dp[1] = 0;
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] == 0;
        for (auto v : a) {
            if (i > v) dp[i] |= dp[i - v] == 0;
        }
    }
    for (int j = 1; ; j++) {
        bool flag = 1;
        for (int i = j + 1; i + j < N; i++){
            if (dp[i] != dp[i + j]) {
                flag = 0;
                break;
            }
        }
        if (flag) {
            puts(dp[n < N ? n : n % j + j] ? "FIRST PLAYER MUST WIN" : "SECOND PLAYER MUST WIN");
            return;
        }
    }
    assert(0);
}

int main() {
    scanf("%d", &K);
    while (K--) work();
}

154. Factorial

输出最小的 $n!$ 末尾 0 的数量为给定值的 $n$,或者 No solution

Sol
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int l = 1, r = 5e8;
    while (l < r) {
        int x = (l + r) / 2;
        int ans = 0;
        for (int y = x / 5; y; y /= 5) {
            ans += y;
        }
        if (ans >= n) r = x;
        else l = x + 1;
    }
    int ans = 0;
    for (int y = l / 5; y; y /= 5) {
        ans += y;
    }
    if (ans != n) puts("No solution");    
    else printf("%d\n", l);
}

155. Cartesian Tree

给定 $(\text{key}, \text{val})$ 构造笛卡尔树。

Sol
#include <bits/stdc++.h>
using namespace std;

#define N 50555

struct Node {
    int key, val, fa, L, R;
    bool operator < (const Node &a) const {
        return key < a.key;
    }
} a[N];

int n;
int id[N];
bool cmp(int x, int y) {
    return a[x].key < a[y].key;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int key, val;
        scanf("%d%d", &key, &val);
        a[i] = {key, val, 0, 0, 0};
        id[i] = i;
    }
    sort(id + 1, id + n + 1, cmp);
    int x = 0;
    for (int i = 1; i <= n; i++) {
        int y = id[i];
        while (x != 0) {
            int fa = a[x].fa;
            if (a[y].val < a[x].val) {
                a[x].R = a[y].L;
                a[a[y].L].fa = x;
                a[y].L = x;
                a[x].fa = y;
                x = fa;
            }
            else {
                break;
            }
        }
        a[y].fa = x;
        a[x].R = y;
        x = y;
    }
    puts("YES");
    for (int i = 1; i <= n; i++) {
        printf("%d %d %d\n", a[i].fa, a[i].L, a[i].R);
    }
}

156. Strange Graph

称满足下列性质的无向连通图是 ‘strange’ 的:

  1. $\forall v \in V, \text{deg}_v \geq 2$.
  2. $\forall v \in V \text{ s.t. deg}_v > 2:$
    • 存在且仅存在一个 $u \in \text{adj}_v, \text{deg}_u = 2$.
    • $\text{adj}_v \backslash u$ 是一个团.

给定一个 strange graph,寻找一条哈密顿回路,或者输出不存在。
$N \leq 10 ^ 4, M \leq 10 ^ 5$

Sol

把高度数的点缩起来,就是求欧拉回路。
输出方案很恶心,我调了很久但是过于弱智,选择了不缩点写法。
读题很重要,这道题少读一个限制就要多写一堆特判。

#include <bits/stdc++.h>
using namespace std;
#define N 10111
int n, m;
int bel[N];
bool vis[N];
vector <int> ans;
list <int> E[N];

void dfs(int x, bool go = 0) {
    vis[x] = 1;
    while (E[x].size()) {
        auto it = E[x].begin();
        int v = *it;
        E[x].erase(it);
        if (!vis[v]) {
            if (bel[x] == bel[v] && !go) {
                dfs(v, 1);
                ans.push_back(v);
            }
            else if (bel[x] != bel[v]){
                dfs(v, 0);
                ans.push_back(v);
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) if (!bel[i] && E[i].size() > 2) {
        for (auto v : E[i]) if (E[v].size() > 2) bel[v] = i;
    }
    for (int i = 1; i <= n; i++) if (!bel[i]) {
        bel[i] = i;
        if (E[i].size() & 1) {
            puts("-1");
            return 0;
        }
    }
    dfs(bel[1]);
    ans.push_back(bel[1]);
    for (auto v : ans) printf("%d ", v);
}

157. Patience

一列 $[1, n – 1]$ 的数放在一列 $n$ 的个格子里,拍一下空格会使得空格左边的数 $+1$ 移动到这个空格来(如果是空格在最左则为 $1$;空格左侧为 $n – 1$ 则输掉游戏),问能够还原为 $1, 2, \cdots, n – 1, \square$ 的初始局面总数。

Sol

标题是说你读题和打表都需要耐心?

打表即可。虽然我不知道在那个年代是怎么打这个表的,我的程序用了超过 4G 内存,外加现代计算机的几分钟。可能我是在用现代“科技”做题?

附为打表程序。
UPD: 我傻了,因为操作唯一,所以不用判重。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
#define read(a) scanf("%d", &a)
#define x first
#define y second

typedef vector <int> vi;
#define N 15
int n;
LL id(vi &a) {
    LL ret = 1;
    for (auto & i : a) ret = ret * (n + 1) + i;
    return ret;
}

unordered_set<LL> vis;

void solve(vi &a) {
    LL x = id(a);
    if (vis.count(x)) return;
    vis.insert(x);
    int z;
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) {
            z = i;
            break;
        }
    }
    for (int i = 0; i < n; i++) if (i != z) {
        if (a[i] != 0 && ((i == 0 && a[i] == 1) || (i != 0 && a[i] == a[i - 1] + 1 && a[i - 1]))) {
            swap(a[i], a[z]);
            solve(a);
            swap(a[i], a[z]);
        }
    }
}

int main() {
    for (n = 1; n <= 13; n++) {
        vis.clear();
        vi a;
        for (int i = 1; i < n; i++) a.push_back(i);
        a.push_back(0);
        solve(a);
        cout << "if (n == " << n << ") puts(\"" << vis.size() << "\");\n";
    }
}

以后再卡构造我是狗

1227G. Not Same

给定 $n$ 个 $[1, n]$ 的数,要求操作至多 $n + 1$ 次数,每次操作将一个互不相同的集合减一。

Sol

我尝试的第一种构造是:第 $i$ 次操作强制删 $i$,不删 $i \bmod n+ 1$。但是这样对于

5
5 1 1 1 1

的数据就解掉了,因为会在输出两行 1 0 0 0 0。后来改成了 $i – 1$ 才行,Tommy 证了,是真的。

#include <bits/stdc++.h>
using namespace std;

#define N 1005

int n;
int a[N], b[N][N];
pair<int, int> c[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= n; i++) c[i] = {a[i], i};
    sort(c + 1, c + n + 1);
    memset(b, -1, sizeof b);
    for (int i = 1; i <= n; i++) {
        a[c[i].second]--;
        b[i][c[i].second] = 1;
        b[i + 1][c[i].second] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; a[c[i].second] && j <= n + 1; j++) {
            if (b[j][c[i].second] == -1) b[j][c[i].second] = 1, a[c[i].second]--;
        }
    }
    bool flag = 0;
    for (int i = 1; i <= n; i++) flag |= b[n + 1][i] == 1;
    printf("%d\n", n + flag);
    for (int i = 1; i <= n + flag; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d", max(0, b[i][j]));
        }
        puts("");
    }
}

1110G. Tree-Tac-Toe

给一个树,树上有些点染了先手的颜色,其余点没染色。现在先后手轮流给没染色的点染黑白,如果某种颜色形成了一个大小不小于 3 的同色联通块则立刻获胜,如果染满了则平局。问最优策略下的游戏结果。

Sol

Tommy 太神啦!什么题都做过不愧是体重比我重 60 斤的 Tommmmmmmmmmmmy。
首先和井字棋相同,先手必不败,我不会直接证但是感受下外加后面的构造可以证明,我们先不考虑初始颜色,讨论如下:

  1. 存在度数为 4 的点,则先手必胜;
  2. 存在度数为 3 的点存在两个出度的度数不小于 2,则先手必胜。
  3. 存在两个距离为偶数的度数为 3 的点,则先手必胜,这一种情况可以看成 1 的拓展。
  4. 其余情况为平局,包括只有两个度数为 3 的距离为奇数的点以及链。

这么讨论很显然,我就差这么 一 点就想到第三个了,但是很可惜做不到。我是狗!

接下来还要处理有颜色的点,可以转化为:先手选择了这个点,那么后手必然要选择我新建的辅助节点。这其实可以通过外接一个根度数为 $2$ 的大小为 $3$ 的子树来做到。于是就做完了。

#include <bits/stdc++.h>
using namespace std;

#define N 2011111

int n, node;
vector <int> E[N];
char s[N / 4];
bool ans;
int dep[N];
bool vis[2];

void dfs(int x, int fa) {
    if (E[x].size() >= 4) ans = 1;
    else if (E[x].size() == 3) {
        int tot = 0;
        for (auto v : E[x]) tot += E[v].size() > 1;
        if (tot >= 2) ans = 1;
        if (vis[dep[x]]) ans = 1;
        vis[dep[x]] = 1;
    }
    for (auto v : E[x]) if (v != fa) dep[v] = dep[x] ^ 1, dfs(v, x);
}

void work() {
    scanf("%d", &n);
    node = n;
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'W') {
            E[i].push_back(++node);
            E[node].push_back(i);
            node += 2;
            E[node - 2].push_back(node - 1);
            E[node - 1].push_back(node - 2);
            E[node - 2].push_back(node - 0);
            E[node - 0].push_back(node - 2);
        }
    }
    vis[0] = vis[1] = 0;
    ans = 0;
    dfs(1, -1);
    if (ans) puts("White");
    else puts("Draw");
    for (int i = 1; i <= node; i++) E[i].clear();
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) work();
}

呐,人总是要有点梦想,万一实现了呢。

acm.sgu.ru@CodeForces
Part 1: $[100, 140)$

100. A+B

print(sum(map(int, input().split())))

101. Domino

给定 100 个骨牌,每个骨牌上写两个数。现在需要把骨牌横着排成一排,使得相邻两张骨牌相邻的数相同,输出方案。

Sol

欧拉回路。

#include <bits/stdc++.h>
using namespace std;

#define N 105

int n;
vector <pair<int, int>> E[7];
vector <int> odd, even; 
bool vis[N];
vector <int> ans;
void dfs(int x) {
    while (E[x].size()) {
        pair <int, int> o = E[x].back();
        E[x].pop_back();
        if (vis[abs(o.second)]) continue;
        vis[abs(o.second)] = 1;
        dfs(o.first);
        ans.push_back(-o.second);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        E[x].push_back({y,  i});
        E[y].push_back({x, -i});
    }
    for (int i = 0; i <= 6; i++) {
        if (E[i].size() % 2 == 1) {
            odd.push_back(i);           
        }
        else if (E[i].size()) {
            even.push_back(i);
        }
    }
    if (odd.size() == 0) {
        dfs(even[0]);
        if (ans.size() == n) {
            for (auto v : ans) {
                printf("%d %c\n", abs(v), v > 0 ? '+' : '-');
            }
        }
        else puts("No solution");
    }
    else if (odd.size() == 2){
        E[odd[0]].push_back({odd[1], n + 1});
        E[odd[1]].push_back({odd[0], -(n + 1)});
        dfs(odd[0]);
            if (ans.size() == n + 1) {
            for (auto v : ans) if (abs(v) <= n){
                printf("%d %c\n", abs(v), v > 0 ? '+' : '-');
            }
        }
        else puts("No solution");
    }
    else puts("No solution");
}

102. Coprimes

print(phi(n))

103. Traffic Lights

$n$ 个路口,$m$ 条路,每个路口有一个红绿灯,两个灯同色时才能通行。给定每个灯的周期,询问起点到终点的最短路。
$n\leq 300, m \leq 14000, l, w \leq 100$

Sol

无论怎么说,到一个点的时间仍然是越早越好——即使可能会等一会儿。

考虑如何处理出每个边的可行区间。预处理不靠谱,因为最坏可能达到 $m \times w ^ 2$ 的复杂度。然而,考虑这个东西的要求是同色而不是同为绿灯,所以直接暴力复杂度是 $O(w)$ 的。注意处理永不可能通行的情况。

总复杂度 $O(\mathrm{Dijkstra} \cdot w).$

#include <bits/stdc++.h>
using namespace std;

const int N = 305;
const int M = 14005;

int S, T, n, m;
int off[N], t[N][2], r[N];
char tmp[10];
struct Edge {
    int v, w;
};
vector <Edge> E[N];
struct Node {
    int x, d;
    bool operator < (const Node &a) const {
        return d < a.d;
    }
};

priority_queue <Node> q;

int dis[N], fr[N];

void dij() {
    memset(dis, 0x3f, sizeof dis);  
    dis[S] = 0; q.push({S, 0});
    while (!q.empty()) {
        Node o = q.top(); q.pop();
        int x = o.x, d = o.d;
        if (d != dis[x]) continue;
        for (auto v : E[x]) {
            int tt = 0;
            while (tt < 300) {
                int nt = tt + d;
                if (((nt + off[x]) % (t[x][0] + t[x][1]) < t[x][0]) == ((nt + off[v.v]) % (t[v.v][0] + t[v.v][1]) < t[v.v][0])) {
                    break;
                }
                tt++;
            }
            if (tt < 300 && dis[v.v] > dis[x] + v.w + tt) {
                dis[v.v] = dis[x] + v.w + tt;
                fr[v.v] = x;
                q.push({v.v, dis[v.v]});
            }
        }
    }
}

int main() {
    scanf("%d %d\n%d %d\n", &S, &T, &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s %d %d %d\n", tmp, r + i, t[i] + 0, t[i] + 1);
        off[i] = t[i][0] + t[i][1] - r[i] - (tmp[0] == 'B' ? t[i][1] : 0);
    }
    for (int i = 1; i <= m; i++) {
        int u, v, l;
        scanf("%d%d%d", &u, &v, &l);
        E[u].push_back({v, l}); 
        E[v].push_back({u, l});
    }
    dij();
    if (dis[T] < 0x3f3f3f3f) {
        printf("%d\n", dis[T]);
        vector <int> ans;
        int x = T;
        while (x != S) {
            ans.push_back(x);
            x = fr[x];
        }
        printf("%d", S);
        reverse(ans.begin(), ans.end());
        for (auto v : ans) {
            printf(" %d", v);
        }
        printf("\n");
    }
    else {
        puts("0");
    }
}

104. Little Shop of Flowers

$F$ 朵花依次放进 $V$ 个花瓶里,花瓶可以空着但花不能改变顺序。$a_{i, j}$ 为 $i$ 放进 $j$ 的给定价值,求最大价值和,输出方案。

Sol

DP

#include <bits/stdc++.h>
using namespace std;

#define N 105

int F, V;
int a[N][N];
int dp[N][N];
bool fr[N][N];
int main() {
    scanf("%d%d", &F, &V);
    for (int i = 1; i <= F; i++) {
        for (int j = 1; j <= V; j++) {
            scanf("%d", a[i] + j);
        }
    }
    memset(dp, 200, sizeof dp);
    dp[0][0] = 0;
    for (int i = 0; i < F; i++) {
        for (int j = 0; j < V; j++) if (dp[i][j] > -0x3f3f3f){
            if (dp[i][j + 1] < dp[i][j]) {
                dp[i][j + 1] = dp[i][j];
                fr[i][j + 1] = 0;
            }
            if (dp[i + 1][j + 1] < dp[i][j] + a[i + 1][j + 1]) {
                dp[i + 1][j + 1] = dp[i][j] + a[i + 1][j + 1];
                fr[i + 1][j + 1] = 1;
            }
        }
    }
    printf("%d\n", dp[F][V]);
    int x = F, y = V;
    vector <int> ans;
    while (x) {
        if (fr[x][y]) {
            ans.push_back(y);
            x--;
        }
        y--;
    }
    reverse(ans.begin(), ans.end());
    for (int i = 0; i < F; i++) {
        printf("%d%c", ans[i], i == F - 1 ? '\n' : ' ');
    }
}

105. Div 3

询问 $1, 12, 123, \cdots, 12345678910$ 这样的数字的前 $n$ 个有多少个被 $3$ 整除。

Sol
n = int(input())
print(n // 3 * 2 + int(n % 3 == 2))

106. The Equation

询问 $ax + by + c = 0$ 在 $x \in [x_1, x_2], y \in [y_1, y_2]$ 的解。

Sol

EXGCD

  1. 特判 0
  2. 取整
  3. 如果不转正,最后可能除负数导致区间反转
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (b == 0) return x = 1, y = 0, a;
    LL t = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return t;
}

int main() {
    LL a, b, c, x1, x2, y1, y2;
    cin >> a >> b >> c >> x1 >> x2 >> y1 >> y2;
    c = -c;
    if (x1 > x2 || y1 > y2) return 0 * puts("0");
    if (a == 0 || b == 0) {
        if (a == 0 && b == 0)
            cout << (c == 0 ? (x2 - x1 + 1) * (y2 - y1 + 1) : 0ll) << endl;
        else {
            if (b == 0) swap(a, b), swap(x1, y1), swap(x2, y2);
            cout << (y1 <= c / b && c / b <= y2 ? x2 - x1 + 1 : 0ll) << endl;
        }
        return 0;
    }
    LL x, y, g;
    g = exgcd(a, b, x, y);
    if (c % g) return 0 * puts("0");
    a /= g, b /= g, c /= g, x *= c, y *= c;
    LL d1 = (x1 - x) / b, d2 = (x2 - x) / b;
    if (x + d1 * b < x1) d1++;
    if (x + d2 * b > x2) d2--;
    LL e1 = (y1 - y) / a, e2 = (y2 - y) / a;
    if (y + e1 * a < y1) e1++;
    if (y + e2 * a > y2) e2--;
    e1 = -e1, e2 = -e2;
    if (d1 > d2) swap(d1, d2);
    if (e1 > e2) swap(e1, e2);
    cout << max(0ll, min(e2, d2) - max(e1, d1) + 1) << endl;
}

107. 987654321 problem

输出有多少个 $n$ 位数的平方的最后九位是 $987654321$。

Sol

打个表发现有 $8$ 个 $9$ 位数满足条件,所以 $n \geq 10$ 就有 $72 \times 10 ^ {n – 10}$ 个。

#include <bits/stdc++.h>
using namespace std;
int main() {
    /*int x = 987654321;
    for (int i = 30000; i < 1e9; i++) {
        long long y = (long long)i * i % 1000000000;
        if (y == 987654321) cout << i << endl;
    }*/
    int n; scanf("%d", &n);
    if (n <= 8) puts("0");
    else {
        if (n == 9) putchar('8');
        else {
            putchar('7'), putchar('2');
            while (n-- > 10) putchar('0');
        }
        puts("");
    }
}

108. Self-numbers II

定义 $$
d(n) = n + \sum Digit_i(n)
$$ $$
S = \lbrace x | x \in [1, n], \lnot (\exists y, d(y) = x )\rbrace
$$ 询问 $|S|$ 以及 $S$ 中 $a_i$ 大的值。
$n \leq 10 ^ 7, K \leq 5000$
Time Limit 0.5s, Memory Limit 4M

Sol

内存很小,所以用 bitset 存 bool。
时间很紧,打表 $O(1)$ 算数位和。
Better: 加上数位和只会影响后 $9 \times \mathrm{Len}$ 个数,因此可以使用循环数组。

#include <bits/stdc++.h>
using namespace std;
#define N 10000
int n, K;
int b[N];
bitset <int(10000090 + 1)> G;
pair <int, int> a[N];
int ans[N];

int main() {
    scanf("%d%d", &n, &K);
    for (int i = 0; i < K; i++) {
        scanf("%d", &a[i].first);
        a[i].second = i;
    }
    sort(a, a + K);
    for (int i = 0; i < N; i++) {
        int su = 0, x = i;
        while (x) su += x % 10, x /= 10;
        b[i] = su;
    }
    int cur = 0, p = 0;
    for (int i = 1; i <= n; i++) {
        if (!G[i]) {
            p ++;
            while (p == a[cur].first) {
                ans[a[cur].second] = i;
                cur++;
            }
        }
        int x = i + b[i / N] + b[i % N];
        G[x] = 1;
    }
    printf("%d\n", p);
    for (int i = 0; i < K; i++) {
        printf("%d%c", ans[i], i == K - 1 ? '\n' : ' ');
    }
}

109. Magic of David Copperfield II

一个 $n \times n(n \leq 100)$ 的网格图,最开始观众的手在 $(1, 1)$,每次魔术师可以让观众的手自行移动 $k_i$(互不相同且 $n \leq k_i \leq 3 \times n$)步,然后魔术师禁用一些格子。如此重复操作,直到所有观众的手都在同一个格子。构造满足条件的方案。

Sol

每次移动,观众都可以到这个图上任何一个奇偶性满足条件的格子,所以每次的移动必然是奇数。为了不破坏连通性,我们每次从角落的格子往里赶鸭子,角落定义为相邻至少两个坏格子的点。奇数这么做就好了,偶数需要在最后一步特判一下,留出一个空位来。

#include <bits/stdc++.h>
using namespace std;
#define N 103
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int n, off, d[N][N], id[N][N], I;
pair <int, int> pos[N * N];
vector <int> buc[2], now;
int L[2];
void clear(vector <int> &a) {
    printf("%d", n + off);
    off += 2;
    for (auto v : a) {
        printf(" %d", v);
        for (int i = 0; i < 4; i++) {
            int tx = pos[v].first + dx[i], ty = pos[v].second + dy[i];
            if (--d[tx][ty] <= 2) {
                d[tx][ty] = 1e9;
                buc[(tx + ty) % 2].push_back(id[tx][ty]);
            }
        }
    }
    printf("\n");
    a.clear();
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            id[i][j] = ++I;
            pos[I] = {i, j};
            for (int q = 0; q < 4; q++) {
                int tx = i + dx[q], ty = j + dy[q];
                d[tx][ty]++;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            L[(i + j) % 2]++;
            if (d[i][j] <= 2) {
                d[i][j] = 1e9;
                buc[(i + j) % 2].push_back(id[i][j]);
            }
        }
    }
    for (int i = 0; i <= n + 1; i++) d[i][0] = d[i][n + 1] = d[0][i] = d[n + 1][i] = 1e9;
    int cur = 1;
    off = n & 1 ? 0 : 1;
    while (L[0] + L[1] > 1) {
        cur ^= 1;
        if (L[cur] == buc[cur].size() && L[cur ^ 1] != 1) {
            buc[cur].pop_back();
            clear(buc[cur]);
            clear(buc[cur ^ 1]);    
            break;
        }
        L[cur] -= buc[cur].size();
        clear(buc[cur]);
    }
}

110. Dungeon

给定 $n \leq 50$ 个球,一束光射向这些球,到表面反射。输出前 $10$ 个被射到的球。

Sol

几何方法难写,考虑三分。
这道题反向卡精度,$\mathrm{eps}$ 要开到 $10^{-8}$ 或更大。

#include <bits/stdc++.h>
using namespace std;
#define N 55
#define cp const point &
typedef double LD;
const LD eps = 1e-8, inf = 1e9;

struct point {
    LD x, y, z;
    point () {}
    point (LD a, LD b, LD c) : x(a), y(b), z(c) {}
    void read() {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        x = a, y = b, z = c;
    }
    point operator + (cp a) const {return {x + a.x, y + a.y, z + a.z};}
    point operator - (cp a) const {return {x - a.x, y - a.y, z - a.z};}
    point operator - () const { return {-x, -y, -z}; }
    point operator * (const LD a) const {return {x * a, y * a, z * a};}
    point unit() {
        LD r = 1 / sqrt(x * x + y * y + z * z);
        return {x * r, y * r, z * r};
    }
    LD len2() {
        return x * x + y * y + z * z;
    }
    LD norm2() {
        return sqrt(x * x + y * y + z * z);
    }
} c[N], cur, dir;

LD dot(cp a, cp b) {
    return a.x * b.x + a.y * b.y + a.z * b.z;
}

point project_to_line(cp a, cp bs, cp bt) {
    return bs + (bt - bs) * (dot(a - bs, bt - bs) / (bt - bs).norm2());
}

int n;
LD R[N], t[N];
bool ban[N];

LD test(int id) {
    LD l = 0, r = inf;
    for (int i = 0; i < 200; i++) {
        LD lmid = (l + l + l + r + r) / 5, rmid = (l + l + r + r + r) / 5;  
        point pl = cur + dir * lmid, pr = cur + dir * rmid;
        if ((pl - c[id]).len2() < (pr - c[id]).len2()) r = rmid;
        else l = lmid;
    }
    point now = cur + dir * l;
    if (sqrt((now - c[id]).len2()) > R[id] + eps) return inf;
    return l;
}
point get(int id, LD r) {
    LD l = 0;
    for (int i = 0; i < 200; i++) {
        LD mid = (l + r) / 2;
        point pmid = cur + dir * mid;
        if ((pmid - c[id]).len2() >= R[id] * R[id]) l = mid;
        else r = mid;
    }
    point ans = cur + dir * l;
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int r;
        c[i].read();
        scanf("%d", &r); R[i] = r; 
    }
    cur.read(); dir.read();
    dir = (dir - cur).unit();
    vector <int> ans;
    for (int q = 0; q < 11; q++) {
        LD mint = inf;
        int id = -1;
        for (int i = 1; i <= n; i++) if(!ban[i]) {
            t[i] = test(i);
            if (t[i] < mint) {
                id = i;
                mint = t[i];
            }
        }
        else ban[i] = 0;
        if (mint == inf) break;
        point on = get(id, t[id]);
        point rp = (on - c[id]).unit();
        point k = project_to_line(-dir, point(0, 0, 0), rp);
        dir = k + k + dir;
        cur = on;
        ans.push_back(id);
        ban[id] = 1;
    }
    for (int i = 0; i < min(10, (int)ans.size()); i++) {
        if (i) printf(" ");
        printf("%d", ans[i]);
    }
    if ((int)ans.size() > 10) printf(" etc.\n");
    else printf("\n");
}

111. Very simple problem

输出 $\lfloor \sqrt n \rfloor (n \leq 10 ^ {1000}).$

Sol

Python 的 sqrt(n) 是对 $\mathrm{64-bit}$ double 的。
Python 的 Decimal 属实弟弟。
但是 Python 的 int 还是很快的。

n = int(input())
l, r = 1, 2
while r * r < n:
    l *= 2
    r *= 2
while l < r:
    mid = (l + r + 1) >> 1
    if mid * mid <= n:
        l = mid
    else:
        r = mid - 1
print(l)

112. a^b – b^a

a, b = map(int, input().split(' '))
print(a ** b - b ** a)

113. Nearly prime numbers

输入格式搞我,PyPy 3 还搞我,心态崩了。

now_token = input().split()
now_token.reverse()
def nxt_token():
    global now_token
    if len(now_token) > 0:
        ret = now_token[-1]
        now_token.pop()
        return ret
    else:
        now_token = input().split()
        now_token.reverse()
        return nxt_token();

n = int(nxt_token())
while n > 0:
    n -= 1
    x = int(nxt_token())
    ans = False
    i = 2
    while i * i <= x:
        if x % i == 0:
            y = x // i
            ans = (y > 1)
            j = 2
            while j * j <= y:
                if y % j == 0:
                    ans = 0
                    break
                j += 1
            break
        i += 1
    if ans:
        print("Yes")
    else:
        print("No")

114. Telecasting station

数轴上有一些城市,每个城市住着一些人,求一个集合点使得走到这个点的距离总和最短。

Sol
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define N 50001
#define NN N + 5

int n;
int c[NN];
LL pre[NN], sum[NN], ans[NN];

void work() {
    pre[0] = sum[0] = 0;
    for (int i = 1; i <= N ; i++) {
        pre[i] = pre[i - 1] + c[i];
        sum[i] = sum[i - 1] + (LL)c[i] * i;
    }
    for (int i = 1; i <= N; i++) {
        ans[i] += pre[i] * i - sum[i];
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x, p;
        scanf("%d%d", &x, &p);
        c[x] += p;
    }
    work();
    reverse(c + 1, c + N + 1);
    reverse(ans + 1, ans + N + 1);
    work();
    reverse(c + 1, c + N + 1);
    reverse(ans + 1, ans + N + 1);
    LL Ans = 0x3f3f3f3f3f3f3f3f;
    int id = 0;
    for (int i = 1; i <= N; i++) {
        if (ans[i] < Ans) {
            Ans = ans[i];
            id = i;
        }
    }
    printf("%d\n", id);
}

115. Calendar

M = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
n, m = map(int, input().split())
if (m < 1) or (m > 12) or (n < 1):
    print("Impossible")
elif n > M[m]:
    print("Impossible")
else:
    d = 0
    for i in range(1, m):
        d += M[i]
    d += n - 1
    print(d % 7 + 1)

116. Index of super-prime

non-increasing

#include <bits/stdc++.h>
using namespace std;

#define N 10001

int p[N / 3], pcnt;
bool vis[N];
vector <int> a;

void init() {
    vis[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!vis[i]) {
            p[++pcnt] = i;
            if (!vis[pcnt]) a.push_back(i);
        }
        for (int j = 1, k; (k = i * p[j]) < N; j++) {
            vis[k] = 1;
            if (i % p[j] == 0) break;
        }
    }
}

int n;
int dp[N], fr[N];

int main() {
    init();
    scanf("%d", &n);
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (auto v : a) {
        for (int i = v; i <= n; i++) {
            if (dp[i] >= dp[i - v] + 1) {
                dp[i] = dp[i - v] + 1;
                fr[i] = v;
            }
        }
    }
    if (dp[n] < 0x3f3f3f3f) {
        printf("%d\n", dp[n]);
        while (n) {
            printf("%d%c", fr[n], fr[n] == n ? '\n' : ' ');
            n -= fr[n];
        }
    } else puts("0");
}

116. Counting

sgu 的数据好假,以后都粘 token 板子了。

now_token = []
def nxt_token():
    global now_token
    if len(now_token) > 0:
        ret = now_token[-1]
        now_token.pop()
        return ret
    else:
        now_token = input().split()
        now_token.reverse()
        return nxt_token();
n = int(nxt_token())
m = int(nxt_token())
k = int(nxt_token())
cnt = 0
for i in range(n):
    a = int(nxt_token())
    if pow(a, m, k) == 0:
        cnt += 1
print(cnt)

117. Digital root

$$
f(n) = \begin{cases} n, & n \leq 9 \\
f(\text{sum of digits of }n), & \text{otherwise}
\end{cases}
$$ 求 $$
f(a_1 + a_1 a_2 + \cdots + a_1 a_2 \cdots a_n)
$$ $a_i \leq 10 ^ 9, n \leq 1000$

Sol

懒狗流 python 卡常,249ms/250ms AC。
Better: 数位和不改变模 $9$ 的值,直接模然后判下 $0$ 就好了 ……我是憨憨

now_token = input().split()
now_token.reverse()
def nxt_token():
    global now_token
    if len(now_token) > 0:
        ret = now_token[-1]
        now_token.pop()
        return ret
    else:
        now_token = input().split()
        now_token.reverse()
        return nxt_token();

N = 10000
NN = N * N * N * N
rt = [0]
for i in range(1, N):
    rt.append((rt[i // 10] + i % 10))

def Sum(cur):
    ans = 0
    while cur > 0:
        a = cur // N
        ans += rt[cur - a * N]
        cur = a
    return ans

K = int(nxt_token())
while K > 0:
    K -= 1
    n = int(nxt_token())
    cur = 0
    l = []
    for i in range(n):
        l.append(int(nxt_token()))
    l.reverse()
    for a in l:
        cur += 1
        cur *= a
    while cur >= 10:
        ans = 0
        while cur > 0:
            a = cur // NN
            ans += Sum(cur - a * NN)
            cur = a
        cur = ans
    print(cur)

119. Magic Pairs

数有多少满足 $0 \leq a < n, 0 \leq b < n$ 的数对 $(a, b), $ 使得 $$
a_0 x + b_0y \equiv 0 \mod n \Rightarrow a x + b y \equiv 0 \mod n
$$ $n \leq 10000$

Sol

我的做法比较憨。注意到最小的 $$\Delta x = \frac {b_0} {\gcd (a_0, b_0)}, \Delta y = \frac {a_0} {\gcd (a_0, b_0)}$$ 那么必然有 $$a \frac {b_0} {\gcd (a_0, b_0)} – b \frac {a_0} {\gcd (a_0, b_0)} \equiv 0 \mod n$$ 那么枚举 $a_0$,解出所有可能的 $b_0$ 就行了。注意到这个条件必要但不充分,需要判一判是不是对于一组特解成立——而且特解还不是简单意义上的 exgcd 特解,因为 $n$ 可以不整除 $\gcd (a, b)$,因此当 $ax + by = \gcd(a, b)$ 时,特解为 $(x\frac n {gcd(n, a, b)}, y\frac n {gcd(n, a, b)})$。

事实上,$a_0 x + b_0y = n \Rightarrow a x + b y = n$ 当且仅当 $\exists k, (a, b) = (a k \bmod n, b k \bmod n)$。充分性显然,必要性的证明思路是:首先令 $b = 0, $,可得 $a | \gcd(a_0, n)$,同理 $b | \gcd(b_0, n)$;然后令 $a = b_0, b = a_0$,得证。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (!b) return x = 1, y = 0, a;
    LL t = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return t;
}
LL n, a, b;
vector <pair<int, int>> ans, aa;
int main() {
    cin >> n >> a >> b;
    LL gg = __gcd(a, b), x, y;
    if (gg == 0) {
        printf("%d\n%d %d\n", 1, 0, 0);
        return 0;
    }
    for (int i = 0; i < n; i++) {
        LL ba0 = b / gg * i, g;
        g = exgcd(a / gg, n, x, y);
        if (ba0 % g) continue;
        x *= ba0 / g;
        x %= n / g; 
        while (x < n) {
            if (x >= 0) ans.push_back({i, (int)x});
            x += n / g;
        }
    }
    exgcd(a, b, x, y);
    x *= n / __gcd(n, gg), y *= n / __gcd(n, gg);
    for (auto v : ans) {
        if ((v.first * x + v.second * y) % n == 0) aa.push_back(v);
    }
    printf("%d\n", (int)aa.size());
    sort(aa.begin(), aa.end());
    for (auto v : aa) {
        printf("%d %d\n", v.first, v.second);
    }
}

120. Arhipelago

给定一个正 $n$ 边形上的两个点,按顺时针顺序输出所有点。

Sol
#include <bits/stdc++.h>
using namespace std;
#define cp const point &
#define N 155
struct point {
    double x, y;
    point () {}
    point (double a, double b) : x(a), y(b) {}
    point operator + (cp a) const {
        return {x + a.x, y + a.y};
    }
    point operator - (cp a) const {
        return {x - a.x, y - a.y};
    }
    point operator * (const double a) const {
        return {x * a, y * a};
    }
    point unit() {
        double l = len();
        return {x / l, y / l};
    }
    point rot(double theta) {
        return {x * cos(theta) + y * sin(theta), -x * sin(theta) + y * cos(theta)};
    }
    double len() {
        return sqrt(x * x + y * y);
    }
} p[N];
const double PI = 3.1415926535897932384626;
int n, n1, n2;

int main() {
    scanf("%d%d%d", &n, &n1, &n2);
    scanf("%lf%lf", &p[n1].x, &p[n1].y);
    scanf("%lf%lf", &p[n2].x, &p[n2].y);
    int dif = min((n2 - n1 + n) % n, (n1 - n2 + n) % n);
    double theta = 2 * PI / n;
    double l = (p[n1] - p[n2]).len(), a = l / 2;
    double r = a / sin(theta / 2 * dif), d = r * cos(theta / 2 * dif);
    point cen;
    if ((n2 - n1 + n) % n == dif) {
        cen = (p[n1] + p[n2]) * 0.5 + (p[n2] - p[n1]).unit().rot(PI / 2) * d;
    }
    else {
        cen = (p[n1] + p[n2]) * 0.5 + (p[n1] - p[n2]).unit().rot(PI / 2) * d;
    }
    point cur = p[n1] - cen;
    for (int i = n1 % n + 1; i != n1; i = i % n + 1) {
        cur = cur.rot(theta);
        p[i] = cur + cen;
    }
    for (int i = 1; i <= n; i++) {
        printf("%.6lf %.6lf\n", p[i].x, p[i].y);
    }
}

121. Bridges painting

给一个 $n$ 个点的图,询问边染色方案,使得每个点都有黑边白边相邻。

Sol

无向图的 DFS 树有这样的性质:只有返祖边没有横叉边;根的每棵子树之间没有边。这样,任取一个 DFS 树,树边按深度交替染色,非树边当做较深的那个的儿子处理,这样至多只有根不满足条件了,如果不满足条件的话考虑调整:

  1. 如果根的树上 $deg > 1$,那么随便选一个子树反色就好了;
  2. 如果根的 $deg = 1$,存在一个返祖边使得与非叶子响邻,那么这条边的颜色可以直接改;
  3. 如果 $1, 2$ 不满足,那么如果这个图是奇环是无解的;否则,随便找一个与根相邻的叶子,把 根->叶子->叶子的最深的 $deg > 2$ 的祖先 这条路径反色就可以了。

当然还有一种更骚一点的写法:如果全是偶度数那么直接交替染色,只有奇环无解;如果存在奇度数那么从奇度数开始交替染色必然有解。正确性我不太会证,但是够骚。

#include <bits/stdc++.h>
using namespace std;
#define N 105 

int n;
vector <int> E[N], cur;
struct edge {
    int x, y;
    edge (int a, int b) {
        if (a < b) x = a, y = b;
        else x = b, y = a;
    }
    bool operator < (const edge &a) const {
        return x < a.x || (x == a.x && y < a.y);
    }
};

map <edge, bool> c;
bool vis[N];

void dfs(int x) {
    vis[x] = 1;
    cur.push_back(x);
    for (auto v : E[x]) if (!vis[v]) dfs(v);
}

void dfsc(int x, int col) {
    for (auto v : E[x]) if (!c.count(edge(x, v))){
        c[edge(x, v)] = col;
        col ^= 1;
        dfsc(v, col);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        while (x) {
            E[i].push_back(x);
            scanf("%d", &x);
        }
    }
    for (int x = 1; x <= 1; x++) if (!vis[x]) {
        cur.clear();
        dfs(x);
        int rt = x;
        for (auto v : cur) if (E[v].size() % 2) rt = v;
        dfsc(rt, 0);
        bool flag = 1;
        for (auto v : cur) {
            bool cc[2] = {0, 0};
            for (auto i : E[v]) cc[c[edge(v, i)]] = 1;
            if (E[v].size() > 1 && (!cc[0] || !cc[1])) flag = 0;
        }
        if (!flag) return 0 * puts("No solution");
    }
    for (int i = 1; i <= n; i++) {
        for (auto v : E[i]) {
            printf("%d ", c[edge(i, v)] + 1);
        }
        printf("0\n");
    }
}

122. The book

$n \leq 1000$ 个点的图,每个点的度数 $\geq \lceil \frac n 2 \rceil$,求一条哈密顿回路。

Sol

人有多大胆,地有多大产 冲不过,自闭了。

这个图的性质叫做 ORE,我们可以构造性地证明这样的哈密顿回路必然存在。
首先,我们随便搞一个极长的链,这样链的起点终点都没有相邻的不在链上的点。我们讨论两种情况:

  1. 起点终点相邻
    那么现在我们有一个环,如果没有做完的话,环上随便找一个出边不在环上的点,把环变成更大的链
  2. 起点终点不相邻
    那么我们想把现在的链变成一个同样大的环,直接找两个在链上相邻的点,使得两个点分别与终点和起点相连,这样断开他们之间的边后与终点、起点相连,就可以得到一个环。

由于 ORE 性质,这样的算法每一步都必然可以进行下去。所以就搞完了。

最优实现是 $O(n ^ 2)$ 的,然而其实写成这个复杂度还是有很多细节的,我直接抄雷希拉姆的板子了。

#include <bits/stdc++.h>
using namespace std;

#define N 1005

int n;
int g[N][N];
int l[N], r[N], nx[N], la[N];
void cover(int x) {
    l[r[x]] = l[x];
    r[l[x]] = r[x];
}
int adj(int x) {
    for (int i = r[0]; i <= n; i = r[i]) {
        if (g[x][i]) return i;
    }
    return 0;
}
vector <int> solve() {
    for (int i = 1; i <= n; i++) {
        l[i] = i - 1;
        r[i] = i + 1;
    }
    int h, t;
    for (int i = 2; i <= n; i++) {
        if (g[1][i]) {
            h = 1, t = i, cover(h), cover(t);
            nx[h] = t;
            break;
        }
    }
    while (1) {
        int x;
        while (x = adj(h)) {
            nx[x] = h;
            h = x;
            cover(h);
        }
        while (x = adj(t)) {
            nx[t] = x;
            t = x;
            cover(t);
        }
        if (!g[h][t]) {
            for (int i = h, j ; i != t; i = nx[i]) {
                if (g[h][nx[i]] && g[t][i]) {
                    for (j = h; j != i; j = nx[j]) la[nx[j]] = j;
                    j = nx[h];
                    nx[h] = nx[i];
                    nx[t] = i;
                    t = j;
                    for (j = i; j != h; j = la[j]) nx[j] = la[j];
                    break;
                }
            }
        }
        nx[t] = h;
        if (r[0] > n) break;
        for (int i = h; i != t; i = nx[i]) {
            if (adj(i)) {
                h = nx[i];
                t = i;
                nx[t] = 0;
                break;
            }
        }
    }
    vector <int> ans;
    for (int i = h; ; i = nx[i]) {
        if (i == 1) {
            ans.push_back(i);
            for (int j = nx[i]; j != i; j = nx[j]) ans.push_back(j);
            ans.push_back(i);
            break;
        }
    }
    return ans;
}
int main() {
    scanf("%d\n", &n);
    for (int i = 1; i <= n; i++) {
        int x;
        while (scanf("%d", &x)) {
            g[i][x] = g[x][i] = 1;
            int ch = getchar();
            if (ch != ' ') break;
        }
    }
    for (auto i : solve()) printf("%d%c", i, n-- == 0 ? '\n' : ' ');
}

123. The sum

n = int(input())
f = [0, 1, 1]
for i in range(3, n + 1):
    f.append(f[-1] + f[-2])
s = 0
for i in range(1, n + 1):
    s += f[i]
print(s)

124. Broken line

给定一个不自交的边平行于坐标轴的 $n\leq 10000$ 边形,求一个点是不是在这个 $n$ 边形内。

Sol

本身是个傻题,但是我写了个线段树,而且因为数据有退化(某条边是某个点到自己,讲道理不会影响但是会导致奇怪的问题)不明原因(在注释那里)挂了。很怪。
其实扰动射线法就完了。

#include <bits/stdc++.h>
using namespace std;

#define N 80212
#define L 10001

struct line {
    int x, l, r;
    line (int a, int b, int c) {
        if (b > c) swap(b, c);
        x = a, l = b, r = c;
    }
    bool operator < (const line &a) const {
        return x < a.x || (x == a.x && l < a.l);
    }
};
vector <line> a;
struct Node {
    int l, r, v;
} t[N * 2];

int tcnt = 0;

int build(int l ,int r) {
    int x = ++tcnt;
    if (l < r) {
        int mid = (0x200000 + l + r) / 2 - 0x100000;
        t[x].l = build(l, mid);
        t[x].r = build(mid + 1, r);
    }
    return x;
}

int qry(int x, int l, int r, int p) {
    if (l == r) return t[x].v;
    int mid = (0x200000 + l + r) / 2 - 0x100000;
    if (p <= mid) return t[x].v + qry(t[x].l, l, mid, p);
    else return t[x].v + qry(t[x].r, mid + 1, r, p);
}

void mod(int x, int l, int r, int ql, int qr, int v) {
    if (l == ql && r == qr) {
        t[x].v += v;
        return;
    }
    int mid = (0x200000 + l + r) / 2 - 0x100000;
    if (qr <= mid) mod(t[x].l, l, mid, ql, qr, v);
    else if (ql > mid) mod(t[x].r, mid + 1, r, ql, qr, v);
    else mod(t[x].l, l, mid, ql, mid, v), mod(t[x].r, mid + 1, r, mid + 1, qr, v);
}

int n;
int X1[N], Y1[N], X2[N], Y2[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        if (x1 > x2 || y1 > y2) swap(x1, x2), swap(y1, y2);
        X1[i] = x1;
        X2[i] = x2;
        Y1[i] = y1;
        Y2[i] = y2;
        if (x1 == x2)  {
            a.push_back({x1, y1, y2});
        }
    }
    build(-L, L);
    int X, Y;
    scanf("%d%d", &X, &Y);
    for (int i =1; i <= n; i++) {
        if (X == X1[i] && Y1[i] <= Y && Y <= Y2[i]) return 0 * puts("BORDER");
        if (Y == Y1[i] && X1[i] <= X && X <= X2[i]) return 0 * puts("BORDER");
    }
    sort(a.begin(), a.end());
    int cur = -0x3f3f3f;
    int m = (int)a.size();
    for (int i = 0, j; i < m; ) {
        j = i;
        int x = a[i].x;
        int u = qry(1, -L, L, Y - 1), v = qry(1, -L, L, Y);
        if (cur <= X && X < x) {
            printf("%s\n", u + v /* == 2 */? "INSIDE" : "OUTSIDE");
            return 0;
        }
        while (j < m && a[j].x == x) {
            int y = qry(1, -L, L, a[j].l);
            if (a[j].l < a[j].r) {
                if (y) mod(1, -L, L, a[j].l, a[j].r - 1, -1);
                else   mod(1, -L, L, a[j].l, a[j].r - 1, 1);
            }
            j++;
        }
        i = j;
    }
    printf("OUTSIDE\n");
}
#include <bits/stdc++.h>
using namespace std;
#define N 10555
int n, X, Y, X1[N], Y1[N], X2[N], Y2[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        if (x1 > x2 || y1 > y2) swap(x1, x2), swap(y1, y2);
        X1[i] = x1, X2[i] = x2, Y1[i] = y1, Y2[i] = y2;
    }
    scanf("%d%d", &X, &Y);
    for (int i =1; i <= n; i++) {
        if (X == X1[i] && Y1[i] <= Y && Y <= Y2[i]) return 0 * puts("BORDER");
        if (Y == Y1[i] && X1[i] <= X && X <= X2[i]) return 0 * puts("BORDER");
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) if (Y1[i] == Y2[i] && Y1[i] < Y && X1[i] <= X && X2[i] > X) cnt++;
    puts(cnt % 2 ? "INSIDE" : "OUTSIDE");
}

125. Shtirlits

$n\times n(n \leq 3)$ 的网格,给你每个格子周围有多少个格子数比他大,构造方案。

Sol

DFS + 剪枝。
我假 AC 是:

  1. 按输入排序
  2. 按度数判可行(是否超过最大度数,是否有两个相邻的满度的点)
  3. 判存在 $0$
  4. 每一步用 $\leq$ 判最优化

当然是假的,但是因为所有卡人数据都这么构造的,于是我们与出题人的斗智斗勇便赢了一次。

#include <bits/stdc++.h>
using namespace std;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int n;
int a[5][5], id[5][5], cc[5][5], deg[5][5] = {{}, {0, 2, 3, 2}, {0, 3, 4, 3}, {0, 2, 3, 2}};
vector < pair<int, int> > c;
void dfs(int x) {
    if (x == n * n) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (cc[i][j] != a[i][j]) return;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                printf("%d%c", 9 - id[i][j], j == n ? '\n' : ' ');
            }
        }
        exit(0);
    }
    const int& u = c[x].first, v = c[x].second;
    for (int i = !!a[u][v]; i < 9; i++) {
        cc[u][v] = 0;
        bool flag = 0;
        for (int d = 0; d < 4; d++) {
            int tx = u + dx[d], ty = v + dy[d];
            if (id[tx][ty] < i) cc[u][v]++;
            else if (id[tx][ty] < 0x3f3f3f3f && id[tx][ty] > i) {
                if (++cc[tx][ty] > a[tx][ty]) flag = 1;
            }
        }
        if (!flag && cc[u][v] <= a[u][v]) {
            id[u][v] = i;
            dfs(x + 1);
            id[u][v] = 0x3f3f3f3f;
        }
        for (int d = 0; d < 4; d++) {
            int tx = u + dx[d], ty = v + dy[d];
            if (id[tx][ty] < 0x3f3f3f3f && id[tx][ty] > i) {
                --cc[tx][ty];
            }
        }
    }
}
int main() {
    cin >> n;
    memset(id, 0x3f, sizeof id);
    memset(a, 0x3f, sizeof a);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];           
            c.push_back({i, j});
        }
    sort(c.begin(), c.end(), [](pair<int, int> x, pair<int, int> y) {return a[x.first][x.second] < a[y.first][y.second];});
    if (n == 3) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[i][j] > deg[i][j]) {
                    return 0 * puts("NO SOLUTION");
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (a[i][j] == deg[i][j]) {
                    for (int d = 0; d < 4; d++) {
                        int tx = i + dx[d], ty = j + dy[d];
                        if (a[tx][ty] == deg[tx][ty]) return 0 * puts("NO SOLUTION");
                    }
                }
            }
        }
    }
    if (a[c[0].first][c[0].second] == 0)dfs(0);
    puts("NO SOLUTION");
}

卡掉数据如下:

3
0 3 0
3 3 3
0 3 0

正解就是按照一个好的顺序用 $=$ 最优化剪枝就行了。感受一下发现明显好一些。

126. Boxes

两个箱子,每次较小的箱子为 $a$ 较大的为 $b$,定义一步操作为 $(a, b) \rightarrow (2a, b – a)$,问能不能搞出 $(0, a + b)$。

Sol

感性理解一下是一个 $\text{log}$ 的过程,冲冲冲。
证明的话,倒推一下发现进行 $i$ 步可以把最小可区分单元为 $\frac {a + b} {2 ^ i}$ 的答案枚举到,所以当然是一个 $\text{log}$ 的。

a, b = map(int, input().split())
ans = 0
while a > 0 and b > 0:
    if a > b:
        a, b = b, a
    b -= a
    a += a
    ans += 1
    if ans > 1000:
        ans = -1
        break
print(ans)

127. Telephone directory

我是菜菜

K = int(input())
n = int(input())
a = []
for i in range(n):
    x = int(input())
    a.append(x)
a.sort()
last = -1
cnt = 0
ans = 2
for i in range(n):
    if a[i] // 1000 == last and cnt < K:
        cnt += 1
    else:
        last = a[i] // 1000
        cnt = 1
        ans += 1
print(ans)

128. Snake

给定 $n$ 个点,构造一个闭合折线,使得边平行于坐标轴,并且相邻两段是垂直的,并且长度最短。

Sol

这道题我最开始不会是因为没注意到必须垂直,似乎这样是个非常难的问题;不过垂直就简单很多了。

同一个 $x$ 上必然只会有孤立的几个 $y$ 的 pair,并且每个 pair 必定连边,否则题目条件无法满足。然后就是判可行,我是这么判的:

  1. 连通
  2. 每个点度数为 $2$
  3. 用扫描线判断不存在这种情况:
    ..*-*..
    *-|-|-*
    *-*.*-*
#include <bits/stdc++.h>
using namespace std;
#define N 10011
int n, e, ans = 0;
int f[N], d[N];
vector <int> X[N + N], Y[N + N];
map <pair<int, int>, int> G;
int getf(int x) {return f[x] == x ? x : f[x] = getf(f[f[x]]);}

struct op {
    int x, y, k, d;
    bool operator < (const op &a) const {
        return x < a.x || (x == a.x && k < a.k);
    }
};
vector <op> c;

void add(int x1, int y1, int x2, int y2) {
    int p1 = G[make_pair(x1, y1)], p2 = G[make_pair(x2, y2)];
    ans += abs(x2 - x1) + abs(y2 - y1);
    d[p1]++, d[p2]++;
    e++;
    f[getf(p1)] = getf(p2);
    if (x1 == x2) {
        if (y1 > y2) swap(y1, y2);
        c.push_back({x1, y1, 0, y2});
    }
    else {
        if (x1 > x2) swap(x1, x2);
        c.push_back({x1, y1, 1, 1});
        c.push_back({x2, y1, 1, -1});
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) f[i] = i;
    for (int i = 1; i <= n; i++) {
        int x, y; scanf("%d%d", &x, &y);
        Y[N + x].push_back(y);
        X[N + y].push_back(x);
        G[make_pair(x, y)] = i;
    }
    for (int i = -10000; i <= 10000; i++) if (X[N + i].size()) {
        if (X[N + i].size() % 2) return 0 * puts("0");
        sort(X[N + i].begin(), X[N + i].end());
        int m = (int)X[N + i].size();
        for (int j = 0; j < m; j += 2) {
            add(X[N + i][j], i, X[N + i][j + 1], i);
        }
    }
    for (int i = -10000; i <= 10000; i++) if (Y[N + i].size()) {
        if (Y[N + i].size() % 2) return 0 * puts("0");
        sort(Y[N + i].begin(), Y[N + i].end());
        int m = (int)Y[N + i].size();
        for (int j = 0; j < m; j += 2) {
            add(i, Y[N + i][j], i, Y[N + i][j + 1]);
        }
    }
    bool flag = 0;
    if (e == n) {
        flag = 1;
        for (int i = 1; i <= n; i++) flag &= (getf(i) == getf(1));
        for (int i = 1; i <= n; i++) flag &= d[i] == 2;
        sort(c.begin(), c.end());
        set <int> yy;
        for (auto i : c) {
            if (!i.k) {
                auto it = yy.upper_bound(i.y);
                if (it == yy.end() || *it >= i.d);
                else flag = 0;
            }
            else {
                if (i.d == 1) yy.insert(i.y);
                else yy.erase(i.y);
            }
        }
    }
    printf("%d\n", flag ? ans : 0);
}

129. Inheritance

给定一个凸包,多次询问一条线切过严格在这个凸包内的长度。
$n \leq 400, m \leq 1000$

Sol

复杂度很松所以直接暴力就行了。
需要判一下 det == 0 && dot == 0。

#include <bits/stdc++.h>
using namespace std;
#define N 405
#define cp const point &
const double eps = 1e-7;
int sgn(double x) {return (x > eps) - (x < -eps);}
struct point {
    double x, y;
    point () {}
    point (double a, double b) {x = a, y = b;}
    point operator + (cp a) const { return {x + a.x, y + a.y}; }
    point operator - (cp a) const { return {x - a.x, y - a.y}; }
    point operator * (const double z) const { return {x * z, y * z};}
    point operator / (const double z) const { return {x / z, y / z};}
    double len2() const {return x * x + y * y;}
};
double det(cp a, cp b) {return a.x * b.y - a.y * b.x;}
double dot(cp a, cp b) {return a.x * b.x + a.y * b.y;}
bool ts(cp a, cp b, cp cs, cp ct) {return sgn(det(a - cs, ct - cs)) * sgn(det(b - cs, ct - cs)) < 0;}
bool onseg(cp a, cp bs, cp bt) {
    return sgn(det(a - bs, bt - bs)) == 0 && sgn(dot(bs - a, bt - a)) <= 0;
}
bool inj(cp as, cp at, cp bs, cp bt) {
    if (onseg(bs, as, at) || onseg(bt, as, at)) return 1;
    if (onseg(as, bs, bt) || onseg(at, bs, bt)) return 1;
    return ts(as, at, bs, bt) && ts(bs, bt, as, at);
}
point inter(cp as, cp at, cp bs, cp bt) {
    double s1 = det(at - as, bs - as);
    double s2 = det(at - as, bt - as);
    return (bs * s2 - bt * s1) / (s2 - s1);
}
int contain(const vector <point>& poly, cp p) {
    int ret = 0, n = poly.size();
    for (int i = 0; i < n; i++) {
        point u = poly[i], v = poly[(i + 1) % n];
        if (onseg(p, u, v)) return 1;
        int x = sgn(det(p - u, v - u)), y = sgn(u.y - p.y), z = sgn(v.y - p.y);
        if (x > 0 && y <= 0 && z > 0) ret++;
        if (x < 0 && z <= 0 && y > 0) ret--;
    }
    return ret & 1 ? 2 : 0;
}
int n, m;
point base;
bool cmp(cp a, cp b) {
    int d = sgn(det(b - base, a - base));
    if (d) return d == 1;
    return (a - base).len2() < (b - base).len2();
}
vector <point> a;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        a.push_back({x, y});
        if (i == 0 || base.x > x) base = a.back();
    }
    sort(a.begin(), a.end(), cmp);
    scanf("%d", &m);
    while (m--) {
        point s, t;
        {
            int x, y, z, w;
            scanf("%d%d%d%d", &x, &y, &z, &w);
            s = {x, y};
            t = {z, w};
        }
        int qs = contain(a, s), qt = contain(a, t); 
        double ans = 0;
        if (qs + qt >= 3) {
            ans = sqrt((t - s).len2());
        }
        else {
            if (qt == 2) swap(qs, qt), swap(s, t); 
            vector <point> inc;
            for (int i = 0; i < n; i++) {
                int j = i == n - 1 ? 0 : i + 1;
                if (sgn(det(a[j] - a[i], t - s)) == 0 && sgn(det(a[j] - s, t - s)) == 0) {
                    inc.clear();
                    break;
                }
                if (inj(s, t, a[i], a[j])) {
                    inc.push_back(inter(s, t, a[i], a[j]));
                }
            }
            if (qs == 2) {
                assert(inc.size() > 0);
                ans = sqrt((s - inc[0]).len2());
            }
            else {
                for (int i = 1; i < (int)inc.size(); i++) {
                    ans = max(ans, sqrt((inc[i - 1] - inc[i]).len2()));
                }
            }
        }
        printf("%.2lf\n", ans);
    }
}

130. Circle

应该练习 python 的,懒了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

#define N 33
int n;
LL f[N];
LL solve(int x) {
    if (f[x]) return f[x];
    LL &ret = f[x];
    for (int i = 0; i < x; i++) ret += solve(i) * solve(x - 1 - i);
    return ret;
}

int main() {
    f[0] = 1;
    cin >> n;
    cout << solve(n) << " " << n + 1 << endl;
}

131. Hardwood floor

用 $1\times 2$ 或者 $2 \times 2$ 挖去一格的 L 形来覆盖 $n \times m$ 的地板。$n, m \leq 9$。

Sol

做法很显然,但是 $dfs$ 复杂度算起来很有意思。
一种可以考虑的计算复杂度的方式是,考虑 DP 中满足一行的话,我们有三种方法满足这一行的两格,三种方法是满足这一行的一格,那么如果我们不考虑下一行的不可行,这一行的方案是 $f$,有 $$ fn = 3f{n – 1} + 3f_{n – 2} $$ 而事实上复杂度远低于这个,因为还有另一行的限制,这样的话我们最多进 $3 ^ n$ 次 $dfs$。
我们还可以考虑用轮廓线来算,这样的话也是 $3 ^ n$ 的。

#include <bits/stdc++.h>
using namespace std;
#define N 10
int n, m, X;
int c[1 << (2 * N)];

void dfs(int x, int y, int z) {
    if (x == X) {
        c[z << n ^ y]++;
        return;
    }
    for (int i = 0; i < n; i++) if (!(x >> i & 1)){
        if (i < n - 1) {
            if (!(x >> (i + 1) & 1)) {
                dfs(x ^ 3 << i, y, z);
                if (!(y >> i & 1)) dfs(x ^ 3 << i, y ^ 1 << i, z);
                if (!(y >> (i + 1) & 1)) dfs(x ^ 3 << i, y ^ 2 << i, z);
            }
            if (!(y & 3 << i)) dfs(x ^ 1 << i, y ^ 3 << i, z);
        }
        if (i > 0 && !(y & 3 << (i - 1))) dfs(x ^ 1 << i, y ^ 3 << (i - 1), z);
        if (!(y & 1 << i)) dfs(x ^ 1 << i, y ^ 1 << i, z);
        return;
    }
}
typedef long long LL;
LL dp[N][1 << N];

int main() {
    scanf("%d%d", &n, &m);
    X = (1 << n) - 1;
    for (int i = 0; i <= X; i++) dfs(i, 0, i);
    dp[0][0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j <= X; j++) if (dp[i][j]) {
            int o = j << n;   
            for (int k = 0; k <= X; k++) {
                dp[i + 1][k] += dp[i][j] * c[o ^ k];
            }
        }
    }
    printf("%lld\n", dp[m][0]);
}

132. Another Chocolate Maniac

放尽量少的骨牌使得已有坏点的 $m \times n $ 网格图不能再放骨牌。
$m \leq 70, n \leq 7$

Sol

可以搞 $mn3 ^ n$ 但是我懒了,写了 $m n 4 ^ n$,第一遍还忘 break 了,比较搞笑。

#include <bits/stdc++.h>
using namespace std;

#define M 75
#define N 7

int m, n, X;
int dp[M][1 << N][1 << N];
char s[N + 2]; 

void dfs(int x, int j, int k, int l, int v) {
    if (dp[x + 1][k][l] <= v) return;
    {
        bool ok = 1;
        for (int i = 0; i < n; i++) if (!(j >> i & 1) && !(k >> i & 1)) ok = 0;
        for (int i = 0; i < n - 1; i++) if (!(j & 3 << i)) ok = 0;
        if (ok) dp[x + 1][k][l] = v;
    }
    for (int i = 0; i < n; i++) {
        if (i < n - 1 && !(j & 3 << i)) dfs(x, j ^ 3 << i, k, l, v + 1);
        if (!(j >> i & 1) && !(k >> i & 1)) {
            dfs(x, j ^ (1 << i), k ^ (1 << i), l, v + 1);
        }
        if (i < n - 1 && (j >> i & 3) != 3 && !(k & 3 << i)) dfs(x, j, k ^ 3 << i, l, v + 1);
        if (!(j >> i & 1) && !(k >> i & 1) && !(l >> i & 1)) {
            dfs(x, j, k ^ (1 << i), l ^ (1 << i), v + 1);
        }
        if (i) {
            if (!(j & 3 << (i - 1))) return;
            if (!(j >> (i - 1) & 1) && !(k >> (i - 1) & 1)) return;
        }
    }
}

int main() {
    scanf("%d%d", &m, &n);
    X = (1 << n) - 1;
    memset(dp, 0x3f, sizeof dp);
    dp[0][X][X] = 0;
    for (int i = 0; i <= m + 1; i++) {
        int S = 0;
        if (i < m) {
            scanf("%s", s);
            for (int j = 0; j < n; j++) {
                if (s[j] == '*') S ^= 1 << j;
            }
        }
        else S = X;
        for (int j = 0; j <= X; j++) for (int k = 0; k <= X; k++) if (dp[i][j][k] < 0x3f3f3f3f) {
            dfs(i, j, k, S, dp[i][j][k]);
        }
    }
    printf("%d\n", dp[m + 2][X][X]);
}

133. Border

#include <bits/stdc++.h>
using namespace std;

#define N 17777
int n;
pair <int, int> a[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        a[i] = {l, r};
    }
    sort(a + 1, a + n + 1);
    int R = 0, ans = 0;
    for (int i = 1; i <= n; ) {
        int j = i;
        while (j <= n && a[j].first == a[i].first) j++;
        for ( ; i < j; i++) {
            int r = a[i].second;
            if (r < R) ans++;
            else R = r;
        }
    }
    printf("%d\n", ans);
}

134. Centroid

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define read(a) scanf("%d", &a)

#define N 16666

int n;
int siz[N], val[N], fa[N];
int ans = 0x3f3f3f3f;
vector <int> E[N], o;

void dfs(int x) {
    siz[x] = 1;
    for (auto v : E[x]) if (v != fa[x]) {
        fa[v] = x;
        dfs(v);
        siz[x] += siz[v];
        val[x] = max(val[x], siz[v]);
    }
    val[x] = max(val[x], n - siz[x]);
    if (val[x] < ans) ans = val[x], o = {x};
    else if (val[x] == ans) o.push_back(x);
}

int main() {
    read(n);
    for (int i = 1; i < n; i++) {
        int u, v; read(u); read(v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs(1);
    printf("%d %d\n", ans, (int)o.size());
    sort(o.begin(), o.end());
    for (auto v : o) printf("%d ", v);
}

135. Drawing Lines

n = int(input())
print(n * (n + 1) // 2 + 1)

136. Erasing Edges

给定一些中点,构造一个满足每条边的中点是给定中点的可退化多边形。

Sol

$n$ 为奇数时满秩,偶数时不满秩,满秩时解一下就好了。

#include <bits/stdc++.h>
using namespace std;
#define N 11000
int n;
double x[N], y[N];
vector < pair<double, double> > ans; 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lf%lf", x + i, y + i);
    double xx = 0, yy = 0;
    for (int i = 0; i < n; i++) {
        if (i & 1) xx -= x[i], yy -= y[i];
        else xx += x[i], yy += y[i];
    }
    ans.push_back({xx, yy});
    for (int i = 0; i < n; i++) {
        xx = 2 * x[i] - xx;
        yy = 2 * y[i] - yy;
        ans.push_back({xx, yy});
    }
    if (abs(ans[0].first - ans[n].first) > 1e-8 || abs(ans[0].second - ans[n].second) > 1e-8) puts("NO");
    else {
        puts("YES");
        for (int i = 0; i < n; i++) printf("%.3lf %.3lf\n", ans[i].first, ans[i].second);
    }
}

137. Funny Strings

给定一个数字列,把首位减一,末位加一后 shift 一定位置得到原列的列称为是 funny 的。问长度为 $n$ 总和为 $K$ 的数字列,保证 $\gcd(n, K) = 1$。

Sol

考虑一个 shift 后与原串等价的过程,相当于一系列合并。如果 shift 的长度与 $n$ 不互素,则有 $a_1 = a_n = a_1 -1 = a_n + 1,$ 显然不成立,所以 shift 的长度一定与 $n$ 互素。互素时,必有 $a_1 = a_n – 1$,其中按照 shift 的方式 $a_1$ 的后继与 $a_n$ 的后继分别与它们相同,并且由于 shift 的长度属于 $\mathbb Z_n^$,且显然后继段的长度也属于 $\mathbb Z_n^$,这中间必然存在着一个一一对应。由于题设条件因此答案存在,我们枚举 shift 的长度就可以了。

#include <bits/stdc++.h>
using namespace std;

int n, K;
int a[10111];

int main() {
    scanf("%d%d", &n, &K);
    int base = K / n, m = K % n;
    for (int i = 1; i < n; i++) if (__gcd(i, n) == 1) {
        int c = 0;
        for (int j = n - 1; j != 0; j = (j + i) % n) c++;
        if (c == m) {
            for (int j = 0; j < n; j++) a[j] = base;
            for (int j = n - 1; j != 0; j = (j + i) % n) a[j]++;
            for (int j = 0; j < n; j++) printf("%d%c", a[j], j == n - 1 ? '\n' : ' ');
            return 0;
        }
    }
    assert(false);
}

138. Games of Chess

某一场比赛的胜者必须打下一场,给定每个人打了多少场,构造一个方案。

Sol

最开始我搞了一个做法:每次取出一个最大的,优先吃 1,然后吃剩下的最大的。这样听起来很靠谱,但

7
5 4 1 1 1 1 1

会挂,为什么会挂很显然。
所以,我们考虑修正这个算法:显然,1 是要吃的,但是不能把后面吃出一个 boss 出来。考虑让比赛场数少的人必败,且这样的人尽量少,这样有一个好,分界线处存在胜场的那个可能会有多的,但是这个可以被第一个人吃掉。我们可以证明这样做是对的。

#include <bits/stdc++.h>
using namespace std;

int n;
vector <pair<int, int>> ans;
pair<int, int> a[111];
int sum[111];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        a[i] = {x, i};
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i].first;
    int cur = 0, L = -1;
    for (int i = n; i >= 1; i--) {
        cur += i == n ? a[i].first : a[i].first - 2;
        if (cur >= sum[i - 1]) {
            L = i;
            break;
        }
    }
    vector < int > u;
    for (int i = 1; i < L; i++) {
        for (int j = 0; j < a[i].first; j++) {
            u.push_back(a[i].second);
        }
    }
    cur -= sum[L - 1];
    for (int i = cur; i; i -= 2) {
        ans.push_back({a[n].second, a[L].second});
        a[n].first --, a[L].first --;
    }
    for (int i = n; i >= L; i--) {
        while (a[i].first > 1 - (i == L)) {
            ans.push_back({a[i].second, u.back()});
            u.pop_back();
            a[i].first --;
        }
        if (i > L) ans.push_back({a[i - 1].second, a[i].second}), a[i - 1].first --;
    }
    printf("%d\n", (int)ans.size());
    for (auto i : ans) {
        printf("%d %d\n", i.first, i.second);
    }

} 

139. Help Needed!

#include <bits/stdc++.h>
using namespace std;
#define N 4

int a[N][N];

int main() {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            scanf("%d", a[i] + j);
        }
    }
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 3; j++) {
            if (a[i][j] == 0) swap(a[i][j], a[i][j + 1]);
        }
        if (i < 3 && a[i][3] == 0) swap(a[i][3], a[i + 1][3]);
    }
    vector <int> b;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            b.push_back(a[i][j]);
    int ans = 0;
    for (int i = 0; i < 16; i++) {
        for (int j = i + 1; j < 16; j++) {
            ans ^= b[i] > b[j];
        }
    }
    puts(ans ? "YES" : "NO");
}

不围棋(NoGo)是一种在 \(9 \times 9\) 的棋盘上进行的一种棋类游戏,游戏下子限制为禁止在棋盘上产生围棋中的吃子,最终无法行动的一方失败,另一方获得胜利。详见 Botzone 上的 NoGo。 = = 这个东西作为 AI 大作业就意味着要……爆肝……然后我把我的 Documentation 粘在下面了…… 还是挺高兴的,第一次写出了 UCT,打爆了上次想写却没写出好的五子棋 AI 的我。

Abstract

Bot 是一个主体采用了 Alpha Beta 优化的最大-最小搜索和上限置信区间蒙特卡洛树搜索(Upper Confidence Boundary Applied to Trees, UCT)的 NoGo Bot。Alpha-Beta 搜索的部分采用了可行步数差来评估局面好坏,应用了 Pattern Match 等评估方法为 Alpha Beta 优化顺序、实现剪枝、作为第二关键字为搜索结果排序,并实现了自适应搜索深度以适应前后期可达深度不同导致的时间利用不充分的问题;UCT 部分使用了经典 UCT 的实现,并且通过估价值限制一定的随机性来提高模拟的有效性,并且每一步初始时利用已有知识初始化了胜率。通过前后期算法的分治,总体胜率能达到第一梯队水平,并使得即使贪心策略被克制的情况下,仍有着不低的胜率。


Algorithm Analysis

在下面的描述中,我们令 \(N = 9 \times 9 = 81\),为棋盘大小。

作为一个完全知识博弈游戏,NoGo 游戏显然存在必胜与必败策略。然而,基于我们的算力远无法遍历 \(O(3 ^ {N})\) 种局面,亦无法遍历 \(O(N!)\) 种合法棋局,我们只能通过剪枝、估价和随机模拟的方法来实现,这在 Bot 中全有体现。

我们通过多局游戏后可以发现开局局势非常简单,此时几乎靠估价函数来进行布局——多产生「眼」,也即最简单的产生可行步数差方式,并且抑制对方产生「眼」,利用 Pattern Match 以及类似的其他方法可以很方便地求得这样的点。当然,不同的估价函数——无论怎么调参——得到的答案可能会存在「循环克制」的问题,Bot 在后面会有针对这种情况进行优化。

到游戏中期时,局面已经变得比较复杂,简单的估价已经无法很好地求得答案了。此时 Alpha-Beta 搜索派上了用场。通过对后几步的预测,Alpha-Beta 可以很轻松地避免因贪心导致的短视,亦可以稳健地在对手出现失误时获得优势。事实上,Bot 的开局也综合估价函数来应用了 Alpha Beta 搜索来避免被估价克制和压制棋力非常弱的对手。

可以发现,随着深度限制 \(k\) 的增长,搜索完第 \(k\) 层的时间 \(t(k)\) 约是 \(O(s ^ k)\) 的,\(s\) 为可行步数。注意到有 \[(\sum_{i = 1}^{k-1} t(i)) < t(k)\] 其中 \(t(k)\) 为搜索完第 \(k\) 层的时间。所以,Bot 采用了迭代加深来进行搜索,充分利用了时间限制。

不过,因为前期通常来说只能搜索出约 \(3\) 层的结果,Bot 前期使用了剪枝,可以在第一步时达到 \(6 \sim 7\) 层。

到游戏偏后期但 Alpha Beta 仍搜索不到游戏终结的时候,由于单纯的评价可行步数差效果很差,搜索里可行步数差相同的不同结果可能会导致不同程度的类似「奇数步赢偶数步输」的情况,单纯应用 Alpha Beta 搜索容易盲目地将自己的优势葬送掉。

UCT 的一次 Simulation 的复杂度为 \(O(Ns)\),其中 \(s\) 为可行步数,前期在 \(1s\) 的时限下只能进行 \(O(10 ^ 2)\) 次模拟,远远不能满足算法准确性需要。然而,注意到中后期后继状态不算多了,Simulation 也能运行约 \(O(10 ^ 3)\) 次,评估胜率也显得比较准确了,因此 Bot 此时采用了通过估价值限制一定的随机性以提高模拟效率的蒙特卡洛搜索来进行 UCT 搜索以在中后期维持并获得优势。

到游戏终局时,胜负已可以轻易判定。为了方便评测,Bot 用 Alpha Beta 来以非常短的时间做出每一步的决策。

这里说一下在 OJ 上的 \(261\) 个版本里出现过的但是最终被抛弃掉的部分尝试:

  1. 在 Alpha Beta 到深度限制时采用多元化估价以替代单一的步数差的估价。这样看起来很优秀,甚至可以避免出现前述缺点,但实际上这样严重依赖于估价函数的准确性以及和其他 bot 的克制性,效果很差。
  2. 在 Alpha Beta 估价时使用 \(O(N ^ 2)\) 的试下策略(Dot Evaluation)来优化贪心函数的短视。这样看起来很棒棒,但是牺牲的复杂度实在是太高,最终极大影响到了搜索的深度,因此最终被舍弃。
  3. 限制 UCT 模拟步数,到达指定深度时用 \[r = \frac {1 + e ^ {-k}} 2 \times D ^ s\] 来预测胜率,其中 \(k\) 为步数差,\(s\) 为任一玩家剩余可行步数,\(D\) 为衰减常数,\(\sqrt[81]{0.1} < D \leq 1\)。
    这样做效果确实不错,OJ 上上传的 IG.TheShy(223) 就是这么做的。然而,为了算法的纯粹性(强迫症),以及为了使 UCT 更稳定,Bot 没有采用这一做法。(然后因为这个原因 Bot 最终被吊打了)

Implementation Introduction

为了尝试使用 OOP 实现程序,Bot 中所有用到的结构体全部进行了封装,模块化实现功能,提高了程序的可拓展性与鲁棒性。这在 Bot 的开发中得到了体现:迭代升级的过程非常流畅,未曾需要对主体程序进行重构。当然,因为存在部分冗余函数,并且需要参数传递,程序相对冗长、常数较大是不可忽视的缺点。

局面使用了 Board 来保存;UFset 是并查集;Point 是用来替代 std::pair<int, int> 的传递坐标的位置,实现了和 pair<int, int> 相互的类型转换;策略保存在 Alpha_BetaUCT 中,两个类都有一个 public 函数 Action()

Board

判断一个局面是否可行的函数 Board::valid() 使用的是随机合并并查集来实现的,复杂度为 \(\Omega(N) \sim O(N \log N )\)。众所周知,判断气数是否合法完全可以使用 Flood Fill 实现,复杂度为 \(O(N)\),看似更优,实则不然。首先,无论是 DFS 还是 BFS 都会用到速度较慢的数据结构,包括栈和队列,常数很大;其次,\(M = 4 N\),边数本身就有大常数。而并查集由于大量的合并操作以及随机合并顺序导致 \(O(N \log N)\) 是非常松的上界,况且其 \(\log N \approx 6 \) 本来就非常小(可看做常数),并且 f[x] = getf(f[f[x]]) 利用寻址比递归快的特性跑得比西方记者快得多。因此,并查集运行的实际效果远优秀于 Flood Fill,甚至优秀于严格 \(O(N \alpha(N))\) 的按秩合并路径压缩并查集。在之后的描述中,我们将 Board::valid() 的复杂度称为 \(O(N)\)。

一个非常常用到的操作是 Board::getValidMoves(),也寻找一个局面下的可行操作。常规的做法是使用 \(O(N ^ 2)\) 的复杂度,进行试下并用 Board::valid() 判断。显然,这个复杂度是不优秀的。Bot 里实现了一个 \(O(N)\) 的 Board::getValidMoves(),使用对联通块的气计数的方法来优化判气复杂度。当然,由于我们两部分搜索都会用到对估价值进行排序,实质上调用一次 Board::getValidMoves() 复杂度是 \(O(N \log N)\) 的,不过由于 \(N\) 很小,并且其余部分函数本身常数就不小,因此这个 \(\log\) 是可以接受的。

Evaluation

对于评分系统,我们主要介绍 Pattern Match。Board::EyeDetect 实现了对 Pattern 的处理,Board::EyeDetect::eval() 通过枚举每一个位置可能成为一口气的方法,来对开局进行比较有效的估价。

我们通常都不会优先去走只有自己能走的点——那样通常会降低自己占气的优势。因此,Bot 针对这种情况进行了判断,对敌人能走的点提高优先级。

以人类智慧设置的参数显然并不一定准确。为了提高评分准确性,Bot 在本地通过模拟退火算法进行了 \(O(10 ^ 4)\) 局左右互搏的游戏,获得了一个效果更好的参数——当然,由于最初退火时没有客观的 UCT 版本对打,最终参数有过拟合的趋势,最终没有采用退火结果。

Alpha Beta

Alpha-Beta 实现部分通过评分系统加扰动来确定搜索顺序,使得搜索有随机化,并使 Alpha-Beta 剪枝更有效,并间接实现了使用贪心值作为二关键字排序,估价相同时默认保留第一个结果,自适应地完成了前中期的交替。

在对选择进行剪枝时,我们可以发现:尽管我们自己的选择从来都是估价函数得到的结果中的前几个,但敌人很可能选择出乎意料的走法。我们知道估价函数是不准确的,所以我们搜索时可以默认敌人比我们更
「聪明」。因此,Bot 的剪枝的限制对于敌人更加宽松,而对于自己的选择则适当收紧,这样在损失极少正确性的情况下 Bot 可以使搜索获得更深的深度。

UCT

UCT 实现很常规,探索常数按论文取到了 \(C= 2\)。说几点优化:

  1. 预处理了所有有关 sqrt, log, exp 的函数;
  2. 使用估价函数加大扰动来实现一种「总体而言,更倾向于采用估价函数大的一步下的随机方法」的模拟,提高了模拟效率;
  3. 每一步初始时利用已有知识初始化了胜率;
  4. IG.TheShy 等版本中采用了前述公式来减少模拟步数,预测胜率;
  5. 随机数发生器采用了 xor-shift-128+,复杂度低且随机性好。

Algorithm Switcher

当可行选择数在 \((L, R)\) 之间时调用 UCT,否则调用 Alpha Beta。在提交版本中,\(L=9,R=27\)。

One more thing…

有时,搜索程序会返回必败,此时搜索会无返回结果。秉承着永不言败的精神,Bot 将会返回一个最有希望的合法点,以期望对手下错来赢得该局游戏。

Code

调用 init() 进行初始化,调用 GetUpdate() 更新敌方策略,调用 Action() 来进行决策。

/* This is a simple NoGo bot written by fstqwq(YANG Zonghan).
 * Current Version : Alpha-Beta + UCT Version
 * For my lovely Lily
 */
#include <bits/stdc++.h>
#include "submit.h"
using namespace std;

/****** Magic ******/

#pragma GCC optimize("-O3")
#define __ __attribute__((optimize("-O3")))
#define inline __ __inline __attribute__((__always_inline__, __artificial__))

/***** Constants *****/

extern int ai_side;
string ai_name = "lily";
typedef signed char stone;
const int N = 9;
const stone NONE = 0, BLACK = 1, WHITE = 2;
const int INF = 999, TLE = 2333;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
const int x8[] = {-1, -1, 1, 1, 1, -1, 0, 0}, y8[] = {-1, 1, -1, 1, 0, 0, 1, -1};
const time_t TIME_LIMIT = time_t(CLOCKS_PER_SEC * 0.9);
const int Score[5] = {99, 32, 16, 8, 4};
const int DefaultDotLimit = 99; // deprecated

/****** Data Structures and Functions ******/

double sqLOG[300000], sq[300000], EXP[100]; // precalculate anything related to sqrt(), log(), exp()
inline double Rate(const int x) {
    return x > 0 ? 1 - EXP[x] : EXP[-x];
}
inline constexpr stone Switch(const stone x) {return stone(3 - x);}
inline bool legal(const int i, const int j) {return i >= 0 && i < N && j >= 0 && j < N;}
inline int min(int a, int b) {return a < b ? a : b;}
inline int max(int a, int b) {return a > b ? a : b;}

inline uint64_t xorshift128plus() { // xorshift128+, from Wikipedia
    static uint64_t s[2] = {200312llu + uint64_t(time(NULL)) * uint64_t(s), 9999999919260817llu ^ uint64_t(dx)};
    uint64_t x = s[0];
    uint64_t const y = s[1];
    s[0] = y;
    x ^= x << 23; // a
    s[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c
    return s[1] + y;
}

inline unsigned Rand() {
    return (unsigned)xorshift128plus();
}

template <class T> inline T Rand(const T st, const T ed) {
    return T(xorshift128plus() % (ed - st + 1)) + st;
}

template <class RandomIt> inline void Shuffle(RandomIt first, RandomIt last) { // random_shuffle()
    for (int i = int(last - first) - 1; i > 0; --i) {
        swap(first[i], first[Rand(0, i)]);
    }
}

template <int SIZE> struct UFset { // Union-Find Set
    int f[SIZE];
    inline UFset () {
        for (int i = 0; i < SIZE; i++) f[i] = i;
    }
    inline void clear () {
        for (int i = 0; i < SIZE; i++) f[i] = i;
    }
    inline int & operator [] (const int x) {return f[x];}
    __ int getf(const int x) {
        return f[x] == x ? x : (f[x] = getf(f[f[x]])); // magic
    }
    inline void merge(const int x, const int y) {
        if (getf(x) != getf(y)) {
            f[getf(y)] = getf(x); // no need of optimization
        }
    }
    inline bool isRoot(const int x) {
        return f[x] == x;
    }
};

struct Point { // pair of int
    int x, y;
    inline Point () {}
    inline Point (const int a, const int b) {x = a, y = b;}
    inline Point (const int a) {x = a / N, y = a % N;}
    inline Point (const pair <int, int> a) {x = a.first, y = a.second;}
    inline Point operator = (const Point b) {x = b.x, y = b.y; return *this;}
    inline bool operator < (const Point &a) const {return x < a.x || (x == a.x && y < a.y);}
    inline operator pair<int, int>() const {return make_pair(x, y);}
};

int lasteval; // Record last value of evaluation, optimization of constant
bool isUCT; // Avoid passing too much bools, optimization of constant

struct Board { // Chessoard
    struct EyeDetect { // A data structure that can evaluate the board by eye detection
        int a[N][N];
        inline int at(const int i, const int j) const {return a[i][j];}
        inline int at(const Point x) const {return a[x.x][x.y];}
        inline void eval(const Board &board, const stone hand) { // Complexity : O(N ^ 2) with constant of 5
            memset(a, 0, sizeof a);
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) if (!board.at(i, j)) {
                    int c[3] = {0};
                    for (int d = 0; d < 4; d++) {
                        int tx = i + dx[d], ty = j + dy[d];
                        if (board.at(tx, ty) >= 0) c[board.at(tx, ty)]++;
                    }
                    if (!c[1] || !c[2]) {
                        const int val = Score[c[0]];
                        if (c[Switch(hand)]) a[i][j] += val;
                        for (int d = 0; d < 4; d++) {
                            int tx = i + dx[d], ty = j + dy[d];
                            if (!board.at(tx, ty)) {
                                a[tx][ty] += val;
                            }
                        }
                    }
                    for (int d = 0; d < 4; d++) {
                        int tx = i + x8[d], ty = j + y8[d];
                        if (board.at(tx, ty) >= 0) c[board.at(tx, ty)]++;
                    }
                    a[i][j] += c[hand];
                }
            }
            a[0][0] += 8; a[N - 1][N - 1] += 8;
            a[0][N - 1] += 8; a[N - 1][0] += 8;
        }
    };

    stone g[N][N];
    inline Board () {memset(g, 0, sizeof g);}
    inline Board (char x) { memset(g, x, sizeof g); }
    inline stone * operator [] (const int x) { return g[x]; }
    inline stone at(const int i, const int j) const { if (i >= 0 && i < N && j >= 0 && j < N) return g[i][j]; else return -1;}
    inline stone at(const Point x) const {if (x.x >= 0 && x.x < N && x.y >= 0 && x.y < N) return g[x.x][x.y]; else return -1;}
    inline void set(const int i, const int j, const char k) {g[i][j] = k;} 
    inline void set(const Point x, const char k) {g[x.x][x.y] = k;}
    inline void reset(const int i, const int j) {g[i][j] = 0;}
    inline void reset(const Point x) {g[x.x][x.y] = 0;}

    inline bool valid() const { // Complexity : O(N ^ 2) // Unused
        UFset<N * N> f;
        int chi[N * N];
        memset(chi, 0, sizeof chi);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (g[i][j]) {
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj)) {
                        if (g[ti][tj]) {
                            if (g[ti][tj] == g[i][j]) {
                                f.merge(i * N + j, ti * N + tj);
                            }
                        }
                        else chi[i * N + j]++;
                    }
                }
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (g[i][j] && !f.isRoot(i * N + j)) {
                    chi[f.getf(i * N + j)] += chi[i * N + j]; 
                }
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (g[i][j] && f.isRoot(i * N + j) && !chi[i * N + j]) {
                    return false;
                }
            }
        }
        return true;
    }

    inline void sort_by_eval(vector <Point> &a, const bool MY[N][N], const bool EN[N][N], const stone hand, const int chi[N * N]) { // Complexity : sort(s ^ 2)
        static pair<int, Point> ret[81];
        static EyeDetect Eval;  
        Eval.eval(*this, hand);
        int c = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (MY[i][j]) {
                int value = (EN[i][j] * 16 + chi[i * N + j] * 4 + Eval.at(i, j)) * 1024 + Rand() % (isUCT ? 16384 : 2048); // Consider value of enemy's availability and randomization
                ret[c++] = make_pair(-value, (Point){i, j});
            }
        }
        sort(ret, ret + c);
        a.resize(c); // Avoid push_back()
        for (int i = 0; i < c; i++) a[i] = ret[i].second;
    }

    inline void getValidPoints(const stone hand, vector <Point> &ret) { // Complexity : O(N ^ 2) + sort_by_eval()
        static UFset<N * N> f;
        static int chi[N * N];
        static bool MY[N][N], EN[N][N];

        // Clear
        ret.clear();
        f.clear();
        memset(chi, 0, sizeof chi);
        memset(MY, 0, sizeof MY);
        memset(EN, 0, sizeof EN);

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (g[i][j]) {
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj) && g[ti][tj] && g[ti][tj] == g[i][j]) {
                        f.merge(i * N + j, ti * N + tj);
                    }
                }
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (!g[i][j]) {
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj) && g[ti][tj] && chi[f.getf(ti * N + tj)] >= 0) {
                        chi[f[ti * N + tj]] = -(chi[f[ti * N + tj]] + 1);
                    }
                }
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj) && g[ti][tj] && chi[f.getf(ti * N + tj)] < 0) {
                        chi[f[ti * N + tj]] = -chi[f[ti * N + tj]];
                    }
                }
            }
        }
        int aval = 0, eavl = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (!g[i][j]) {
                int o[3] = {0}, c[3] = {0}, e = 0;  
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj)) {
                        if (g[ti][tj]) {
                            c[g[ti][tj]]++;
                            if (chi[f.getf(ti * N + tj)] == 1) o[g[ti][tj]]++;
                        }
                        else e++;
                    }
                }
                if ((o[1] == 0 || o[1] < c[1] || e) && (!o[2]) && (c[1] + e)) (hand == BLACK ? (aval++, MY) : (eavl++, EN))[i][j] = 1;
                if ((o[2] == 0 || o[2] < c[2] || e) && (!o[1]) && (c[2] + e)) (hand == WHITE ? (aval++, MY) : (eavl++, EN))[i][j] = 1;
                chi[i * N + j] = o[hand];
            }
        }
        lasteval = aval - eavl;
        sort_by_eval(ret, MY, EN, hand, chi); // shuffle the return value by eye evaluation
    }

    inline int eval(const stone hand) const { // Complexity : O(N ^ 2)
        int ret = 0;
        static UFset<N * N> f;
        static int chi[N * N];
        f.clear();
        memset(chi, 0, sizeof chi);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (g[i][j]) {
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj) && g[ti][tj] && g[ti][tj] == g[i][j]) {
                        f.merge(i * N + j, ti * N + tj);
                    }
                }
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (!g[i][j]) {
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj) && g[ti][tj] && chi[f.getf(ti * N + tj)] >= 0) {
                        chi[f[ti * N + tj]] = -(chi[f[ti * N + tj]] + 1);
                    }
                }
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj) && g[ti][tj] && chi[f.getf(ti * N + tj)] < 0) {
                        chi[f[ti * N + tj]] = -chi[f[ti * N + tj]];
                    }
                }
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (!g[i][j]) {
                int o[3] = {0}, c[3] = {0}, e = 0;  
                for (int d = 0; d < 4; d++) {
                    int ti = i + dx[d], tj = j + dy[d]; 
                    if (legal(ti, tj)) {
                        if (g[ti][tj]) {
                            c[g[ti][tj]]++;
                            if (chi[f.getf(ti * N + tj)] == 1) o[g[ti][tj]]++;
                        }
                        else e++;
                    }
                }
                if ((o[1] == 0 || o[1] < c[1] || e) && (!o[2]) && (c[1] + e)) ret++;
                if ((o[2] == 0 || o[2] < c[2] || e) && (!o[1]) && (c[2] + e)) ret--;
            }
        }
        return lasteval = (hand == BLACK ? ret : -ret);
    }
};

/****** Main Strategies ******/

Board Main;
stone my, en;
int Step = 0;
time_t StartTime;

inline bool isTLE() {return clock() - StartTime > TIME_LIMIT;}

class Alpha_Beta {
    private:
    __ int dfs(const int Steps, const stone hand, int alpha, const int beta) {
        if (!Steps) return Main.eval(hand);
        if (isTLE()) return -TLE;
        vector <Point> choice;
        Main.getValidPoints(hand, choice);
        int width = min(16 + (choice.size() < 50) * 16 + (hand == en) * 16, (int)choice.size()); // Limit the width of searching, assuming that enemy is wiser
        for (int j = 0 ; j < width; j++) {
            const Point &i = choice[j];
            Main.set(i, hand);
            int value = -dfs(Steps - 1, Switch(hand), -beta, -alpha);
            Main.reset(i);
            if (value == TLE) return -TLE;
            if (value >= beta) return beta;
            if (value > alpha) alpha = value;
        }
        return alpha;
    }

    int ans_value = -INF;
    Point ans = {0, 0};

    public:
    inline pair<int, int> Action() {
        isUCT = 0;
        vector <Point> choice;
        Main.getValidPoints(my, choice);

        ans = *choice.begin(); // assert choice.size() > 0
        ans_value = -1;

        unsigned StepLim = 2;
        while (!isTLE() && abs(ans_value) < INF) {
            int tmp_value = -INF;
            Point tmp = ans; // Instead of {0, 0}, never say die.

            unsigned vised = 0;
            for (auto i : choice) {
                Main.set(i, my);
                int value = -dfs(StepLim, en, -INF, -tmp_value);
                Main.reset(i);  

                if (value == TLE) break;

                vised++;

                if (value > tmp_value) {
                    tmp_value = value;
                    tmp = i;
                }
            }
            if (vised == choice.size()) {
                ans = tmp;
                ans_value = tmp_value;
                StepLim++;
            }
        }

        return ans;
    }
};

class UCT {
    private:
    static constexpr int ROUNDS_PER_GAME = 10;
    static constexpr double C = 1.4;
    struct Node {
        Board board; stone hand;
        vector <Point> choice;
        vector <Node*> son;
        Node* fa;
        unsigned size, now;
        int N;
        double Q;
        inline double value(const int faN) const {
            return (double)(N - Q) / N + C * sqLOG[faN] / sq[N];
        }
        inline Node* BestChild() const {
            if (!now) return NULL;
            Node *ret = son[0]; double rv = 0;
            for (unsigned i = 0; i < now; i++) {
                double val = son[i]->value(N);
                if (val > rv) ret = son[i], rv = val; 
            }
            return ret;
        }
    };

    Node t[int(1e5)], *ptr, *root;

    inline Node* newNode(const Board &x, const stone hand, const Point step = {-1, -1}, Node* fa = NULL) {
        ptr->board = x;
        ptr->hand = hand;
        ptr->fa = fa;
        if (fa != NULL) ptr->board.set(step, Switch(hand));
        ptr->board.getValidPoints(hand, ptr->choice);
        ptr->size = (unsigned)ptr->choice.size(), ptr->now = 0;
        ptr->son.resize(ptr->size);
        ptr->N = 0, ptr->Q = 0;
        return ptr++;
    }

    inline void update(Node *x, double Y) {
        while (x != NULL) {
            x->N += ROUNDS_PER_GAME;
            x->Q += Y;
            Y = ROUNDS_PER_GAME - Y;
            x = x->fa;
        }
    }

    inline Node* expand(Node *x) {
        x->son[x->now] = newNode(x->board, Switch(x->hand), x->choice[x->now], x);
        update(x->son[x->now], ROUNDS_PER_GAME * Rate(lasteval));
        return x->son[x->now++];
    }

    inline Node* policy(Node *x) {
        while (x->size) {
            if (x->now < x->size) return expand(x);
            else x = x->BestChild();
        }
        return x;
    }

    inline double simulation(const Node *x) {
        static Board tmp;
        static vector <Point> choice;
        int T = ROUNDS_PER_GAME; double Y = 0;
        while (T--) {
            stone hand = x->hand;
            tmp = x->board;
            while (true) {
                tmp.getValidPoints(hand, choice);
                if (!choice.size()) {
                    Y += int(hand != x->hand);
                    break;
                }
                tmp.set(choice[0], hand);
                hand = Switch(hand);
            }
        }
        return Y;
    }

    public:
    inline pair<int, int> Action() {
        isUCT = 1;
        ptr = t; 
        root = newNode(Main, my);

        // UCT Search
        while (!isTLE()) {
            Node *x = policy(root);
            double result = simulation(x);
            update(x, result);
        }
        Node *bc = root->BestChild();
        Point ans;
        for (unsigned i = 0; i < root->now; i++) {
            if (root->son[i] == bc) {
                ans = root->choice[i];
                break;
            }
        }
        return ans;
    }
};

Alpha_Beta alphabeta;
UCT uct;

inline void init() {
    cerr << "GLHF" << endl;
    if (ai_side == 0) my = BLACK, en = WHITE;
    else my = WHITE, en = BLACK;
    // precalculate
    for (int i = 0; i < 100; i++) EXP[i] = exp(-i) / 2;
    for (int i = 1; i < 300000; i++) sqLOG[i] = (double)sqrtl(log(i));
    for (int i = 1; i < 300000; i++) sq[i] = (double)sqrtl(i);
}

inline void GetUpdate(pair<int, int> location) {
    Step++;
    vector <Point> choice;
    Main.getValidPoints(en, choice);    
    Main.set(location, en);
}

inline pair<int, int> Action() {
    Step++;
    StartTime = clock();

    if (Step == 1) { // First move of BLACK
        Main.set(make_pair(0, 0), my);
        return make_pair(0, 0);
    }

    vector <Point> choice;
    Main.getValidPoints(my, choice);

    Point ans;
    if (choice.size()) {
        ans = (9 < choice.size() && choice.size() < 27) ? uct.Action() : alphabeta.Action(); // divide-and-conqure on algorithms
    }
    else {  // Never say die!
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) if (!Main.at(i, j)) {
                choice.push_back({i, j});
            }
        }
        if (choice.size()) ans = choice[Rand() % (choice.size())];
    }

    Main.set(ans, my);
    return ans;
}

那传说 忘却了我的寂寞
英雄名不堪得
何必较我混沌徒费口沫
这人间 毕竟我真正走过
一途平九百波 九千错
凌云渡成正果
但我 有九九八十一种不舍


Day -1

和 QWsin、wxh 还有一位绵阳小哥住在一间寝室里,还是比较 Excited 的。

七中爷爷们还有南山爷爷们都在左右隔壁,栋栋也不远。

食堂好评。

晚上和 Menci、zyz、Qizy(ZYQN)、Sengxian 等等打炸弹小分队。我好菜啊.jpg

Day 0

上午开幕式,蜜汁校长讲话,“泥萌都是 CCF NOI 的孩子!”。dzd 先生骚话连篇。

Qizy 真牛逼,这么快就撩到 chrt 了。

下午笔试 AK,试机只有传统题,感觉药丸。

晚上心态不太好,开了一道 splay,一道 fft,一道树上前缀和,只能瞎写。最后 fft 没写。

NOI2003 文本编辑器 30min 1A,本来是好事,但是这是我 day1 惨挂的伏笔。

做了做 wxh 的毒瘤题。真毒。

去隔壁四中爷爷们那里 gay 了一会儿,嘿嘿嘿。

晚上睡不着,突然接到初中和高中好朋友的电话,被人惦记着的感觉真幸福。

Day 1

早饭不太舒服。

T1,造计算机?

T2,卧槽,字符集很小的字符串题,怕是药丸。

T3,九老师的 DP,好难。

于是怼 T1。先写了一发暴力,然后再找了好久规律,直到发现一位加一可以看做是一个 xor 和一个区间翻转。复杂度好像超了,想了一会儿发现可以在线段树上 dfs,对 32 位做暴力,然后再区间翻转复杂度就比较对了,算了算内存开得下。

时间已经过去 2h,不过我大概 20 min 就写完了,过了编译直接 1A。退役了想想,还是挺佩服自己在考场上的代码能力的,毕竟 200+ 行代码能够完美无缺地在 20 min 内写完,也可以说挺厉害的了吧。

把对拍写完,赛程过半,心有点慌。T2 因此看题不仔细,把 K 看做了一个 1e5 级别的数,然后怎么想都不行,把脑子里出现的 hash 正解给枪毙了。于是我只能先写 24 分暴力。

这个时候,我做出了一个改变我一生的决定。因为头天晚上 splay 很顺手,我居然没有继续认真看条件,特 么 在 考 场 上 准 备 用 L C T 维 护 链!

然后 1h 过去,写挂。

这个时候是真的慌了。看 T3,本来暴力挺好想的,愣是想了 40 min。

最后当然只能交交最简单的暴力了。


100 + 32 + 10,看成绩还不算太惨,rk 100 左右,还能翻。

wxh MLE,惨惨,不过还是比我高,这才是真正的大佬.jpg。

栋栋崩崩。QWsin 崩崩崩。


发了条说说,说 day2 AK 还能翻。

其实不用 AK 就能翻,不过我是傻子。

本来他们在打 deeeep.io,wxh 在栋栋的带领下开始打东方,毒瘤。

想打三国杀,结果大家都不打,我网页版三国杀也被盗号,找回真麻烦(10 月才找回成功)。

Day 1.5

早上忘记在干嘛了。

下午三国杀。

wxh:连营,AK,杀!

身份证掉了,去办了个临时的。

晚上不想写题,想着 Day 2 需要 AK 心态就比较崩。

Day 2

比 Day 1 有了更重的心理压力。

T1 是一道被我一眼看出来的 2-SAT,但我不会。

T2 是一道看起来像网络流的题。

T3 是防 AK (假)动态凸包。

因为不会 2-SAT,所以很慌,自己 YY 出来的 2-SAT 无法正常工作,骗分也没太有正常工作的可能。

有点崩。

T2,先写暴力网络流。

然后挂大样例,发现从第 29 天开始自己的输出就错了。

知道是建图挂了,但检查不出来。

心态崩了。

这时去把 T3 暴力写了,发现自己可能对向量排序不太熟练,希望有分。

调 T2。
调 T2。
调 T2。
看 T1,没啥好想到的。
调 T2。
调 T2。
调 T2。

时间一分一秒过去。

我终于知道,我要退役了。

看见时间,每跳一次心凉一次。

写了个大家都看不见的 AFO。

游戏结束了。

哭得有点累。


55 + 40 + 20。

下午讲题时,因为分低,连题都听不完,就被叫出去填面试表。

身不由己。

之前的成绩还可以,所以拿到了 sjtu 一本。

尬笑拍了个照,尬笑和张老师握了个手,和进了队的凯爷以及让我潜入四中听课,愿意替我背锅的文老师尬打招呼。

啊,然后在一个少有人看见的地方哭了一会儿。

天真蓝。阳光挺刺眼的,不过过一会儿太阳就落山了。

没去和爸妈老师吃饭,丢脸。

QWsin 似乎比我惨,好像没有签到约。


下午晚上三国杀,吼了一声,只有我不是 THU,全场沉默。

这可是八人局啊。

Day 3

上午错过早饭,和 QWsin 去下象棋。

Qizy 在和 Chrt 下跳棋,哼。

下午拿了个惨白色的牌子,提前回去了。

机场办临时身份证真麻烦。

金中 yylidiw 爷爷告诉我我的图怎么挂了。哦,原来我的“优化”这么厉害。


就这么退役了啊。

day1 如果 T2 没挂,我就 Au 了呀。

或者,day2 我能写出一个 O(nm) 的 2-SAT,并且不“优化”建图,也行呀。

或者,我 day1 没挂,day2 哪怕写不出 2-SAT,只要写对网络流,就能进队啊。

或者,我 day1 被卡常,day2 不失误,也能进队啊。

……

哪有那么多如果,可笑。

wxh 挂了两天 T1,照样能够在 Au 线边上。

栋栋 day1 雪崩,day2 还不是能翻回来。

人家 yql 还不是 day2 翻回了集训队。

哪有那么多如果,实力不济才是最大原因;发挥失常才是常态。

毕竟靠着运气走到现在,也比大多数人好运了吧。

不过,我可能与 thu 无缘了啊。

在二月对自己实力高估后,现在与 pku 也无缘啦。

也罢,这些都不重要,至少还有大学上。退役才是真的不甘心。

该怪谁呢?

怪学校辣鸡,支持竞赛非常晚,比别人少 x >= 1 年学习时间,进队后没有队友?

不吧,人家 LCA 还不是一年集训队。

只能说自己努力不够吧,省选后因为各种原因太水了。

太水了。

没有再来一年的机会,为什么我还要水呢?

后悔,没用啊。你高二了,没有重来的机会了。

你说 Never say die,也只能呐喊到游戏的最后一刻呀。现在,游戏结束了。

那就在这止步吧,永远不要再给自己留下这种尴尬的局面。

那一年我们望着星空
有那么多的灿烂的梦
以为快乐会永久
像不变星空陪着我