强迫思考不断进行,焦虑和抑郁水平不断加重,我的热情和精力被不断消磨。

以及,山有木兮。

我在中关村的星巴克里面趴在桌上睡着了。

现时两点半。高铁八点半才开。最早六点半才能进站。通勤需半个小时。

前事已毕后事未接的这四个小时,我终于没有什么迫切的任务需要应对了。

已经可以了,不需要再努力了。

然后陷入消极情绪。在一个没人注意的小角落我悄无声息。我知道我被世界抛弃。

外面阳光热烈,人群来往,嬉笑脸上。里面朋友聚会,对饮谈话,相视而笑。

这世界与我无关。

DEL 至少作为一个 OIer 已经死去了。

省选退役。
第一天代码版本没有核对好,交了个一半的,丢了100.
第二天读入优化写错。windows 拍不出错 linux RE. 200 全没有.
我的竞赛生涯就是笑话。

有了这 400 分会怎样?
那么多“如果”漏了出来。如果我把那天的咖喱全都吃光是不是好一点。

抱歉。真的抱歉。
只能走到一半,就走不下去了。
我尽力了可是运气不站在我这边。当时我在逞能。现在我也是。


有几十篇存货一起放上来吧。排版大概是不会排的了。更新也不会更了。
为了方便都设为了前一天的日期。也算是纪念至少在一天前 DEL 还是一个 OIer 吧。
不过这里大概很快就被人忘记了吧。

雅礼省赛集训 2018 Sol.

3.23

T1

给一棵以 1 号点为根的树。每一个点有一些怪,移动速度和在 1 号点的人一样。

对每一个终点,问最多碰到多少怪。

Sol.

裸的长链剖分。

听了题解以及跟 @whj 讨论了一下,其实只需两遍 dfs。一遍收集深度$\times2$,另一遍收集深度$\times2-2$.

#include <bits/stdc++.h>
using namespace std;
template<class T>
inline void read(T&x)
{
    T p = 1, n = 0; char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>inline void read(T&x,U&y){read(x), read(y);}
template<class T,class U,class V>inline void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1e5 + 10;
struct E{int v, n;}e[maxn << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v)
{
    e[ec] = (E){v, h[u]}; 
    h[u] = ec++; 
    e[ec] = (E){u, h[v]}; 
    h[v] = ec++;
}
int depth[maxn], size[maxn], hson[maxn], maxd[maxn];
void dfs(int u = 1, int f = 0)
{
    size[u] = 1; hson[u] = 0; 
    maxd[u] = depth[u];
    for(int i = h[u], v = e[i].v ;i; i = e[i].n, v = e[i].v) 
    if(v != f)
    {
        depth[v] = depth[u] + 1, dfs(v, u);
        size[u] += size[v]; 
        if(maxd[v] > maxd[hson[u]]) maxd[u] = maxd[v], hson[u] = v;
    }
}
int w[maxn], a[maxn]; 
bool flag[maxn];
void collect(int u, int f)
{
    w[depth[u]] += a[u];
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) 
    if(v != f && !flag[v])
        collect(v, u);
}
int ans[maxn];
void dfs2(int u = 1, int f = 0, bool ff = false)
{
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) 
    if(v != f && v != hson[u])
        dfs2(v, u, true);
    if(hson[u]) 
    {
        dfs2(hson[u], u, false); 
        flag[hson[u]] = 1;
    }
    collect(u, f);
    ans[u] = w[depth[u] * 2 - 2] + w[depth[u] * 2 - 1];
    if(ff) 
    {
        memset(w, 0, sizeof w); 
        memset(flag, 0, sizeof flag);
    }
}
void dfs3(int u = 1, int f = 0)
{
    for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
        ans[v] += ans[u], dfs3(v, u);
}
int main()
{
    freopen("escape.in", "r", stdin);
    freopen("escape.out", "w", stdout);
    int n; read(n);
    for(int i = 1; i <= n; ++i) read(a[i]);
    for(int i = 1, u, v; i < n; ++i) read(u, v), add_edge(u, v);
    depth[1] = 1; dfs();
    dfs2();
    dfs3();
    for(int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
    return 0;
}

T2

定义 $ f_k(n)=f_{k-1}*1(n)=\sum_{d|n} f_{k-1}(d) $ . 给 $ x,k,f_0 $ , 求 $ f_k(n) $ .

Sol.

卷积满足结合律,考虑使用快速幂计算 $ 1^k $ ,其中乘法定义为卷积。要注意到只求某一项的值,这一项的因数级别在 $ O(n^{3/4}) $ (@whj 语),所以可以过。

还有一种使用牛顿级数的做法。

注意到 $ 1^k=\sum_i{k\choose i}(\Delta^i1^x)^0 $ ,$ k $ 很小且 $ (\Delta^i1^x)^0(v) $ 是很容易预处理出来的。

#include <bits/stdc++.h>
using namespace std;
template<class T>
inline void read(T&x)
{
    T p = 1, n = 0; char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>inline void read(T&x,U&y){read(x), read(y);}
template<class T,class U,class V>inline void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1e5 + 10, mod = 998244353;
int f[maxn], a[maxn], tmp[maxn], ret[maxn], t2[maxn], ac;
int calc(int k)
{
    for(int i = 0; i < ac; ++i) ret[a[i]] = 0;
    ret[1] = 1;
    for(int i = 0; i < ac; ++i) t2[a[i]] = 1;
    for(; k; k >>= 1)
    {
        if(k & 1)
        {
            for(int i = 0; i < ac; ++i) tmp[a[i]] = 0;
            for(int i = 0; i < ac; ++i) for(int j = 0; j <= i; ++j) if(a[i] % a[j] == 0)
                (tmp[a[i]] += 1ll * ret[a[j]] * t2[a[i] / a[j]] % mod) %= mod;
            for(int i = 0; i < ac; ++i) ret[a[i]] = tmp[a[i]];
        }
        for(int i = 0; i < ac; ++i) tmp[a[i]] = 0;
        for(int i = 0; i < ac; ++i) for(int j = 0; j <= i; ++j) if(a[i] % a[j] == 0)
            (tmp[a[i]] += 1ll * t2[a[j]] * t2[a[i] / a[j]] % mod) %= mod;
        for(int i = 0; i < ac; ++i) t2[a[i]] = tmp[a[i]];
    }
}
int main()
{
    freopen("machine.in", "r", stdin);
    freopen("machine.out", "w", stdout);
    int n; read(n);
    for(int i = 1; i <= n; ++i) read(f[i]);
    int m; read(m);
    while(m--)
    {
        int k, x; read(k, x);
        ac = 0;
        for(int i = 1; i * i <= x; ++i) if(x % i == 0)
        {
            a[ac++] = i;
            if(i * i != x) a[ac++] = x / i;
        }
        sort(a, a + ac);
        calc(k);
        int ans = 0;
        for(int i = 0; i < ac; ++i) (ans += 1ll * f[a[i]] * ret[x / a[i]] % mod) %= mod;
        printf("%d\n", ans);
    }
    return 0;
}

T3

交互题。

一棵二叉树,每条边有颜色,告诉你现在的起点深度。你可以调用 move 使用某一颜色的边,query 查询当前点深度,你要跳到深度为 0 的点。

100 分初始深度为 $10^5$ 要求 query 调用不超过 $51000$ 次, move 调用不超过 $ 10^6 $ 次。

Sol.

每次走 $ 6 $ 步,分类讨论 $ 2^6=64 $ 种情况。期望每次询问能跳 $ 63\over32 $ 步,能过。其实写丑了,根本不必要手写讨论。

#include "maze.h"

int seed = 20180323, x = 3;
int rrand()
{
    return (x = (x + seed + x % 41 * seed % 41) % 41)  % 32;
}

int excl(int i, int j)
{
    if(i != 0 && j != 0) return 0;
    if(i != 1 && j != 1) return 1;
    if(i != 2 && j != 2) return 2;
}
int fi[100], se[100], th[100], fo[100], fif[100], six[100];
void findpath(int initialDeep, int T)
{
    if(!query()) return;
    int last = -1; bool flag = false;
    for(int i = 0; i < 2; ++i)
    {
        if(move(i)) return; 
        if(query() > initialDeep) move(i);
        else {last = i; flag = true; break;}
    }
    if(!flag) move(2), last = 2;
    
    int curdep = initialDeep - 1;
    while(curdep > 4)
    {
        int cnt = 0;
        for(int i = 0; i <= 2; ++i) if(i != last)
        {
            for(int ii = 0; ii < 32; ++ii)
            fi[cnt + ii] = i;
            for(int j = 0; j <= 2; ++j) if(j != i)
            {
                for(int jj = 0; jj < 16; ++jj)
                se[cnt + jj] = j;
                for(int k = 0; k <= 2; ++k) if(k != j)
                {
                    for(int kk = 0; kk < 8; ++kk) th[cnt + kk] = k;
                    for(int l = 0; l <= 2; ++l) if(l != k)
                    {
                        for(int ll = 0; ll < 4; ++ll) fo[cnt + ll] = l;
                        for(int m = 0; m <= 2; ++m) if(m != l)
                        {
                            for(int mm = 0; mm < 2; ++mm) fif[cnt + mm] = m;
                            for(int n = 0; n <= 2; ++n) if(n != m)
                                six[cnt++] = n;
                        }
                    }
                }
            }
        }
        
        int pa = rrand();
        move(fi[pa]); move(se[pa]); move(th[pa]); move(fo[pa]); move(fif[pa]); move(six[pa]);
        int d = query();
        if(d == curdep + 6) 
        move(six[pa]), move(fif[pa]), move(fo[pa]), move(th[pa]), move(se[pa]), move(fi[pa]), move(last = excl(fi[pa], last)), curdep -= 1;
        else if(d == curdep + 4) 
        move(six[pa]), move(fif[pa]), move(fo[pa]), move(th[pa]), move(se[pa]), move(last = excl(se[pa], fi[pa])), curdep -= 2;
        else if(d == curdep + 2) 
        move(six[pa]), move(fif[pa]), move(fo[pa]), move(th[pa]), move(last = excl(th[pa], se[pa])), curdep -= 3;
        else if(d == curdep)
        move(six[pa]), move(fif[pa]), move(fo[pa]), move(last = excl(fo[pa], th[pa])), curdep -= 4;
        else if(d == curdep - 2)
        move(six[pa]), move(fif[pa]), move(last = excl(fif[pa], fo[pa])), curdep -= 5;
        else if(d == curdep - 4)
        move(six[pa]), move(last = excl(six[pa], fif[pa])), curdep -= 6;
        else 
        last = six[pa], curdep -= 6;
    }
    if(curdep == 0) return;
    for(int i = curdep; i; --i)
    {
        bool flag = false;
        for(int j = 0; j < 2; ++j) if(j != last)
        {
            move(j);
            if(query() > i) 
            {
                move(j);
                if(last == 2) {move(1), last = 1, flag = true; break;}
            }
            else {last = j; flag = true; break;}
        }
        if(!flag) move(2), last = 2;
    }
}

3.25

即便是原题大战又怎样。。还是菜到打不出来QAQ

A

给出一个长度为 m 的序列 A, 请你求出有多少种 1..n 的排列, 满足 A 是它的一个 LIS.

$ 1\le m\le n\le15 $ .

Sol.

考虑需要的信息。保证合法性需要对答案有贡献的序列的 LIS 信息(A 在 LIS 的信息显然包括其中),转移需要局部已处理的集合的信息。

LIS 数组满足单调性,可以将之压为二进制状态。

$ f_{S, S_0} $ 表示考虑了集合 $ S $ ,LIS 信息为 $ S_0 $ 的合法方案数。又注意到恒有 $ S_0\subset S $ ,所以用一个三进制描述这个状态即可。复杂度 $ O(n^23^n) $ .

要注意使用了标准化技术后转移拓扑序和下标的顺序是不一致的。要用个队列保存转移。

转移时精致一点。。打错了好多。。

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 20, maxm = 1.5e7;
int a[maxn], A[maxn], pow3[maxn], log3[maxm];
bool flag[maxn];
long long dp[maxm] = {0};
queue<int> q[maxn];
int main()
{
    freopen("arg.in", "r", stdin);
    freopen("arg.out", "w", stdout);
    int n, m; read(n, m);
    for(int i = 0; i < m; ++i) read(a[i]), --a[i], flag[a[i]] = 1;
    pow3[0] = 1; for(int i = 1; i <= n; ++i) pow3[i] = pow3[i - 1] * 3;
    for(int i = 1; i < pow3[n]; ++i) log3[i] = log3[i / 3] + 1;
    int N = pow3[n];
    dp[0] = 1; q[0].push(0);
    long long ans = 0;
    for(int i = 0; i < n; ++i)
    {
        while(!q[i].empty())
        {
            int S = q[i].front(); q[i].pop();
            bool f = false;
            for(int j = 0; j < n; ++j) if((S / pow3[j]) % 3 == 0)
            {
                f = true;
                int T = S + 2 * pow3[j];
                for(int k = j + 1; k < n; ++k) if((T / pow3[k]) % 3 == 2)
                {
                    T -= 1 * pow3[k];
                    break;
                }
                int cnt = 0, ac = 0;
                for(int k = 0; k < n; ++k) 
                {
                    if((T / pow3[k]) % 3 == 2) ++cnt;
                    if((S / pow3[k]) % 3 != 0 && k == a[ac]) ++ac;
                }
                if(!flag[j]) 
                {
                    if(cnt <= m)
                    { 
                        if(!dp[T]) q[i + 1].push(T);
                        dp[T] += dp[S]; 
                    }
                }
                else
                {
                    if(cnt > m || a[ac] != j) continue;
                    if(!dp[T])q[i + 1].push(T);
                    dp[T] += dp[S]; 
                }
            }
        }
    }
    while(!q[n].empty()) ans += dp[q[n].front()], q[n].pop();
    printf("%lld\n", ans);
    return 0;
}

B

给定一个正 n 边形及其三角剖分, 共 2n − 3 条边 (n 条多边形的边和 n − 3 条对角线), 每条边
的长度为 1.
共 q 次询问, 每次询问给定两个点, 求它们的最短距离.

Sol.

强烈抗议出原题。当时还跟 mhx 讨论了一个下午。思路实在太妙就记了下来。

平面图、网格图上很多特殊性质可以利用。分治是其中要考虑的。

3.30

table

program

path

4.2

c

一棵树上 A 和 B 轮流给结点对应染红色蓝色。A 要使红蓝联通块差大, B 使小。问最后整棵树的联通块差。

Sol.

记 $ S_A/S_B/E_A/E_B $ 为各颜色点数和同色边数,则联通块数有 $ S_A $