『模拟赛』多校A层冲刺NOIP2024模拟赛09（更新 T4）

news/2024/10/20 16:02:36
Rank

还行

image

A. 排列最小生成树 (pmst)

签，有点可惜。

考虑连 \(i\) 与 \(i+1\) 时，所有边边权都是小于 \(n\) 的，因此我们只考虑边权小于 \(n\) 的边即可。因为边权为 \(|p_i-p_j|\times|i-j|\)，所以只考虑 \(|p_i-p_j|\lt \sqrt{n}\) 和 \(|i-j|\lt \sqrt{n}\) 的情况，每个点只用连 \(\sqrt{n}\) 条边，复杂度为 \(\mathcal{O(n\sqrt{n}\log n)}\)。桶记录每一条边可以优化掉排序，并查集按秩合并优化，然后就过了。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define P_B(x) push_back(x)
#define M_P(a, b) make_pair(a, b)
#define fi first
#define se second
const int Ratio = 0;
const int N = 5e4 + 5;
int n, cnt;
int a[N], fx[N], p[N], siz[N];
ll ans;
vector<pii> e[N];
namespace Wisadel
{inline int Wfind(int x){if(x == fx[x]) return x;return fx[x] = Wfind(fx[x]);}short main(){freopen("pmst.in", "r", stdin) , freopen("pmst.out", "w", stdout);n = qr;fo(i, 1, n) a[i] = qr, fx[i] = i, p[a[i]] = i, siz[i] = 1;for(int i = 1; i * i <= n; i++) fo(j, 1, n - i){int zc = 1ll * abs(a[j + i] - a[j]) * i;if(zc < n) e[zc].P_B(M_P(j, j + i));}for(int i = 1; i * i <= n; i++) fo(j, 1, n - i){int zc = 1ll * abs(p[j] - p[j + i]) * i, zd = 1ll * abs(p[j] - p[j + i]);if(1ll * zd * zd > 1ll * n && zc < n) e[zc].P_B(M_P(p[j], p[j + i]));}fo(i, 1, n) if(e[i].size()){for(pii j : e[i]){int _ = Wfind(j.fi), __ = Wfind(j.se);if(_ != __){if(siz[_] >= siz[__]){siz[_] += siz[__];fx[__] = _;}else{siz[__] += siz[_];fx[_] = __;}ans += i;}}}printf("%lld\n", ans);return Ratio;}
}
signed main(){return Wisadel::main();}

B. 卡牌游戏 (cardgame)

真正的签，不知道跟 T2 换位置有什么深意。

发现卡牌数量互质情况下每一对牌都会 pk 一次，当不互质时，会重复 \(gcd(n,m)\) 次完全一样的对局，此时对于一张牌显然不会与其余所有牌 pk，手模发现它只会和从它开始与它间隔 \(gcd(n,m) - 1\) 个的牌 pk，然后 \(\mathcal{O(n)}\) 跑一遍就做完了。

为了方便，我分成了 \(n\le m\) 和 \(n\gt m\) 两种情况做。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define M_P(a, b) make_pair(a, b)
#define fi first
#define se second
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 1e5 + 5, M = 5e5;
int n, m;
int a[N], b[N];
ll win, lose, ping;
vector<int> sum[N];
namespace Wisadel
{short main(){freopen("cardgame.in", "r", stdin) , freopen("cardgame.out", "w", stdout);n = qr, m = qr;fo(i, 1, n) a[i] = qr;fo(i, 1, m) b[i] = qr;int gcd = __gcd(n, m);if(n <= m){fo(len, 1, gcd){for(int i = len; i <= m; i += gcd)sum[len].P_B(b[i]);sort(sum[len].begin(), sum[len].end());}fo(i, 1, n){int zu = i % gcd; if(zu == 0) zu = gcd;int zc = lower_bound(sum[zu].begin(), sum[zu].end(), a[i]) - sum[zu].begin();zc++;win += 1ll * (zc - 1);int zd = upper_bound(sum[zu].begin(), sum[zu].end(), a[i]) - sum[zu].begin();zd++;ping += 1ll * (zd - zc);lose += 1ll * (m / gcd - zd + 1);}win *= gcd, ping *= gcd, lose *= gcd;}else{fo(len, 1, gcd){for(int i = len; i <= n; i += gcd)sum[len].P_B(a[i]);sort(sum[len].begin(), sum[len].end());}fo(i, 1, m){int zu = i % gcd; if(zu == 0) zu = gcd;int zc = lower_bound(sum[zu].begin(), sum[zu].end(), b[i]) - sum[zu].begin();zc++;lose += 1ll * (zc - 1);int zd = upper_bound(sum[zu].begin(), sum[zu].end(), b[i]) - sum[zu].begin();zd++;ping += 1ll * (zd - zc);win += 1ll * (n / gcd - zd + 1);}win *= gcd, ping *= gcd, lose *= gcd;}printf("%lld\n%lld\n%lld\n", win, lose, ping);return Ratio;}
}
signed main(){return Wisadel::main();}

C. 比特跳跃 (jump)

又一道魔改最短路。

  • \(s=1\) 时，发现除了最大点为 \(11\cdots 1_{(2)}\) 之外的情况，都能找到一个点与一个数的位与值为 0，所以特判 \(n\) 即可。

  • \(s=2\) 时，发现对三点一定有 \(a\oplus b+b\oplus c=a\oplus c\)，因此我们可以省掉 \(a\rightarrow c\) 这条边，即每个点只与与其一位不一样的点连边即可，每个点只有 \(\log n\) 条。

  • \(s=3\) 时，发现 \((a|b) + (b|c) \ge (a|c)\)。对于点 \(i\) 边权最少是 \(i\)。我们考虑给每个点多映射一个虚点，点到虚点的边权为 \(k\times i\)，虚点到实点边权为 \(0\)，然后在虚点上连边，同样只与与其一位不一样的点连边，若该点该位为 1 那么没有额外边权，否则边权为 \(k\times 2^i\) （\(i\) 为位数）。这样连只多了 \(n\times(2+\log n)\) 条边，大概是最优的连法。

然后对 \(s\neq 1\) 的情况跑一遍 dijkstra 就做完了，是目前最优解。

对于 \(s=2\) 中的 \(a\oplus b+b\oplus c=a\oplus c\) 指任意三点存在这样的关系，是一种组合而不是排列。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define M_P(a, b) make_pair(a, b)
#define fi first
#define se second
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 2e5 + 5, M = 5e5;
int n, m, s, k;
int hh[N], to[N << 4], ne[N << 4], cnt;
ll dis[N], w[N << 4];
bool yz[N];
struct rmm
{ll dis; int u;bool operator < (const rmm &a) const {return a.dis < dis;}
};
namespace W
{void Wadd(int u, int v, ll val){to[++cnt] = v;w[cnt] = val;ne[cnt] = hh[u];hh[u] = cnt;}void Wdij(int x){priority_queue<rmm> q;memset(dis, 0x3f, sizeof dis);dis[x] = 0;q.push({0, x});while(q.size()){int u = q.top().u; q.pop();if(yz[u]) continue;yz[u] = 1;for(int i = hh[u]; i != -1; i = ne[i]){int v = to[i];if(dis[v] > dis[u] + w[i]){dis[v] = dis[u] + w[i];q.push({dis[v], v});}}}}
}
namespace W1
{short main(){fill(dis + 1, dis + 1 + n, 0);int zc = 1;while(zc <= n) zc *= 2;if(n == zc - 1){dis[n] = k;for(int i = hh[n]; i != -1; i = ne[i])dis[n] = min(dis[n], w[i]);}else dis[n] = 0;fo(i, 2, n) printf("%lld ", dis[i]); puts("");return Ratio;}
}
namespace W2
{short main(){fo(i, 0, n) fo(j, 0, 16){int v = i ^ (1 << j);ll val = 1ll * k * (1 << j);if(v <= n) W::Wadd(i, v, val);}W::Wdij(1);fo(i, 2, n) printf("%lld ", dis[i]); puts("");return Ratio;}
}
namespace W3
{short main(){fo(i, 0, n) {fo(j, 0, 16){int v = i ^ (1 << j);if(v <= n){ll val = ((i >> j) & 1) ? 0 : 1ll * k * (1 << j);W::Wadd(i + n + 1, v + n + 1, val);}}W::Wadd(i, i + n + 1, 1ll * k * i);W::Wadd(i + n + 1, i, 0);}W::Wdij(1);fo(i, 2, n) printf("%lld ", dis[i]); puts("");return Ratio;}
}
namespace Wisadel
{short main(){freopen("jump.in", "r", stdin) , freopen("jump.out", "w", stdout);n = qr, m = qr, s = qr, k = qr;memset(hh, -1, sizeof hh);fo(i, 1, m){int a = qr, b = qr, c = qr;W::Wadd(a, b, c), W::Wadd(b, a, c);}if(s == 1) return W1::main();if(s == 2) return W2::main();if(s == 3) return W3::main();return Ratio;}
}
signed main(){return Wisadel::main();}

D. 区间 (interval)

据说是线段树区间历史和板子。

Upd：更像是单调栈板子。

将询问按右端点升序离线，发现第一个条件相当于是 \(a_l\) 是 \(a_i(i\in[l,r-1])\) 的最大值，维护一个单调递减的单调栈，然后二分出满足条件二的最大区间，区间中的点贡献加 1，然后删除栈内元素记得加 tag 表示该点不再有贡献，线段树维护即可。

点击查看代码 
#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define M_P(a, b) make_pair(a, b)
#define fi first
#define se second
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 1e6 + 5, M = 5e5;
int n, m, top;
int a[N], b[N];
struct rmm{int id, l, r;} q[N];
pii st[N];
int tag[N << 2];
ll sum[N << 2], lazy[N << 2], ans[N];
namespace Wisadel
{#define ls (rt << 1)#define rs (rt << 1 | 1)#define mid ((l + r) >> 1)void Wpushdown(int rt, int l, int r){sum[ls] += lazy[rt] * (mid - l + 1 - tag[ls]);sum[rs] += lazy[rt] * (r - mid - tag[rs]);lazy[ls] += lazy[rt], lazy[rs] += lazy[rt];lazy[rt] = 0;}void Wadd(int rt, int l, int r, int x, int y){if(x <= l && r <= y){sum[rt] += r - l + 1 - tag[rt], lazy[rt]++;return ;}if(lazy[rt]) Wpushdown(rt, l, r);if(x <= mid) Wadd(ls, l, mid, x, y);if(y > mid) Wadd(rs, mid + 1, r, x, y);sum[rt] = sum[ls] + sum[rs];}void Wdel(int rt, int l, int r, int x){if(l == r){tag[rt]++;return ;}if(lazy[rt]) Wpushdown(rt, l, r);if(x <= mid) Wdel(ls, l, mid, x);else Wdel(rs, mid + 1, r, x);tag[rt] = tag[ls] + tag[rs];}ll Wq(int rt, int l, int r, int x, int y){if(x <= l && r <= y) return sum[rt];if(lazy[rt]) Wpushdown(rt, l, r);ll res = 0;if(x <= mid) res += Wq(ls, l, mid, x, y);if(y > mid) res += Wq(rs, mid + 1, r, x, y);return res;}short main(){freopen("interval.in", "r", stdin) , freopen("interval.out", "w", stdout);n = qr;fo(i, 1, n) a[i] = qr;fo(i, 2, n) b[i] = qr;m = qr;fo(i, 1, m) q[i].l = qr, q[i].r = qr, q[i].id = i;sort(q + 1, q + 1 + m, [](rmm &A, rmm &B){return A.r < B.r;});int j = 1;fo(i, 1, n){int l = 1, r = top, zc = 0;while(l <= r)if(st[mid].se < b[i]) zc = mid, r = mid - 1;else l = mid + 1;if(zc) Wadd(1, 1, n, st[zc].fi, i - 1);while(j <= m && q[j].r == i) ans[q[j].id] = Wq(1, 1, n, q[j].l, i), j++;while(top && st[top].se <= a[i]) Wdel(1, 1, n, st[top].fi), top--;st[++top] = M_P(i, a[i]);}fo(i, 1, m) printf("%lld\n", ans[i]);return Ratio;}
}
signed main(){return Wisadel::main();}

末

又双叒叕回去整改了，打的不烂。只是 T3 好多性质没切，有点恼。

赛后一分钟得知 T1 建 110 条边就过了，大样例需要建 99 条，本地跑 0.95s 多，念在 OJ 速度不如本地，只建了 100 条。

下午信友队晚上 STAOI，所以现在才发。

Upd：这两场打的都还行。

尝试着跳过今天，使得 CSP 赶在我状态好的时候。

下午改 T4，改信友队题。

完结撒花~

现找的。

image

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.ryyt.cn/news/73848.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈，一经查实，立即删除！

相关文章

云原生架构视图

云原生架构视图

关于云原生的概念，业内有没有统一的定义，比较主流的还是CNCF(Cloud Native Computing Foundation，云原生计算基金会)对云原生的定义。原文如下： Cloud native technologies empower organizations to build and run scalable applications in public, private, and hybrid …
阅读更多...
2024-2025-1 20241328 《计算机基础与程序设计》第四周学习总结

2024-2025-1 20241328 《计算机基础与程序设计》第四周学习总结

学期（如2024-2025-1） 学号20241428《计算机基础与程序设计》第4周学习总结 作业信息这个作业属于哪个课程 <班级的链接>（如2024-2025-1-计算机基础与程序设计）这个作业要求在哪里 <作业要求的链接>(如2024-2025-1计算机基础与程序设计第一周作业)这个作业的目标…
阅读更多...
dynamics 365 op需要如何配置权限，才可以导入数据

dynamics 365 op需要如何配置权限，才可以导入数据

1、dynamics 365 op已经给了导入权限，且有记录的创建权限，但是一直没有导入按钮。2、后来发现当前人必须又导入数据的【删除】权限，才能有导入按钮。 记得收藏并关注，掌握更多相关知识！！！
阅读更多...
高等数学 7.3 齐次方程

高等数学 7.3 齐次方程

目录一、齐次方程*二、可化为齐次的方程 一、齐次方程 如果一阶微分方程可化成 \[\cfrac{\mathrm{d}y}{\mathrm{d}x} = \varphi \left( \cfrac{y}{x} \right) \tag{1} \]的形式，那么就称这方程为齐次方程。 在齐次方程 \[\cfrac{\mathrm{d}y}{\mathrm{d}x} = \varphi \left( \…
阅读更多...
2024-2025-1 20231309《计算机基础与程序设计》第三周助教总结

2024-2025-1 20231309《计算机基础与程序设计》第三周助教总结

课程答疑 最近同学们的提问大多都是与虚拟机、Linux命令有关，往往是在具体操作上出现了未曾意料的报错。 而出现此类问题的主要原因包括：操作不规范，如Linux命令输入不准确等解决方案：出现报错后首先检查自己输入的命令是否准确无误，例如是否少空格少参数等，再看是否有缺…
阅读更多...
20222319 2024-2025-1 《网络与系统攻防技术》实验二实验报告

20222319 2024-2025-1 《网络与系统攻防技术》实验二实验报告

1.实验内容 本周继续课堂学习了缓冲区溢出的相关知识，面向本次实验，主要学习了后门程序的生成方法，用ncat、socat实现两台计算机间互传文件的方法，体会了通过msf工具与执行好的后门程序实现对被攻击计算机的监听过程。 1.1实验内容目录 (1)使用netcat获取主机操作Shell，cr…
阅读更多...
PbootCMS的数据库是哪个文件

PbootCMS的数据库是哪个文件

PbootCMS 支持多种数据库，包括 MySQL 和 SQLite。你可以通过查看 config/database.php 文件来确定当前网站使用的数据库类型。 步骤打开 config/database.php 文件：使用文本编辑器或 IDE 打开 config/database.php 文件。查看 type 参数：在文件中找到 type 参数，该参数指定…
阅读更多...
pbootcms设置的会话目录创建失败！runtime/session/无法写入的解决方案

pbootcms设置的会话目录创建失败！runtime/session/无法写入的解决方案

当用户在安装PBootCMS模板时遇到报错信息：“pbootcms设置的会话目录创建失败！网站目录/runtime/session/无法接入”，可以尝试以下两种解决方案： 解决方案一：检查网站目录权限登录服务器：通过SSH登录到你的服务器。更改目录权限：使用 chmod 命令更改 runtime/ 目录及其子…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023