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

2023冲刺国赛模拟 36.1

时间：2023-07-14 18:55:48浏览次数：49  
标签：int res sum 国赛 2023 first 36.1 inv mod

最近越来越懒了，估了很长时间的题解， OI 生涯结束前是凑不够 200 篇博客了，但退役前还是努力写点东西吧。

第一次写题解的大约在暑假集训，原因是当时改模拟赛题目经常参考学长的博客，于是自己也尝试这写了博客；然而省选以后，改题就很少参考学长的博客，一个原因是很难找到模拟赛题目的题解，一个原因是下发题解大多数也能理解了（貌似不理解的题都被我直接弃了）。从那之后自己的题解就变的很不连续， 3 个多月只写了 40 篇左右题解。

T1 染色题

观察题目的性质，容易发现奇数位置和偶数位置的颜色互不干扰，对于任意序列，如果 \(a_{i}\) 和 \(a_{i+2}\) 不相等，我们认为 \(i\) 位置上存在一个小球，容易发现原题目限制相当于区间 \(L, R\) 不存在奇数和偶数位置都存在小球。考虑 dp 求解方案，设 \(f_i\) 表示当前最后一个小球在位置 \(i\) 的方案数，枚举 \(i\) 前合法的 \(j\) 进行转移即可，由于合法的奇偶性相同的 \(j\) 构成一段区间，可以使用前缀和优化为 \(O(n)\) 。注意到确定 \(a_1, a_2\) 后整个序列才能完全确定，因此总方案数乘以 \(8\) 即为答案。

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

const int max1 = 1e6;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;

int n, m, Min[max1 + 5];

int f[max1 + 5], sum[max1 + 5], ans;

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

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

    scanf("%d%d", &n, &m);
    for ( int i = 1; i <= n; i ++ )
        Min[i] = i;
    for ( int i = 1, L, R; i <= m; i ++ )
    {
        scanf("%d%d", &L, &R);

        if ( R > 2 )
            Min[R - 2] = min(Min[R - 2], L);
    }

    for ( int i = n - 1; i >= 1; i -- )
        Min[i] = min(Min[i + 1], Min[i]);
    
    f[0] = sum[0] = ans = 1;

    for ( int i = 1; i <= n - 2; i ++ )
    {
        if ( i > 1 )
            f[i] = sum[i - 2];
        
        int p = Min[i] - 1 - ((Min[i] ^ i) & 1);
        if ( p >= 0 )
            Add(f[i], sum[p]);

        sum[i] = f[i];

        if ( i > 1 )
            Add(sum[i], sum[i - 2]);

        Add(ans, f[i]);
    }

    ans = 8LL * ans % mod;

    printf("%d\n", ans);

    return 0;
}

T2 石头剪刀布

首先考虑枚举 \(u\) ，容易发现 \(u\) 向上合并的过程可以类似线段树进行优化为 \(O(\log n)\) 。

设函数 \(f(L, R, x, y)\) 表示选手编号位于 \([L, R]\) ， \(u\) 编号位于 \([x, y]\) 的答案，设 \(mid=\tfrac{L+R}{2}\) ，发现对于 \(u<mid\) ，都会和 \([mid, R]\) 区间的概率合并，对于 \(u>mid\) ，都会和 \([L, mid]\) 的区间的概率合并，因此 \(f\) 函数可以递归进行求解。不难发现 \(f\) 函数会递归形成 \(O(\log n)\) 个区间，满足 \(x\le L\le R\le y\) ，这部分的概率是可以直接预处理的，总复杂度可以做到 \(O(n\log n)\) 。

code 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <iostream>
using namespace std;

const int max1 = 3e5;
const int mod = 998244353;

int n, m;
char s[max1 + 5];
int inv[max1 + 5];

struct Data
{
    int f[3];

    void Clear ()
    {
        memset(f, 0, sizeof(f));
        return;
    }

    Data operator + ( const Data &A ) const
    {
        Data res; res.Clear();
        res.f[0] = (res.f[0] + 1LL * f[0] * A.f[0]) % mod;

        res.f[0] = (res.f[0] + 2LL * f[0] * A.f[1] % mod * inv[3]) % mod;
        res.f[1] = (res.f[1] + 1LL * f[0] * A.f[1] % mod * inv[3]) % mod;

        res.f[0] = (res.f[0] + 1LL * f[0] * A.f[2] % mod * inv[3]) % mod;
        res.f[2] = (res.f[2] + 2LL * f[0] * A.f[2] % mod * inv[3]) % mod;

        res.f[1] = (res.f[1] + 1LL * f[1] * A.f[1]) % mod;

        res.f[1] = (res.f[1] + 2LL * f[1] * A.f[2] % mod * inv[3]) % mod;
        res.f[2] = (res.f[2] + 1LL * f[1] * A.f[2] % mod * inv[3]) % mod;

        res.f[1] = (res.f[1] + 1LL * f[1] * A.f[0] % mod * inv[3]) % mod;
        res.f[0] = (res.f[0] + 2LL * f[1] * A.f[0] % mod * inv[3]) % mod;

        res.f[2] = (res.f[2] + 1LL * f[2] * A.f[2]) % mod;

        res.f[2] = (res.f[2] + 2LL * f[2] * A.f[0] % mod * inv[3]) % mod;
        res.f[0] = (res.f[0] + 1LL * f[2] * A.f[0] % mod * inv[3]) % mod;

        res.f[2] = (res.f[2] + 1LL * f[2] * A.f[1] % mod * inv[3]) % mod;
        res.f[1] = (res.f[1] + 2LL * f[2] * A.f[1] % mod * inv[3]) % mod;
        return res;
    }
};

Data P[max1 + 5][20];
pair <Data, int> Q[max1 + 5][20];

pair <Data, int> Solve ( int L, int R, int x, int y )
{
    pair <Data, int> res;
    if ( L >= x && R <= y )
        return Q[L][__lg(R - L + 2)];

    int mid = (L + R) >> 1;

    if ( y <= mid )
    {
        res = Solve(L, mid - 1, x, y);
        res.first = res.first + P[mid][__lg(R - mid + 1)];
        return res;
    }
    if ( x >= mid )
    {
        res = Solve(mid + 1, R, x, y);
        res.first = P[L][__lg(mid - L + 1)] + res.first;
        return res;
    }

    pair <Data, int> resL = Solve(L, mid - 1, x, y), resR = Solve(mid + 1, R, x, y);
    resL.first = resL.first + P[mid][__lg(R - mid + 1)];
    resR.first = P[L][__lg(mid - L + 1)] + resR.first;

    res.second = resL.second + resR.second;

    res.first.f[0] = (1LL * resL.first.f[0] * resL.second + 1LL * resR.first.f[0] * resR.second) % mod * inv[res.second] % mod;
    res.first.f[1] = (1LL * resL.first.f[1] * resL.second + 1LL * resR.first.f[1] * resR.second) % mod * inv[res.second] % mod;
    res.first.f[2] = (1LL * resL.first.f[2] * resL.second + 1LL * resR.first.f[2] * resR.second) % mod * inv[res.second] % mod;
    return res;
}

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

    scanf("%d%d%s", &n, &m, s + 1);

    inv[1] = 1;
    for ( int i = 2; i <= max(3, n); i ++ )
        inv[i] = 1LL * (mod - mod / i) * inv[mod % i] % mod;

    for ( int i = 1; i <= n; i ++ )
    {
        P[i][0].Clear();
        if ( s[i] == 'R' )
            P[i][0].f[0] = 1;
        else if ( s[i] == 'S' )
            P[i][0].f[1] = 1;
        else
            P[i][0].f[2] = 1;
    }

    for ( int k = 1; (1 << k) <= n; k ++ )
        for ( int i = 1; i + (1 << k) - 1 <= n; i ++ )
            P[i][k] = P[i][k - 1] + P[i + (1 << (k - 1))][k - 1];
    
    for ( int i = 1; i <= n; i ++ )
    {
        Q[i][1].first.Clear();
        Q[i][1].second = 1;

        if ( s[i] == 'R' )
            Q[i][1].first.f[0] = 1;
        else if ( s[i] == 'S' )
            Q[i][1].first.f[1] = 1;
        else
            Q[i][1].first.f[2] = 1;
    }

    Data tmp1, tmp2;
    for ( int k = 2; (1 << k) - 1 <= n; k ++ )
    {
        for ( int i = 1; i + (1 << k) - 2 <= n; i ++ )
        {
            Q[i][k].second = Q[i][k - 1].second + Q[i + (1 << (k - 1))][k - 1].second;

            tmp1 = Q[i][k - 1].first + P[i + (1 << (k - 1)) - 1][k - 1];
            tmp2 = P[i][k - 1] + Q[i + (1 << (k - 1))][k - 1].first;

            for ( int j = 0; j < 3; j ++ )
                Q[i][k].first.f[j] = 1LL * (tmp1.f[j] + tmp2.f[j]) * inv[2] % mod;
        }
    }

    int L, R, x, y;
    while ( m -- )
    {
        scanf("%d%d%d%d", &L, &R, &x, &y);
        printf("%d\n", Solve(L, R, x, y).first.f[0]);
    }

    return 0;
}

T3 树状数组

预处理 \(f_{i, k, 0/1}\) 表示当前位于序列第 \(i\) 个位置，只考虑低 \(k\) 位，初始第 \(k\) 位为 \(0/1\) ，其余位为 \(0\) 时，第一个满足低 \(k\) 位均为 \(0\) 的时刻，通过判断 \(f_{i, k-1, 0/1}\) 很容易求解 \(f_{i, k, 0/1}\) 。

预处理 \(ans_i\) 表示初始值为 \(0\) ，经过 \([i, n]\) 的所有操作后得到的数，转移考虑找到最大的满足存在 \(f_{i, k, 0}\) 的 \(k\) ，容易发现高于 \(k\) 的二进制位不会收到 \(-1\) 操作的影响，直接异或求解即可，小于等于 \(k\) 的二进制位可以继承 \(f_{i, k, 0}\) 处的 \(ans\) 信息。

考虑查询，从低到高依次枚举 \(x\) 的二进制位，通过跳 \(f_{L, i, 0}\) 可以消去 \(x\) 的第 \(i\) 位，如果不存在对应的 \(f_{L, i, 0}\) ，说明第 \(i\) 位及以上不会受到 \(-1\) 操作的影响，此时可以直接得到答案。

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

const int max1 = 5e5;
const int inf = 0x3f3f3f3f;

int n, m, k, A, B;
int val[max1 + 5], sum[max1 + 5];

int f[max1 + 5][30][2], ans[max1 + 5], last;

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

    scanf("%d%d%d%d%d", &n, &m, &k, &A, &B);
    for ( int i = 1; i <= n; i ++ )
        scanf("%d", &val[i]);
    val[n + 1] = 0;
    
    sum[0] = 0;
    for ( int i = 1; i <= n + 1; i ++ )
    {
        sum[i] = sum[i - 1];
        if ( val[i] != -1 )
            sum[i] ^= val[i];
    }
    
    f[n + 1][0][0] = n + 2; f[n + 1][0][1] = inf;
    for ( int i = n; i >= 1; i -- )
    {
        if ( val[i] == -1 )
        {
            f[i][0][0] = i + 1;
            f[i][0][1] = i + 1;
        }
        else
        {
            if ( !(val[i] & 1) )
            {
                f[i][0][0] = i + 1;
                f[i][0][1] = f[i + 1][0][1];
            }
            else
            {
                f[i][0][0] = f[i + 1][0][1];
                f[i][0][1] = i + 1;
            }
        }
    }

    for ( int u = 1; u <= k - 1; u ++ )
    {
        f[n + 1][u][0] = n + 2; f[n + 1][u][1] = inf;

        for ( int i = n; i >= 1; i -- )
        {
            if ( val[i] == -1 )
            {
                f[i][u][0] = i + 1;
                f[i][u][1] = i + 1;
            }
            else
            {
                f[i][u][0] = f[i][u][1] = inf;

                int j = f[i][u - 1][0];

                if ( j != inf )
                {
                    if ( !(((sum[i - 1] ^ sum[j - 1]) >> u) & 1) )
                        f[i][u][0] = j;
                    else
                        f[i][u][0] = f[j][u][1];
                }
                
                j = f[i][u - 1][0];

                if ( j != inf )
                {
                    if ( !(((sum[i - 1] ^ sum[j - 1]) >> u) & 1) )
                        f[i][u][1] = f[j][u][1];
                    else
                        f[i][u][1] = j;
                }
            }
        }
    }

    ans[n + 1] = 0;
    for ( int i = n; i >= 1; i -- )
    {
        int u = -1;
        for ( int j = k - 1; j >= 0; j -- )
            if ( f[i][j][0] != inf )
                { u = j; break; }

        if ( u == -1 )
            ans[i] = sum[i - 1] ^ sum[n];
        else
            ans[i] = (((sum[i - 1] ^ sum[n]) >> (u + 1)) << (u + 1)) | (ans[f[i][u][0]] & ((1 << (u + 1)) - 1));
    }

    int L, x;
    while ( m -- )
    {
        scanf("%d%d", &L, &x);

        L = L ^ ((1LL * A * last + B) % n);
        x = x ^ ((1LL * A * last + B) % (1 << k));

        for ( int i = 0; i <= k - 1; i ++ )
        {
            if ( (x >> i) & 1 )
            {
                if ( f[L][i][1] == inf )
                {
                    last = (x ^ (((sum[L - 1] ^ sum[n]) >> i) << i)) | (ans[L] & ((1 << i) - 1));
                    break;
                }

                x ^= ((sum[f[L][i][1] - 1] ^ sum[L - 1]) >> (i + 1)) << (i + 1);
                x ^= 1 << i;
                L = f[L][i][1];
            }
        }

        if ( !x )
            last = ans[L];
        
        printf("%d\n", last);
    }

    return 0;
}

标签：int,res,sum,国赛,2023,first,36.1,inv,mod
From： https://www.cnblogs.com/KafuuChinocpp/p/17554763.html

相关文章

  • C/C++学生宿舍管理系统[2023-07-14]
    C/C++学生宿舍管理系统[2023-07-14]课程名称：程序设计实践专业班级：学生姓名：学号：任课教师：张闻强学期：2022-2023学年第2学期课程报告任务书题目 学生宿舍管理系统主要内容 用C语言开发一个简单的学生宿舍管理系统。实现宿舍......
  • SMU Summer 2023 Contest Round 3
    A.CurriculumVitae题意：给出一串01序列，可以删除任意个元素，使得1后面没有0思路：枚举01分界点，使得统计前面0的个数和后面1的个数，取最大值。点击查看代码#include<bits/stdc++.h>usingnamespacestd;inta[110];intmain(){ios::sync_with_stdio(0),cin.tie(0),co......
  • 每日总结2023年7月14日
    今日学习：完全图的概念，有向完全图和无向完全图。邻接矩阵的概念，邻接矩阵怎么画。邻接表怎么存储图的信息；图的遍历：深度优先、广度优先；拓扑排序：把有向边表示活动开始的先后关系。这种有向图称为用顶点表示活动网咯，成为AOE网络；图的最小生成树（普利姆算法Prime）；明天的计划：把图和基础算法......
  • 【考后总结】7 月多校国赛模拟赛 3
    7.14冲刺国赛模拟36T1染色题关键性质是奇数偶数位上可以放置的只有两种，若\(i\)和\(i-2\)选的颜色不同，那么在\(i\)位置放一个球，\([l,r]\)的限制等价于\([l+2,r]\)中奇数位和偶数位不同时有球。设\(f_i\)为\(i\)放置一个球的合法方案数，这样直接枚举上一个球所在......
  • 2023年iOS App Store上架流程详解（上）
    ​ 很多开发者在开发完iOSAPP、进行内测后，下一步就面临上架AppStore，不过也有很多同学对APP上架AppStore的流程不太了解，下面我们来说一下iOSAPP上架AppStore的具体流程，如有未涉及到的部分，大家可以及时咨询，共同探讨。内容：在完成iOSAPP开发和内部测试后，下一个步骤就是将应用......
  • 冲刺国赛模拟 36
    感觉思想都不难，但是场上不是想不出来就是写不动，见了鬼了。染色题考虑一个转化：对于奇数位置，在\(a_i\neqa_{i+2}\)的地方放一个红球，对于偶数位置在同样的地方放个蓝球。这样每个区间的限制变成\([l,r-2]\)不能同时有红蓝球，转移前缀和优化一下即可。#include<iostream>#inc......
  • 行业追踪，2023-07-14，汽车零部件在反弹时已清仓，耐心等待第二波买点重现
    自动复盘2023-07-14凡所有相，皆是虚妄。若见诸相非相，即见如来。k线图是最好的老师，每天持续发布板块的rps排名，追踪板块，板块来开仓，板块去清仓，丢弃自以为是的想法，板块去留让市场来告诉你工--号:醉卧梦星河欧奈尔行业RPS排名天天更新追踪主力行业......
  • 20230714练习总结
    LOJ3686/JOISC2022DAY1京都观光考虑从\((x1,y1)\)只转一次弯到\((x2,y2)\)。先向南走当且仅当：\[\boxed{\frac{a_{x1}-a_{x2}}{x1-x2}<\frac{b_{y1}-b_{y2}}{y1-y2}}\]很容易想到斜率相关。但是如果只是对比两行，因为有列的条件参与，无法判断某一行是否一定不会被走过，于是......
  • 2023年6月工作资料
    DCMM数据管理能力步骤https://mp.weixin.qq.com/s/EUtjBofyyYQ3GkD56WIPIA多层网关已成过去，网关多合一成潮流，网关改造正当时｜Higress1.0正式发布https://mp.weixin.qq.com/s/MjDBpn0k2FsGm9-nMol3Zwskywalking支持的采集指标及告警设置http://1json.com/smonitor/smonitor-s......
  • 助创智水未来，宏电亮相2023深圳国际水务科技博览会
    2023年7月11-13日，2023深圳国际水务科技博览会在深圳会展中心盛大举办。展会以“科技创新，助力水利高质量发展”为主题，旨在集中展示我国水利水务行业最新科技产品与技术，推动新科技与水利水务的深度融合，此次展会吸引了200+行业优秀企业参展。作为国内智慧水利水务专家型企业，宏电股份受......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99