叠甲
今天从凌晨 \(0\) 点 \(00\) 分 一直盯着电脑屏幕到现在
要瞎了\(.jpg\)
赛后总结先咕一段时间吧
眼睛实在是不想再看任何电子显示屏了
QAQ
NOIP模拟赛
| 题目名称 | 上升序列 | 树上标记 | 发送消息 | 猜数 |
|---|---|---|---|---|
| 题目类型 | 传统型 | 传统型 | 传统型 | 传统型 |
| 目录 | inc | mark | message | guess |
| 可执行文件名 | inc | mark | message | guess |
| 输入文件名 | inc.in | mark.in | message.in | guess.in |
| 输出文件名 | inc.out | mark.out | message.out | guess.out |
| 每个测试点时限 | 2.0秒 | 2.0秒 | 4.0秒 | 2.0秒 |
| 内存限制 | 512MB | 512MB | 512MB | 512MB |
| 子任务数目 | 10 | 20 | 10 | 10 |
| 测试点是否等分 | 是 | 是 | 是 | 是 |
T1 上升序列（inc）
题目描述
藤坦坦和藤茵茵在玩一个这样的猜数：有 $ n $ 张卡片排成一排，第 $ i $ 张卡片的正面写着 $ a_i $，背面写着 $ b_i $。藤坦坦可以任意翻转这些卡片，让任何一面朝上（但是卡片之间的顺序不能换）。
藤坦坦操作完之后，藤茵茵需要按照从前往后的顺序拿取其中一些卡片，但需要保证，每拿取一张卡片，朝上的这一面上的数字要比上一张卡片大。
现在，两人想知道应该如何配合，能让藤茵茵拿到尽可能多的卡片。
输入格式
从文件 inc.in 中读取数据
输入的第一行一个整数 $ n $。
输入的第二行 $ n $ 个整数，第 $ i $ 个整数为 $ a_i $。
输入的第三行 $ n $ 个整数，第 $ i $ 个整数为 $ b_i $。
输出格式
输出到文件 inc.out 中
输出一行一个整数，表示藤茵茵最多能拿到的卡片数
输入样例 1
10
2 6 6 7 5 3 8 1 10 3
7 7 2 1 2 5 4 2 4 10
输出样例 1
5
样例 1 解释
最优策略是，藤坦坦选择正面朝上的数字为：2 6 6 1 2 5 8 1 10 3
然后藤茵茵从前往后依次选择：1,2,5,8,10
输入样例 2
见下发文件 sample_inc2.in
输出样例 2
见下发文件 sample_inc2.out
数据范围与约定
- 对于 20% 的数据，保证 $ 1 \leq n \leq 10, 1 \leq a_i, b_i \leq 1000 $。
- 对于 50% 的数据，保证 $ 1 \leq n \leq 1000, 1 \leq a_i, b_i \leq 1000 $。
- 对于 80% 的数据，保证 $ 1 \leq n \leq 5000 $。
- 对于 100% 的数据，保证 $ 1 \leq n \leq 10^6, 1 \leq a_i, b_i \leq 10^9 $。
T2 树上标记（mark）
题目描述
有一棵 $ n $ 个点的树，藤茵茵和藤坦坦现在要在这棵树上进行如下操作：
- 藤茵茵选择两个点 $ A $ 和 $ B $，满足 $ A $ 和 $ B $ 在树上都只有一个邻居，然后从 $ A $ 沿最短路径走到 $ B $，并把沿途经过的点打上标记
- 藤坦坦选择一个点 $ S $，然后沿最短路径走到距离 $ S $ 最近的已经被打上标记的点
- 现在，兄妹俩希望他们俩走的步数的乘积最大。你来帮助兄妹俩算一算，这个最大值是多少呢？
- 同时，兄妹俩还有一个疑问，藤茵茵有多少种选择 $ A, B $ 的方法，使得藤坦坦能选出一个 $ S $ 来达到最大乘积呢？
注意：这里的 $ (A, B) $ 是无序的二元组，所以 $ A, B $ 和 $ B, A $ 视为藤茵茵的同一种选法
输入格式
从文件 mark.in 中读取数据
第一行一个正整数 $ n $ 表示树上点数
接下来 $ n - 1 $ 行，每行两个正整数 $ u, v $ 表示一条树边 $ (u, v) $
输出格式
输出到文件 mark.out 中
输出一行两个整数，分别表示两个人步数乘积的最大值和藤茵茵的选择方案数
输入样例 1
6
1 2
1 3
2 4
2 5
2 6
输出样例 1
4 3
样例 1 解释
- 藤茵茵取 $ (A, B) = (4, 5) $，走的步数为 2，藤坦坦取 $ S = 3 , S $ 最近的标记点是 2，步数是 2，因此乘积为 $ 2 \times 2 = 4 $
- 除此之外，藤茵茵也可以取 $ (A, B) = (4, 6) $ 或 $ (A, B) = (5, 6) $，都存在 $ S $ 能使乘积达到最大
输入样例 2~4
见下发文件 sample_mark2~4.in
输出样例 2~4
见下发文件 sample_mark2~4.out
数据范围与约定
| 测试点编号 | $ n \leq $ | 特殊性质 |
|---|---|---|
| 1~2 | 20 | 无 |
| 3~5 | 200 | 无 |
| 6~7 | 3000 | A |
| 8~10 | 3000 | 无 |
| 11~13 | $ 3 \times 10^5 $ | A |
| 14~17 | $ 3 \times 10^5 $ | 无 |
| 18~20 | $ 10^6 $ | 无 |
特殊性质 A：数据保证对每个 $ i = 1, 2, \dots, n - 1 , u_i $ 在 $ [1, i] $ 中均匀随机选取，$ v_i = i + 1 $。
T3 发送消息（message）
题目描述
藤茵茵今天拿到了一个数字串 $ S $，它决定把这个数字串传递给藤坦坦。
因为数字串很长，所以藤茵茵想了一种简单的表示方式：把数字串分解为若干级长的由相同数字组成的连续段，假设每一段有 $ k $ 个数字 $ x $，则传递时用 $ \overline{kx} $ 表示。
比如，如果 $ S = 112223 $，则 $ S $ 分为三个级长的相同数字连续段：11, 222, 3，然后分别表示为 21, 32, 13，所以最后她传递给藤坦坦的串就为 213213。再比如 $ S = 11111111111122 $，则传递给藤坦坦的串为 12122。
藤坦坦在收到藤茵茵发送的串 $ T $ 以后，又用同样的方式进行表示，变成字符串 $ Q $ 传递给藤一零。
当藤一零收到 $ Q $ 之后，它有了一个疑问，藤茵茵拿到的 $ S $ 可能有几种情况呢？
输入格式
从文件 message.in 中读取数据
一个由 $ 0 \sim 9 $ 组成的数字串 $ Q $
输出格式
输出到文件 message.out 中
输出 $ S $ 的方案数，答案对 $ 10^9 + 7 $ 取模
输入样例 1
2122
输出样例 1
3
样例 1 解释
可能的 $ S $ 有以下三种情况：
-
$ S = 122 $，发送给藤坦坦后 $ T = 1122 $，然后发给藤一零变成 $ Q = 2122 $ .
-
$ S = \underbrace{222 \dots 2}_{112 \text{ 个}2} $，发送给藤坦坦后 $ T = 1122 $，然后发给藤一零变成 $ Q = 2122 $ .
-
$ S = \underbrace{2222222 \dots 222}_{211 \text{ 个}2} $ ，(博客园的latex好像有点问题我不换行他后面这公式出不来)
发送给藤坦坦后 $ T = \underbrace{222 \dots 2}_{212 \text{ 个}2} $，然后发给藤一零变成 $ Q = 2122 $
输入样例 2
1022112
输出样例 2
1032
输入样例 3
122112122112
输出样例 3
128451905
数据范围与约定
令 $ n = |Q| $
- 测试点 1：$ n \leq 2 $
- 测试点 2,3：$ n \leq 7 $
- 测试点 4,5：$ n \leq 50 $
- 测试点 6,7,8：$ n \leq 1000 $，并且 $ Q $ 中没有数字 0
- 测试点 9,10：$ n \leq 1000 $
T4 猜数（guess）
题目描述
有 $ n $ 个小球，每个小球有一个重量 $ w $，任意两个小球的重量不相同。现在藤坦坦想知道这 $ n $ 个小球中第二重的球是哪一个。
但是，藤坦坦并不知道每个小球的重量，实验室只有一个天平，每次可以比较两个小球的重量。
在藤坦坦到来之前，已经有其它同学进行了 $ m $ 次比较，并记录在了实验报告上，第 $ i $ 次比较得到的结果为 $ x_i $ 比 $ y_i $ 重。
现在，藤坦坦想通过尽可能少的次数，来确定哪个小球是第二重的。
你需要帮藤坦坦找到最小的操作次数 $ K $，使得无论任何情况，都一定能在 $ K $ 次内确定第二重的小球。
输入格式
从文件 guess.in 中读取数据
第一行两个非负整数 $ n, m $ 表示小球的数量和已经比较的次数
接下来 $ m $ 行，每行两个正整数 $ x, y $ 表示已经确定 $ x $ 比 $ y $ 重
输出格式
输出到文件 guess.out 中
输出最小值 $ K $ 使得存在一种策略，能保证 $ K $ 次内一定确定第二重的小球。
输入样例 1
4 2
1 2
4 3
输出样例 1
2
样例解释 1
已经确定的关系为 $ w_1 > w_2 ， w_4 > w_3 $，最优策略如下：
- 先询问 $ w_1 $ 和 $ w_4 $ 的关系
- 如果 $ w_1 > w_4 $，我们可以确定的是 $ w_1 $ 为最大值，$ w_3 $ 不可能为次大值，因此再询问一次$ w_2 $ 和 $ w_4 $ 即可确定第二大
- 如果 $ w_1 < w_4 $，我们可以确定的是 $ w_4 $ 为最大值，$ w_2 $ 不可能为次大值，因此再询问一次 $ w_1 $ 和 $ w_3 $ 即可确定第二大
无论哪种情况都可以在两次确定次大值，同时如果只询问一次不可能保证能找到次大值，因此答案为 2
数据范围与约定
- 对于 10% 的数据，$ n \leq 5 $。
- 对于 30% 的数据，$ n, m \leq 300 $。
- 对于另外 10% 的数据，保证事先测试的 $ x $ 都不同。
- 对于另外 10% 的数据，保证事先测试的 $ y $ 都不同。
- 对于另外 10% 的数据，保证每个球都至少被事先比较过一次。
- 对于 100% 的数据，$ 1 \leq n, m \leq 5 \times 10^5 ， x \neq y $，保证给定的 $ m $ 条结果不会矛盾，保证相同的比较不会出现两次。