CSP-J难度模拟赛(复现)
题目 | ||||
---|---|---|---|---|
Time limit | 1000ms | 1000ms | 1000ms | 1000ms |
Memory limit | 256MiB | 512MiB | 512MiB | 512MiB |
输入输出 | 传统题 | 传统题 | 传统题 | 传统题 |
题目 | |
---|---|
Time limit | 2000ms |
Memory limit | 512MiB |
输入输出 | 传统题 |
A. 分糖果
题目描述
小明所在的幼儿园有个小朋友,第个小朋友有颗糖。
今天,幼儿园老师要选一些三人小组出去吃糖。如果一个小组的三个小朋友所带的糖的总数恰好是的倍数,那么这三个小朋友分到的糖是一样的,都会感到开心。
每个小朋友只能参加最多一个小组(也可以不参加)。
请帮助幼儿园老师组成最多的小组,使得每个小组的小朋友都是开心的。
输入格式
第一行输入。
第二行输入个数,。
输出格式
第一行输出,表示最多能组成多少组。
接下来行,每行三个数字,表示这一组三个小朋友的编号。
如果有多解,输出任意一种方案即可。
样例输入 #1
3
1 2 5
样例输出 #1
0
样例输入 #2
6
1 2 3 1 5 6
样例输出 #2
2
3 1 2
6 4 5
数据范围
对于30%的数据:。
对于100%的数据:。
B. 乒乓球
题目描述
小明和小红在打乒乓球比赛。
规则是这样的:对于每一颗球,如果小红赢,小红得一分,如果小明赢,小明得一分。谁的得分首先大于等于分,且比对方的得分高出至少分,则赢得此局比赛。
在记录了颗球的胜负关系后,聪明的裁判员大翼发现:对于任意第颗球来说,第颗球的胜负关系,与第颗球的胜负关系一模一样。因此,大翼只记录了前颗球的胜负关系。
然而,在记录完毕后,他发现一个重要的问题:他忘记统计两个人分别赢了几局了!
这真是好尴尬啊。还是请你帮他还原一下最终的结果吧!
输入格式
第一行输入,如题所述。
接下来一行一个长度为的字符串,第个字符是A
表示第局小明赢了,B
表示第局小红赢了。
输出格式
第一行输出两个整数X:Y
,分别表示最后小明/小红赢了几局。
样例输入 #1
20 3
AAB
样例输出 #1
1:0
样例解释 #1
最终的序列实际上是AABAABAABAABAABAABAA
,在第颗球结束时,小明和小红的部分是,小明赢得一局。在颗球记录完毕时,当前比分是。
样例输入 #2
1000 6
AABBAB
样例输出 #2
24:23
数据范围
对于5%的数据:字符串中只包含A
。
对于30%的数据:。
对于另外30%的数据:保证无论是谁得分到达分时,必定取得这局的胜利。
对于另外15%的数据:保证是的倍数。
对于100%的数据:。
C. 与或
题目描述
小明,没错又是小明。
他有一个长度为的数组,还有个运算符|
以及个运算符&
。此处and
和or
就是二进制下的与以及或操作。
小明需要把这个数用上述个符号从左到右连接起来,然后从左到右计算结果。
显然,不同的安排方式可能导致不同的结果。
例如 ,有一个&
和一个|
,那么如果是1&2|5
,结果是,如果是1|2 &5
,结果是。
小明希望得到最大的结果,在这个基础上,希望整个表达式的字典序尽量小(此处|
的字典序小于&
),请帮助小明计算最小的字典序。
输入格式
第一行输入。
接下来一行输入个正整数表示。
输出格式
第一行输出最大的结果。
第二行输出一个字符串表示字典序最小的符号序列。
样例输入 #1
4 2
1 3 5 7
样例输出 #1
7
||&
样例解释 #1
三种不同的符号序列产生的结果:
||&=7,|&|=7,&||=7
。
都是,||&
字典序最小。
样例输入 #2
4 1
1 3 5 7
样例输出 #2
7
&&|
样例解释 #3
三种不同的符号序列产生的结果:
&&|=7,&|&=5,|&&=1
。
数据范围
对于30%的数据:。
对于另30%的数据:。
对于另10%的数据:。
对于100%的数据:。
D. 跳舞
题目描述
小明在家打游戏,楼下在跳广场舞,吵死了。
有个舞者排成一排,第个舞者的属性是。
在每一刻,一个人可以邀请自己左侧或者右侧相邻的人跳舞,如果这两个人的属性的最大公约数,则这个人很开心,然后会开心回家睡觉。此时,他离开了跳舞的队列,他左右侧的两个人现在相邻了。
广场舞可太吵了,问:假设小明可以安排跳舞的顺序,最多能让多少个人回家睡觉!
输入格式
第一行输入。
接下来一行输入个正整数表示。
输出格式
一个数字表示答案。
样例输入 #1
5
1 6 3 2 4
样例输出 #1
3
样例解释 #1
让先跟跳舞,跳完走人。让跟跳舞,跳完走人。让跟跳舞,跳完走人。
剩下俩人,分别属性是,他俩去广场上站着吧。
样例输入 #2
6
6 2 3 4 15 9
样例输出 #2
5
数据范围
对于30%的数据:。
对于70%的数据:。
对于100%的数据:。
E. 音乐播放器
题目描述
赵喜娜有一个音乐播放器(赛后回家看)。
他的音乐播放器里面一共有首歌,赵喜娜对第首歌的喜爱程度是。
赵喜娜今天选择了随机播放模式,具体地:
他的播放器会随机播放一首歌,等这首歌结束后,会继续随机播放下一首歌(不排除这首歌跟刚那首歌一样的可能性)。
当赵喜娜首次听到第首歌的时候,他的愉悦程度会增加,第二次及以后听到,则没有反应了。
当赵喜娜听完某首歌后,总的愉悦程度,赵喜娜就会开心的关掉播放器,完成今天的听歌。
问:赵喜娜听到的最后一首歌是第首歌的概率是多少?
可以证明结果一定可以被化简为一个分数,你需要输出。
提示:解此题的时候也许你可能不得不在意义下除以一个数字(此处是质数),那么你就需要逆元这个东西。
如果你不会逆元的话,简单介绍一下逆元:
假设你现在需要求的结果,比如,如果你直接每步计算的话,答案是。但实际上结果显然是。
所以你需要更高级的东西,费马小定理:假设有质数以及非负整数,那么。也就是说,实际上就是意义下的数字。
那么就可以写成。反正乘以等于没乘对吧。
也就是说,我们如果要的话,可以当成要乘以。
就是在意义下的逆元。
输入格式
第一行输入。
接下来一行输入个正整数表示。
输出格式
个数字表示答案。
样例输入 #1
4 3
1 2 3 4
样例输出 #1
582309206 582309206 915057324 915057324
样例解释 #1
想要以结尾或者以结尾,赵喜娜必须只听到歌和歌。
那么听歌序列只能是或者是这样。
的概率是。
的概率是。
的概率是。
...
所以最终以结尾的概率是。
以结尾的概率同样是。
在意义下是。
以和结尾的概率一样,都是。
样例输入 #2
4 7
1 2 3 4
样例输出 #2
582309206 582309206 748683265 83187030
数据范围
对于15%的数据:。
对于40%的数据:。
对于60%的数据:。
对于另10%的数据:只有两种取值。
对于85%的数据:。
对于100%的数据:$n\leq 100,S\leq 10000,1\leq a_i\leq S,\sum a_i \geq S$。