DAY 1

(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})} ceil imes max(1,ST_{enemy}-DE_{my}))$$ (真难打)

其中 (max(a,b))代表取$ a (和) b (的最大值;)lceil x ceil (的值为不小于) 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 eq 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)左右,需要普通的读入优化。

原文地址:https://www.cnblogs.com/juruohqk/p/11073268.html