以后再卡构造我是狗

1227G. Not Same

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

Sol

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

5
5 1 1 1 1

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

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

#define N 1005

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

1110G. Tree-Tac-Toe

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

Sol

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

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

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

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

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

#define N 2011111

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

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

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

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

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

acm.sgu.ru@CodeForces

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

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

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

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

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

哈哈。

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

清明时节,细雨纷纷。

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

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

当然,我不在了。

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

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

不管怎么说,加油吧。

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

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

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


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

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

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

2017.5.7 CTSC Day 0

早上起很早去赶飞机…然后离线了他们的数论入门题来玩耍,结果被虐了?QAQ
下午到酒店发现没和董先生谭先生分到一家酒店甚是尴尬…本来和Wuvin先生分到一间的,结果ZYQN先生和我换啦于是我跟一位现充天津大爷fnoi12bzzhan一间。(wori这位大爷秀恩爱的技巧简直炫酷
晚上去八十中吃完晚饭就滚了…打了场TC……结果rating变化迟迟不出现QAQ。
睡前和大爷瞎bb到十二点过。

2017.5.8 CTSC Day 1

吐槽!八十中的早饭一点都没有平常的饭好吃QAQ。
然后进考场发现键盘是个平板一样的东西TAT不过还好。看题,发现怎么……一点也不CTSC啊……怎么这么noi啊……然后第一题简直就是签到题,然而考场上我觉得:这tm是CTSC怎么可能让我A题呢?于是写了30+21就跑路了233.第二题不是IOI原题嘛……然而我WC睡过去了QAQ,于是写了个SPFA加剪枝的暴力感觉好虚啊…第三题是一个第一眼看上去很蠢的题,“看见了NOIP的眼神.jpg”……然后写完发现过不了样例……WTF!才发现那个贝叶斯公式是有用的,前后的确定事件都会影响中间的随机事件……于是看公式看了一个小时,看样例解释才把公式看懂。于是写了发暴力…然而我太蠢了不会反着用公式TAT于是正向NM反向只会\(O(N ^ 2M)\)……觉得很虚于是反向写了个线段树查那个线性递推。
期望:51 + 20 + 35,实际51 + 10 + 50。
第二题剪枝剪挂,居然有十分真是奇迹;\(O(wys)\)还是有用的,不然怎么解释\(O(N \log N M)\)过\(10 ^ 4\)呢233……不过这分很低就对了。第一题我真是蠢,居然不做完哎。

2017.5.9 CTSC Day 1.5

上午听十五人队吹逼。感觉那些评委就是,我不知道你在讲什么,但是他们让我提问,好尴尬怎么办啊……
于是出现了一些比较厉害的提问,包括但不限于:
“你讲的很好,我就有一个问题,什么是本质不同的子串呢?”
“可你这个和OI有什么关系呢?”
……
YJQ的提问也好劲啊233。
下午迷之王选秘书来讲王选,我觉得如果我以后去当某个很厉害的人的秘书,一定要让他死之前给我做个PPT,这样我动动嘴皮子就发达了。于是董先生选择推WA,我拖着谭先生去五道口和戴爷愉快玩耍吹逼。五道口体校真大…没自行车根本走不下来。学校还是挺漂亮的?不过到处都是一片奇怪的紫色。晚上戴爷请吃清青小火锅,于是在我踢掉五次电磁炉电源线的同时,他们开始由不严谨的证明讲到了某些奇怪的积分……于是我只能吃吃吃吃吃装作没听到QAQ。

2017.5.10 CTSC Day 2

又是奇怪的题…第一题B君的gift真是233…我硬是没想Lucas在那里打表瞎找规律,不过幸好找到A掉了233。第二题…是…什么鬼啊QAQ…好难想啊(我不知道那个定理真是尴尬),第三题是什么神几何题啊QAQ不太会啊。于是写3k代码来获取第二题的部分分,第三题推出来投影也不会做只能瞎骗分TAT。
期望:100 + 10 + 0,实际100 + 10 + 0。
于是第二题是有定理有算导数据结构后还要维护一个奥妙重重的东西……卧槽。第三题竟然是A*……标程800行太强啦!不过xumingkuan大爷居然退火+遗传怒A这题太强啦。
啊,于是毫无悬念地Ag滚了。还是太菜啦TAT。
下午看到面试名单心一沉,嗷YJQ可能进不了队了啊。然后面试,YJQ和xumingkuan的口语和其他选手的不是一个水平的啊…听着myy英语只能说,勉强听得懂QAQ。YJQ的面试好劲啊!虽然不管怎么说可能还是进不了队,但是那股自信,我可能是没有的啊QAQ。
晚上听名单简直是羞耻,念铜牌银牌和念“你们都考跪了哈哈哈”名单差不多。

2017.5.11 APIO Day -1

因为没安排就睡到了11点。然后颓颓颓,专业口胡APIO历年题目233。晚上去吃了个非常尴尬的烤鸭。
晚上打了场CF,xjb写了几道题,最后一道太麻烦了没写QAQ。

2017.5.12 APIO Day 0

把上午的培训翘了。中午去吃饭,下午听了点奇奇怪怪的东西,那个肉眼无损的拉长图形好厉害啊QwQ。
晚上不想去听算法题,在图书馆写代码直到被保安赶走。
回酒店又乱散发负能量TAT我这人怎么这样啊。

2017.5.13 APIO

早上起晚,于是和室友一起去星爸爸解决了早饭然后打的到八十中。结果这个APIO搞得好像很像USACO……233。只是我们被强制集中考试了而已。
前两道题都是迷之交互题;当然其实第一题只是强制在线的传统题而已;而第二题也其实只是个提交一个构造法的答案提交题而已。
第一题越看越像noi2016的网格…但是我奇怪的离散化建图写挂了QAQ,于是只能交前两个Subtask。第二题好有趣啊w然而玩了一个小时连minValue都没搞出来QAQ弄得我自信心下溢。弃疗看第三题,虽然一眼分数规划但是发现描述好复杂看起来好难哦,于是先用Floyd写第一个Subtask,结果写出来发现这不就是神犇(sb)题么,然后我愚蠢的写了个垃圾的东西先交Subtask2,然后去掉了重复计算,准备过第三个Subtask……结果直接A了?喵哈!
悠闲地开始玩第二题,发现随便放一个就可以找到minValue了真是233。然后构造了好久maxValue,最后在我最开始的那一个小时乱搞的思路里捡出了一个可行的,即如果每次都给已知的更大的放更多的石子,那么留下来的一定是一堆小的加大的中更大的,最后取个交就知道是哪些分数更大啦QwQ。然后我又玩不出greaterValue了,到最后我惊奇的发现如果给那两个要比较的相同的石子,一定存在一个石子数量使得一个选一个不选。太强啦!然后就二分搞搞。(后来我发现我二分上下界根据我的想法的话是设错了,然而碰到了正解233)。后面的allValue智商不足不想玩了,直接把greaterValue写成比较函数然后sort。(事后知道stable_sort分数更高的我眼泪流下来)
然后23 + 60 + 100。我明明可以考更高的,结果第一题第二题失误都还是太大了,Au也没什么卵用啊。

2017.5.14 THUPC

THUPC……哎,从入门到智障选手。
M题提示那么明显我们就是不看题……结果输出”mom”和”mother”就可以了我们还只看输入输出搞了所有单词出来,智障吧QAQ。
C题简直娱乐,直接A了。
H题想了想挺简单的?于是直接主席树二分写了……结果被卡常数卡成狗……到最后卡不动了1200ms……弃疗写整体二分才过了QAQ。
大家都不会做算法题了于是我昏天黑地地调完了阳光体育。啥?哦就是猪国杀那种。
然后A和J的思路都只差一步了QAQ但是太弱了没想出最后一步就GG了。
一共4道?然而4道最高15名,我们Fail太多直接50+了QAQ。
于是…因为董先生的选择,他正式退役了。祝好啊QAQ。
我也要准备收拾东西去杭二了QwQ,thusc再来北京。
嗷……听说他们晚上飞机命运多舛…orz。不过我还听说董先生六点才回到家,早上就返校了,简直太强了。
呐。CTSC && APIO && THUPC 2017就写到这里吧。

Day 0

上午省选集训考试……\(N ^ 3 \log K\)过\(N = 500, K = 10 ^
{12}\)是什么鬼啊……反正除了几何做不来,其他题都是Eazy AC fun吧……

下午回到了学校这边。去隔壁咖啡坐了一会儿,敲了一道模板题。走的时候被班上同学抓住嘲讽了一波……然后因为手机没电没见到某些人。

晚上难以入眠,刷着逼乎听着歌好久才睡着。

Day 1

自带的迟到buff让大家等了十分钟……真是不好意思呢QAQ。

键盘Backspace贼小,\键键位奇怪,差评。幸好这次组织得终于不像NOIp那么水了。

看题。第一题一眼傻逼,然而最开始思路偏了?敲了个链剖,然后发现自己维护的东西是错的,怒删写暴力发现跑的贼快。写暴力的时候看到有一个地方要break,突然发现做过原题(BZOJ3252),然后就写完暴力写线段树了。不过傻逼的我还是写挂了两次(幸好写了暴力),然后终于拍上了。

第二题一眼就会做了然而觉得可能并调不出来。于是先码了个不优秀的暴力。

第三题几何,不会,\(N ^ 3\)写完就没管了。

开始码第二题……数据结构调死人,特别是代码太长连翻页都很困难的时候。我调点分本来就慢……然后还有一个链剖和线段树,还有大模拟。最后半个小时发现没有调出来的希望的时候,退出去卡了卡暴力常,就扫雷去了。

下午出分等死人,然后100 + 20 + 30。幸好都拿稳了。

看到我校初三选手200?Excuse me?暴力AC了T2?

喵喵喵?BFS就能AC?

我不想在博客上说脏话,所以我无话可说。

dhc因为T1 MLE就一直很不高兴……然后他的T2写了正解并AC,听说暴力A了直接崩了……

tsw A了T3,然而因为T1手写堆挂了,10分滚?哎。

lsw和wzk好像都考得不太好样。

回家没什么心情,刷知乎颓颓颓。说好的再写遍模板,刚写完sa就不想写了。

Day 2

大家一脸视死如归地走进考场。

wzk说他今天AK都没法进队了,可怜。

dhc说他今天不AC两道题就退役了。

tsw先生……要高于200才能进队。

初三大爷和我反而压力没那么大……但是其实不过两题也是滚粗的。

才发现监考的小姐姐好萌啊qwq。

T1 sbdp,大概写完和写完暴力再加上拍上不超过15分钟吧?

T2 RMQ裸题,再加上非常恶心的输出(后来才发现那个输出比RMQ难写多了

T3 字符串,弃疗

于是怼了三个半小时T2,幸好写了对拍拍出了4个错误,但是极限数据要3.5s,后来发现不用快速乘也可以,再卡卡常,2.9s…好虚啊。

T3用STL写了个\(N ^ 2 \log N\)的暴力,过1000好悬啊,怕是没分。

出考场发现大家几乎全是退役的表情。

dhc因为心理压力太大直接先开的T2T3,结果因为太急没做出来直接带崩心态。T1都交的暴力和骗分。

lsw挂惨了。wzk也挂了貌似,他第二题用了FFT,过了大样例,但是据说处理挂了。

只有tsw写了200分……但他NOIp和DAY1都挂了不该挂的东西,也不稳。

中午dhc直接回家了,wzk也走了。我和其他两人和熊老去吃了火锅。

下午回电子科大前就听说出成绩了。然后100 + 100 + 0。
讲道理是进不了队的,但是大家都考得不好。 rk10。

初三大爷在杀完后rk15,差一名。虽然很可惜,但我觉得暴力进队这种事情本来就不该发生。

ZYQN翻盘失败了……哎。

zms也挂了,他和lxl大爷好像非常难过。本来觉得他们挺稳的啊,世事无常。

akb在两道题爆炸的情况下还能rk13……太强了。

进队本来该很高兴的……为什么我高兴不起来呢。

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

莫名提前的考前综合征让我无法入眠。

我什么都会一点,也可以叫什么都不会,因为总担心自己不会别人会的东西。

这几天……先是在UESTC校赛里被七中大爷和UESTC的三位大爷粉碎,然后又在水水的省选集训里昏昏欲睡,过着醉生梦死的生活。

不知道后天我将怎么面对结果。抑或是成功的喜悦,还是退役后如释重负呢?

我希望是前者。

与其苟延残喘,不如纵情燃烧。

就算再不自信,我也只能尽我全力说着:

SCOI2017,我准备好了。

AK is yzh.

夜未央、天未亮,我在幸存的沙场
只盼望、此生再,奔向思念的脸庞
泪未干、心未凉,是什么依然在滚烫
入阵曲,四面楚歌谁独唱

Countdown: 7 Days.