2023/10/10：孩童的双眸

未来的瞳孔！

近在咫尺的视野盲点？!

2023/10/9 上午模拟赛，笔者被锤烂了。

但是，为什么想不到呢？

我通常将“直觉”作为导向，如果直觉是正确的，那么大概就有了。不过我做过的题少得可怜，因此直觉真的很不靠谱。什么都想不到，即使想到了也漏洞百出。

也许只有大量的训练才能根治这一问题，但也许我也看不见什么。

我们周围的环境中有着大量的微观粒子，它们都在阻挡我们的实现。也就是说，我们和瞎子无异。

造成这种情况实属可悲，但也无法避免。这是宇宙中最坏的结果，只能说可怜。

我们是低等文明吗？显然是。我们连地球上的东西都看不全。

也许那从来就不是盲点，这个世界的规则不许我们看到它们。亡灵游荡于世间，所认知的规则已经不再成立。

既然这样，视觉还有什么用呢？

欢迎收看十月大型新番《暂时没有名字》，上集回顾，大家非常想看续集，那么我们日更！

空间大盗与时间旅人

空间大盗是可以转移硬盘的存储顺序，从而让数据毁坏的。

我要向 @AC_love 宣战！学习自己喜欢的知识是一个人的自由，没有任何人可以阻止！

我要向 ACL 投出加农炮！捍卫老年高二选手的强大学习能力与做题能力，我辈义不容辞！！即使我是高二最弱战斗力，我也要站出来，不依赖时间旅人朋友的力量，大战邪恶势力！！

可以将这段话视作玩笑，没有任何引战的意思。大家好好学习，一起进步！

Deltix Summer 2021 (Div. 1 + Div. 2)

Portal.

你猜猜为什么随机到了这场呢？

我是——傻手！

Easy Problems

如果赶时间可以跳过。

A. A Variety of Operations

Portal.

发现答案是 $[-1,2]$ ，直接搞。

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

int main(void) {
    int T; scanf("%d", &T); 
    while (T--) {
        int c, d; scanf("%d%d", &c, &d); 
        if (d > c) swap(c, d);
        if ((c - d) % 2 != 0) puts("-1");
        else {
            if (c == 0 && d == 0) puts("0");
            else if (c == d) puts("1");
            else puts("2");
        }
    }   
    return 0;
}

B. Take Your Places!

Portal.

对奇偶讨论一下就行。

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

int n, even, odd;
int a[100005];

inline void calc1(void) {
    if (even != odd) return puts("-1"), void(); 
    int suma = 0, sumb = 0;
    int posa = 1, posb = 2;
    for (int i = 1; i <= n; ++i) if (a[i] % 2 == 0) {
        suma += abs(posa - i); posa += 2;
        sumb += abs(posb - i); posb += 2;
    }
    printf("%d\n", min(suma, sumb));
}

inline void calc2(void) {
    if (abs(even - odd) != 1) return puts("-1"), void(); 
    if (even > odd) {
        int pos = 1, ans = 0;
        for (int i = 1; i <= n; ++i)
            if (a[i] % 2 == 0) ans += abs(pos - i), pos += 2;
        printf("%d\n", ans);
    } else {
        int pos = 1, ans = 0;
        for (int i = 1; i <= n; ++i)
            if (a[i] % 2 == 1) ans += abs(pos - i), pos += 2;
        printf("%d\n", ans);
    }
}

int main(void) {
    int T; scanf("%d", &T); 
    while (T--) {
        scanf("%d", &n); even = 0, odd = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", a + i); 
            if (a[i] % 2 == 0) ++even;
            else ++odd;
        }
        if (n % 2 == 0) calc1();
        else calc2();
    }   
    return 0;
}

C. Compressed Bracket Sequence

Portal.

$O(n^2)$ 枚举即可。

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

i64 ans;
int n, c[1005];

int main(void) {
    scanf("%d", &n); 
    for (int i = 0; i < n; ++i) scanf("%d", c + i); 
    for (int l = 0; l < n; l += 2) {
        i64 cur = c[l], mn = c[l];
        for (int r = l + 1; r < n; ++r)
            if (r % 2 == 0) cur += c[r];
            else {
                i64 i = max(0ll, cur - c[r]);
                i64 j = min({mn, cur - 1, c[l] - 1ll});
                if (i <= j) ans += j - i + 1;
                cur -= c[r];
                mn = min(mn, cur);
            }
    }
    return !printf("%d\n", ans); 
}

D. Take a Guess

Portal.

按位或加按位与等于运算加，解方程就行。

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

int n, k, a[10005]; 
int qsum(int x, int y) {
    int s, t;
    cout << "and " << x << " " << y << endl; cin >> s; 
    cout << "or " << x << " " << y << endl; cin >> t; 
    return s + t; 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> k; 
    int x = qsum(1, 2), y = qsum(1, 3), z = qsum(2, 3); 
    a[2] = (x - y + z) / 2; a[1] = x - a[2]; a[3] = z - a[2]; 
    for (int i = 4; i <= n; ++i) a[i] = qsum(1, i) - a[1]; 
    nth_element(a + 1, a + k, a + n + 1); 
    cout << "finish " << a[k] << endl; 
    return 0; 
}

Medium Problems

有一定难度的问题。

E. Equilibrium

Portal.

套路地，令 $v_i=a_i-b_i$ ，每次可以将奇数位置 $+1$ ，偶数位置 $-1$ ，问最少操作次数使之变成 $0$ 。

将 $v$ 前缀和一下，发现每次操作实际上是在前缀和区间上进行 $k/2$ 组区间加。那么答案就直接推出来了： $s_{l-1}-\min\{s_{l\dots r}\}$ 。当然需要判掉无解，也不难。

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

int n, q; 
int a[100005]; 
i64 s[100005]; 
i64 mn[17][100005], mx[17][100005]; 

inline i64 qmin(int l, int r) {
    int k = __lg(r - l + 1); 
    return min(mn[k][l], mn[k][r - (1 << k) + 1]); 
}
inline i64 qmax(int l, int r) {
    int k = __lg(r - l + 1); 
    return max(mx[k][l], mx[k][r - (1 << k) + 1]); 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> q; 
    for (int i = 1; i <= n; ++i) cin >> a[i]; 
    for (int i = 1, x; i <= n; ++i) cin >> x, a[i] -= x; 
    for (int i = 1; i <= n; ++i) mn[0][i] = mx[0][i] = s[i] = s[i - 1] + a[i]; 
    for (int i = 1; i <= 17; ++i) for (int j = 1; j + (1 << i) - 1 <= n; ++j)
        mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << i - 1)]), 
        mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << i - 1)]); 
    while (q--) {
        int l, r; cin >> l >> r; 
        if (s[r] == s[l - 1] && qmax(l, r) <= s[l - 1]) cout << s[l - 1] - qmin(l, r) << "\n"; 
        else cout << "-1\n"; 
    }
    return 0; 
}

* F. Sports Betting

Portal.

有 $n(n\le 14)$ 个人，两两之间会打比赛。每人有一个实力值 $a_i$ ，在 $i$ 与 $j$ 的比赛中， $i$ 有 $\frac {a_i}{a_i+a_j}$ 的概率获胜，其他情况则是 $j$ 获胜。 $i$ 在与 $j$ 的比赛中获胜则称 $i$ 打败了 $j$ 。若 $i$ 打败了 $j$ ， $j$ 打败了 $k$ ，则认为 $i$ 也打败了 $k$ 。若 $i$ 打败了除了他自己以外的所有人，则称 $i$ 是一个 Winner（是否打败了自己不要求），注意 Winner 可能有多个。现在你需要求出 Winner 的期望数量，对 $10^9+7$ 取模。

考虑状压 DP，设 $f(i,S)$ 代表 $i$ 打败了 $S$ 中人的概率。容斥，答案为：

$f(i,S)=1-\sum_{T\subset S}f(i,T)\prod_{j\in S-T}\prod_{k\in T} \frac{a_j}{a_j+a_k}$

预处理 $g(i,S)=\prod_{j\in S} \frac{a_j}{a_j+a_i}$ ，那么：

$f(i,S)=1-\sum_{T\subset S}f(i,T)\prod_{k\in T} g(k,S-T)$

时间复杂度 $O(n^2 3^n)$ 。

#include <bits/stdc++.h>
using namespace std; 
const int P = 1000000007; 
const int N = 2000000; 

int n; 
int a[1 << 14], f[14][1 << 14], g[14][1 << 14]; 
int inv[N + 5]; 
inline int lowbit(int x) { return x & -x; }

inline int calc(int T, int ST) {
    int res = 1; 
    for (int i = 0; i < n; ++i)
        if (T >> i & 1) res = 1ll * res * g[i][ST] % P; 
    return res; 
}

int main(void) {
    inv[1] = 1; 
    for (int i = 2; i <= N; ++i) inv[i] = 1ll * (P - P / i) * inv[P % i] % P; 

    scanf("%d", &n); 
    for (int i = 0; i < n; ++i) scanf("%d", &a[1 << i]); 
    for (int i = 0; i < n; ++i) {
        g[i][0] = 1; 
        for (int s = 1; s < 1 << n; ++s)
            g[i][s] = 1ll * g[i][s ^ lowbit(s)] * a[lowbit(s)] % P * inv[a[lowbit(s)] + a[1 << i]] % P; 
    }
    for (int i = 0; i < n; ++i)
        for (int s = 0; s < 1 << n; ++s) if (s >> i & 1) {
            f[i][s] = 1; 
            for (int t = (s - 1) & s; t; t = (t - 1) & s)
                f[i][s] = (f[i][s] - 1ll * f[i][t] * calc(t, s - t) % P) % P; 
        }
    int ans = 0; 
    for (int i = 0; i < n; ++i) ans = (ans + f[i][(1 << n) - 1]) % P; 
    printf("%d\n", (ans + P) % P); 
    return 0; 
}

Hard Problems

比较困难的问题。

** G. Gates to Another World

Portal.

有 $2^n$ 个点，编号为 $i,j$ 的点之间有无向边当且仅当 $\mathrm{popcount}(i \oplus j)=1$ 。
有 $m$ 次操作，每次询问 $a,b$ 是否能互相到达，或者删除编号在 $[l,r]$ 之间的所有点，保证没有点会被删除两次。
$n\le 50,m\le 5\times 10^4$ 。

考虑逆时旅人，将删点改成加点。

最主要的问题是，如何用一种方式来压缩图？对于一个没有被删点的连续 $2^i$ 段，一定是连通的。这种方式与线段树有直接关系，考虑用线段树结构来刻画这个东西，然后点数就与删点次数有关。

注意一个位置只会被删除一次，这很好，我们可以在线段树上区间染色，代表这些点存活到了 $i$ 时刻。

这样对于动态开点线段树上的存在的点，才是有意义的点，其余所有点都可以被映射到它们身上。对于每个节点将在 $\min\{ls_i,rs_i\}$ 时刻将它的左右儿子分裂开（不再连通），逆时旅人并查集维护即可。

本题卡空间，注意你的内存消耗。

#include <bits/stdc++.h>
using namespace std; 
typedef long long i64; 
const int N = 50005 * 120; 

struct Query {
    string op; 
    i64 x, y; 
} Q[50005]; 

int n, m, ans[50005]; 
int fa[N + 5]; 
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int ls[N + 5], rs[N + 5], dat[N + 5], tot; 
#define leaf(o) (!ls[o] && !rs[o])
inline void pushdown(int o) {
    if (!ls[o]) ls[o] = ++tot; if (!rs[o]) rs[o] = ++tot; 
    if (dat[o]) dat[ls[o]] = dat[rs[o]] = dat[o], dat[o] = 0; 
}
void update(int o, i64 l, i64 r, i64 x, i64 y, int t) {
    if (x <= l && r <= y) return dat[o] = t, void(); 
    pushdown(o); i64 mid = l + r >> 1; 
    if (x <= mid) update(ls[o], l, mid, x, y, t); 
    if (mid < y) update(rs[o], mid + 1, r, x, y, t); 
}
int locate(int o, i64 l, i64 r, i64 p) {
    if (leaf(o)) return o; i64 mid = l + r >> 1; 
    if (p <= mid) return locate(ls[o], l, mid, p); 
    return locate(rs[o], mid + 1, r, p); 
}
vector<pair<int, int>> edge[50005]; 
void connect(int x, int y) {
    if (leaf(x) && leaf(y)) return edge[min(dat[x], dat[y])].emplace_back(x, y), void(); 
    if (leaf(x)) return connect(x, ls[y]), connect(x, rs[y]); 
    if (leaf(y)) return connect(ls[x], y), connect(rs[x], y); 
    connect(ls[x], ls[y]); connect(rs[x], rs[y]); 
}

int main(void) {
    for (int i = 1; i <= N; ++i) fa[i] = i; 
    ios_base::sync_with_stdio(0); 
    
    cin >> n >> m; i64 u = 1ll << n; 
    dat[++tot] = m + 1; 
    for (int i = 1; i <= m; ++i) {
        cin >> Q[i].op >> Q[i].x >> Q[i].y; 
        if (Q[i].op == "block") update(1, 0, u - 1, Q[i].x, Q[i].y, i); 
    }
    for (int i = 1; i <= tot; ++i) if (!leaf(i)) connect(ls[i], rs[i]); 
    for (int i = m + 1; i >= 1; --i) {
        for (auto [u, v] : edge[i]) fa[find(u)] = find(v); 
        if (Q[i].op == "ask") ans[i] = (find(locate(1, 0, u - 1, Q[i].x)) == find(locate(1, 0, u - 1, Q[i].y))); 
    }
    for (int i = 1; i <= m; ++i) if (Q[i].op == "ask") cout << ans[i] << 
    "\n"; 
    return 0; 
}

** H. DIY Tree

Portal.

给定一个 $n$ 个点的无向带权完全图，找出一个满足第 $i(i\le k)$ 个度数 $\le d_i$ 的最小生成树。 $n\le 50,k\le 5$ 。

本题正解需要使用拟阵，但是此内容在算法竞赛中的应用不多，对笔者来说学习的收益过低，因此这里写一下本题的随机化做法。

sto lsy orz！

给生成树定义估价函数 $f(T)=\sum_{i=1}^K \max\{0,D_i-d_i\}$ ，其中 $D_i$ 代表实际度数。

先求出最小生成树，然后对其进行调整。每次选择一条边权最大的，删去后 $f$ 会减小的边 $e_1$ ，替换成加上后 $f$ 不会变大的边权最小的边 $e_2$ ，时间复杂度为 $O(n^3)$ 。

随机化这个过程，我们给 $e_1$ 和 $e_2$ 的选择加上一个概率，不选就接着扫。

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

mt19937 Rand(time(0));

int n, k; 
int a[55], G[55][55];  
struct edge {
    int u, v, w, f; 
    edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
    bool operator< (const edge &a) const { return w < a.w; }
}; 
vector<edge> e; 

int Ans = 1e9; 
int fa[55];  
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int d[55]; 
inline int f(void) {
    int r = 0; 
    for (int i = 1; i <= k; ++i) r += max(0, d[i] - a[i]); 
    return r; 
}
void solve(void) {
    // cerr << "SOLVE\n"; 
    int ans = 0; 
    for (int i = 1; i <= n; ++i) fa[i] = i, d[i] = 0; 
    for (auto &it : e) {
        it.f = 0; 
        int u = find(it.u), v = find(it.v); 
        if (u == v) continue; fa[u] = v; 
        ans += it.w; ++d[it.u]; ++d[it.v]; it.f = 1; 
    }
    int now = 0; 
    while (now = f()) {
        // cerr << now << "\n"; 
        int p = -1; 
        while (p == -1) {
            for (int i = e.size() - 1; i >= 0; --i) {
                auto &it = e[i]; 
                if (it.f && (d[it.u] > a[it.u] || d[it.v] > a[it.v]) && Rand() % 4) { 
                    --d[it.u], --d[it.v]; ans -= it.w; it.f = 0; 
                    p = i; break; 
                }
            }
        }
        for (int i = 1; i <= n; ++i) fa[i] = i; 
        for (auto &it : e) if (it.f) fa[find(it.u)] = find(it.v); 
        int tmp = 1e9; 
        for (int i = 0; i < e.size(); ++i) {
            auto &it = e[i]; 
            if (i != p && !it.f && find(it.u) != find(it.v)) {
                ++d[it.u]; ++d[it.v]; 
                tmp = min(tmp, f() - now); 
                --d[it.u]; --d[it.v]; 
            }
        }
        bool flag = 0; 
        while (!flag) {
            for (int i = 0; i < e.size(); ++i) {
                auto &it = e[i]; 
                if (i != p && !it.f && find(it.u) != find(it.v)) {
                    ++d[it.u]; ++d[it.v]; 
                    if ((f() - now < 0 || tmp >= 0) && Rand() % 4) { it.f = 1, ans += it.w, flag = 1; break; } 
                    --d[it.u]; --d[it.v]; 
                }
            }
        }
    }
    Ans = min(Ans, ans); 
}

int main(void) {
    ios_base::sync_with_stdio(0); 
    cin >> n >> k; 
    for (int i = 1; i <= k; ++i) cin >> a[i]; 
    for (int i = k + 1; i <= n; ++i) a[i] = 1e9; 
    for (int i = 1, x; i < n; ++i) for (int j = i + 1; j <= n; ++j)
        cin >> x, e.emplace_back(i, j, x); 
    sort(e.begin(), e.end()); 
    double st = clock(); 
    do solve(); while (1000 * (clock() - st) / CLOCKS_PER_SEC < 5700); 
    cout << Ans << "\n"; 
    return 0; 
}

After Memories

我们可以相信我们的视觉吗？

在当下的情况，也许我们可以小心翼翼地踱步，来保证不要看不清会导致我们摔倒的东西。

但这也只是表象，我们依然无法看清一切。当忽略的东西足够多，终将酿成大祸。

也许这就是生命终结的原因。如果有生物可以看清一切，那我相信它们是永生的。

愿你能在遥远的天际线边找到自我