\(NOIP\)模拟\(DAY1\)

​ $by $ 一扶苏一

---

题目一览

• \(T1\)大美江湖

• \(T2\)腐草为萤

---

\(T1\)大美江湖

【题目背景】

细雪飘落长街，枫叶红透又一年
不只为故友流连，其实我也恋长安
听门外足音慢，依稀见旧时容颜
故事几经悲欢，结局都与你有关
——银临《大美江湖》

【问题描述】

扶苏听着《大美江湖》，在剑三里控制着他的人物炮姐来到了长安。 长安城中有一个任务，需要扶苏进入地下的机关道，机关道是一个 \(n×m\) 的矩形地 图，里面有一些怪物和药水。扶苏操控着炮姐在机关道中游荡。有些时候他希望问问你 他的角色有多少攻击力、防御力以及丢失了多少血量。 具体的，在输入文件中会给出一个$ n×m \(的矩形地图，地图中第\) i \(行第 j 列的字符\) C_{ij} \(代表机关道中第\) i \(行第\) j \(列的元素是什么。具体的，\)C_{ij}\(={‘.’,‘\)R\(’,‘\)Q\(’,‘\)Y\(’,‘\)M$’}。 其中，

1、字符 . 代表此处可以通过，且无其他元素

2、字符 \(R\) 代表此处为生命药水，可以减少炮姐 10 点丢失的血量 \(HP\)

3、字符 \(Q\) 代表此处为力量药水，可以增加炮姐 5 点攻击力 \(ST\)

4、字符$ Y $代表此处为防御药水，可以增加炮姐 5 点防御力 \(DE\)

5、字符$ M $代表此处为怪物，炮姐会损失相应血量 每只怪物都有三个参数来描述他们的属性，分别是血量 \(HP_{enemy}\)，攻击力$ ST_{enemy}$，防御力 \(DE_{enemy}\)。且所有怪物的属性都相同。 一旦走到怪物格，遭遇战将开始。扶苏一定会打死怪物，怪物对炮姐造成的伤害为

​ \[max(1,\lceil \frac {HP_{enemy}} {max(1,ST_{my}-DE_{enemy})}\rceil \times max(1,ST_{enemy}-DE_{my}))\] （真难打）

其中 \(max(a,b)\)代表取$ a \(和\) b \(的最大值；\)\lceil x \rceil \(的值为不小于\) x \(的最小整数；下标为\) enemy \(的参数代表怪物的参数，下标为\) my \(的参数代表炮姐的参数 你会收到\) q \(次操作，每次操作要么是一次查询，要么是一次移动。 对于移动，你会再获得一个数字参数，这个参数只可能是\) 1/2/3/4 $其中的一个，代表 炮姐向地图的 左/右/上/下 移动。

【输入格式】

输入文件名为$ mzq.in\(。 输入文件中有且仅有一组数据，第一行为两个正整数\) n \(和\) m$,代表地图的大小。下面 \(n\) 行，每行$ m \(个字符，描述机关道的地图 下面一行有三个正整数，分别代表\)HP_{enemy}\(，\)ST_{enemy}\(，\)DE_{enemy} $下面一行有两个整数 \(x\),\(y\)，代表炮姐初始在第 $x \(行第\) y \(列出发。如果出发点有怪物，不发生战斗，如果有道具，不会将其捡拾。 下面一行给出两个正整数，代表炮姐初始的\) ST \(和\) DE\(。 下面一行给出一个整数\) q\(，代表操作个数以下\)q$行，每行首先有一个数字，如果是 1，则代表一次查询。否则数字一定是 2， 代表炮姐的一次移动，一个空格后会给出一个数字，作为移动的参数。

【输出格式】

输出文件名为$ mzq.out\(。 对于每个查询，输出一行三个用空格隔开的整数，代表炮姐损失的血量\) HP\(，当前的攻击力\) ST\(，以及当前的防御力\) DE$

【输入输出样例 】

\(mzq.in\)

5 5

$MMMMM $

$R R R R R $

$QQQQQ $

\(YYYYY\)

. . . . .

5 5 5

5 1

10 10

8

2 3

1

2 3

2 3

2 3

1

2 2

1

$mzq.out $

0 10 15

1 15 15

2 15 15

【数据规模与约定】

本题共 10 个测试点，不捆绑测试，各测试点等分。各测试点的数据性质如下表

测试点编号	n	m	q	特殊性质
1	=1	=1	=0	无
2、3	=1	\(\leq 10\)	\(\leq 1000\)	无
4、5	=1	=1	\(\leq 1000\)	保证人物不移动
6、7、8	\(\leq 100\)	\(\leq 100\)	\(\leq 10000\)	保证地图中没有怪物
9、10	\(\leq 100\)	\(\leq 100\)	\(\leq 10000\)	无

对于100%的数据，\(1≤n,m≤100,0≤q≤10000\)，保证移动是合法的，即无需担心走到地图外。我们认为人物不会因为打怪而死亡。

对于100%的数据，怪物和人物的攻击力、血量、防御力都不超过100，不低于0。

注意：如果多次进入同一个格子，格子上的药水可以重复拾取，小怪会重复出现

注意：如果在拾取药水的时候人物损失的生命值低于10，则会将损失的生命值降至0

题目分析：

扶苏出的题就是毒瘤（划掉

对于这种给出不同测试点的具体数据的题，我们可以考虑分步得分

测试点1

​ 一共有0个操作，那么就说明没有输出，所以一定会得到10分

测试点4、5

​ 保证人物不移动，所以一定不会有减血，也不会有任何能力值的增加。那么有多少1就输出多少组数据。得到20分

测试点6、7、8

​ 地图上没有怪物，就不需要计算减血的那个复杂式子，直接累加药水的属性就好了。又能得到30分

测试点2、3、9、10

​ 就是一个暴力模拟，模拟每一次行走减血的式子和药水的属性可以\(O(1)\)算的，所以总复杂度是\(O(q)\)的

---

\(T2\)腐草为萤

题目描述：

扶苏给了你一棵树，这棵树上长满了幼嫩的新叶，我们约定这棵树的根是 \(1\)，每个节
点都代表树上的一个叶子。
如果你不知道什么叫树，你可以认为树是一个边数比节点个数少 $1 \(的无向连通图。 我们如果约定节点\) u \(是树\) T \(的根，则可以定义一个节点\) v \(到根的路径为该无向图上\) u\(,\) v$
两个节点之间的简单路径上的节点集合(包括路径的两个端点)。可以证明，这样的简单路
径只有一条。
我们定义节点$ x \(是节点\) y \(的祖先\)(x\neq y)\(，当且仅当\) x \(在\) y \(到根的路径上。 现在扶苏想在这棵树上选定一个集合，将其称之为幼嫩集合，来比较集合中的节点 哪个最幼嫩。注意到一旦集合中存在两个节点\) u\(,\) v\(，使得\) u \(是\) v \(的祖先，那么一定\) v $要比
$u \(更幼嫩，因为\) v $是在 $u \(的枝丫上生长出来的，那么这样的集合就是没有意义的。也就是 说，扶苏所选择的集合一定满足要求“对于任意集合中的元素对\) (u, v)\(，\)u $不是 \(v\) 的祖
先”。
扶苏其实对这些节点哪个最幼嫩并不感兴趣，也对他能选出多少集合不感兴趣，因
为这些都是为了问你下面的问题而创造出的题目背景。
扶苏给每个节点都定义了一个权值，具体的，我们会给出一个参数$ T\(，规定\) i $号节点
的权值为 \(T^i\)。
我们定义一个幼嫩集合幼嫩指数为集合内节点的权值和。现在扶苏想请问你，对于
他所有可能选出的集合，这些集合的幼嫩指数之和是多少。
为了避免答案过大，请你输出答案对 \(10^9+7\) 取模的结果。

题解:
子任务 1：
只有一个点，所以只有{1} 这一种集合，于是答案为 1。期望得分 5 分。

子任务 2、3：
爆搜，枚举所有可能的集合，然后计算答案。
由于每个点只有选进集合或不选两种可能，所以一共有 2
n 个集合，然后可以
O(n) 的去检验集合是否合法，顺便统计答案。于是总复杂度 \(O(2n×n)\)。期望得分25分。

子任务 4、5：
考虑 \(DP\)。设$ f_u \(是以\) u \(为根的子树的答案。 如果\) u \(没有孩子，那么\) f_u = u$
T。
如果$ u \(只有一个孩子\) v\(，那么要么选\) u \(不选\) u \(的子孙，要么不选\) u\(。不选\) u
\(的答案即为\) f_v\(，选\) u \(的答案即为\) u
T\(。两种情况加起来就是\) f_u$。
如果 \(u\) 有两个孩子$ x,y$。考虑要么选 \(u\)，要么只选 \(x\) 的子树内的元素，要么
只选$ y$ 的子树内的元素，要么既选 x 内的元素又选 y 内的元素但不选 u。前三种
情况的答案易得。现在考虑第四种情况的答案。设 s 是 x 子树内的某个集合。考
虑无论 y 的子树内怎么选，再加上 s 都是合法的，因为 y 和 x 之间没有祖先后
代关系且 s 在 x 之内。设$ g_u $是以 u 为根能选择的集合个数，那么一共有 \(g_y\) 个
集合选择 s 以后依旧合法，设 s 的权值和为$ ws\(，于是 s 的贡献即为\) w_s×g_y\(。由于 fx 为 x 子树内所有可能集合的权值和，所以可以发现  ws  fx 。于是\) x $子树内
的集合对答案的总贡献是 \(f_x×g_y\)。同理，y 子树内的集合对答案的贡献是$ f_y×g_y$。
于是 \(f_u=f_y×g_x+f_x×g_y+f_x+f_y+u\)
T。\(g_u=g_x×g_y+g_x+g_y+1\)。时间复杂度O(n)，期望得分 30
分。

子任务6、7：
虑在遍历子节点的时候，已经遍历了一些子节点，现在新加入了一个子节点。
由于新加入一个子节点与之前遍历的子节点没有祖先后代关系，于是可以之前遍历
过得子树看成一棵子树，然后问题就变成了子任务4、5。期望得分 40 分。
需要注意的是由于读入规模达到了\(10^6\)左右，需要普通的读入优化。