做汽车团购网站有哪些,wordpress老版本号,深圳网站建设建设,新手学做网站pdf手A.
题干#xff1a;
A. 仰望星空
单测试点时限: 2.0 秒
内存限制: 512 MB 你就这样静坐在草地上#xff0c;离我稍远的地方。 我用眼角瞅着你#xff0c;你什么话也别说。 语言是误会的根源。 但是#xff0c;每天#xff0c;你可以坐得离我近一些…… 你和她一起仰头…A.
题干
A. 仰望星空
单测试点时限: 2.0 秒
内存限制: 512 MB 你就这样静坐在草地上离我稍远的地方。 我用眼角瞅着你你什么话也别说。 语言是误会的根源。 但是每天你可以坐得离我近一些…… 你和她一起仰头仰望着布满星辰的天空。你的星星对她而言只不过是众星中的一颗。
她会喜欢仰望天际所有的繁星他们都会是她的朋友。但你深信你不会是万众中一颗毫不起眼的星星。
于是你默默地记录着每天你们仰望星空时的距离你发现每天你们的距离或许减少、或许不变但一定不会增加。
可是你们在一起仰望星空的日子太长了长到你只记得你们第一天在星空下的距离。
今天你们的距离是 A 你们又在一起仰望星空了。你却突然想知道一起仰望星空 N 天来你们之间的距离之和。
由于你已经不记得每天的距离只能依稀记起第一天的距离是 B 所以你只想知道你们这么多天来的距离之和有多少种不同的可能性。
输入
输入数据包含一行包含三个整数 N,A,B (2≤N≤109,1≤A≤B≤109 )分别表示你们一起仰望星空的天数、今天你们之间的距离以及第一天你们之间的距离。
输出
输出数据包含一行一个整数表示不同可能和的个数。
样例
Input
3 1 2Output
2提示
对于样例有以下几种不同的距离情况{2,1,1},{2,2,1} 他们的和分别是 4 和 5 所以有两种不同的和。
解题报告 不算思维的思维题啊贪心出最大的可能取值和最小的可能取值就行了。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
ll n,a,b;
int main()
{cinnab;ll minn a*(n-1) b;ll maxx a b*(n-1);printf(%lld\n,maxx-minn1);return 0 ;}不少人没开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 用空格隔开表示需要选择的歌词的长度和结尾。
输出
对于每一个询问输出一个整数表示答案。
答案可能会很大你只需要输出对于 1097 取模后的结果。
样例
Input
312121
4
2 21
3 31
4 22
3 22Output
3
0
1
2提示
样例中第一个询问312121, 312121, 312121.
第二个询问无。
第三个询问312121.
解题报告 就是个dp[i][j][k]两边预处理第一遍出状态的个数第二遍出答案然后O(1)输出就行了。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
const ll mod 1e9 7;
int q;
char s[MAX];
ll dp[12][12][4005],qq[12][12],yong[12][12][4005];
ll C[2005][2005];
void init() {C[0][0]1;for(int i1; i2001; i) {C[i][0]1;for(int j1; ji; j) {C[i][j](C[i-1][j-1]C[i-1][j])%mod;}}
}
int main()
{init();cin(s1);int n strlen(s1);if(n 1) {int q,len,x,y;scanf(%d,q);while(q--) {scanf(%d,len);scanf(%1d%1d,x,y);printf(0\n);} return 0 ;}for(int i 1; in; i) {for(int j i1; jn; j) {dp[s[i]-0][s[j]-0][i-1];dp[s[i]-0][s[j]-0][i-1]%mod;qq[s[i]-0][s[j]-0] (qq[s[i]-0][s[j]-0] 1) % mod;//以ij为尾的数有多少种. }}for(int x 0; x9; x) {for(int y 0; y9; y) {for(int i 0; in; i) {//记录直接用 for(int j i; jn; j)yong[x][y][i] (C[j][i] * dp[x][y][j])%mod;}}}cinq;int x,y,len;while(q--) {scanf(%d,len);len-2;scanf(%1d%1d,x,y);if(len2 n) {puts(0);continue;}if(len 0) {printf(%lld\n,qq[x][y]%mod); continue;}if(len 0) {puts(0);continue;}printf(%lld\n,yong[x][y][len]%mod);}return 0 ;}注意N给到了1e5所以需要特判一波是否大于字符串长度如果大于了直接输出0就行了不然肯定RE啊
不过据说这题标解不是n^2*100的做法的。。改天再想想、、
这题WYZ大佬还有个别的做法从后往前 枚举每一个X同时记录Y的个数然后输出答案同时记录因为查询次数过多肯定有重复查询所以类似记忆化搜索那样记录答案貌似也过了。Orz DEF不会其实E还可以做做的然后F是个SAM好像是目前也不会。
总之这场比赛写题半小时挂机一个半小时题目跨度忒大了点。。两题后就没可做题了。。可能还是苔菜了吧。。
