2024.8.18
130124202408181003
DATE #:20240818
ITEM #:DOC
WEEK #:SUNDAY
DAIL #:捌月拾伍
TAGS< BGM = "pure imagination--Rook1e" > < theme = oi-contest > < [NULL] > < [空] > < [空] >``` 前天是小兔子,昨天是小鹿,今天是你。-- Clannad ```
CODET1 玩具
时间限制: 1 s 内存限制: 512 MB 测评类型: 传统型
题目描述
小T给小L买了一个玩具—毛毛虫。(不要鄙视小T的审美),毛毛虫的构造非常简单,由上下两部分组成:
上半部分是毛毛虫的身体,长度为 b b b。
下半部分是毛毛虫的脚,每只脚占一个单位长度,毛毛虫共有 L L L 只脚。
一开始毛毛虫的脚在最左边 L L L 个位置,身体在最左边 b b b个位置,最后毛毛虫的脚要在最右边 L$ 个位置,身体在最右边 b b b 个位置。
现在,毛毛虫要从木板的左边爬到右边。木板的长度为 n n n,由于小T比较穷,用了很多年的木板在某些位置已经破了。毛毛虫不能将脚放在这些破的位置。
众所周知,毛毛虫是通过蠕动爬行的,因此,毛毛虫的运动分为两种操作:
- 将某一只脚向右移动若干距离,要求最后的落脚点的木板不能是破的,并且,要严格在前一只脚的左边。
- 将上半部分身体向右移动 1 1 1个距离,要求移动后所有的脚仍然在身体下方。
这两种的操作均需要花费 1 1 1的时间。
现在,小T希望聪明的你告诉他,毛毛虫爬到最右边(即身体的的最右一格在 n n n n号位置,并且所有的脚也在最右边)最少需要多少时间。
当然,有的时候,小T家的木板已经残破不堪,毛毛虫无法到达最右边,那么请输出 “ I M P O S S I B L E ” “IMPOSSIBLE” “IMPOSSIBLE”。
问题保证最开始的 L L L 个位置和最后的 L L L 个位置木板都是好的。
输入格式
第一行空格隔开的三个数 L , b , n L,b,n L,b,n。
第二行连续 n n n 个 0 / 1 0/1 0/1, 0 0 0 表示当前位置木板是破的, 1 1 1 表示当前位置木板完好。
输出格式
一行一个数,表示毛毛虫花费的最少时间。(或者“IMPOSSIBLE” “ I M P O S S I B L E ” “IMPOSSIBLE” “IMPOSSIBLE”)
样例输入
1 3 511011
样例输出
5
数据范围与约定
20 % 20\% 20% 的数据满足 n ≤ 10 n \le 10 n≤10。
对于另外 20 % 20\% 20% 的数据,满足 L = 1 L = 1 L=1。
对于另外 15 % 15\% 15% 的数据,满足没有破的地板。
对于另外 25 % 25\% 25% 的数据,满足 n , m ≤ 10000 n, m \le 10000 n,m≤10000。
100 % 100\% 100% 的数据满足
//2024.8.17
//by white_ice
//#115. 【2020.11.22 NOIP模拟赛 T2】玩具
#include
直接输出impossible可以获得5分的友情分
但是正解也是非常难崩,直接贪心加模拟即可
每次记录最后一个虫脚出现的位置即可
CODET2 找朋友
时间限制: 1 s 内存限制: 1024 MB 测评类型: 传统型
题目描述
N 个鱼缸排成一列,按照 1 , 2 , … , N 1, 2, \ldots, N 1,2,…,N 的顺序编号。第 i i i 个鱼缸里水的高度为 H i H_i Hi ,保证 H i < W H_i < W Hi<W 。
现在放入 M M M 条鱼,第 i i i 条鱼被放入第 P i P_i Pi 个鱼缸,同时它最多能跳 J i J_i Ji 单位。鱼 i i i 能从鱼缸 a a a 跳到鱼缸 b b b 当且仅当 ∣ a − b ∣ ≤ 1 |a - b| ≤ 1 ∣a−b∣≤1 且 J i > W − H a J_i > W - H_a Ji>W−Ha 。
现在每条鱼开始寻找朋友,他们从一开始所在的鱼缸开始跳,直到跳到某个鱼缸然后停下。等所有鱼都停下了,处在同一鱼缸的鱼就会相互认识。求最后相互认识的鱼的对数的最大值。
输入格式
第一行三个正整数 N , M , W N, M, W N,M,W( 2 ≤ N ≤ 1 0 4 , 1 ≤ M ≤ 200 , 2 ≤ W ≤ 1 0 6 2 ≤ N ≤ 10^4, 1 ≤ M ≤ 200, 2 ≤ W ≤ 10^6 2≤N≤104,1≤M≤200,2≤W≤106)。
第二行 N N N 个正整数 H 1 , H 2 , … , H N H_1, H_2, \ldots, H_N H1,H2,…,HN( 1 ≤ H i < W 1 ≤ H_i < W 1≤Hi<W)。
接下来的 M M M 行描述每条鱼,其中的第 i i i 行有两个正整数 P i , J i P_i, J_i Pi,Ji( 1 ≤ P i ≤ N , 1 ≤ J i ≤ 1 0 6 1 ≤ P_i ≤ N, 1 ≤ J_i ≤ 10^6 1≤Pi≤N,1≤Ji≤106)。
输出格式
一行一个整数表示答案。
样例输入
3 4 5 4 2 3 1 1 3 3 2 3 1 7
样例输出
3
样例说明
鱼 1 1 1 由于 J 1 < W − H 1 J_1 < W - H_1 J1<W−H1 只能留在鱼缸 1 1 1 。
类似地,鱼 3 3 3 只能留在鱼缸 2 2 2 。
令鱼 4 4 4 跳到鱼缸 2 2 2 ,鱼 2 2 2 跳到鱼缸 2 2 2 。此时鱼 2 , 3 , 4 2, 3, 4 2,3,4 两两认识,对数达到 3 3 3 ,可以证明这是最大值。
数据规模与约定
子任务编号 分数 额外限制 1 3 H i H_i Hi 全部相同 2 7 N , M ≤ 20 N, M ≤ 20 N,M≤20 3 9 N , M ≤ 50 N, M ≤ 50 N,M≤50 4 14 M ≤ 50 M ≤ 50 M≤50 5 67 — 时间限制: $ 1 \text{s}$
空间限制: 1024 MB 1024 \text{MB} 1024MB
//2024.8.18
//by white_ice
#include
发现每一条鱼都有一个跳跃区间,
我们只要计算区间中重叠最多的地方即可
预处理出区间,离散化后使用区间DP求解
CODET3 异或
时间限制: 2 s 内存限制: 1024 MB 测评类型: 传统型
题目描述
给定一个长度为 n n n 的非负整数列 a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1,a2,...,an 和非负整数 x x x,
求有多少个非空子序列 1 ≤ b 1 < b 2 < ⋯ < b k ≤ n 1 \leq b_{1} < b_{2} < \cdots < b_{k} \leq n 1≤b1<b2<⋯<bk≤n , 满足对任意的 ( i , j ) ( 1 ≤ i < j ≤ k ) (i, j)(1 \leq i < j \leq k) (i,j)(1≤i<j≤k) 都有 a b i ⊕ a b j ≥ x a_{b_{i}} \oplus a_{b_{j}} \geq x abi⊕abj≥x。
其中 ⊕ \oplus ⊕ 表示按位异或。
由于这个数可能非常大,你只需要回答这个数除以 998244353 998244353 998244353 998244353 的余数即可。
输入格式
第一行两个整数 n , x ( 1 ≤ n ≤ 3 ⋅ 1 0 5 , 0 ≤ x < 2 60 ) n, x\left(1 \leq n \leq 3 \cdot 10^{5}, 0 \leq x < 2^{60}\right) n,x(1≤n≤3⋅105,0≤x<260) 。
第二行 n n n 个整数 a 1 , a 2 , … , a n ( 0 ≤ a i < 2 60 ) a_{1}, a_{2}, \ldots, a_{n}\left(0 \leq a_{i} < 2^{60}\right) a1,a2,…,an(0≤ai<260) 。
输出格式
一行一个整数,表示满足条件的子序列的个数除以 998244353 998244353 998244353 的余数。
样例输入1
3 0 0 1 2
样例输出1
7
样例输入2
3 2 0 1 2
样例输出2
5
样例输入3
3 3 0 1 2
样例输出3
4
样例输入4
7 4 11 5 5 8 3 1 3
样例输出4
35
样例解释
第一组样例数据中,所有 2 3 − 1 2^3 − 1 23−1 个非空子序列都合法。
第二组样例数据中,除 [ 1 , 2 ] [1, 2] [1,2] 和 [ 1 , 2 , 3 ] [1, 2, 3] [1,2,3] 外,所有非空子序列都合法。
第三组样例数据中,合法的子序列有 [ 1 ] , [ 2 ] , [ 3 ] [1], [2], [3] [1],[2],[3] 和 [ 2 , 3 ] [2, 3] [2,3]。
数据范围
对于 10 % 10\% 10% 的测试点,满足 n ≤ 20 n \leq 20 n≤20。
对于另外 20 % 20\% 20% 的测试点,满足 n ≤ 5000 n \leq 5000 n≤5000。
对于另外 50 % 50\% 50% 的测试点,满足 n ≤ 1 0 5 n \leq 10^5 n≤105。
对于 100% 100 % 100\% 100% 的测试点,满足 1 ≤ n ≤ 3 ⋅ 1 0 5 , 0 ≤ x < 2 60 , 0 ≤ a i < 2 60 1 \leq n \leq 3 \cdot 10^{5}, 0 \leq x < 2^{60}, 0 \leq a_{i} < 2^{60} 1≤n≤3⋅105,0≤x<260,0≤ai<260。
//2024.8.18
//by white_ice
//#120. 【2020.11.25 NOIP模拟赛 T3】异或
#include
先引入一个引理:
结论:一个集合中任意两项异或的最小值,一定为排序后相邻两项异或的最小值。
十分简单证明
那么我们就可以在子树上DP了,
转移:
f i = ∑ j = 1 i − 1 f j [ a j ⊕ a i ≤ x ] + 1 f_i=\sum\limits_{j=1}^{i-1}f_j[a_j \oplus a_i \le x]+1 fi=j=1∑i−1fj[aj⊕ai≤x]+1
这个扔到trie树上维护即可。
CODET4 送给好友的礼物
时间限制: 5 s 内存限制: 512 MB 测评类型: 传统型
题目背景
小 M 和小 B 是一对好朋友,她们很喜欢草莓。
题目描述
给定一棵包含 n n n 个节点的树 T T T,节点从 1 ∼ n 1 \sim n 1∼n 顺序编号。
小 M 和小 B 在时刻 0 0 0 都在 1 1 1 号节点。
从时刻 1 1 1 开始的每个时刻初,小 M 和小 B 都可以选择:移动到一个和自己所在节点直接相连的节点,或者停留在当前所在的节点。
树上有 k k k 个草莓,它们分布在 k k k 个不同的节点上。
小 M 和小 B 想要收集到所有的草莓,任何一个时刻末,如果小 M 或者小 B 在某一个草莓所在的节点上,那么这个草莓就被收集了。
她们不想花费太多的时间,因此你需要回答:至少在第几时刻末,小 M 和小 B 可以收集到所有的草莓,并且都回到节点 1 1 1。
输入格式
第一行两个整数 n n n 和 k k k ( 1 ≤ k ≤ n ≤ 415 ) (1 \leq k \leq n \leq 415) (1≤k≤n≤415),分别表示树的节点个数和草莓的个数。
接下来 n − 1 n-1 n−1 行,每行两个整数 u u u 和 v v v ( 1 ≤ u , v ≤ n ) (1 \leq u,v \leq n) (1≤u,v≤n),表示树上有一条从 u u u 到 v v v 的边。
接下来一行 k k k 个互不相同的整数 a 1 , a 2 ⋯ a k a_1,a_2 \cdots a_k a1,a2⋯ak,分别表示这 k k k 个草莓所在的节点。
输出格式
一行一个整数,所求答案。
输入样例 #1
7 4 1 2 2 3 2 4 1 5 5 6 6 7 3 4 5 7
输出样例 #1
6
输入样例 #2
1 1 1
输出样例 #2
0
样例解释
小 M 的路线是:1->2->3->2->4->2->1
小 B 的路线是:1->5->6->7->6->5->1
数据范围
- Subtask 1 (6 分): n ≤ 3 n \leq 3 n≤3
- Subtask 2 (1 分): k = 1 k = 1 k=1
- Subtask 3 (11 分): n ≤ 7 n \leq 7 n≤7
- Subtask 4 (17 分): k ≤ 20 k \leq 20 k≤20
- Subtask 5 (42 分): n ≤ 90 n \leq 90 n≤90
- Subtask 6 (23 分):无特殊限制。
1 ≤ k ≤ n ≤ 415 , 1 ≤ u , v ≤ n 1 \leq k \leq n \leq 415, 1 \leq u,v \leq n 1≤k≤n≤415,1≤u,v≤n
//2024.8.18
//by white_ice
//送给好友的礼物 | P7276
#include
P7276 送给好友的礼物 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)在这里看吧。。。
T5 广播
时间限制: 2 s 内存限制: 512 MB 测评类型: 传统型题目描述
C 国有 n n n 个城市,非常巧合的是这 n n n 个城市刚好构成了一棵树。C 国的国王是位日理千机的贤君,为了能及时发布自己的命令,于是决定在每个城市都建造一个信号塔,信号塔能传播信息,城市 i i i 的信号塔的传播能力是 v a l i val_i vali: 表示如果城市 i i i 和城市 j j j 的距离 d i s t ( i , j ) ≤ v a l i dist(i, j) \leq val_i dist(i,j)≤vali,那么就能把信息从城市 i i i 传到城市 j j j。国王所在的城市为 1 1 1 号城市,国王想尽可能快的让自己发布的命令在 i i i 号城市被执行,所以他希望把命令从 1 1 1 号城市传播到 i i i 号城市这个过程中的传播次数尽可能少。输出从 1 1 1 号城市到 i i i 号城市所需的最少传播次数。
输入格式
输入的第一行有一个正整数 n n n,表示城市数量。
接下来一行有 n n n 个正整数,表示传播距离 v a l val val。
接下 n − 1 n-1 n−1 行每行有个正整数 x i , y i x_i,y_i xi,yi,表示一条边。
输出格式
输出一行 n − 1 n-1 n−1 个正整数,用空格隔开,表示答案。
样例
input
8 1 3 1 1 1 1 1 1 1 2 1 3 1 4 2 5 2 6 3 7 3 8
output
1 1 1 2 2 2 2
数据范围与提示
保证输入的边形成一棵树。
对于 20 % 20\% 20% 的数据,有 n ≤ 1000 n \leq 1000 n≤1000;
对于接下来 10 % 10\% 10% 的数据,有 n ≤ 2 × 1 0 5 n \leq 2 \times 10^5 n≤2×105,且是一棵完全二叉树;
对于接下来 10 % 10\% 10% 的数据,有 n ≤ 2 × 1 0 5 n \leq 2 \times 10^5 n≤2×105,且是一条链;
对于接下来 20 % 20\% 20% 的数据,有 n ≤ 50000 n \leq 50000 n≤50000;
对于接下来 40 % 40\% 40% 的数据,有 n ≤ 2 × 1 0 5 n \leq 2 \times 10^5 n≤2×105。
时间限制:$ 2 \text{s}$
空间限制: 512 MB 512 \text{MB} 512MB
是的,有T5
我们将原图转化成新图,将节点 i i i和距离它小于 v a l i val_i vali的所有点连边,
考虑优化建边过程,
使用点分治优化即可
最后的图刚好是个01bfs,直接跑就好