首页 > 其他分享 >9.13 模拟赛(炼石计划 11 月 04日 CSP-S 十连测 #7)

9.13 模拟赛(炼石计划 11 月 04日 CSP-S 十连测 #7)

时间:2024-09-13 20:05:22浏览次数:6  
标签:11 炼石 04 魔咒 感染 细胞 心目 游戏 病毒

炼石计划 11 月 04日 CSP-S 十连测 #7【补题】 - 比赛 - 梦熊联盟 (mna.wang)

复盘

基本上一眼秒了 T1,先写这题。在 8:30 写完了对拍。用了将近一个小时。然后放到桌面 2 就没管,一直拍到了比赛结束。

T2 什么牛魔题面???出题人学过语文吗???

T3 把题读懂了,但是一直不能正确模拟出样例 1,怀疑是题目读错了,先跳。

T4 是数据结构题。想冲正解没冲出来。感觉可以枚举 \(l1,r1\) 然后线段树维护最大子段和,复杂度 \(\mathcal O(n^2 \log n)\),能拿 \([50,60]\) 分。于是先写暴力。

写的中途意识到线段树是不必要的,维护两个 set 即可。很像 ODT 但不是 ODT。

调了一会 RE 样例全过,但是 \(5000\) 的极限数据跑了 \(4\) 秒,时限 \(3\) 秒。尝试卡常但卡不动。

尝试重新写线段树维护最大子段和,写一半放弃了,因为维护最大子段的左右端点太麻烦,而且不一定比 set 快。

写对拍,放桌面 2。做 T2 T3。

终于是在比赛结束前一个半小时读懂了题面,但一点思路没有。

\(n\le 5\) 的应该是爆搜,但是复杂度未知。实际上加上记忆化就能做到稳过的复杂度,但我忘了((((((

然后骗分,\(p = 1\) 输出 \(0\),\(p = 2\) 输出 \(1 \sim n\)。

T3 发现确实是我模样例错了,不是读错题了。稍微推了推发现正解不会一点。于是先写了 \(n \le 10\) 的搜索。

尝试思考链的特殊性质。设计了一个 DP,状态是正解,但是转移写挂了。虽然过了样例但是手造一组就挂了。比赛结束了没调出来。

预计:\(100+40+20+50=210\);实际:\(100+74+20+51=245\)。T2 骗分拿这么多真没想到。

一分没挂!赢赢赢!!!

补题:\(100+100+100+51\)。

总结

好的:

  • 没挂分。

菜的:

  • 不会 T2 黄题。
  • 读题耗时间太长。

知识点

  • T1:模拟。
  • T2:阅读理解,思维,构造。
  • T3:树上背包 DP。

题解

A. 矩阵最大值

首先处理修改之前的答案。

注意到一次修改 \((x, y)\)只会影响到 \(\mathcal O(1)\) 个位置的状态(状态指这个值是否既是当前行的最大值又是当前列的最大值)。这些位置分别是:

  • \((x, y)\);
  • \(x\) 所在行的最大值;
  • \(y\) 所在行的最大值。

因此你需要动态维护每行/每列的最大值的位置。这是极易的。

B. 病毒感染

为了凑字数把 题解:P9287 [ROI 2018] Viruses 复制过来。

注意到,这是一道假扮成 OI 题的语文阅读理解题。

题意

有 \(n\) 个细胞和 \(n\) 种病毒,编号均 \(1 \sim n\)。

每个时刻每个细胞都会感染恰好一个病毒。令当前细胞 \(i\) 中感染的病毒编号为 \(c_i\)。最开始第 \(i\) 个细胞感染的病毒是 \(i\),即 \(c_i = i\)。

在每个细胞心目中都有对每个病毒的能力的排名。即给定一个 \(n \times n\) 的矩阵 \(a\),其中 \(a_{i, j}\) 表示在第 \(i\) 个细胞心目中,病毒 \(j\) 是第几强的。例如若 \(a_{1,1}=2,a_{1,2}=1,a_{1,3}=3\) 则表示细胞 \(1\) 认为病毒 \(2\) 最强,病毒 \(1\) 其次,病毒 \(3\) 最菜。

细胞会互相攻击。当细胞 \(i\) 攻击细胞 \(j\) 时,如果 \(a_{j,c_i} > a_{j,c_j}\),则细胞 \(j\) 将会感染病毒 \(c_i\),即 \(c_j \gets c_i\)。即当细胞 \(j\) 认为 \(i\) 的病毒更强时,它会放弃自己现有的病毒,而感染更强的。

细胞们可以任意安排攻击顺序。当且仅当没有细胞可以被任意一名病毒感染时,游戏宣告结束。显然游戏的最终局面(\(c_1\dots c_n\))可能不唯一。

我们定义在某个游戏的最终局面里,一个病毒是「牛的」,这个病毒没有灭绝,即存在至少一个细胞感染了这个病毒。

你需要解决两个问题:

  • 求哪些病毒是「稳定的」。一个病毒是稳定的,当且仅当这个病毒在所有游戏的最终局面里都是牛的。
  • 求哪些病毒是「可行的」。一个病毒是稳定的,当且仅当这个病毒在至少一种游戏的最终局面里是牛的。

Part.1 「稳定的病毒」

考虑求解哪些病毒是「稳定的」。

我们断言病毒 \(i\) 是「稳定的」当且仅当 \(a_{i, 1} = i\),即细胞 \(i\) 认为病毒 \(i\) 是最强的。

我们考虑题目中描述的能够发生感染的条件:

当细胞 \(i\) 攻击细胞 \(j\) 时,……,当细胞 \(j\) 认为 \(i\) 的病毒更强时,它会放弃自己现有的病毒,而感染更强的。

我们知道细胞 \(i\) 最开始感染的是病毒 \(i\),所以细胞 \(i\) 最开始感染的就是它认为的最强的病毒。而接下来的感染过程如果能够发生,就代表感染源是一种(细胞 \(i\) 认为的)更强的病毒。显然这矛盾。

Part.2 「可行的病毒」

考虑求解哪些病毒是「可行的」。

首先以 \(\mathcal O(n)\) 的复杂度枚举 \(i\),表示我们要判断病毒 \(i\) 是否「可行」

根据题目描述,如果病毒 \(i\) 可行,那么当游戏结束时它一定存在于某个细胞内。不妨再以 \(\mathcal O(n)\) 的复杂度枚举 \(j\) 表示判断是否存在一种游戏的最终局面,使得细胞 \(j\) 感染了病毒 \(i\)。如果不存在这样的 \(j\) 则病毒 \(i\) 不是「可行的」。

游戏结束的条件是不存在任何一对细胞可以攻击。那么如果病毒 \(k\) 满足它在细胞 \(i\) 心中比病毒 \(j\) 要强(即 \(a_{i, k} < a_{i, j}\)),而且存在一个细胞 \(l\)(\(l \ne i\)) 感染了病毒 \(k\),那么当前游戏是不能结束的。因为细胞 \(l\) 还可以攻击细胞 \(j\)。

这给我们的启发是,只有在当前局面里,细胞 \(i\) 心目中比病毒 \(j\) 强的病毒都灭绝(即不存在任何一个细胞感染这个病毒)时,游戏才会在此时结束。而此时结束就满足了我们的设想:细胞 \(j\) 感染了病毒 \(i\)。

所以我们现在要判断是否每个(在细菌 \(j\) 心目中)比病毒 \(i\) 强的病毒 \(k\) 都存在至少一种方案灭绝。

如何把病毒 \(k\) 灭绝?我们知道(在细菌 \(j\) 心目中)比病毒 \(i\) 弱的病毒存在是没有影响的,所以我们可以用这些病毒把病毒 \(k\) 灭绝。

把病毒 \(k\) 灭绝还需要满足一个条件,就是杀它的病毒(在细菌 \(k\) 心目中)要比病毒 \(k\) 强。因此我们把满足上个条件的病毒标记,然后枚举(在细菌 \(k\) 心目中)比病毒 \(k\) 强即可。

代码

int n, p, a[N][N], b[N][N];
// a[i][j] 表示在细菌 i 心目中第 j 强的病毒
// b[i][j] 表示在细菌 i 心目中第 j 个病毒的排名
bool st[N];		// 把在细菌 j 心目中比病毒 i 强的病毒标记

signed main() {
	cin >> n;
	
	for (int i = 1; i <= n; ++ i )
		for (int j = 1; j <= n; ++ j ) {
			cin >> a[i][j];
			b[i][a[i][j]] = j;
		}
	
	vector<int> res;
	cin >> p;
	if (p == 1) {
		for (int i = 1; i <= n; ++ i )
			if (a[i][1] == i) res.push_back(i);
	} else {
		for (int i = 1; i <= n; ++ i ) {		// 判断病毒 i 能否活下来
			bool Alive = false;			// 判断病毒 i 能否在任意一个细菌 j 中活下来
			for (int j = 1; j <= n && !Alive; ++ j )
				if (b[j][i] <= b[j][j]) {				// 首先它要比细菌 j 中最初的病毒(病毒 j)要强,不然没机会
					memset(st, 0, sizeof st);
					
					for (int k = 1; k < b[j][i]; ++ k ) {
						st[a[j][k]] = true;		// 把在细菌 j 心目中比病毒 i 强的病毒标记
					}
					
					bool all_destroyed = true;		// 判断在细菌 j 心目中比病毒 i 强的病毒标记是否都灭绝
					for (int k = 1; k < b[j][i] && all_destroyed; ++ k ) {
						int x = a[j][k];		// 取出一个在细菌 j 心目中比病毒 i 强的病毒
						
						bool ok = false;		// 判断是否存在一个没有标记的病毒,且在细菌 x 心目中比病毒 x 强
						for (int l = 1; l < b[x][x] && !ok; ++ l )
							if (!st[a[x][l]]) ok = true;
						
						if (!ok) all_destroyed = false;
					}
					
					if (all_destroyed) Alive = true;
				}
			
			if (Alive) res.push_back(i);
		}
	}
	
	cout << res.size() << '\n';
	for (int v : res) cout << v << ' ';
	
	return 0;
}

C. 怪物猎人

我们考虑树上的某个位置对答案的贡献:

  • 如果这个位置接受了魔咒:它的贡献为 \(0\),而且它和它儿子的组合技施不出来。
  • 如果这个位置没接受魔咒:它和它儿子的组合技能施出来。它能够和它的父亲使出组合技取决于其父亲是否没接受魔咒。

总之只有当一个位置没有被接受魔咒时它才会有贡献。其贡献的多少(\(1\) 倍还是 \(2\) 倍)取决于与它相邻的点。

考虑树形 DP。设 \(f(u, i, 0/1)\) 表示只考虑 \(u\) 的子树,当总共有 \(i\) 个点接受魔咒,且点 \(u\) 有/没有接受魔咒的答案。

初始化 \(f(u,0,0) = 0,f(u,1,1) = hp_u\)。

转移考虑树上背包(有依赖的背包问题)。枚举其儿子 \(v\),枚举 \(v\) 的子树中选择了 \(j\) 个点接受魔咒。

\[\begin{matrix} \operatorname{chkmin}(f(u, i, 0), f(u,i+j,0)+ \min\{f(v, j, 0) + hp_v, f(v, j, 1)\}) \\ \operatorname{chkmin}(f(u, i, 1), f(u,i+j,1)+ \min\{f(v, j, 0), f(v, j, 1)\}) \\ \end{matrix} \]

按照 size 倒序转移即可。

提交记录 #613744 - 梦熊联盟 (mna.wang)

标签:11,炼石,04,魔咒,感染,细胞,心目,游戏,病毒
From: https://www.cnblogs.com/2huk/p/18412798

相关文章

  • P2285 [HNOI2004] 打鼹鼠
    [HNOI2004]打鼹鼠题目描述鼹鼠是一种很喜欢挖洞的动物,但每过一定的时间,它还是喜欢把头探出到地面上来透透气的。根据这个特点阿牛编写了一个打鼹鼠的游戏:在一个$n\timesn$的网格中,在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠,如果$i$时刻......
  • ubuntu20.04 | pip | python包管理工具
    前言我们在使用python的过程中,时常需要安装python库或框架来开发python应用程序,这个时候就需要用到pip命令了。最近需要使用pymodbus库,来实现modbusRTU通信,但是需要安装特定的版本号,接下来,就以pymodbus库为例,总结了一下pip的使用教程具体操作<1>查看某个python库是否......
  • ubuntu-22.04.4编译升级安装 OpenSSH_9.8p1+OpenSSL 3.3.2+zlib1.3.1
     实验镜像ubuntu-22.04.4-live-server-amd64.iso#安装必备和常用软件包#安装相关的依赖项,如有遗漏再次安装aptinstall-y libz-devvimgccwgettarlrzsznanomakenet-tools #安装zlib./configure--prefix=/usr/local/zlibmake&&makeinstall #安装......
  • A-计算机毕业设计定制:93904 家庭健康管理系统(免费领源码)可做计算机毕业设计JAVA、PHP
    摘 要随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,家庭健康管理系统被用户普遍使用,为方便用户能够可以随时进行家庭健康管理系统的数据信息管理,特开发了SSM家庭健康管理系......
  • 《Civilization: Beyond Earth》启动失败?《文明太空》msvcr110.dll问题解决方案大放送
    当您在尝试启动《文明:太空》(Civilization:BeyondEarth)时遇到“找不到msvcr110.dll”或“msvcr110.dll缺失”的错误提示,这意味着您的计算机上缺少或损坏了MicrosoftVisualC++2012运行时库中的一个关键组件。msvcr110.dll是许多基于C++开发的游戏和应用程序正常运行所必需的......
  • P10466 邻值查找
    #include<bits/stdc++.h>usingnamespacestd;#definexfirst#defineysecondtypedefpair<int,int>PII;typedeflonglongll;typedefunsignedlonglongull;typedefunsignedintuint;typedefvector<string>VS;typedefvector<int>......
  • P1115 最大子段和(DP)
    #include<bits/stdc++.h>usingnamespacestd;#definexfirst#defineysecondtypedefpair<int,int>PII;typedeflonglongll;typedefunsignedlonglongull;typedefunsignedintuint;typedefvector<string>VS;typedefvector<int>......
  • Win11系统提示找不到rdvgumd64.dll文件的解决办法
    其实很多用户玩单机游戏或者安装软件的时候就出现过这种问题,如果是新手第一时间会认为是软件或游戏出错了,其实并不是这样,其主要原因就是你电脑系统的该dll文件丢失了或没有安装一些系统软件平台所需要的动态链接库,这时你可以下载这个rdvgumd64.dll文件(挑选合适的版本文件)把它......
  • 11月PMP考试的同学,参加保定考点考试有机会赢万元大奖!
    当前,国家和企业对项目管理的价值日益重视,各行各业对专业项目管理人才的需求不断扩大。根据PMI的调查数据,到2027年,全球项目管理工作岗位需求量将达到8800万。中国的项目管理工作岗位需求量占比将超出全球的一半,达到4600万。而与之相对应的是,截至2023年,国内PMP有效持证人数只有约60万......
  • P11037 【MX-X3-T4】「RiOI-4」上课
    P11037【MX-X3-T4】「RiOI-4」上课本文主要解释不断\(+1\)的过程如何快速实现的具体流程。题意给定正整数\(n,q\)和\(n\)个区间\([l_i,r_i]\)。有\(q\)组询问,每次询问给定一个整数\(x\)。在每个区间内选择一个整数\(a_i\)(\(l_i\leqa_i\leqr_i\)),使得所选整数的总......