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

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

100. A+B

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

101. Domino

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

Sol

欧拉回路。

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

#define N 105

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

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

102. Coprimes

print(phi(n))

103. Traffic Lights

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

Sol

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

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

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

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

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

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

priority_queue <Node> q;

int dis[N], fr[N];

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

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

104. Little Shop of Flowers

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

Sol

DP

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

#define N 105

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

105. Div 3

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

Sol

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

106. The Equation

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

Sol

EXGCD

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

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

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

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

107. 987654321 problem

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

Sol

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

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

108. Self-numbers II

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

Sol

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

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

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

109. Magic of David Copperfield II

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

Sol

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

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

110. Dungeon

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

Sol

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

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

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

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

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

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

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

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

111. Very simple problem

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

Sol

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

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

112. a^b – b^a

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

113. Nearly prime numbers

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

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

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

114. Telecasting station

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

Sol

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

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

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

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

115. Calendar

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

116. Index of super-prime

non-increasing

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

#define N 10001

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

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

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

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

116. Counting

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

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

117. Digital root

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

Sol

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

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

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

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

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

119. Magic Pairs

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

Sol

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

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

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

120. Arhipelago

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

Sol

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

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

121. Bridges painting

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

Sol

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

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

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

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

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

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

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

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

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

122. The book

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

Sol

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

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

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

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

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

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

#define N 1005

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

123. The sum

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

124. Broken line

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

Sol

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

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

#define N 80212
#define L 10001

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

int tcnt = 0;

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

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

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

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

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

#include <bits/stdc++.h>
using namespace std;
#define N 10555
int n, X, Y, X1[N], Y1[N], X2[N], Y2[N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        if (x1 > x2 || y1 > y2) swap(x1, x2), swap(y1, y2);
        X1[i] = x1, X2[i] = x2, Y1[i] = y1, Y2[i] = y2;
    }
    scanf("%d%d", &X, &Y);
    for (int i =1; i <= n; i++) {
        if (X == X1[i] && Y1[i] <= Y && Y <= Y2[i]) return 0 * puts("BORDER");
        if (Y == Y1[i] && X1[i] <= X && X <= X2[i]) return 0 * puts("BORDER");
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) if (Y1[i] == Y2[i] && Y1[i] < Y && X1[i] <= X && X2[i] > X) cnt++;
    puts(cnt % 2 ? "INSIDE" : "OUTSIDE");
}

125. Shtirlits

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

Sol

DFS + 剪枝。
我假 AC 是：

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

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

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

卡掉数据如下：

3
0 3 0
3 3 3
0 3 0

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

126. Boxes

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

Sol

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

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

127. Telephone directory

我是菜菜

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

128. Snake

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

Sol

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

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

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

   ..*-*..
   *-|-|-*
   *-*.*-*

#include <bits/stdc++.h>
using namespace std;
#define N 10011
int n, e, ans = 0;
int f[N], d[N];
vector <int> X[N + N], Y[N + N];
map <pair<int, int>, int> G;
int getf(int x) {return f[x] == x ? x : f[x] = getf(f[f[x]]);}

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

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

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

129. Inheritance

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

Sol

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

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

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

130. Circle

应该练习 python 的，懒了。

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

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

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

131. Hardwood floor

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

Sol

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

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

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

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

132. Another Chocolate Maniac

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

Sol

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

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

#define M 75
#define N 7

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

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

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

133. Border

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

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

134. Centroid

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

#define N 16666

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

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

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

135. Drawing Lines

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

136. Erasing Edges

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

Sol

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

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

137. Funny Strings

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

Sol

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

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

int n, K;
int a[10111];

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

138. Games of Chess

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

Sol

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

7
5 4 1 1 1 1 1

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

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

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

} 

139. Help Needed!

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

int a[N][N];

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