【EOJ Monthly 2018.12 - A，B，C】套题训练，部分题解

A.

题干：

A. 仰望星空

单测试点时限: 2.0 秒

内存限制: 512 MB

你就这样静坐在草地上，离我稍远的地方。
我用眼角瞅着你，你什么话也别说。
语言是误会的根源。
但是，每天，你可以坐得离我近一些……

你和她一起仰头仰望着布满星辰的天空。你的星星对她而言只不过是众星中的一颗。

她会喜欢仰望天际所有的繁星，他们都会是她的朋友。但你深信你不会是万众中一颗毫不起眼的星星。

于是你默默地记录着每天你们仰望星空时的距离，你发现每天你们的距离或许减少、或许不变，但一定不会增加。

可是你们在一起仰望星空的日子太长了，长到你只记得你们第一天在星空下的距离。

今天，你们的距离是 A ；你们又在一起仰望星空了。你却突然想知道一起仰望星空 N 天来，你们之间的距离之和。

由于你已经不记得每天的距离，只能依稀记起第一天的距离是 B ，所以你只想知道你们这么多天来的距离之和有多少种不同的可能性。

输入

输入数据包含一行，包含三个整数 N,A,B (2≤N≤109,1≤A≤B≤109 )，分别表示你们一起仰望星空的天数、今天你们之间的距离以及第一天你们之间的距离。

输出

输出数据包含一行一个整数，表示不同可能和的个数。

样例

Input

3 1 2

Output

2

提示

对于样例有以下几种不同的距离情况：{2,1,1},{2,2,1} ；他们的和分别是 4 和 5 ，所以有两种不同的和。

解题报告：

  不算思维的思维题啊，，贪心出最大的可能取值和最小的可能取值就行了。

AC代码：

#include
#include
#include
#include
#include

（不少人没开longlong所以WA？？）

B.

  好像是蒙特卡洛模拟，，据说随机数也能过。。明天补补吧。。

C.

题干：

C. 她的名字

单测试点时限: 4.0 秒

内存限制: 512 MB

“他走过一个又一个星球，
却始终放不下对她的思念。“
”深情终究是一趟孤独的旅程，
她是他永远的牵绊。”

我们每个人心中都有一只小狐狸。我们渴望被自己喜欢的人驯服。

爱情是彼此之间至为甜蜜的臣服。我们都是傻痴痴的小狐狸，徒具一副精明的外表。

就像你走到哪都挂念着她，想把她写进自己的歌里，成为你们共同的记忆。

你想从她全部由数字构成的名字里取出其中的 N 个数字，维持原来的顺序，组成结尾为数字 XY 的新词。

你自然希望自己的歌能够很长很长，歌词的每一句都能饱含甜蜜。

所以你想知道，她的名字能够组成多少个长度为 N 且结尾为数字 XY 的新词（如果从她名字中取出的任意一个数字位置不同，两个词就被认为是不同的）。

输入

第一行包含一个由数字构成的字符串 S (1≤|S|≤2 000 )。

第二行包含一个整数 Q (1≤Q≤5⋅105 )，表示需要选择的不同结尾数量。

接下来的 Q 行，每行包含了一个整数 N (1≤N≤5⋅105 ) 和两个数字 XY ，用空格隔开，表示需要选择的歌词的长度和结尾。

输出

对于每一个询问，输出一个整数，表示答案。

答案可能会很大，你只需要输出对于 109+7 取模后的结果。

样例

Input

312121
4
2 21
3 31
4 22
3 22

Output

3
0
1
2

提示

样例中第一个询问：312121, 312121, 312121.

第二个询问：无。

第三个询问：312121.

解题报告：

   就是个dp[i][j][k]，，两边预处理，，第一遍出状态的个数，第二遍出答案，然后O(1)输出就行了。

AC代码：

#include
#include
#include
#include
#include

注意N给到了1e5，，所以需要特判一波是否大于字符串长度，如果大于了直接输出0就行了，不然肯定RE啊，，

不过据说这题标解不是n^2*100的做法的。。改天再想想、、

这题WYZ大佬还有个别的做法，，从后往前 枚举每一个X，同时记录Y的个数，然后输出答案同时记录，因为查询次数过多，，肯定有重复查询，所以类似记忆化搜索那样记录答案，，貌似也过了。Orz

DEF不会，，其实E还可以做做的，，然后F是个SAM好像是，，目前也不会。

总之这场比赛写题半小时挂机一个半小时，，题目跨度忒大了点。。两题后就没可做题了。。可能还是苔菜了吧。。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！