雅礼省赛集训 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 $

标签: none

添加新评论