首页 > 其他分享 >『模拟赛』多校A层冲刺NOIP2024模拟赛20

『模拟赛』多校A层冲刺NOIP2024模拟赛20

时间:2024-11-09 21:31:04浏览次数:5  
标签:ch 20 int son 模拟 st define NOIP2024 mod

Rank

mission failed

image

A. 星际联邦

由于急着想切题,上来没细看就打了个树状数组上去,果然寄了,然后又各种方式优化,最终还是寄了,只有 50pts。

正解是学最小生成树时直接跳过的 prim 和菠萝,但是偏不这么做,而是找性质得出严格 \(\mathcal{O(n)}\) 的做法。image

首先比较平凡发现一个点的最优连边方式一定是与左边的最大值或右边的最小值连边。那么我们可以维护一个单调递增的队列,实质上队列第 \(i\) 个元素表示 \([1,i]\) 的最大值的位置。那么倒序遍历,每次考虑当前最大值与下一个最大值之间的整个区间。我们将当前最大值向下个最大值之后的最小值连边,区间内的点在向最大值与向其后面最小值连边中取优。复杂度 \(\mathcal{O(n)}\)。

考虑这样做的正确性,从连通性和最优性分析。

连通性:从最后一段区间考虑,最右边的点一定和最大值连边,之后的点无论和最大值还是它后面的点连边都会直接并入这个连通块;对于之后的区间,由于后面所有点都已存在于一个连通块内,且已经现将最大值并入该连通块,因此无论向哪里连边都会被并入该连通块。

最优性:对于区间内的点来说很显然,主要考虑最大值的连边方式;若最大值不连后面的点而是区间内的点,由于要求连通故该区间内点一定会连向后面的点,且二者所连后面的点是相同的,都是最小值;那么由于边权为 \(u_j-u_i\),而 \(u_{max}\gt u_{i}\),故后面的点向最大值连边是更优的,所以假设不成立,最优性得证。

点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
    char ch = getchar_unlocked(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar_unlocked()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar_unlocked()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 3e5 + 5;
const int mod = 1e9 + 7;
int n;
int a[N], mx[N];
ll ans;
namespace Wisadel
{
    short main()
    {
        freopen("star.in", "r", stdin), freopen("star.out", "w", stdout);
        n = qr;
        fo(i, 1, n) a[i] = qr;
        mx[1] = 1;
        fo(i, 2, n) mx[i] = a[i] > a[mx[i - 1]] ? i : mx[i - 1];
        int mn = 1e9, now = n;
        while(now)
        {
            int to = mx[now];
            if(now != n) ans += mn - a[to];
            fu(i, now, to + 1) ans += min(mn - a[i], a[i] - a[to]), mn = min(mn, a[i]);
            mn = min(mn, a[to]), now = to - 1;
        }
        printf("%lld\n", ans);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}
// 佳墙坂诶迦币等渔塞

B. 和平精英

一眼看出数据结构但不知道怎么写的题。

一个结论:设合法分配方案的影响力结果二进制下 1 的个数为 \(x\),则分配到与组的数二进制下 1 的个数一定不小于 \(x\),分配到或组一定不大于 \(x\)。比较显然,手模即可。

那么我们可以每次询问以 \(\mathcal{O(\log V)}\) 的复杂度枚举这个个数,然后用上述结论辅助判断。

首先,若区间内没有个数为 \(x\) 的数很好办,直接比对即可。考虑若有怎么办,讨论其是否全部相等。容易得出若存在不相等的数则一定无法得到一个合法分配,因为或组一定会多出 1,而与组一定会少 1;若全相等那么讨论其分配情况然后比对即可。

维护这个东西用线段树很好实现,总复杂度 \(\mathcal{O(n\log^2n)}\),当然 st 表也行,需要用到什么优化。

点击查看代码
// ubsan: undefined
// accoders
#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
    char ch = getchar_unlocked(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar_unlocked()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar_unlocked()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int n, m;
int a[N], sum[31][N];
int qzh[31], hzy[31], sumnum[31];
struct rmm{int yu, huo; rmm(int a = (1ll << 31) - 1, int b = 0){yu = a, huo = b;}} zc[31];
namespace Wisadel
{
    bool Wck(int i, int l, int r)
    {
        if(qzh[i] == hzy[i] && zc[i].yu == zc[i].huo && sum[i][r] - sum[i][l - 1] > 1)
            return 1;
        if(sumnum[i] && sumnum[30] - sumnum[i] && qzh[i] == hzy[i + 1])
            return 1;
        return 0;
    }
    struct tree
    {
        rmm t[N << 2];
        #define ls (rt << 1)
        #define rs (rt << 1 | 1)
        #define mid ((l + r) >> 1)
        rmm Wmerge(rmm a, rmm b){return {a.yu & b.yu, a.huo | b.huo};}
        void Wupd(int rt, int l, int r, int x, int val)
        {
            if(l == r)
            {
                t[rt] = {val, val};
                return ;
            }
            if(x <= mid) Wupd(ls, l, mid, x, val);
            else Wupd(rs, mid + 1, r, x, val);
            t[rt] = Wmerge(t[ls], t[rs]);
        }
        rmm Wq(int rt, int l, int r, int x, int y)
        {
            if(x <= l && r <= y) return t[rt];
            rmm res = {(1ll << 31) - 1, 0};
            if(x <= mid) res = Wmerge(res, Wq(ls, l, mid, x, y));
            if(y > mid) res = Wmerge(res, Wq(rs, mid + 1, r, x, y));
            return res;
        }
    } t[31];
    short main()
    {
        freopen("peace.in", "r", stdin), freopen("peace.out", "w", stdout);
        n = qr, m = qr;
        fo(i, 1, n)
        {
            int x = qr;
            int num = __builtin_popcount(x);
            t[num].Wupd(1, 1, n, i, x);
            fo(j, 0, 30) sum[j][i] = sum[j][i - 1] + (j == num);
        }
        while(m--)
        {
            int l = qr, r = qr;
            fo(i, 0, 30) zc[i] = t[i].Wq(1, 1, n, l, r);
            qzh[0] = zc[0].huo;
            fo(i, 1, 30) qzh[i] = qzh[i - 1] | zc[i].huo;
            hzy[30] = zc[30].yu;
            fu(i, 29, 0) hzy[i] = hzy[i + 1] & zc[i].yu;
            sumnum[0] = sum[0][r] - sum[0][l - 1];
            fo(i, 1, 30) sumnum[i] = sumnum[i - 1] + sum[i][r] - sum[i][l - 1];
            bool ok = 0;
            fo(i, 0, 30) if(Wck(i, l, r)){ok = 1; break;}
            puts(ok ? "YES" : "NO");
        }
        return Ratio;
    }
}
signed main(){return Wisadel::main();}
// 佳墙坂诶迦币等渔塞

C. 摆烂合唱

如果想到表达式树就成签到了。

题比较良心,每个运算都加了括号,那么直接建出表达式树,然后 dp 求到每个节点为 1/0 的概率。发现只有运算为 &| 的时候存在 \(x\) 的值不影响答案的情况,考虑 dfs 时分讨,求出不影响答案的概率并赋到兄弟节点上,最后 dfs 一遍过程中统计答案输出即可。

细节是建树时左右子节点位置,和输出顺序有关,以及各种取模问题。复杂度 \(\mathcal{O(n)}\)。

点击查看代码
#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
    char ch = getchar_unlocked(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar_unlocked()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar_unlocked()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 3e5 + 5;
const int mod = 998244353;
int n, inv2, rot;
string s;
int pre[N], tot;
int son[N][2], fx[N];
ll f[N][2], g[N];
stack<int> st;
namespace Wisadel
{
    ll Wqp(ll x, int y)
    {
        ll res = 1;
        while(y)
        {
            if(y & 1) res = res * x % mod;
            x = x * x % mod;
            y >>= 1;
        }
        return res;
    }
    void Wdfs(int u, bool le)
    {
        if(son[u][0]) Wdfs(son[u][0], 0), Wdfs(son[u][1], 1);
        if(s[pre[u]] == 'x') f[u][0] = f[u][1] = inv2;
        else if(s[pre[u]] == '&') f[u][1] = f[son[u][0]][1] * f[son[u][1]][1] % mod, f[u][0] = (1 - f[u][1] + mod) % mod;
        else if(s[pre[u]] == '|') f[u][0] = f[son[u][0]][0] * f[son[u][1]][0] % mod, f[u][1] = (1 - f[u][0] + mod) % mod;
        else f[u][1] = (f[son[u][0]][0] * f[son[u][1]][1] % mod + f[son[u][0]][1] * f[son[u][1]][0] % mod) % mod, f[u][0] = (1 - f[u][1] + mod) % mod;
        if(s[pre[fx[u]]] == '&') g[son[fx[u]][le ^ 1]] = f[u][0];
        if(s[pre[fx[u]]] == '|') g[son[fx[u]][le ^ 1]] = f[u][1];
    }
    void Wq(int u, ll ans) // 能肆意换的概率
    {
        ans = (1 - ((1 - ans + mod) % mod) * ((1 - g[u] + mod) % mod)%mod + mod) % mod;
        if(son[u][0]) Wq(son[u][0], ans), Wq(son[u][1], ans);
        else printf("%lld\n", (1 - ans + mod) % mod);
    }
    short main()
    {
        // freopen(".in", "r", stdin), freopen(".out", "w", stdout);
        freopen("binary.in", "r", stdin), freopen("binary.out", "w", stdout);
        n = qr; cin >> s; int len = s.size(); s = " " + s;
        fo(i, 1, len)
            if(s[i] == '(') st.push(-1);
            else if(s[i] != ')') st.push(++tot), pre[tot] = i;
            else
            {
                int x2 = st.top(); st.pop();
                int suan = st.top(); st.pop();
                int x1 = st.top(); st.pop();
                fx[x1] = fx[x2] = suan;
                son[suan][0] = x1, son[suan][1] = x2;
                st.pop();
                st.push(suan);
            }
        rot = st.top();
        inv2 = Wqp(2, mod - 2);
        Wdfs(rot, 0);
        Wq(rot, 0);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}
// 佳墙坂诶迦币等渔塞

D. 对称旅行者

暴力挂了,不知道为什么。

好像也好改,不过来不及了,仙姑。

也是赤上史了。从整个机房几乎没什么动静就能得出来。

但还是好多不该犯的错,感觉 T1 结论应该是能想出来的,T2 也应该想到更优的暴力。

不过能自己改出来题是好的,可惜太慢没打上 abc。

生涯还能打几场 abc 呢?


完结撒花~

╮(╯▽╰)╭ 模拟赛打一场少一场了。

image

标签:ch,20,int,son,模拟,st,define,NOIP2024,mod
From: https://www.cnblogs.com/Ratio-Yinyue1007/p/18537331

相关文章

  • 2024-2025-1 20241319 《计算机基础与程序设计》第七周学习总结
    作业信息这个作业属于哪个课程2024-2025-1-计算机基础与程序设计这个作业要求在哪里https://www.cnblogs.com/rocedu/p/9577842.html#WEEK07这个作业的目标数组与链表基于数组和基于链表实现数据结构无序表与有序表树图子程序与参数作业正文https://www.c......
  • 2024-2025-1 20241307《计算机基础与程序设计》第七周学习总结
    作业信息这个作业属于哪个课程(2024-2025-1-计算机基础与程序设计)这个作业要求在哪里(2024-2025-1计算机基础与程序设计第七周作业)这个作业的目标作业正文(2024-2025-1学号20241307《计算机基础与程序设计》第七周学习总结)教材学习内容总结《计算机科学概......
  • 网鼎杯2024 MISC04
    网鼎杯2024MISC04新知识:peano曲线下载文件是一个看起来特别无序的图片应该是经过了某种算法,但是我并没有见过,所以是看了wp是一种图像加密算法,需要把这个红线还原重组成二维码,搜索一个是这个Peano曲线fromPILimportImagefromtqdmimporttqdmdefpeano(n):ifn==......
  • 多校A层冲刺NOIP2024模拟赛20
    多校A层冲刺NOIP2024模拟赛20\(T1\)A.星际联邦\(25pts\)部分分\(25pts\):暴力建边后跑\(Kruskal\)或\(Prim\)。点击查看代码structnode{ intfrom,to,w;};inta[300010];vector<node>e;structDSU{ intfa[300010]; voidinit(intn) { for(inti......
  • 笔趣阁纯净版V2024.10.13
    今天给大家推荐一款非常棒的免费小说阅读软件--笔趣阁纯净版版。不管你是想重温经典文学作品,还是想追读时下最火的小说,这款应用都能满足你的需求。对于小说和漫画爱好者来说,它是一个极佳的阅读工具,带你畅游在书籍的海洋中,享受阅读的乐趣。软件特色:1、界面设计非常简洁,没有......
  • 「NOIP2022」比赛
    洛谷。题目简述给定两个数列\(a,b\),有\(q\)次询问,每次询问\([L,R]\)的所有子区间\([l,r]\)的\(\max_{i=l}^ra_i\times\max_{i=l}^rb_i\)之和。其中,\(n,q\le2.5e5\)。分析这很像历史版本和,但是我们写过的只有一个数组\(a\)的。那么先从部分分开始。对于\(n,......
  • NOIP 模拟赛 Day 6
    T1每次赢的人放在最后,可以发现一轮过后相对位置不变,比赛模式图类似一个二叉树,每个人从最底层往上打,可以一层一层计算每个人打到这一层的概率,再往上的概率就是乘上另一个半场的每个人打到这一层的概率乘这个人赢过对方的概率的和,枚举\(x\)所在的每一个位置,复杂度是\(O(n^3)\),......
  • 2024最新网络安全专业高薪岗位,网络安全入门到精通,收藏这篇就够了
    2024年,随着人工智能、云安全、供应链威胁、SecOps和产品安全威胁日益凸显,五类“顶流”安全职位(人才)有望加入CISO的“50万年薪俱乐部”。在传统网络安全职位薪酬体系中,处于金字塔顶端的是CISO、网络安全总监、信息安全经理、高级软件安全工程师、IT安全架构师等。根据企业规模......
  • 2024-2025-1-《计算机基础与程序设计》20241313刘鸣宇
    作业信息这个作业属于哪个课程 <班级的链接>(如2024-2025-1-计算机基础与程序设计)这个作业要求在哪里 <作业要求的链接>(如2024-2025-1计算机基础与程序设计第一周作业)这个作业的目标 <写上具体方面>作业正文 ...本博客链接教材学习内容总结《计算机基础与科学概论》第八章......
  • 51c大模型~合集20
    我自己的原文哦~ https://blog.51cto.com/whaosoft/11634780#Transformer大模型尺寸变化大模型尺寸正在重走CNN的老路;马斯克:在特斯拉也是这样, Transformer大模型尺寸变化,正在重走CNN的老路! Transformer大模型尺寸变化,正在重走CNN的老路!看到大家都被LLaMA3.1吸引了注......