雅礼省赛集训 2018 Sol.

雅礼省赛集训 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 查询当前点深度,你要跳到深度为 的点。

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_

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

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

#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

添加新评论

bst g22 jinniu lilai opebet orange88 vinbet xbet yuebo zunlong shijiebei bet007 hg0088 ju111 letiantang m88 mayaba qg777 qianyiguoji sbf777 tengbohui tlc ule weilianxier waiweitouzhu xingfayule xinhaotiandi yinheyule youfayule zhongying 2018shijiebei w88 18luck 188bet beplay manbet 12bet 95zz shenbo weide1946 ca88 88bifa aomenxinpujing betway bodog bt365 bwin tongbao vwin weinisiren 88jt fenghuangyule hongyunguoji 918botiantang huanyayule jianada28 jixiangfang libo long8 hongzuyishi zuqiutouzhu