『模拟赛』CSP-S模拟6

news/2024/9/28 17:42:06
Rank

一般

恼了怎么又狠狠挂分啊啊啊啊

image

A. 一般图最小匹配

签。（这么多天终于签上了是吧）

结论是，跟图完全没关系。题意转换完就是从 \(n\) 个数中选出 \(m\) 对差的绝对值之和最小的数。显然我们选的每一对数都应该是这 \(n\) 个数中相邻的一组，sort 一下，设 \(f_{i,j,k}\) 表示到第 \(i\) 个点选了 \(j\) 对有/没有选这个数的最小值，转移方程如下：

\[f_{i,j,0}=min(f_{i-1,j,0},f_{i-1,j,1}) \]

\[f_{i,j,1}=f_{i-1,j-1,0}+a_i-a_{i-1} \]

最终结果即为 \(f_{n,m,0}\) 与 \(f_{n,m,1}\) 中的较小值。

因为赛时觉得可能会爆 int（但事实上容易证明并不会），开 long long 的话 \(5000\times 5000\) 又有可能炸，于是用了滚动数组优化。

点击查看代码 
#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 fi first
#define se second
const int Ratio = 0;
const int N = 5000 + 5;
const int mod = 1e9 + 7;
int n, m;
int a[N];
ll f[2][2501][2];// n; m; choose or not
namespace Wisadel
{short main(){freopen("match.in", "r", stdin) , freopen("match.out", "w", stdout);n = qr, m = qr;fo(i, 1, n) a[i] = qr;sort(a + 1, a + 1 + n);memset(f, 0x3f, sizeof f);f[1][0][0] = 0;fo(i, 2, n){int zc = i & 1, cz = !zc;f[zc][0][0] = f[cz][0][0];fo(j, 1, m){f[zc][j][0] = min(f[cz][j][0], f[cz][j][1]);f[zc][j][1] = f[cz][j - 1][0] + a[i] - a[i - 1];}}printf("%lld\n", min(f[n & 1][m][1], f[n & 1][m][0]));return Ratio;}
}
int main(){return Wisadel::main();}

B. 重定向

签。

很水的贪心，从前往后扫只要有能够删一个数使得字典序变小的方案就直接换就行，具体如下：

首先扫出 \(1\) ~ \(n\) 中未出现的数，然后动态维护当前位可出现的数，即到这一位未出现过的数。由于只能删一个数，所以只要遇到能比当前优的操作就记下然后结束遍历。

  • 当 \(a_i \neq 0\) 时

  • 若 \(a_{i+1}=0\)，首先考虑整个序列未出现的数中最小的是否比 \(a_i\) 大，若是则直接删掉 \(a_i\) 并令 \(a_{i+1}\) 为那个未出现的最小数；若不是则再考虑到当前位未出现的最小数是否比整个序列未出现的最小数小，若是则我们选择删掉到当前位未出现的最小数在原序列中对应的数，并令 \(a_{i+1}\) 为这个值；若仍不满足，则说明此位无论如何操作都没有能使该序列字典序变小，继续循环即可。

  • 若 \(a_{i+1}\neq 0\)，则只用判断是否有 \(a_{i}\gt a_{i+1}\)，若是则删掉 \(a_i\) 即可。

  • 当 \(a_i=0\) 时

很简单，判断是否有到当前位未出现的最小数是否比整个序列未出现的最小数小，若是则同上，不是则直接给其赋值整个序列未出现的最小数即可。

有点复杂可能了，赛时有个地方不小心打炸了导致 VSCode 直接罢工了，怎么编译都是“已放弃运行”，auto save 也失灵了，导致有几个细节改了没保存，狠狠挂了 45pts。

点击查看代码 
#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 fi first
#define se second
const int Ratio = 0;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
int n, k, kb;
int a[N], yz[N];
set<int> st;
priority_queue<int, vector<int>, greater<int> > q;
namespace Wisadel
{short main(){freopen("repeat.in", "r", stdin) , freopen("repeat.out", "w", stdout);int T = qr;while(T--){n = qr; k = 0; st.clear();fo(i, 1, n) yz[i] = 0;bool kong = 0;fo(i, 1, n) a[i] = qr, yz[a[i]] = 1, st.insert(i);while(q.size()) q.pop();fo(i, 1, n) if(!yz[i]) kong = 1, q.push(i);if(kong){// 有空位fo(i, 1, n - 1){if(a[i]) st.erase(a[i]);if(a[i] != 0 && a[i + 1] == 0){if(q.top() < a[i]){k = i;a[i + 1] = q.top();q.pop();q.push(a[i]);break;}else if(*st.begin() < q.top()){kb = *st.begin();k = -1;a[i + 1] = -1;break;}}if(a[i] != 0 && a[i + 1] != 0 && a[i] > a[i + 1]){k = i;q.push(a[i]);break;}if(a[i] == 0){if(*st.begin() < q.top()){kb = *st.begin();k = -1;a[i] = -1;break;}else{a[i] = q.top();st.erase(a[i]);q.pop();}}}if(k == 0) k = n;fo(i, 1, n){if((k == -1 && kb == a[i]) || k == i) continue;if(a[i] == 0) a[i] = q.top(), yz[q.top()] = 1, q.pop();if(a[i] == -1) a[i] = kb;printf("%d ", a[i]);}}else{fo(i, 1, n) if(a[i] > a[i + 1]){k = i; break;}if(k == 0) k = n;fo(i, 1, n){if(k == i) continue;printf("%d ", a[i]);}}printf("\n");}return Ratio;}
}
int main(){return Wisadel::main();}

C. 斯坦纳树

虚树？

牛牛错误的情况挺简单的，就是一个非点集中点连了三个点集中点的情况，即：

image

首先认为边权不为 0，发现维护一个点数逐渐增加的这样的图并不好实现，于是考虑倒着做删点操作。当一个点被删掉时，我们称其为虚点。显然若虚点存在则答案为 0。一个显然的结论是：若一个点的边数小于 3，则它不会对答案产生贡献，可以直接删掉，证明就是推出上图的步骤。一点被删掉后需要将与它相连的点两两连边保证树的形态，最后再判断每个子节点是否符合删点的要求再做一遍即可。由于每个点只用删一次，时间复杂度是 \(\mathcal{O(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 fi first
#define se second
const int Ratio = 0;
const int N = 3e5 + 5;
const int mod = 1e9 + 7;
int n, ecnt, sum;
int a[N], fa[N], cnt[N], son[3];
int ans[N];
struct edge{int u, v;} e[N];
set<int> st[N];
namespace Wisadel
{int Wfind(int x){if(x == fa[x]) return x;return fa[x] = Wfind(fa[x]);}void Wdel(int u){if(st[u].size() <= 2 && !cnt[u]){sum--; int num = 0;for(int v : st[u]) son[++num] = v;st[u].clear();fo(i, 1, num){fo(j, 1, num) if(i != j) st[son[i]].insert(son[j]);st[son[i]].erase(u);}fo(i, 1, num) Wdel(son[i]);}}short main(){freopen("tree.in", "r", stdin) , freopen("tree.out", "w", stdout);n = qr;fo(i, 1, n) fa[i] = i;fo(i, 1, n - 1){int a = qr, b = qr, c = qr;if(c == 0){int _ = Wfind(a), __ = Wfind(b);if(_ > __) swap(_, __);fa[__] = _;}else e[++ecnt].u = a, e[ecnt].v = b;}fo(i, 1, n - 1) st[Wfind(e[i].u)].insert(Wfind(e[i].v)), st[fa[e[i].v]].insert(fa[e[i].u]);fo(i, 1, n) a[i] = qr, a[i] = Wfind(a[i]), cnt[a[i]]++;fu(i, n, 1){ans[i] = !sum, cnt[a[i]]--;if(!cnt[a[i]]) sum++, Wdel(a[i]);}fo(i, 1, n) printf("%d", ans[i]);return Ratio;}
}
int main(){return Wisadel::main();}

D. 直径

神秘 \(\mathcal{O(n^6\log n)}\) 超级 dp 题。

末

起码签上 T1 了。

不过 VSCode 爆炸导致挂分还是太戏剧了，也算是经验++吧，虽然不挂 Rank5，但没准就为将来正式比赛攒 rp 了呢？

明天没模拟赛啊，感觉又要状态--了，晚上开 ABC 吧，争取AK（赛后也算）。

完结撒花~

image

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

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

相关文章

ESXi 5.5 系统克隆到SD卡或USB磁盘上

ESXi 5.5 系统克隆到SD卡或USB磁盘上

对于如何将安装在本地磁盘上的ESXi系统克隆到SD卡或USB磁盘上，以便快速实现ESXi主机的VSAN-Ready状态。正好猫猫也有点兴趣，所以，就研究了下这个方式，大致的工作思路就是“先通过dd命令将ESXi系统克隆到VMFS Datastore成为一个文件，然后再从文件弄到SD卡或USB磁盘即可”。…
阅读更多...
昆明理工大学计算机考研专业课答题卡

昆明理工大学计算机考研专业课答题卡

--昆工昆明理工大学、计算机技术、人工智能、软件工程、网络空间安全、891计算机专业核心综合、计算机系统结构、计算机软件与理论、网络与信息安全、计算机应用技术、综合程序设计
阅读更多...
BUUCTF（PWN）- rip

BUUCTF（PWN）- rip

BUUCTF（PWN）- rip 打开题目得到靶机信息: node5.buuoj.cn:29045 和附件 pwn1查看文件信息为 64-bit ，用 ida 打开附件 首先 shift+f12 查找字符串，能看见 system、/bin/sh 字样，点击 please input 或者 ok,bye!!! 跳转直接进入 main 函数查看gets 并没有限制输入，gets 函…
阅读更多...
Springboot实战——黑马点评之秒杀优化

Springboot实战——黑马点评之秒杀优化

Springboot实战——黑马点评之 秒杀优化 1 秒杀优化 先来复习以下，秒杀优惠券业务的现有实现逻辑：以上流程图中的操作串行执行，效率极低。 其中 判断秒杀库存 以及 校验一人一单 属于对数据库的读取，耗时较少；扣减库存 以及 创建订单 属于对数据库的写操作，耗时相对较久。…
阅读更多...
PARTVI-Oracle数据库管理与开发-数据库管理员的概念

PARTVI-Oracle数据库管理与开发-数据库管理员的概念

18. 数据库管理员的概念 18.1. 数据库管理员的职责 数据库管理员（DBA）的主要责任是使企业数据对其用户可用。DBA必须与开发人员紧密合作，确保他们的应用程序有效地使用数据库，并与系统管理员合作，确保物理资源充足且使用高效。Oracle DBA负责了解Oracle数据库架构以及数据…
阅读更多...
实验作业1

实验作业1

实验一 任务一 源代码#include<stdio.h> int main() {printf(" o \n");printf("<H>\n");printf("I I\n");printf(" o \n");printf("<H>\n");printf("I I\n");return 0; }效果 源代码#incl…
阅读更多...
01. 感知层环境安装

01. 感知层环境安装

1. 软件以及驱动的安装安装ZigBee无线网络节点开发平台 IAR Embedded Workbench（简称EW） 安装串口驱动(CH340芯片)。点击安装64位的。后续就可以使用串口对开发板进行调试。 仿真器驱动程序(用来烧录代码)的安装。 安装串口工具(XCOM)。2. IAR创建工程打开安装的IAR软件，点击…
阅读更多...
黑马PM-内容项目-需求分析

黑马PM-内容项目-需求分析

需求分析的定义需求分析的时机需求分析的步骤
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 尧图建网站 广利置业