fstqwq – Never say die.

Constructive – 极道加训

2019-11-25 by fstqwq·0 Comments

以后再卡构造我是狗

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。
首先和井字棋相同，先手必不败，我不会直接证但是感受下外加后面的构造可以证明，我们先不考虑初始颜色，讨论如下：

存在度数为 4 的点，则先手必胜；
存在度数为 3 的点存在两个出度的度数不小于 2，则先手必胜。
存在两个距离为偶数的度数为 3 的点，则先手必胜，这一种情况可以看成 1 的拓展。
其余情况为平局，包括只有两个度数为 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

2019-10-28 by fstqwq·0 Comments

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

acm.sgu.ru@CodeForces

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

#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

特判 0
取整
如果不转正，最后可能除负数导致区间反转

#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 树，树边按深度交替染色，非树边当做较深的那个的儿子处理，这样至多只有根不满足条件了，如果不满足条件的话考虑调整：

如果根的树上 $deg > 1$，那么随便选一个子树反色就好了；
如果根的 $deg = 1$，存在一个返祖边使得与非叶子响邻，那么这条边的颜色可以直接改；
如果 $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，我们可以构造性地证明这样的哈密顿回路必然存在。
首先，我们随便搞一个极长的链，这样链的起点终点都没有相邻的不在链上的点。我们讨论两种情况：

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

由于 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 是：

按输入排序
按度数判可行（是否超过最大度数，是否有两个相邻的满度的点）
判存在 $0$
每一步用 $\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");
}

卡掉数据如下：

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

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 必定连边，否则题目条件无法满足。然后就是判可行，我是这么判的：

连通
每个点度数为 $2$
用扫描线判断不存在这种情况：
```
..*-*..
*-|-|-*
*-*.*-*
```

#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");
}

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:

应该输出

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);
    }
}

NoGo Bot

2018-10-30 by fstqwq·1 Comment

不围棋（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$ 个版本里出现过的但是最终被抛弃掉的部分尝试：

在 Alpha Beta 到深度限制时采用多元化估价以替代单一的步数差的估价。这样看起来很优秀，甚至可以避免出现前述缺点，但实际上这样严重依赖于估价函数的准确性以及和其他 bot 的克制性，效果很差。
在 Alpha Beta 估价时使用 $O(N ^ 2)$ 的试下策略(Dot Evaluation)来优化贪心函数的短视。这样看起来很棒棒，但是牺牲的复杂度实在是太高，最终极大影响到了搜索的深度，因此最终被舍弃。
限制 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_Beta 与 UCT 中，两个类都有一个 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$。说几点优化：

预处理了所有有关 sqrt, log, exp 的函数；
使用估价函数加大扰动来实现一种「总体而言，更倾向于采用估价函数大的一步下的随机方法」的模拟，提高了模拟效率；
每一步初始时利用已有知识初始化了胜率;
在 IG.TheShy 等版本中采用了前述公式来减少模拟步数，预测胜率;
随机数发生器采用了 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;
}

成年祭。

2018-09-28 by fstqwq·2 Comments

十八年浑浑噩噩地混了过去。
17 岁的那年，充斥着幻梦，棱角和失望。

「你已经是个大人了，要明白所有事情都不是闹着玩的了。」
也许那个曾经叛逆的少年正在逐渐学会放弃，但我好怀念那个到处写满 “Never say die” ，跌跌撞撞但又勇往直前的小孩子。

想来，在另一个时间线里，我现在应该在秦皇岛，准备今天用 ACM 生涯里第一场比赛作为给自己的献礼。

哈哈。

Anyway, life still goes on.
Happy 18th birthday to myself.

密码保护：SJTU

2018-06-13 by fstqwq·要查看留言请输入您的密码。

又是一年四月天

2018-04-05 by fstqwq·2 Comments

清明时节，细雨纷纷。

年年岁岁花相似，岁岁年年人不同。

——不对，wxh、mcfx、yfz 都还在，再一次毫无悬念屠杀 uestc 校赛。

当然，我不在了。

一头天天喊着我名字当傻逼的李斯猪，一只菜到变形还自暴自弃的妹狗狗，——希望省选不是你们 OI 的终点。

还有 Yonda 和 €，有机会当然是最好的；再不济，也能感受一下 T1 选手的实力，明年再战也无妨。

不管怎么说，加油吧。

永远相信，汗水是不会骗人的。

Now the old king is dead, long live the king.

NOI 2017 退役

2017-11-20 by fstqwq·7 Comments

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

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，也只能呐喊到游戏的最后一刻呀。现在，游戏结束了。

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

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

BZOJ 代码 (latest update: 20170807)

2017-08-07 by fstqwq·0 Comments

退役记坑了好久了……但还是不想写

然后这几天想玩RNN，于是预处理了一下自己BZOJ上的AC代码：

删去除 C/C++ 的其他语言
删去多余空行
将题目名称变为注释

于是，你可以点这里下载我的BZOJ AC代码。

2017.6.21-2017.7.14 CDQZ训练

2017-06-22 by fstqwq·2 Comments

唔……张老师让我每天写总结……QwQ
2016.6.21

今天去七中玩耍第一天，地铁居然这么快好评。

上午做题，

T1是欧拉心算，我居然推出来了（虽然的确很简单）；

T2是一道很简单的卷积，我竟然没看出卷积的本质……最开始思路卡在了我去年出过的一道题上，不仅超级麻烦而且时间跑满了。后来发现枚举端点不仅快而且好……暴力艹了过去。事实上可以FFT，因为本质上就是个卷积。

T3动态仙人掌，求加点后的直径。然而我连树的部分分都不会……后来被讲题时才点醒，LCT维护距离就好了。（讲正解时睡过去了TAT

然后下午晚上开始花式字符串。

你们怎么那么熟练啊？QAQ

我反正基本上都不太会，跟节奏都显得比较吃力。

不管吧，至少多见了很多奇技淫巧。

而且至少没颓废了，想了题了。

希望能够跟上dalao们的节奏吧……

吃饭好贵啊QAQ一天40快破产了。（听YJQ说便当和肥肠粉便宜

哦中午返校我不知道怎么进学校，碰了下大门被保安质问好久……（我演技不够熟练233）

碰到精爷，他说在七中过得很好，恩祝福他能够在七中得到更好的资源和条件吧。

2017.6.22

我甚至记不到FancyCoder老师到底讲了什么…大概只记得一个K维数点了…而且我觉得按照bitset的做法空间是不是会炸啊？TAT

下午第一题我推出了一个幂求和可搞的多项式……然后掏出wwwwodddd3.pdf乱抄一通＝＝，第二题神tm bitset，第三题好神的字符串啊TAT不会。

于是210，输出无解得了10分。

好像这个世界就我一个写第一题的N log N呢……不过幸好我只有一步带log，跑起来和O(N)最慢的差不多。

晚上因为没课我回家昏睡了10个小时 = =。

2017.6.23

上午是陈老师的题。他们太强啦怎么什么都会做啊？于是我敲了三道暴力。结果还有一道差点敲挂了，交上去前才改了出来。于是20+50+70，感谢陈老师良心暴力分；然而mcfx 290…绝望。

于是下午大家又水水地把三道题带过了。我只能一个人上去找陈老师深入交♂流(捂脸

啊呸哪里来的交流明明是单向的(逃

2017.6.24

唔…神tm计数不会，于是我怼T2……退火加三分套三分，交上去居然有70分，改了改就90了……orz……

他们怎么什么题都会啊，讲课那么快……

2017.6.25

膜Seter……HackVM手玩了59分233，然后被HackVM的Quine吓尿了，还有这种操作.jpg。然后他们都会点分TAT……

晚上神tm讲提答，结果讲着讲着就变成构造专场了……

2017.6.26

T1怎么这么简单……T2推结论失败，于是上wiki强行看懂上升幂符号然后顺便hack了一波大爷们的代码2333……结果我0写成1滚了……

晚上神tm数学……博弈比什么几何有趣多了……

2017.6.27

三道YJQ良心送分题……

然而我T1 dfs x -> X 丢了88分 TAT

T2暴力打挂只有15……

T3没去推也是个暴力分

于是垫底滚了

艹

2017.6.28

网络流写挂 100 -> 10

暴力写挂 70 -> 0

又垫底啦2333

YJQ讲博弈比Seter有趣！

2017.6.29

YJQ出原题！哼。

T2出锅强行改题意233……然而我凸包写挂滚了。

于是又垫底咯233

2016.6.30

T1 sbdp……然而司机写了一个特别神的六方dp，神到令人目瞪口呆.jpg ，然而再神也T了……233

T2 矩形面积并好强啊！

T3 dp好神啊！

2017.7.1

简单Fail树上线段树合并……

然而其他都不会了233凸包都写挂了

2017.7.2

T1看来像是一个简单AC自动机……然而有坑，首先因为字符集很大我们不能像26一样直接更新Fail指针到每个节点，但是暴力跳要T。于是需要一颗主席树……差点TLE orz

T2 T3 神题 orz

2017.7.3

T1 挺蠢的呀TAT我没想到是我傻

T2 最小割树可过……而且因为度数小，FF比dinic快？艹

T3 cnmbmdzz

2017.7.4

最开始没看懂T1题意……真丢人，我退群吧

T2 分段计数容斥DP……然后我太菜了只会暴力

T3 强行题意 cnmbmdzz

2017.7.5

毒瘤yjq搬花oj原题

T1是征途加强版……我没看出来这是征途我是不是应该可以退群了

T2 卧槽？这能做？（wsj A了这题后）卧槽？这都能A？

T3 胖题不会自杀吧

2017.7.6

垃圾windows下的lemon不能输出long double 60 -> 0

T2 假题意 cnmbmdzz

T3 提答，出题人给的checker是一坨屎……于是吓得我学习了一下python字符串处理；然后题也不良心，一个meet in the middle可以艹6个点

2017.7.7

LNR day1

签到题想了一个小时

然后T2 woc能做？（然后后来想想题解很有道理orz

T3 小学数学杀TAT……然后被大佬点醒后推了推式子，xjb不用杜教筛拿了60。被xmk老爷证了是 $ \sqrt M$的，然而常数……

160，似乎打了T2暴力后分数还可以？

2017.7.8

全场梦游心态爆炸

艹

然后都没敢交题不然分数太惨了。

cnmbmdzz

第一题好题？挺厉害的分类讨论dp，但是我就是不会TAT

第二题也是好题？首先展开式子就可以 O(N) 预处理了，然后就可以跑凸包了orz

第三题构造神题 orz

2017.7.9

因为有我的题我就睡过去了Zzzzz

其实T1非常妙。但我的毛病是不去深入思考，于是就暴力分orz

T2其实也很妙？被CTSC论文吓走了。

T3我单独写一篇出题记吧2333，最后看看得分分布很妙呀QwQ

2017.7.10

T1先是被题意杀，后还是不会……然后看了看std，恩很有道理…我记得noip前也有道关于排列的dp用了这个思想然后我也gg了。

T2 虚树居然没挂……233

T3 明明是一道乱搞题非要subtask……orz

2017.7.11

T1 三维数点没卡过去，然后std是个很简单的容斥？oi学傻了，小学都会的东西都不会了

T2 字符串弃疗

T3 挺好推的博弈吧……然后我弃疗了？orz

2017.7.12

T1 状压预处理写挂inf次……卡常技术不高超没卡过去

T2 傻逼网络流，但是标程答案是错的真是 * 苟了；同时学习了一波牛逼的建图，转化的思路挺秒的233

T3 好牛逼的转化

2017.7.13

本来是UNR，起床起晚睡一天

啊呸，睡了一个上午，下午晚上星巴克一直坐着的，xjb切bzoj

2017.7.14

T1 xjb乱搞本来94分，结果subtask 38分……orz

T2 感觉没想到直径实在是太蠢了；数据水到给了20分链

T3 全场都会的sb dp吧……

下午颁奖。于是拿了个光荣垫底奖。不过主要是看表演233

hbb唱START:DASH好萌啊！（为什么不伪声（滑稽

大佬好萌啊QwQ

csz和yjq增援操！哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈

神tm唱歌，结果变成底层群员蹲地上gay来gay去……

说好的写总结，结果写了一大堆废话。

感谢张老师给我这个机会到七中去见了世面，感谢yjq大力相助让我有机会到七中来玩。

唔，越到退役越乱想好多。

曾经的我以为，我一定能够完成前人都能完成的事情。

YJQ 是我真正接触oi后的偶像？233

然后我就以 YJQ所取得的成绩作为我衡量自己的标准。

然而我还是太菜了。

noip心态一崩考得特别炸，连500都没上。

然而这仍然阻挡不了我冬令营时候的狂妄，拒了PKU的省队一本。

当时想想，我可是要和他们一样THU的，哪里需要保底。

于是thuwc成功成为了50 ~ 60名中的一个，给了希望，然后幻灭。

省选靠着运气才进了B队。

APIO，我因为NOIP爆炸，连国际金的资格都没有，更何况我还差14分。

THUSC，炸到连面试都没进。

还有几天NOI了，结果是未知的，但是其实也是已知的了。

似乎，我这一路已经证明了，我也许终将是个弱者。

因为，我既没有足够的天赋，也没有其他天赋异禀的人努力。

自己的能力与努力，远没达到自己的期望，更别谈达到那些真正的强者了。

我看到wxh，我才知道，原来我真的是在浪费时间。

我相比起他们，就是玩了一年高二。

我浪费了那么多时间，我该干的事情都没干；

甚至占走了那些还有着梦想的人的一个省队名额。

可我还不想退役啊……

我还有……

好多事没完成啊……

我还有……

好多东西没学啊……

……

但，也许，几天后我就要止步了。

至少我这一路走过来，还是付出了一点努力的吧。

不管怎么样，我做过的题虽然少，但是还是比大多数人多了吧。

在弱校搞oi不是借口，但的确有好多好多我在七中同学身上感受不到的无奈。

我能够走到现在，运气的确占了很大成分，但是自我奋斗也许还是有的吧。

虽然，一切我做的事情都太无力太卑微了，更何况我还水。

入阵曲，伴我无悔的狂妄。

「HAOI2016」找相同字符

2017-06-15 by fstqwq·0 Comments

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。

两行，两个字符串 $s_1,s_2$，长度分别为$n_1, n_2$。字符串中只有小写字母。

输出一个整数表示答案

样例输入

aabb
bbaa

样例输出

$1 \leq n_1, n_2 \leq 200000$

内存限制: 256 MiB 时间限制: 1000 ms

传送门：

https://loj.ac/problem/2064 或 http://www.lydsy.com/JudgeOnline/problem.php?id=4566

网上大部分题解都是关于SAM的……

然而我又用SA水过了QAQ

从两个串中分别取出一个后缀，对答案的贡献是他们的$\mathrm{LCP}$的长度；并且枚举所有后缀就是枚举了所有情况，因为实质上我们枚举的是相同子串的开头。

这样，如果将两个串加入位置在$\mathrm{split}$的分隔符拼接在一起变为$S$，答案变为了$$
\sum_{i = 1} ^ {\mathrm{split} – 1} \sum_{j = \mathrm{split} + 1}^{|S|} \mathrm{LCP}(i, j)
$$转化问题到后缀数组上，那么问题就转化为分别统计对于每个$h_i$，当他作为最小值即$\mathrm{LCP}$时，对答案做贡献的次数$\mathrm{cnt}_i$。

如果只考虑一个点，那么也就是统计经过它的符合条件的区间数。这个点左右合法区间端点必然是一个连续的区间$[L_i, R_i]$，为了避免重复我们定义$L_i$为最小的使得$\mathrm{min}(h_{[L_i, i)}) \gt h_i$的值，$R_i$为最小的使得$\mathrm{min}(h_{[i, R_i]}) \geq h_i$的值，有$$
\mathrm{cnt}_i = \sum_{l = L_i} ^ {i – 1} \sum_{r = i} ^ {R_i} h_i \cdot [(\mathrm{sa}_l < \mathrm{split} \ \mathrm{and}\ \mathrm{sa}_r > \mathrm{split}) \ \mathrm{or}\ (\mathrm{sa}_l > \mathrm{split} \ \mathrm{and}\ \mathrm{sa}_r < \mathrm{split})]
$$两个$\sum$可以用乘法原理和前缀和$O(1)$求出，剩下的问题就是求$L_i$和$R_i$了，这是一个单调栈的经典问题。

所以我们就在求出后缀数组后，$O(N)$解决了这道题。

/* Never Say Die */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <bitset>
using namespace std;
typedef long long LL;
typedef double D;
typedef pair<int, int> pii;
#define mp(a, b) make_pair(a, b)
#define fir first
#define sec second
inline int min(int a, int b) {return a < b ? a : b;}
inline int max(int a, int b) {return a > b ? a : b;}
int ch = 0;
template <class T> inline void read(T &a) {
	bool f = 0; a = 0;
	while (ch < '0' || ch > '9') {if (ch == '-') f = 1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {a = a * 10 + ch - '0'; ch = getchar();}
	if (f) a = -a;
}

#define MAXN 400010

void Sort(int in[], int out[], int p[], int n, int m) {
	static int P[MAXN];
	for (int i = 1; i <= m; i++) P[i] = 0;
	for (int i = 1; i <= n; i++) P[in[i]]++;
	for (int i = 2; i <= m; i++) P[i] += P[i - 1];
	for (int i = n; i; i--) out[P[in[p[i]]]--] = p[i];
}

char s[MAXN];
int sa[MAXN], rk[MAXN], h[MAXN];

int n, l1;
void getsa() {
	static int t1[MAXN], t2[MAXN], *x = t1, *y = t2;
	int m = 127;
	for (int i = 1; i <= n; i++) x[i] = s[i], y[i] = i;
	Sort(x, sa, y, n, m);
	for (int j = 1, i, k = 0; k < n; m = k, j <<= 1) {
		for (i = n - j + 1, k = 0; i <= n; i++) y[++k] = i;
		for (i = 1; i <= n; i++) if (sa[i] > j) y[++k] = sa[i] - j;
		Sort(x, sa, y, n, m);
		for (swap(x, y), i = 2, x[sa[1]] = k = 1; i <= n; i++) {
			x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k : ++k;
		}
	}
	for (int i = 1; i <= n; i++) rk[sa[i]] = i;
	for (int i = 1, k = 0; i <= n; h[rk[i++]] = k) {
		k -= !!k;
		for (int j = sa[rk[i] - 1]; s[i + k] == s[j + k]; k++);
	}
}

int sta[MAXN], p[MAXN], L[MAXN], R[MAXN], s1[MAXN], s2[MAXN];

void work() {
	int top = 0; sta[0] = -1;
	for (int i = 1; i <= n; i++) {
		while (sta[top] >= h[i]) {
			R[p[top]] = i - 1;
			top--;
		}
		L[i] = p[top] + 1;
		sta[++top] = h[i], p[top] = i;
	}
	while (top) R[p[top--]] = n;
	for (int i = 1; i <= n; i++) s1[i] = s1[i - 1] + (sa[i] < l1);
	for (int i = 1; i <= n; i++) s2[i] = s2[i - 1] + (sa[i] > l1);
	LL ans = 0;
	for (int i = 2; i <= n; i++) {
		ans += (LL)h[i] * ((s2[i - 1] - s2[L[i] - 2]) * (s1[R[i]] - s1[i - 1]) + (s1[i - 1] - s1[L[i] - 2]) * (s2[R[i]] - s2[i - 1]));
	}
	printf("%lld\n", ans);
}

int main() {
	scanf("%s", s + 1);
	n = (int)strlen(s + 1);
	s[l1 = ++n] = '|';
	scanf("%s", s + n + 1);
	n += (int)strlen(s + n + 1);
	getsa();
	work();
	return 0;
}

QAQ这么搞我什么时候才能学会SAM啊……