CSP-S

DiaoHantong · 2025-09-21 22:05:48 · 个人记录

P3205 [HNOI2010] 合唱队

题目描述

为了在即将到来的晚会上有更好的演出效果，作为 AAA 合唱队负责人的小 A 需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共 n 个人，第 i 个人的身高为 h_i 米（1000 \le h_i \le 2000），并已知任何两个人的身高都不同。假定最终排出的队形是 A 个人站成一排，为了简化问题，小 A 想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按以下原则依次将每个人插入最终排出的队形中：

第一个人直接插入空的当前队形中。
对从第二个人开始的每个人，如果他比前面那个人高（h 较大），那么将他插入当前队形的最右边。如果他比前面那个人矮（h 较小），那么将他插入当前队形的最左边。

当 n 个人全部插入当前队形后便获得最终排出的队形。

例如，有 6 个人站成一个初始队形，身高依次为 1850, 1900, 1700, 1650, 1800, 1750，
那么小 A 会按以下步骤获得最终排出的队形：

因此，最终排出的队形是 1750, 1650, 1700, 1850, 1900, 1800。

小 A 心中有一个理想队形，他想知道多少种初始队形可以获得理想的队形。

请求出答案对 19650827 取模的值。

输入格式

第一行一个整数 n。
第二行 n 个整数，表示小 A 心中的理想队形。

输出格式

输出一行一个整数，表示答案 \bmod 19650827 的值。

输入输出样例 #1

输入 #1

4
1701 1702 1703 1704

输出 #1

说明/提示

对于 30\% 的数据，n \le 100。
对于 100\% 的数据，n \le 1000，1000 \le h_i \le 2000。

P4302 [SCOI2003] 字符串折叠

题目描述

折叠的定义如下：

一个字符串可以看成它自身的折叠。记作 S = S
X(S) 是 X 个 S 连接在一起的串的折叠。记作 X(S) = SSSS…S。
如果 A = A’, B = B’，则 AB = A’B’。例如：因为 3(A) = AAA, 2(B) = BB，所以 3(A)C2(B) = AAACBB，而 2(3(A)C)2(B) = AAACAAACBB

给一个字符串，求它的最短折叠。

例如 AAAAAAAAAABABABCCD 的最短折叠为：9(A)3(AB)CCD。

输入格式

仅一行，即字符串 S，长度保证不超过 100。

输出格式

仅一行，即最短的折叠长度。

输入输出样例 #1

输入 #1

NEERCYESYESYESNEERCYESYESYES

输出 #1

说明/提示

一个最短的折叠为：2(NEERC3(YES))

P2470 [SCOI2007] 压缩

题目描述

给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。

bcdcdcdcd 可以压缩为 bMcdRR，下面是解压缩的过程：

已经解压的部分	解压结果	缓冲串
b	b	b
bM	b	.
bMc	bc	c
bMcd	bcd	cd
bMcdR	bcdcd	cdcd
bMcdRR	bcdcdcdcd	cdcdcdcd

输入格式

输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。

输出格式

输出仅一行，即压缩后字符串的最短长度。

输入输出样例 #1

输入 #1

aaaaaaa

输出 #1

输入输出样例 #2

输入 #2

bcdcdcdcdxcdcdcdcd

输出 #2

说明/提示

在第一个例子中，解为aaaRa，在第二个例子中，解为bMcdRRxMcdRR。

【限制】

50%的数据满足：1<=n<=20

100%的数据满足：1<=n<=50

P1941 [NOIP 2014 提高组] 飞扬的小鸟

题目背景

NOIP2014 提高组 D1T3

题目描述

Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。

为了简化问题，我们对游戏规则进行了简化和改编:

游戏界面是一个长为 n，高为 m 的二维平面，其中有 k 个管道（忽略管道的宽度）。

小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。

小鸟每个单位时间沿横坐标方向右移的距离为 1，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度 x，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度 y。小鸟位于横坐标方向不同位置时，上升的高度 x 和下降的高度 y 可能互不相同。

小鸟高度等于 0 或者小鸟碰到管道时，游戏失败。小鸟高度为 m 时，无法再上升。

现在,请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。

输入格式

第 1 行有 3 个整数 n, m, k，分别表示游戏界面的长度，高度和水管的数量，每两个整数之间用一个空格隔开；

接下来的 n 行，每行 2 个用一个空格隔开的整数 x 和 y，依次表示在横坐标位置 0 \sim n-1 上玩家点击屏幕后，小鸟在下一位置上升的高度 x，以及在这个位置上玩家不点击屏幕时，小鸟在下一位置下降的高度 y。

接下来 k 行，每行 3 个整数 p,l,h，每两个整数之间用一个空格隔开。每行表示一个管道，其中 p 表示管道的横坐标，l 表示此管道缝隙的下边沿高度，h 表示管道缝隙上边沿的高度（输入数据保证 p 各不相同，但不保证按照大小顺序给出）。

输出格式

共两行。

第一行，包含一个整数，如果可以成功完成游戏，则输出 1，否则输出 0。

第二行，包含一个整数，如果第一行为 1，则输出成功完成游戏需要最少点击屏幕数，否则，输出小鸟最多可以通过多少个管道缝隙。

输入输出样例 #1

输入 #1

输出 #1

1
6

输入输出样例 #2

输入 #2

输出 #2

0
3

说明/提示

【输入输出样例说明】

如下图所示，蓝色直线表示小鸟的飞行轨迹，红色直线表示管道。

【数据范围】

对于 30\% 的数据：5 \leq n \leq 10, 5 \leq m \leq 10, k=0，保证存在一组最优解使得同一单位时间最多点击屏幕 3 次；

对于 50\% 的数据：5 \leq n \leq 20, 5 \leq m \leq 10，保证存在一组最优解使得同一单位时间最多点击屏幕 3 次；

对于 70\% 的数据：5 \leq n \leq 1000, 5 \leq m \leq 100；

对于 100\% 的数据：5 \leq n \leq 10000，5 \leq m \leq 1000，0 \leq k < n，0 < x,y < m，0 < p < n，0 \leq l < h \leq m， l + 1 < h。

P5020 [NOIP 2018 提高组] 货币系统

题目背景

NOIP2018 提高组 D1T2

题目描述

在网友的国度中共有 n 种不同面额的货币，第 i 种货币的面额为 a[i]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 n、面额数组为 a[1..n] 的货币系统记作 (n,a)。

在一个完善的货币系统中，每一个非负整数的金额 x 都应该可以被表示出，即对每一个非负整数 x，都存在 n 个非负整数 t[i] 满足 a[i] \times t[i] 的和为 x。然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额 x 不能被该货币系统表示出。例如在货币系统 n=3, a=[2,5,9] 中，金额 1,3 就无法被表示出来。

两个货币系统 (n,a) 和 (m,b) 是等价的，当且仅当对于任意非负整数 x，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。

现在网友们打算简化一下货币系统。他们希望找到一个货币系统 (m,b)，满足 (m,b) 与原来的货币系统 (n,a) 等价，且 m 尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的 m。

输入格式

输入文件的第一行包含一个整数 T，表示数据的组数。

接下来按照如下格式分别给出 T 组数据。每组数据的第一行包含一个正整数 n。接下来一行包含 n 个由空格隔开的正整数 a[i]。

输出格式

输出文件共有 T 行，对于每组数据，输出一行一个正整数，表示所有与 (n,a) 等价的货币系统 (m,b) 中，最小的 m。

输入输出样例 #1

输入 #1

2
4
3 19 10 6
5
11 29 13 19 17

输出 #1

2
5

说明/提示

在第一组数据中，货币系统 (2, [3,10]) 和给出的货币系统 (n, a) 等价，并可以验证不存在 m < 2 的等价的货币系统，因此答案为 2。在第二组数据中，可以验证不存在 m < n 的等价的货币系统，因此答案为 5。

【数据范围与约定】

对于 100\% 的数据，满足 1 ≤ T ≤ 20, n,a[i] ≥ 1。