首页 > 其他分享 >2023冲刺国赛模拟 20.1

2023冲刺国赛模拟 20.1

时间：2023-06-18 09:03:55浏览次数：44  
标签：20.1 prod leaf int max1 国赛 2023 now mod

我是越来越摆了，一下午就改了一道题；而且这么菜，看了半天的题解做法还没看懂。又是被暴踩的一天。

T1 树染色

比较套路的想法是考虑当前以 \(u\) 为根的子树，考虑第一次选择 \(u\) 子树内的叶节点，此时我们必须选择 \(u\) 以上的节点作为链顶，这会对方案数产生贡献。

考虑通过第一条链划分子问题，设第一条链经过 \(u\) 的儿子为 \(v\) ，此时 \(u\) 子树选择的第一条链相当于在 \(v\) 子树内选择的第一条链，对于 \(u\) 的其他儿子，这条链不会影响其子树内的决策，但是可以确定其子树内选择的第一条链的链顶方案数产生的贡献。

设 \(f_{u,0/1}\) 表示当前考虑以 \(u\) 为根的子树，不考虑当前子树内第一条链的链顶方案数产生的贡献，第一条链颜色为黑 / 白时，子树的美观度之和。

转移考虑枚举 \(u\) 子树内第一条链经过 \(u\) 的儿子 \(v\) ，同时计算链之间的顺序关系造成的贡献，设 \(leaf_u\) 为 \(u\) 子树内叶节点的数量，那么有：

\[f_{u,0}=\sum_{v}f_{v,0}(\prod_{p\ne v}(a_if_{p,0}+b_if_{p,1})deep_u)(leaf_u-1)!(\prod_{p}\tfrac{1}{(leaf_p-[v=p])!}) \]

直接 dp 即可。

code 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;
const int max1 = 5e5;
const int mod = 998244353;
int n;
struct Node
{
    int v, A, B;
    Node () {}
    Node ( int __v, int __A, int __B )
        { v = __v, A = __A, B = __B; }
};
vector <Node> edge[max1 + 5];
int inv[max1 + 5], fac[max1 + 5], ifac[max1 + 5];
int leaf[max1 + 5], f[max1 + 5][2], g[max1 + 5][2];
int prod[max1 + 5][2];

void Dfs ( int now, int fa, int depth )
{
    for ( auto p : edge[now] )
        if ( p.v != fa )
            Dfs(p.v, now, depth + 1);

    int son = 0; leaf[now] = 0;
    for ( auto p : edge[now] )
    {
        if ( p.v == fa )
            continue;
        
        ++son;
        prod[son][0] = prod[son][1] = (1LL * p.A * f[p.v][0] + 1LL * p.B * f[p.v][1]) % mod * ifac[leaf[p.v]] % mod;
        leaf[now] += leaf[p.v];
    }

    if ( !son )
    {
        leaf[now] = 1;
        f[now][0] = f[now][1] = depth;
        g[now][0] = g[now][1] = 1;
    }
    else
    {
        prod[0][0] = prod[son + 1][1] = 1;
        for ( int i = 1; i <= son; i ++ )
            prod[i][0] = 1LL * prod[i - 1][0] * prod[i][0] % mod;
        for ( int i = son; i >= 1; i -- )
            prod[i][1] = 1LL * prod[i + 1][1] * prod[i][1] % mod;

        f[now][0] = f[now][1] = g[now][0] = g[now][1] = son = 0;
        for ( auto p : edge[now] )
        {
            if ( p.v == fa )
                continue;

            ++son;
            g[now][0] = (g[now][0] + 1LL * p.A * g[p.v][0] % mod * prod[son - 1][0] % mod * prod[son + 1][1] % mod * ifac[leaf[p.v] - 1] % mod * fac[leaf[now] - 1]) % mod;
            g[now][1] = (g[now][1] + 1LL * p.B * g[p.v][1] % mod * prod[son - 1][0] % mod * prod[son + 1][1] % mod * ifac[leaf[p.v] - 1] % mod * fac[leaf[now] - 1]) % mod;
            
            f[now][0] = (f[now][0] + 1LL * p.A * g[p.v][0] % mod * depth % mod * prod[son - 1][0] % mod * prod[son + 1][1] % mod * ifac[leaf[p.v] - 1] % mod * fac[leaf[now] - 1]) % mod;
            f[now][1] = (f[now][1] + 1LL * p.B * g[p.v][1] % mod * depth % mod * prod[son - 1][0] % mod * prod[son + 1][1] % mod * ifac[leaf[p.v] - 1] % mod * fac[leaf[now] - 1]) % mod;
        }
    }
    return;
}

int main ()
{
    freopen("treecolor.in", "r", stdin);
    freopen("treecolor.out", "w", stdout);

    scanf("%d", &n);
    for ( int i = 2, x, y, A, B; i <= n; i ++ )
    {
        scanf("%d%d%d%d", &x, &y, &A, &B);
        edge[x].push_back(Node(y, A, B));
        edge[y].push_back(Node(x, A, B));
    }
    inv[1] = 1;
    for ( int i = 2; i <= n; i ++ )
        inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;
    fac[0] = ifac[0] = 1;
    for ( int i = 1; i <= n; i ++ )
    {
        fac[i] = 1LL * fac[i - 1] * i % mod;
        ifac[i] = 1LL * ifac[i - 1] * inv[i] % mod;
    }

    Dfs(1, 0, 0);
    printf("%d\n", (g[1][0] + g[1][1]) % mod);

    return 0;
}

T2 关路灯

首先考虑询问给定 \([L,R,s]\) 如何处理，一个比较显然的想法是一次跳完一整个方向，设当前节点为 \(now\) ，前驱为 \(pre\) ，后继为 \(suf\) ，不妨设 \(x_{now}-x_{pre}>x_{suf}-x_{now}\) ，那么此时我们一定需要向后跳，比较自然的想法是找到 \(suf\) 后第一个点 \(i\) ，满足 \(x_{i+1}-x_{i}>x_{now}-x_{pre}\) ，那么到达点 \(i\) 后，我们可能转向，考虑再进行一步操作，最终移动到的位置只可能是 \(pre\) 或 \(i+1\) ，设 \(p\) 为当前点与前驱，后继距离的较大值，容易发现 \(p\) 翻倍了。循环进行这个过程，那么当前点的移动会被划分为 \(O(\log w)\) 次移动。

考虑处理 \([L,R]\) 内每个点对当前询问的贡献，比较显然的是每个点都会在一个时刻第一次到达左右端点，此时进行的操作就是从当前端点跳到另一个端点，如果我们可以统计每个点在这个时刻的贡献，那么答案也就不难计算了。

直接预处理每个点到达 \(1\) 或 \(n\) 的所有移动，由于一个点会被拆分为 \(O(\log w)\) 次移动，设第 \(i\) 次移动当前点控制的区间为 \([L,R]\) ，不难发现一次移动只会改变 \([L,R]\) 中一个指针，假设当前点首先触碰到询问的右端点，那么这个时刻一定发生在控制区间右端点的移动过程中，具体来讲就是第一个包含当前询问右端点的区间，当然由于当前点可能先触碰到左端点，因此需要检查当前点对应的区间左端点 \(L\) 是否大于询问左端点。

显然有一种扫描线的思路，以统计先触碰到询问右端点的点的贡献为例，实现的操作就是在当前点控制区间右端点移动过程中删除上一个区间，插入下一个区间，统计所有满足控制区间左端点大于询问左端点的点的贡献。

code 
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int max1 = 1e5, max2 = 3e5;
int n, m, x[max1 + 5];

struct Question
{
    int pos, id;
    Question () {}
    Question ( int __pos, int __id )
        { pos = __pos, id = __id; }
};
vector <Question> qusL[max1 + 5], qusR[max1 + 5];
long long ans[max2 + 5];
struct Option
{
    int pos;
    long long val;
    Option () {}
    Option ( int __pos, long long __val )
        { pos = __pos, val = __val; }
};
vector <Option> optL[max1 + 5], optR[max1 + 5];

struct ST_List
{
    int list[max1 + 5][20];

    void Build ()
    {
        list[1][0] = 0x3f3f3f3f;
        for ( int i = 2; i <= n; i ++ )
            list[i][0] = x[i] - x[i - 1];
        for ( int k = 1; (1 << k) <= n; k ++ )
            for ( int i = 1; i + (1 << k) - 1 <= n; i ++ )
                list[i][k] = max(list[i][k - 1], list[i + (1 << (k - 1))][k - 1]);
    }

    int Query_Front ( int now, int x )
    {
        for ( int i = 20; i >= 0; i -- )
            if ( now - (1 << i) + 1 >= 1 && list[now - (1 << i) + 1][i] < x )
                now -= 1 << i;
        return now;
    }

    int Query_Back ( int now, int x )
    {
        for ( int i = 20; i >= 0; i -- )
            if ( now + (1 << i) - 1 <= n && list[now][i] < x )
                now += 1 << i;
        return now;
    }
}ST;

struct Data
{
    long long sum;
    int cnt;

    Data () {}
    Data ( long long __sum, int __cnt )
        { sum = __sum, cnt = __cnt; }

    Data operator + ( const Data &A ) const
        { return Data(sum + A.sum, cnt + A.cnt); }
    
    Data operator - ( const Data &A ) const
        { return Data(sum - A.sum, cnt - A.cnt); }
};

struct Bit
{
    #define lowbit(now) ( now & -now )

    Data tree[max1 + 5];
    void Build ()
    {
        for ( int i = 0; i <= n; i ++ )
            tree[i] = Data(0LL, 0);
        return;
    }

    void Insert ( int now, const Data &x )
    {
        while ( now <= n )
        {
            tree[now] = tree[now] + x;
            now += lowbit(now);
        }
        return;
    }

    Data Query ( int now )
    {
        Data res = Data(0LL, 0);
        while ( now )
        {
            res = res + tree[now];
            now -= lowbit(now);
        }
        return res;
    }

    Data Query ( int L, int R )
    {
        return Query(R) - Query(L - 1);
    }
}Tree;

int main ()
{
    freopen("light.in", "r", stdin);
    freopen("light.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for ( int i = 1; i <= n; i ++ )
        scanf("%d", &x[i]);
    for ( int i = 1, L, R; i <= m; i ++ )
    {
        scanf("%d%d", &L, &R); ans[i] = 1LL * ( R - L + 1 ) * ( x[R] - x[L] );
        if ( L != R )
        {
            if ( R - L != 1 )
            {
                qusR[R].push_back(Question(L, i));
                qusL[L].push_back(Question(R, i));
            }
        }
    }

    ST.Build();

    for ( int i = 1; i <= n; i ++ )
    {
        int L = i, R = i, now = i; long long sum = 0;
        while ( true )
        {
            if ( L == 1 || R == n )
                break;

            int pre = x[now] - x[L - 1], suf = x[R + 1] - x[now];
            if ( pre < suf )
            {
                int p = ST.Query_Front(L, suf);
                optL[L - 1].push_back(Option(R, sum + x[now]));
                optL[p - 1].push_back(Option(-R, sum + x[now]));
                sum += x[now] - x[p];
                L = now = p;
            }
            else
            {
                int p = ST.Query_Back(R + 1, pre + 1) - 1;
                optR[R + 1].push_back(Option(L, sum - x[now]));
                optR[p + 1].push_back(Option(-L, sum - x[now]));
                sum += x[p] - x[now];
                R = now = p;
            }
        }
    }

    Tree.Build();
    for ( int i = 1; i <= n; i ++ )
    {
        for ( auto v : optR[i] )
        {
            if ( v.pos > 0 )
                Tree.Insert(v.pos, Data(v.val, 1));
            else
                Tree.Insert(-v.pos, Data(-v.val, -1));
        }

        for ( auto v : qusR[i] )
        {
            Data d = Tree.Query(v.pos + 1, n);
            ans[v.id] += d.sum + 1LL * d.cnt * x[i];
        }
    }

    Tree.Build();
    for ( int i = n; i >= 1; i -- )
    {
        for ( auto v : optL[i] )
        {
            if ( v.pos > 0 )
                Tree.Insert(v.pos, Data(v.val, 1));
            else
                Tree.Insert(-v.pos, Data(-v.val, -1));
        }

        for ( auto v : qusL[i] )
        {
            Data d = Tree.Query(1, v.pos - 1);
            ans[v.id] += d.sum - 1LL * d.cnt * x[i];
        }
    }

    for ( int i = 1; i <= m; i ++ )
        printf("%lld\n", ans[i]);
    return 0;
}

T3 树状数组

考虑 dp ，设 \(f_{i,j,k}\) 表示当前考虑 \(a\) 序列前 \(i\) 个数，当前生成的 \(x\) 从 \(R\) 的第 \(j\) 位开始失配，失配位后面存在 \(k\) 个位置为 \(1\) 的方案数。

先考虑统计答案，容易发现比较大小的过程实质上就是取出当前两个数的二进制 lcp ，比较下一位的大小即可，因此这样设计状态可以直接计算答案。

考虑转移，如果 \(a_i=0\) ，如果 \(k\ne 0\) ，显然转移到 \(f_{i,j,k-1}\) ，如果 \(k=0\) ，容易发现此时 \(x\) 是可以唯一确定的，因此直接对 \(x\) 进行操作，暴力求解转移到的状态即可； \(a_i=1\) 同理。

钦定 \(a_i=0\) 只需要预处理前后缀 dp 直接拼接即可。

code 
#include <cstdio>
#include <algorithm>
using namespace std;
const int max1 = 1e5, max2 = 20;
const int mod = 998244353;

int n, k, lim;
char s[max1 + 5];
int id[max2 + 5][max2 + 5], total;
int trans[max2 * max2 + 5][2];
int f[max1 + 5][max2 * max2 + 5], g[max1 + 5][max2 * max2 + 5];

#define lowbit(x) (x & -(x))

int Option0 ( int x )
{
    return x - lowbit(x);
}

int Option1 ( int x )
{
    return x + lowbit((1 << k) - 1 - x);
}

int Find ( int x )
{
    for ( int i = k - 1; i >= 0; i -- )
        if ( ((x ^ lim) >> i) & 1 )
            return id[i][__builtin_popcount(x & ((1 << i) - 1))];
    return 0;
}

void Add ( int &x, int y )
{
    x += y;
    if ( x >= mod )
        x -= mod;
    return;
}

int main ()
{
    freopen("fenwick.in", "r", stdin);
    freopen("fenwick.out", "w", stdout);

    scanf("%d%d%d%s", &n, &k, &lim, s + 1);
    for ( int i = 0; i < k; i ++ )
        for ( int j = 0; j <= i; j ++ )
            id[i][j] = ++total;
    
    for ( int i = 0; i < k; i ++ )
    {
        for ( int j = 0; j <= i; j ++ )
        {
            if ( !j )
                trans[id[i][j]][0] = Find(Option0(((lim >> i) ^ 1) << i));
            else
                trans[id[i][j]][0] = id[i][j - 1];
            
            if ( j == i )
                trans[id[i][j]][1] = Find(Option1((((lim >> i) ^ 1) << i) | ((1 << i) - 1)));
            else
                trans[id[i][j]][1] = id[i][j + 1];
        }
    }
    trans[Find(lim)][0] = Find(Option0(lim));
    trans[Find(lim)][1] = Find(Option1(lim));

    f[0][Find(0)] = 1;
    for ( int i = 1; i <= n; i ++ )
    {
        for ( int S = 0; S <= total; S ++ )
        {
            if ( s[i] != '1' )
                Add(f[i][trans[S][0]], f[i - 1][S]);
            if ( s[i] != '0' )
                Add(f[i][trans[S][1]], f[i - 1][S]);
        }
    }
    for ( int i = 0; i <= lim; i ++ )
        g[n + 1][Find(i)] = 1;
    
    for ( int i = n; i >= 1; i -- )
    {
        for ( int S = 0; S <= total; S ++ )
        {
            if ( s[i] != '1' )
                Add(g[i][S], g[i + 1][trans[S][0]]);
            if ( s[i] != '0' )
                Add(g[i][S], g[i + 1][trans[S][1]]);
        }
    }

    for ( int i = 1; i <= n; i ++ )
    {
        if ( s[i] == '1' )
            puts("0");
        else
        {
            int ans = 0;
            for ( int S = 0; S <= total; S ++ )
                Add(ans, 1LL * f[i - 1][S] * g[i + 1][trans[S][0]] % mod);
        
            printf("%d\n", ans);
        }
    }

    return 0;
}

标签：20.1,prod,leaf,int,max1,国赛,2023,now,mod
From： https://www.cnblogs.com/KafuuChinocpp/p/17488676.html

相关文章

  • 《近期回忆录》2023.6.17
    我们都是行走在镜面边缘的人。低下头看到的，是半个迷茫的自己，和半个不见底的深渊。——百度贴吧noip，《行走在镜面的边缘》记2023.5.5-2023.6.17，谨以此送给一个半月以来疯狂的自己。 日志阶段性sum瞎扯(bushi)  2023.5.7新的开始NOCAI创新编程初赛&&蓝桥......
  • 2023-06-17 tp6如何开启debug调试
    我安装的tp6没有.env文件，官网的文档是说把tp6在根目录生成的.exmaple.env文件改名为.env就可以了，如果没有该文件就直接创建一个，然后在里面添加代码：APP_DEBUG=true；如果想关闭调试则设置为false即可。注意：官方说明该调试只可用于本地测试，部署到生产环境时会失效。tp6官方文档：ht......
  • 面经2023
    东方甄选：Kafka和mq区别Varchar建立索引后用int查是否能使用索引Redis集群模式和非集群模式client有什么区别Redis集群模式怎么知道key在哪个槽是server端做的逻辑还是client做的分槽逻辑白龙马setnx和设置过期时间是原子操作不联合索引，如果用Abetween和B等于xx，是否会用到索......
  • 2023-06-17 闲话
    生活在这一周里面陷入了一团糟，不妨称之为随机生活。像吃饭睡觉这样的最最基础的物质生活完全没法保证规律，作息是随机作息：第一天到家的作息是三点到六点，中午睡了一小时，晚上熬夜看了欧冠决赛；前天是十二点到六点，昨天是十点到五点。你觉得这不是迈上正轨了吗，我觉得不然，比如我们看看......
  • 2023-06-17：说一说redis中渐进式rehash？
    2023-06-17：说一说redis中渐进式rehash？答案2023-06-17：在Redis中，如果哈希表的数组一直保持不变，就会增加哈希冲突的可能性，从而降低检索效率。为了解决这个问题，Redis会对数组进行扩容，通常是将数组大小扩大为原来的两倍。然而，这个扩容过程会引起元素在哈希桶中的分散，导致元素的移动。由......
  • 2023-06-17：说一说redis中渐进式rehash？
    2023-06-17：说一说redis中渐进式rehash？答案2023-06-17：在Redis中，如果哈希表的数组一直保持不变，就会增加哈希冲突的可能性，从而降低检索效率。为了解决这个问题，Redis会对数组进行扩容，通常是将数组大小扩大为原来的两倍。然而，这个扩容过程会引起元素在哈希桶中的分散，导致元素的移动。......
  • neon linux安装matlab2023a的离线文档
    1.changetodirectorycd/media/munication/59A4D5FD759E19972.mountR2023a_Doc_Linux.isosudomount-oloopR2023a_Doc_Linux.isocdrom/3.changetodirectorycdcdrom/bin/glnxa64/4.installdocsudo./mpminstall-doc--matlabroot=/usr/local/......
  • 路径之谜(DFS)-2016年蓝桥杯国赛
    路径之谜-2016年国赛1、题目描述2、解题思路3、代码实现1、题目描述  小明冒充X星球的骑士，进入了一个奇怪的城堡。  城堡里边什么都没有，只有方形石头铺成的地面。  假设城堡地面是n×n*个方格。如下图所示。  按习俗，骑士要从西北角走到东南角。可以横向或纵向移动，但......
  • 十一届蓝桥杯研究生组国赛-循环小数(数论)
    十一届蓝桥杯研究生组国赛-循环小数1、题目描述2、解题思路3、代码实现1、题目描述  已知S是一个小于11的循环小数，请计算与S相等的最简真分数是多少。  例如0.3333⋯0.3333⋯等于1331，0.1666⋯0.1666⋯等于1661。输入描述  输入第一行包含两个整数p和q，表示......
  • The baby-bust economy “婴儿荒”经济 | 经济学人20230603版社论双语精翻
    2023年6月3日《经济学人》（TheEconomist）封面文章暨社论（Leaders）精选：《“婴儿荒”经济》（“Thebaby-busteconomy”）。baby-bust即“婴儿荒”（生育低谷），与历史上1946~1964年间著名的baby-boom即“婴儿潮”（生育高峰）相对立。Thebaby-busteconomy“婴儿荒”经济Globalfertilityhascoll......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99