[关闭]
@P2Oileen 2017-09-17T06:43:10.000000Z 字数 2753 阅读 347

七校模拟题目

day1

Problem A. Count(count.c/cpp/pas)

Input file: count.in
Output file: count.out
Time limit: 1 seconds
Memory limit: 512 megabytes
给定n,求合法的 组数。一组x 是合法的,当且仅当

• 累乘
合法的可能有很多,请你输出方案数mod 998244353。
Input
一行由空格隔开的两个整数,分别是n 和m。
Output
一行表示答案。
Examples

count.in count.out
6 1 10
6 3 2248

第一个样例中,合法的方案有共10种。
Notes
• Subtask1; 17pts 满足n ≤ 50,m = 2.
• Subtask2; 28pts 满足n ≤ 100,m ≤ 3.
• Subtask3; 55pts 满足n ≤ 109,m ≤ 100.

qyj大佬那天给了一个很奇妙的思路:打表找规律……
还真的找到了orz 很强很强 不管怎么样就这么莫名其妙的AC了
题解的思路很复杂……好讨厌 不管了


Problem B. Delete(delete.c/cpp/pas)

Input file: delete.in
Output file: delete.out
Time limit: 2 seconds
Memory limit: 512 megabytes
给定一个序列,你需要通过不断的操作来消除这个序列。每次你可以选择一个上升或者下降子序列将其删除,将剩下的序列作为新序列,继续删除操作。直到新序列为空,操作结束。
具体得说,一次操作可以表述为如下较为形式的语言:对于一个序列(x1; x2; :::; xn),一次操作可以选择1 ≤ a1 < a2 < … < ak ≤ n,将xa1 ; xa2 ; ... ; xak删去。其中k 和ai 都是你可以决定的,但是必须要满足xa1 < xa2 < ... < xak,或者xa1 > xa2 > ... > xak。
我们希望你在500 次内将序列删空,请你输出任意一种删除序列的方式,数据保证一定存在解。
为了方便起见,保证(x1; x2; :::; xn) 是一个1::n 的排列。
Input
第一行包含一个正整数n。第二行n 个数,ai。
Output
输出第一行,d 表示删除序列的次数。
接下来d 行,每行第一个整数qi,表示第qi 次操作删除的元素个数。紧接着qi 个元素,ti;j 表示第i 次删除操作中,删除的第j 个元素。
Examples

delete.in
3
1 3 2
2
delete.out
2 1 2
1 3

Notes
• Subtask1; 10pts 满足n ≤ 1000.
• Subtask2; 24pts 满足n ≤ 50000.
• Subtask3; 66pts 满足n ≤ 64000.

500次足够把这个序列删空了……每次贪心地选择最长的子序列再删去就可以了orz
就是在选子序列的时可以用线段树维护一下,能把原来O(n^2)的算法变成nlogn
wyj暴力AC%%%


Problem C. Floor it(floor.c/cpp/pas)

Input file: floor.in
Output file: floor.out
Time limit: 1 seconds
Memory limit: 512 megabytes
,求
Input
一行由空格隔开的两个非负整数,分别是n 和p。
Output
一行表示答案。
Examples

floor.in floor.out
5 97 11

Notes
• Subtask1; 1pts 满足n ≤ 1018; p = 1.
• Subtask2; 15pts 满足n ≤ 20; p ≤ 998244353.
• Subtask3; 51pts 满足n ≤ 106; p ≤ 998244353.
• Subtask4; 33pts 满足n ≤ 1018; p ≤ 998244353.

万物皆可斐波那契……


day2

排列(permutation)

【题目描述】
给定一个n*n 的矩阵f,你需要求出有多少个1~n 的排列x 满足对于1<=i≠j<=n,均有f[i,j]=min(x[i],x[j]),并输出字典序最小的一个。
有多组数据。
【输入数据】
第一行一个整数t 表示数据组数。
每组数据第一行一个正整数n。接下来n 行每行n 个整数,第i行第j 列的整数表示f[i,j]。
【输出数据】
对于每组数据,如果不存在这样的排列,输出一行一个整数-1。
否则输出两行,第一行一个整数表示排列个数对998244353 取模的结果,第二行n 个整数表示字典序最小的排列。
【样例输入】
1
2
0 1
1 0
【样例输出】
2
1 2
【数据范围】
对于20%的数据,n<=8。
对于60%的数据,n<=40。
对于100%的数据,t<=10,Σn<=2000,=0,1<=<=n。
各档数据中均有一半保证全部有解。

最开始我的思路很常规……但是显然无法确定值,于是我暴力了
看了题解发现可以从n开始往前推 很有道理啊,这样就能确定元素了……


字符串(string)

【题目描述】
定义两个字符串A,B 相似当且仅当满足以下两个条件中的至少一个:
(1)A 和B 相同;
(2)将A 分为长度相同的两个子串A0,A1,将B 分为长度相同的两个子串B0,B1,满足A0 相似于B0,A1 相似于B1 或A0 相似于B1,A1 相似于B0。
给定两个字符串S,T,问它们是否相似。
有多组数据。
【输入数据】
第一行一个整数t 表示数据组数。
每组数据第一行一个字符串S,第二行一个字符串T,保证它们长度相同。
【输出数据】
每组数据一行,若相似输出YES,不相似输出NO。
【样例输入】
2
abab
baab
aabb
abab
【样例输出】
YES
NO
【数据范围】
对于30%的数据,
对于60%的数据,
对于100%的数据,

能看出相似的传递性。a相似于c,b相似于c,则a相似于b
所以分别找到和两个字符串相似的字典序最小的字符串,如果相同则输出YES


数(number)

【题目描述】
给定正整数n,m,问有多少个正整数满足:
(1)不含前导0;
(2)是m 的倍数;
(3)可以通过重排列各个数位得到n。
【输入数据】
一行两个整数n,m。
【输出数据】
一行一个整数表示答案对998244353 取模的结果。
【样例输入】
1 1
【样例输出】
1
【数据范围】
对于20%的数据,n<10^10。
对于50%的数据,n<10^16,m<=20。
对于100%的数据,n<10^20,m<=100。

状压记录0 到9 剩余个数以及mod m 的值的情况下的方
案数。转移时枚举最高位填的数字,最后一次转移不要枚
举0。


添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注