专栏文章

CSP-S

DDiaoHantong
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mintrns9
此快照首次捕获于
2025/12/02 08:13
3 个月前
此快照最后确认于
2025/12/02 08:13
3 个月前
查看原文

P3205 [HNOI2010] 合唱队

题目描述

为了在即将到来的晚会上有更好的演出效果，作为 AAA 合唱队负责人的小 A 需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共 nn 个人，第 ii 个人的身高为 hih_i 米（1000≤hi≤20001000 \le h_i \le 2000），并已知任何两个人的身高都不同。假定最终排出的队形是 AA 个人站成一排，为了简化问题，小 A 想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按以下原则依次将每个人插入最终排出的队形中：
  • 第一个人直接插入空的当前队形中。
  • 对从第二个人开始的每个人，如果他比前面那个人高（hh 较大），那么将他插入当前队形的最右边。如果他比前面那个人矮（hh 较小），那么将他插入当前队形的最左边。
当 nn 个人全部插入当前队形后便获得最终排出的队形。
例如，有 66 个人站成一个初始队形，身高依次为 1850,1900,1700,1650,1800,17501850, 1900, 1700, 1650, 1800, 1750，
那么小 A 会按以下步骤获得最终排出的队形：
  • 18501850。
  • 1850,19001850, 1900，因为 1900>18501900 > 1850。
  • 1700,1850,19001700, 1850, 1900，因为 1700<19001700 < 1900。
  • 1650,1700,1850,19001650, 1700, 1850, 1900，因为 1650<17001650 < 1700。
  • 1650,1700,1850,1900,18001650, 1700, 1850, 1900, 1800，因为 1800>16501800 > 1650。
  • 1750,1650,1700,1850,1900,18001750, 1650, 1700, 1850, 1900, 1800，因为 1750<18001750 < 1800。
因此，最终排出的队形是 1750,1650,1700,1850,1900,18001750, 1650, 1700, 1850, 1900, 1800。
小 A 心中有一个理想队形，他想知道多少种初始队形可以获得理想的队形。
请求出答案对 1965082719650827 取模的值。

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

CPP
4
1701 1702 1703 1704

输出 #1

CPP
8

说明/提示

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

P4302 [SCOI2003] 字符串折叠

题目描述

折叠的定义如下：
  1. 一个字符串可以看成它自身的折叠。记作 S = S
  2. X(S) 是 XX 个 S 连接在一起的串的折叠。记作 X(S) = SSSS…S。
  3. 如果 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，长度保证不超过 100100。

输出格式

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

输入输出样例 #1

输入 #1

CPP
NEERCYESYESYESNEERCYESYESYES

输出 #1

CPP
14

说明/提示

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

P2470 [SCOI2007] 压缩

题目描述

给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。
bcdcdcdcd 可以压缩为 bMcdRR，下面是解压缩的过程：
已经解压的部分解压结果缓冲串
bbb
bMb.
bMcbcc
bMcdbcdcd
bMcdRbcdcdcdcd
bMcdRRbcdcdcdcdcdcdcdcd

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

CPP
aaaaaaa

输出 #1

CPP
5

输入输出样例 #2

输入 #2

CPP
bcdcdcdcdxcdcdcdcd

输出 #2

CPP
12

说明/提示

在第一个例子中，解为aaaRa，在第二个例子中，解为bMcdRRxMcdRR。
【限制】
50%的数据满足：1<=n<=20
100%的数据满足：1<=n<=50

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

题目背景

NOIP2014 提高组 D1T3

题目描述

Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。
为了简化问题，我们对游戏规则进行了简化和改编:
游戏界面是一个长为 nn，高为 mm 的二维平面，其中有 kk 个管道（忽略管道的宽度）。
小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。
小鸟每个单位时间沿横坐标方向右移的距离为 11，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度 xx，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度 yy。小鸟位于横坐标方向不同位置时，上升的高度 xx 和下降的高度 yy 可能互不相同。
小鸟高度等于 00 或者小鸟碰到管道时，游戏失败。小鸟高度为 mm 时，无法再上升。
现在,请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。

输入格式

第 11 行有 33 个整数 n,m,kn, m, k，分别表示游戏界面的长度，高度和水管的数量，每两个整数之间用一个空格隔开；
接下来的 nn 行，每行 22 个用一个空格隔开的整数 xx 和 yy，依次表示在横坐标位置 0∼n−10 \sim n-1 上玩家点击屏幕后，小鸟在下一位置上升的高度 xx，以及在这个位置上玩家不点击屏幕时，小鸟在下一位置下降的高度 yy。
接下来 kk 行，每行 33 个整数 p,l,hp,l,h，每两个整数之间用一个空格隔开。每行表示一个管道，其中 pp 表示管道的横坐标，ll 表示此管道缝隙的下边沿高度，hh 表示管道缝隙上边沿的高度（输入数据保证 pp 各不相同，但不保证按照大小顺序给出）。

输出格式

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

输入输出样例 #1

输入 #1

CPP
10 10 6 
3 9  
9 9  
1 2  
1 3  
1 2  
1 1  
2 1  
2 1  
1 6  
2 2  
1 2 7 
5 1 5 
6 3 5 
7 5 8 
8 7 9 
9 1 3

输出 #1

CPP
1
6

输入输出样例 #2

输入 #2

CPP
10 10 4 
1 2  
3 1  
2 2  
1 8  
1 8  
3 2  
2 1  
2 1  
2 2  
1 2  
1 0 2 
6 7 9 
9 1 4 
3 8 10

输出 #2

CPP
0
3

说明/提示

【输入输出样例说明】
如下图所示，蓝色直线表示小鸟的飞行轨迹，红色直线表示管道。
【数据范围】
对于 30%30\% 的数据：5≤n≤10,5≤m≤10,k=05 \leq n \leq 10, 5 \leq m \leq 10, k=0，保证存在一组最优解使得同一单位时间最多点击屏幕 33 次；
对于 50%50\% 的数据：5≤n≤20,5≤m≤105 \leq n \leq 20, 5 \leq m \leq 10，保证存在一组最优解使得同一单位时间最多点击屏幕 33 次；
对于 70%70\% 的数据：5≤n≤1000,5≤m≤1005 \leq n \leq 1000, 5 \leq m \leq 100；
对于 100%100\% 的数据：5≤n≤100005 \leq n \leq 10000，5≤m≤10005 \leq m \leq 1000，0≤k<n0 \leq k < n，0<x,y<m0 < x,y < m，0<p<n0 < p < n，0≤l<h≤m0 \leq l < h \leq m， l+1<hl + 1 < h。

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

题目背景

NOIP2018 提高组 D1T2

题目描述

在网友的国度中共有 nn 种不同面额的货币，第 ii 种货币的面额为 a[i]a[i]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 nn、面额数组为 a[1..n]a[1..n] 的货币系统记作 (n,a)(n,a)。
在一个完善的货币系统中，每一个非负整数的金额 xx 都应该可以被表示出，即对每一个非负整数 xx，都存在 nn 个非负整数 t[i]t[i] 满足 a[i]×t[i]a[i] \times t[i] 的和为 xx。然而， 在网友的国度中，货币系统可能是不完善的，即可能存在金额 xx 不能被该货币系统表示出。例如在货币系统 n=3n=3, a=[2,5,9]a=[2,5,9] 中，金额 1,31,3 就无法被表示出来。
两个货币系统 (n,a)(n,a) 和 (m,b)(m,b) 是等价的，当且仅当对于任意非负整数 xx，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。他们希望找到一个货币系统 (m,b)(m,b)，满足 (m,b)(m,b) 与原来的货币系统 (n,a)(n,a) 等价，且 mm 尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的 mm。

输入格式

输入文件的第一行包含一个整数 TT，表示数据的组数。
接下来按照如下格式分别给出 TT 组数据。 每组数据的第一行包含一个正整数 nn。接下来一行包含 nn 个由空格隔开的正整数 a[i]a[i]。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

CPP
2
5

说明/提示

在第一组数据中，货币系统 (2,[3,10])(2, [3,10]) 和给出的货币系统 (n,a)(n, a) 等价，并可以验证不存在 m<2m < 2 的等价的货币系统，因此答案为 22。 在第二组数据中，可以验证不存在 m<nm < n 的等价的货币系统，因此答案为 55。
【数据范围与约定】
对于 100%100\% 的数据，满足 1≤T≤20,n,a[i]≥11 ≤ T ≤ 20, n,a[i] ≥ 1。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...