AHOI / HNOI 2017 大赏

2020-03-10

如果说 “我做了一套 AHOI”, 恐怕和 “我做了一套 HNOI” 给人的感觉不太一样…

但其实是一样的? ~~OI 什么时候能实现地域的平衡啊.~~ 这辈子不可能了.

其实不如 SDOI R2 毒瘤 (

「AHOI / HNOI2017」单旋

“邪恶的「卡」带着他的邪恶的「常数」来企图毁灭 H 国.”

可以说是很形象了.

题目链接

https://loj.ac/problem/2018

解题思路

这是一道性质题.

本题最重要的性质就是, 如果把某个节点 $u$ “spaly” 到根, 那么整棵二叉搜索树的形态不会发生较大改变.

具体地说, 假设当前要把最小值对应节点 $u$ “spaly” 到根, 实际上只做了这几个操作:

$u$ 的右儿子接到 $u$ 父亲 $f$ 的左儿子上.
把 $u$ 设成根, 然后把原来的根接到 $u$ 的右儿子上.

考虑这个过程中的节点深度变化, 可以发现 $u$ 的深度变为 $1$, $u$ 原来的右儿子深度不变, 其余点的深度 $+1$.

那么可以用 BIT 维护这个深度了.

既然关键码互不相同, 那我们直接把关键码离散化后的值视作节点编号, 这样子树内编号一定是连续的. 因为操作的特殊性: 只选择最大值和最小值, 所以直接修改到 1 / n 即可.

再考虑插入操作怎么实现.

注意道每次插入一个节点 $u$, $u$ 的父亲 $f$ 一定是 $u$ 的前驱 / 后继中深度较深的一个, 使用 STL 里的 set 直接维护即可.

时间复杂度 $O(n\log n)$.

~~感谢这道题让我知道 spaly 多么蠢…~~

代码实现

代码实现中有一些简单的技巧…

诸如预先在 set 中插入 0, n+1 以避免讨论, 以及利用平衡树旋转时的技巧简化代码.

> 点击显示 / 隐藏

// LOJ #2018
// DeP
#include <set>
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef set<int>::iterator IT;
const int MAXN = 1e5 + 5;

int nB, m, ans;
int Q[MAXN], A[MAXN], B[MAXN];

namespace BIT {
    int C[MAXN];

    inline int lowbit(const int& x) { return x & -x; }

    inline int Qry(const int& pos) {
        int ret = 0;
        for (int i = pos; i; i -= lowbit(i)) ret += C[i];
        return ret;
    }

    inline void Mdy(const int& pos, const int& val) {
        for (int i = pos; i <= nB + 1; i += lowbit(i)) C[i] += val;
    }
    inline void Mdy(const int& L, const int& R, const int& val) {
        Mdy(L, val), Mdy(R+1, -val);
    }
}

// 其实 spaly 的名字只是来哗众取宠的
namespace Spaly {
    int pre[MAXN], ch[2][MAXN], root;
    set<int> S;

    inline void init() { S.insert(0), S.insert(nB + 1); }

    // 类似于 splay 中的 connect ?
    inline void spaly(int u, int w) {
        if (u == root) return;
        int fa = pre[u];
        if (w) BIT::Mdy(1, fa, 1); else BIT::Mdy(fa, nB, 1);
        BIT::Mdy(u, u, 1 - ans);
        ch[w][fa] = ch[w ^ 1][u];
        if (ch[w][fa]) pre[ch[w][fa]] = fa;
        ch[w ^ 1][u] = root, pre[root] = u, pre[root = u] = 0;
    }

    inline void insert(const int& v) {
        int u = lower_bound(B+1, B+1+nB, v) - B;
        if (!root) root = u, ans = 1;
        else {
            IT ite = S.lower_bound(u), suf = ite, nxt = --ite;
            int fa = BIT::Qry(*nxt) > BIT::Qry(*suf)? *nxt: *suf;
            ans = BIT::Qry(fa) + 1, pre[u] = fa, ch[fa == *nxt][fa] = u;
        }
        S.insert(u), BIT::Mdy(u, u, ans - BIT::Qry(u));
    }

    inline int Nxt(int w) {
        int u = w? *(++S.rbegin()): *(++S.begin());
        return ans = BIT::Qry(u), spaly(u, w), u;
    }
    inline void Rmv(int w) {
        int u = Nxt(w);
        S.erase(u), pre[root = ch[w ^ 1][u]] = 0;
        if (w) BIT::Mdy(1, u, -1); else BIT::Mdy(u, nB, -1);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(m);
    for (int i = 1; i <= m; ++i) {
        read(Q[i]);
        if (Q[i] == 1) read(A[i]), B[++nB] = A[i];
    }
    // solve
    Spaly::init();
    sort(B+1, B+1+nB);
    for (int i = 1; i <= m; ++i) {
        switch (Q[i]) {
            case 1: Spaly::insert(A[i]); break;
            case 2: Spaly::Nxt(0); break;
            case 3: Spaly::Nxt(1); break;
            case 4: Spaly::Rmv(0); break;
            case 5: Spaly::Rmv(1); break;
            default: fprintf(stderr, "ERR\n");
        }
        printf("%d\n", ans);
    }
    return 0;
}

「AHOI / HNOI2017」影魔

题目链接

https://loj.ac/problem/2019

解题思路

直接统计不好维护, 于是将操作离线, 枚举每个位置, 依次加入贡献 / 差分统计贡献.

记 $c = \max \{ k_s \mid i < s < j \}$, 依次讨论什么情况下对答案会有 $p_1$ / $p_2$ 的贡献.

$i + 1 = j$

此时不存在此 $c$, 对答案有 $p_1$ 的贡献.
$c \le \min \{k_i, k_j \}$

此时有 $p_1$ 的贡献. 但是不好直接统计, 于是转化一下, 考虑某个位置 $i$ 对答案有贡献的情况.

对于每个位置 $i$, 利用单调栈处理出左侧第一个比 $k_i$ 的位置 $L_i$, 以及右侧第一个比 $k_i$ 大的位置 $R_i$. 可以得到
- 如果一个询问完全包含 $[L_i, R_i]$, 那么对答案有 $p_1$ 的贡献.
$\min \{ k_i, k_j \} < c < \max \{ k_i, k_j \}$

此处有 $p_2$ 的贡献. 沿用 Case 2 的思路. 可以发现
- 如果一个区间包含 $L_i$, 那么 $L_i$ 可以在 $[i+1, R_i - 1]$ 对答案有 $p_2$ 的贡献.
- 如果一个区间包含 $R_i$, 那么 $R_i$ 可以在 $[L_i + 1, i-1]$ 对答案有 $p_2$ 的贡献.

这样就做完了. 实际代码实现并不复杂…

考虑到拆成扫描线之后修改 / 查询的操作总和达到了 $10^6$ 的级别…

于是使用 BIT 实现区间加 / 区间求和, 时间复杂度 $O(n \log n)$.

代码实现

> 点击显示 / 隐藏

// LOJ #2019
// DeP
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef long long LL;
const int MAXN = 2e5 + 5, MAXM = 5 * MAXN;

struct Ask {
    int type, x, L, R, val;
    bool operator < (const Ask& rhs) const {
        return x < rhs.x || (x == rhs.x && type < rhs.type);
    }
} Q[MAXM];

int n, m, qidx;
int A[MAXN], p1, p2;
int Lpos[MAXN], Rpos[MAXN], stk[MAXN], top;
LL Ans[MAXN];

namespace BIT {
    LL C1[MAXN], C2[MAXN];

    inline int lowbit(const int& x) { return x & -x; }

    inline void Mdy(const int& pos, const int& val) {
        for (int i = pos; i <= n; i += lowbit(i)) C1[i] += val, C2[i] += 1LL * val * pos;
    }
    inline void Mdy(const int& L, const int& R, const int& val) { Mdy(L, val), Mdy(R+1, -val); }

    inline LL Qry(const int& pos) {
        LL ret = 0;
        for (int i = pos; i; i -= lowbit(i)) ret += C1[i] * (pos + 1) - C2[i];
        return ret;
    }
    inline LL Qry(const int& L, const int& R) { return Qry(R) - Qry(L-1); }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(m), read(p1), read(p2);
    for (int i = 1; i <= n; ++i) read(A[i]);
    // solve
    stk[top = 0] = 0;
    for (int i = 1; i <= n; ++i) {
        while (top && A[stk[top]] < A[i]) Rpos[stk[top--]] = i;
        Lpos[i] = stk[top], stk[++top] = i;
    }
    while (top) Rpos[stk[top--]] = n + 1;
    for (int i = 1; i <= n; ++i) {
        if (i < n)
            Q[++qidx] = (Ask){ 0, i + 1, i, i, p1 };
        if (Lpos[i] >= 1 && Rpos[i] <= n)
            Q[++qidx] = (Ask){ 0, Rpos[i], Lpos[i], Lpos[i], p1 };
        if (Lpos[i] >= 1 && i + 1 <= Rpos[i] - 1)
            Q[++qidx] = (Ask){ 0, Lpos[i], i + 1, Rpos[i] - 1, p2 };
        if (Rpos[i] <= n + 1 && Lpos[i] + 1 <= i - 1)
            Q[++qidx] = (Ask){ 0, Rpos[i], Lpos[i] + 1, i - 1, p2 };
    }
    for (int L, R, i = 1; i <= m; ++i) {
        read(L), read(R);
        Q[++qidx] = (Ask){ i, L-1, L, R, -1 };
        Q[++qidx] = (Ask){ i, R, L, R, 1 };
    }
    sort(Q+1, Q+1+qidx);
    for (int i = 1; i <= qidx; ++i) {
        if (Q[i].type == 0) BIT::Mdy(Q[i].L, Q[i].R, Q[i].val);
        else Ans[Q[i].type] += Q[i].val * BIT::Qry(Q[i].L, Q[i].R);
    }
    // output
    for (int i = 1; i <= m; ++i) printf("%lld\n", Ans[i]);
    return 0;
}

「AHOI / HNOI2017」礼物

当年入门多项式的时候写的题…

题目链接

https://loj.ac/problem/2020

解题思路

首先旋转的操作可以看作是在枚举一个起始点 $k$, 超出部分复制一遍 $x_i$ 接到 $x_n$ 后面即可. 把差异值形式地写下来就是

$\min_{c, k} \{ \sum_{i=1}^n (x_{i+k} - y_i + c) ^ 2 \}$

展开, 得

$\sum_{i=1}^n (x_i^2 + y_i^2) + 2c \cdot \sum_{i=1}^n (x_i - y_i) + n c^2 - 2 \sum_{i=1}^n x_{i+k} y_i$

除了最后面的和式, 其余部分直接统计 / 二次函数极值就可以解决.

考虑构造一个序列 $t_i = x_{n-i+1}$, 那么

$\sum_{i=1}^n x_{i+k} y_i = \sum_{i=1}^n t_{n-i+1+k} y_i$

这就是一个卷积的形式了, 使用 FFT / NTT 优化这一过程即可.

时间复杂度 $O(n \log n)$.

代码实现

> 点击显示 / 隐藏

// LOJ #2020
// DeP
#include <cmath>
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 1 << 18 | 1;
const int P = 998244353, G = 3, iG = 332748118;

int fpow(int base, int b) {
    int ret = 1;
    while (b > 0) {
        if (b & 1) ret = 1LL * ret * base % P;
        base = 1LL * base * base % P, b >>= 1;
    }
    return ret;
}

namespace Poly {
    int r[MAXN];
    inline void init(const int& Lim, const int& L) {
        for (int i = 1; i < Lim; ++i) r[i] = (r[i>>1] >> 1) | ((i & 1) << (L-1));
    }

    void NTT(int* f, const int& Lim, const int& type) {
        for (int i = 1; i < Lim; ++i) if (i < r[i]) swap(f[i], f[r[i]]);
        for (int Mid = 1; Mid < Lim; Mid <<= 1) {
            int unit = fpow(type > 0? G: iG, (P - 1) / (Mid << 1));
            for (int i = 0; i < Lim; i += Mid << 1) {
                int w = 1;
                for (int j = 0; j < Mid; ++j, w = 1LL * w * unit % P) {
                    int f0 = f[i+j], f1 = 1LL * w * f[i+j+Mid] % P;
                    f[i+j] = (f0 + f1) % P, f[i+j+Mid] = (f0 - f1 + P) % P;
                }
            }
        }
        if (type < 0) {
            int inv = fpow(Lim, P-2);
            for (int i = 0; i < Lim; ++i) f[i] = 1LL * f[i] * inv % P;
        }
    }
}

int n, m, ans;
int a[MAXN], b[MAXN], t[MAXN];

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= n; ++i) read(b[i]);
    // calc c
    int B = 0;
    for (int i = 1; i <= n; ++i)
        ans += a[i] * a[i] + b[i] * b[i], B += a[i] - b[i];
    int c1 = floor(-1.0 * B / n), c2 = ceil(-1.0 * B / n);
    ans += min(n * c1 * c1 + 2 * B * c1, n * c2 * c2 + 2 * B * c2);
    // polynomial
    for (int i = 1; i <= n; ++i) t[n + i] = t[i] = a[n - i + 1];
    int Lim = 1, L = 0;
    while (Lim <= 2*n + n) Lim <<= 1, ++L;
    Poly::init(Lim, L), Poly::NTT(t, Lim, 1), Poly::NTT(b, Lim, 1);
    for (int i = 0; i < Lim; ++i) t[i] = 1LL * t[i] * b[i] % P;
    Poly::NTT(t, Lim, -1);
    int p2 = -P;
    for (int i = n + 1; i <= 2 * n; ++i) p2 = max(p2, 2 * t[i]);
    // output
    printf("%d\n", ans - p2);
    return 0;
}

「AHOI / HNOI2017」大佬

很真实的题面.

题目链接

https://loj.ac/problem/2021

解题思路

首先有一个朴素的 DP, 把能丢到状态的都丢进去…

考虑到打倒大佬可以分为两部分, 也就是保证自己存活, 以及摧毁大佬自信.

注意到 “保证存活” 这一限制和每天采用什么策略有关, 而 “摧毁自信” 只和总天数有关.

于是可以 DP 出保证存活的条件下最大斗争天数.

设 $f(i, j)$ 表示第 $i$ 天, 自信值为 $j$ 时用于打倒大佬的最大天数. 则有转移

$f(i, j - a_i) = \max \{\ f(i-1, j) + 1\ \}$

表示这天选择同大佬斗争.

$f(i, j - a_i + w_i) = \max \{\ f(i-1, j)\ \}$

表示这天去做水题续命…

在得到最大斗争天数 $md$ 后, 直接 BFS 计算这些天内能积累的的讽刺能力 $F$, 以及所用天数 $D$.

那么对于一个自信值为 $C$ 的大佬, 依次枚举 “怼大佬” 的次数, 即 0, 1, 2, 并判定即可.

对于使用两次 “怼大佬” 操作的情况, 利用 Two-Pointer 的技巧配合 $F$ 的单调性枚举即可.

具体地说, 当前合法的两次操作 $i, j$ 满足 $F_i + F_j \le C$, 且 $C - F_i - F_j + D_i + D_j \le md$.

(换言之, 不能直接把大佬自信值嘲讽到负, 且剩余部分可以还嘴解决)

这种带搜索的题目, 时间复杂度不想分析了, $O(\texttt{能过})$.

代码实现

> 点击显示 / 隐藏

// LOJ #2021
// DeP
#include <map>
#include <queue>
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef pair<int, int> Pii;
const int MAXN = 105, MAXM = 1e6 + 5, MAXC = 1e8;

int n, m, mc, md;
int A[MAXN], W[MAXN];

int f[MAXN][MAXN];
int F[MAXM], D[MAXM], nF;
map<int, int> M;
map<Pii, bool> vis;

void BFS() {
    static int QF[MAXM], QL[MAXM], Qd[MAXM];
    int head = 1, tail = 0;
    QF[++tail] = 1, QL[tail] = 0, Qd[tail] = 1;
    while (head <= tail) {
        int fe = QF[head], l = QL[head], d = Qd[head]; ++head;
        if (!M.count(fe)) M[fe] = d;
        if (d >= md || 1LL * fe * l > MAXC) continue;
        if (!vis[Pii(l+1, fe)]) {
            QF[++tail] = fe, QL[tail] = l + 1, Qd[tail] = d + 1;
            vis[Pii(l+1, fe)] = true;
        }
        if (1 < l && 1LL * fe * l <= MAXC && !vis[Pii(l, fe * l)]) {
            QF[++tail] = fe * l, QL[tail] = l, Qd[tail] = d + 1;
            vis[Pii(l, fe * l)] = true;
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(m), read(mc);
    for (int i = 1; i <= n; ++i) read(A[i]);
    for (int i = 1; i <= n; ++i) read(W[i]);
    // solve
    for (int i = 1; i <= n; ++i)
        for (int j = A[i]; j <= mc; ++j) {
            f[i][j - A[i]] = max(f[i][j - A[i]], f[i-1][j] + 1);
            int p = min(mc, j - A[i] + W[i]);
            f[i][p] = max(f[i][p], f[i-1][j]);
        }
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= mc; ++j) md = max(md, f[i][j]);
    BFS();
    for (auto ite = M.begin(); ite != M.end(); ++ite)
        F[++nF] = ite->first, D[nF] = ite->second;
    // output
    while (m--) {
        static int C, ans;
        read(C), ans = C <= md;
        for (int i = 1; i <= nF && !ans; ++i)
            ans |= F[i] <= C && D[i] + C - F[i] <= md;
        for (int j = 1, i = nF; i && !ans; --i)
            while (!ans && j <= nF && F[i] + F[j] <= C)
                ans |= D[i] + D[j] + C - F[i] - F[j] <= md, ++j;
        printf("%d\n", ans);
    }
    return 0;
}

「AHOI / HNOI2017」队长快跑

这是一道 ~~计算几何~~ nan 题, 至少当年是这样.

题目链接

https://loj.ac/problem/2022

解题思路

似乎这道题 6-10 的数据是错的, 嘿嘿.

于是去学习了某一种广为流传的做法, 希望做法不假.

首先有一步转化, 每一个机关, 都可以根据其对起点 $S$ 到终点 $T$ 的影响, 看作倾角为 $\frac{\pi}{2}$ 或 $\frac{\pi}{2}$ 的两条射线.

~~感觉不画图是不会明白的, 那么祭上 lb2003 的题解吧~~

此时的情况就比较少了, 利用两个单调队列, 维护一条合法路径即可. 由维护路径的过程可以得知, 此时得到的答案一定是最优的.

时间复杂度 $O(n)$.

代码实现

能用整数的地方就用整数来提高精度…

再利用单调队列的时候, 使用了一些技巧来简化代码.

> 点击显示 / 隐藏

// LOJ #2022
// DeP
#include <cmath>
#include <cstdio>
#include <cassert>
#include <algorithm>
using namespace std;

typedef long long LL;
const int MAXN = 1e6 + 5;

namespace Geo {
    const double INFD = 1e18;

    struct Vector {
        LL x, y;
        Vector(LL _x = 0, LL _y = 0): x(_x), y(_y) { }
        Vector operator + (const Vector& rhs) const { return Vector(x + rhs.x, y + rhs.y); }
        Vector operator - (const Vector& rhs) const { return Vector(x - rhs.x, y - rhs.y); }
    };
    typedef Vector Point;

    inline LL Dot(const Vector& A, const Vector& B) { return A.x * B.x + A.y * B.y; }
    inline LL Cross(const Vector& A, const Vector& B) { return A.x * B.y - A.y * B.x; }

    inline double Length(const Vector& A) { return sqrt(Dot(A, A)); }
    inline double angle(const Vector& v) { return atan2(v.y, v.x); }
}
using namespace Geo;

inline void read(Point& p) { scanf("%lld%lld", &p.x, &p.y); }

int n, nA;
double theta[MAXN];
Point A[MAXN], P[MAXN], S, T;
int Q[2][MAXN], head[2], tail[2];
int pre[MAXN], idx[MAXN], t[MAXN], type[MAXN]; // 0: up, 1: down

inline bool cmp(const int& x, const int& y) {
    return P[x].x < P[y].x;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    scanf("%d", &n), read(T);
    for (int i = 1; i <= n; ++i)
        read(P[i]), scanf("%lf", theta + i);
    // solve
    S = Point(0, 0);
    for (int i = 1; i <= n; ++i) {
        double angl = angle(S - P[i]), angr = angle(T - P[i]);
        // 注意处理 angl > angr 的情况
        if (angl > angr) type[i] = !(angr < theta[i] && theta[i] < angl);
        else type[i] = angl < theta[i] && theta[i] < angr;
    }
    for (int i = 1; i <= n; ++i) idx[i] = i;
    sort(idx+1, idx+1+n, cmp);
    A[++nA] = S;
    for (int i = 1; i <= n && P[idx[i]].x < T.x; ++i)
        if (S.x < P[idx[i]].x) A[++nA] = P[idx[i]], t[nA] = type[idx[i]];
    A[++nA] = T;
    for (int d = 0; d < 2; ++d) Q[d][head[d] = tail[d] = 1] = 1;
    for (int i = 2; i <= nA; ++i) {
        int d = t[i], sign = (d > 0? 1: -1);
        int &head0 = head[d], &tail0 = tail[d], *Q0 = Q[d];
        int &head1 = head[d^1], &tail1 = tail[d^1], *Q1 = Q[d^1];
        if (head1 < tail1 && Cross(A[i] - A[Q1[head1]], A[Q1[head1+1]] - A[Q1[head1]]) * sign <= 0) {
            while (head1 < tail1 &&
                    Cross(A[i] - A[Q1[head1]], A[Q1[head1+1]] - A[Q1[head1]]) * sign <= 0) ++head1;
            pre[i] = Q1[head1];
            head0 = ++tail0, Q0[tail0] = Q1[head1];
        } else {
            while (head0 < tail0 &&
                    Cross(A[i] - A[Q0[tail0-1]], A[Q0[tail0]] - A[Q0[tail0-1]]) * sign <= 0) --tail0;
            pre[i] = Q0[tail0];
        }
        Q0[++tail0] = i;
    }
    // output
    double ans = 0.0;
    for (int i = nA; i != 1; i = pre[i]) ans += Length(A[i] - A[pre[i]]), assert(i != 0);
    printf("%.10lf\n", ans);
    return 0;
}

「AHOI / HNOI2017」抛硬币

题目链接

https://loj.ac/problem/2023

解题思路

这是一道组合数学题. 分 $a = b$ 和 $a > b$ 两种情况讨论.

$a = b$

先考虑所有情况数, 即 $2 ^ {a + b}$.

如果把硬币全部翻转, 最后输赢的结果却不一定翻转. 所以此时要统计 $A$ 获胜的情况, 需要减去翻转前后 $A$ 都输给 $B$, 也就是平局的方案数. 那么答案为
$\frac{1}{2}\ (\ 2 ^ {a + b} - \sum_{i=1}^a \binom{a}{i} \binom{b}{i})$
考虑右侧和式的组合意义, 即两次在 $a$ 个物品中选出 $i$ 个. 等价于一次选出 $i$ 个, 另一次选出 $a-i$ 个. 也就是在 $2a$ 个物品中选出 $a$ 个. 即
$\frac{1}{2}\ (\ 2 ^ {a + b} - \sum_{i=1}^a \binom{a}{i} \binom{a}{a-i}) = \frac{1}{2}\ (\ 2 ^ {a + b} - \binom{2a}{a})$
式子中有个 / $2$, 但 $2$ 在这些个模数下不存在逆元, 于是可以认为模数为 $2 \times 10^k$, 最后直接将结果 / $2$ 即可.

但是这样有些… 考虑帕斯卡法则, 有
$\binom{2a}{a} = \binom{2a-1}{a-1} + \binom{2a-1}{a}$
而 $\binom{2a-1}{a-1} = \binom{2a-1}{a}$, 所以答案为
$2 ^ {a + b - 1} + \binom{2a - 1}{a - 1}$
从而避开了 / $2$ 的操作.
$a > b$

还是从翻转硬币的角度入手, 这次要考虑翻转前后 $A$ 都获胜的情况. 那么答案为
$\frac{1}{2}\ (\ 2 ^ {a + b} + \sum_{i=0}^b \sum_{j=1}^{a-b-1} \binom{b}{i} \binom{a}{i + j})$
改变枚举顺序, 得
$\frac{1}{2}\ (\ 2 ^ {a + b} + \sum_{i=1}^{a-b-1}\sum_{j=0}^b \binom{b}{b-j}\binom{a}{i+j} ) = \frac{1}{2}\ (\ 2 ^ {a + b} + \sum_{i=1}^{a-b-1} \binom{a+b}{b+i} )$
稍微整理一下, 得
$\frac{1}{2}\ (\ 2 ^ {a + b} + \sum_{i=1+b}^{a-1} \binom{a+b}{i} )$
利用上一情况的处理方法处理掉 / $2$ 即可. (如果把和式处理掉, 那就是后文的优化 3 了)

推出来式子之后直接抄了一份鲁棒性良好的拓展卢卡斯的板子上去, 喜获第一个点跑 10s 的好成绩.

接下来的问题在于如何卡常…

考虑到模数一定形如 $10^k$, 也就是质因数仅包含 $2$ 和 $5$.

那么枚举质因数的过程可以省略, 中国剩余定理的过程也可以简化不少.
在能用 int 的情况下, 避免使用 long long.

在现代评测机下效果并不显著…
考虑到组合数具有对称性, 计算组合数只需要算一半即可, 常数减半.

具体实现的时候, 需要讨论 $a + b$ 奇偶性来避免少加一项的麻烦.
预处理一个 “伪阶乘”, 即在阶乘中除去 $2$ / $5$ 的倍数, 用于优化拓展 Lucas 计算.

此处优化最为明显.

还有一个小地方就是 $2^9 = 512$, 远小于 $5^9 = 1953125$, 开在一起对缓存不友好…

不过可以简化代码 doge

代码实现

> 点击显示 / 隐藏

// LOJ #2023
// DeP
#include <cstdio>

typedef long long LL;
const int MAXL = 25, MAXN = 2e6 + 5;

void exgcd(int a, int b, int& x, int& y) {
    if (!b) x = 1, y = 0;
    else exgcd(b, a % b, y, x), y -= a / b * x;
}
inline int inv(const int& n, const int& m) {
    static int x, y;
    return exgcd(n % m, m, x, y), (x % m + m) % m;
}

int fpow(LL base, LL b, int m) {
    int ret = 1;
    while (b > 0) {
        if (b & 1) ret = ret * base % m;
        base = base * base % m, b >>= 1;
    }
    return ret;
}

char Ctl[MAXL];
int M[MAXL], pow2[MAXL], pow5[MAXL], fac[2][MAXN];

int calc(LL n, int d, int p) {
    if (!n) return 1;
    // "伪阶乘" 使用
    int s = fpow(fac[d == 5][p - 1], n / p, p);
    return 1LL * s * fac[d == 5][n % p] % p * calc(n / d, d, p) % p;
}

int MultiLucas(LL n, LL m, int d, int p, int k) {
    int c = 0;
    for (LL i = n; i; i /= d) c += i / d;
    for (LL i = m; i; i /= d) c -= i / d;
    for (LL i = n-m; i; i /= d) c -= i / d;
    // 这里也是优化
    if (c >= k) return 0;
    return 1LL * fpow(d, c, p) * calc(n, d, p) % p *
        inv(calc(m, d, p), p) % p * inv(calc(n-m, d, p), p) % p;
}

int ExLucas(LL n, LL m, int k) {
    const int &fact1 = pow2[k], &fact2 = pow5[k];
    int a1 = MultiLucas(n, m, 2, fact1, k), a2 = MultiLucas(n, m, 5, fact2, k);
    int ret = 1LL * inv(fact2, fact1) * fact2 % M[k] * a1 % M[k];
    ret = (ret + 1LL * inv(fact1, fact2) * fact1 % M[k] * a2 % M[k]) % M[k];
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // init
    fac[0][0] = fac[1][0] = 1;
    for (int i = 1; i < 512; ++i) // 2 ^ 9
        fac[0][i] = (i % 2 == 0)? fac[0][i-1]: 1LL * i * fac[0][i-1] % 512;
    for (int i = 1; i < 1953125; ++i) // 5 ^ 9
        fac[1][i] = (i % 5 == 0)? fac[1][i-1]: 1LL * i * fac[1][i-1] % 1953125;
    pow2[0] = pow5[0] = M[0] = 1;
    for (int i = 1; i <= 9; ++i)
        M[i] = M[i-1] * 10, pow2[i] = pow2[i-1] * 2, pow5[i] = pow5[i-1] * 5;
    // input
    LL a, b; int K;
    while (scanf("%lld%lld%d", &a, &b, &K) != EOF) {
        // solve
        int Mod = M[K], ans = fpow(2, a + b - 1, Mod);
        if (a == b) ans = (ans - ExLucas(a + a - 1, a - 1, K) + Mod) % Mod;
        else {
            for (LL i = (a + b) / 2 + 1; i < a; ++i)
                ans = (ans + ExLucas(a + b, i, K)) % Mod;
            if ((a + b) % 2 == 0)
                ans = (ans + ExLucas(a + b - 1, (a + b) / 2, K)) % Mod;
        }
        // output
        sprintf(Ctl, "%%0%dd\n", K), printf(Ctl, ans);
    }
    return 0;
}

DepletedPrism's Blog

AHOI / HNOI 2017 大赏

「AHOI / HNOI2017」单旋

题目链接

解题思路

代码实现

「AHOI / HNOI2017」影魔

题目链接

解题思路

代码实现

「AHOI / HNOI2017」礼物

题目链接

解题思路

代码实现

「AHOI / HNOI2017」大佬

题目链接

解题思路

代码实现

「AHOI / HNOI2017」队长快跑

题目链接

解题思路

代码实现

「AHOI / HNOI2017」抛硬币

题目链接

解题思路

代码实现