首页 > 代码库 > 20140712 总结

20140712 总结

2024-07-11 20:01:18   220人阅读

今天是钟神出的题，也是他讲的课，简直是，10多张ppt，除了第一张写着“数据结构”之外，没有一片没有提到HJA....

如果这都不是真爱...

哎，果然是钟神最业界良心，还给了数据范围...

想了很久的classic，想起了MiddleNum，然后发现自己连EasyNum都没过....然后我就放弃治疗了

然后第k短路...曾经以为要必须用A*才行...然后捉摸着反正写不来，我就暴力枚举一次边，看看能不能在k==2的时候骗个几分...

最后骗了0分....

 

 -----------------------------------------------------------------------------

Classic!

 (classic.pas/c/cpp)

 

【题目描述】

今天讲的数据结构题在后面。

Classic是一个极富创意的成果。

还记得我曾经给你们讲过的东西吗？

求L到R之间各位数字和在x到y之间的数的和对1,000,000,007取模的值。

 

【输入格式】

第一行一个整数L。

第二行一个整数R。

第三行两个整数x、y。

 

【输出格式】

一行一个整数代表答案。

 

【样例输入】

1

100

4 13

 

【样例输出】

3575

 

【数据范围与规定】

对于30%的数据，0≤L≤R≤103。

对于50%的数据，0≤L≤R≤109。

对于80%的数据，0≤L≤R≤1018。

对于100%的数据，0≤L≤R≤1050，0≤x≤y≤500。

 

题解：就是一个多mod几次的MiddleNum

 1 #define NOMBRE "classic" 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define LL "%I64d" 6  7 const int MOD = 1000000007; 8 const int MAXL = 60; 9 const int MAXS = 600;10 11 long long Pri, num[MAXL][MAXS][2][2], sum[MAXL][MAXS][2][2];12 char InputC;13 int x, y, a[MAXL][2], len[2];14 15 void Init(int cj){16     while ((InputC=getchar())!=‘\n‘)17         a[++len[cj]][cj] = InputC-48;18 19     num[1][0][1][cj] = 1;20     for (register int i=1; i<=len[cj]; i++)21         for (register int j=0; j<=i*9; j++){22             for (register int l=0; l<=9; l++)23                 (num[i+1][j+l][0][cj] += num[i][j][0][cj]%MOD) %= MOD,24                 (sum[i+1][j+l][0][cj] += sum[i][j][0][cj]*10%MOD+l*num[i][j][0][cj]%MOD) %= MOD;25             for (register int l=0; l<=a[i][cj]; l++)26                 (num[i+1][j+l][l==a[i][cj]][cj] += num[i][j][1][cj]%MOD) %+ MOD,27                 (sum[i+1][j+l][l==a[i][cj]][cj] += sum[i][j][1][cj]*10%MOD+l*num[i][j][1][cj]%MOD) %= MOD;28         }29 }    30 31 int main(){32     freopen(NOMBRE ".in", "r", stdin);33     freopen(NOMBRE ".out", "w", stdout);34 35     memset(a, 0, sizeof(a));36     memset(len, 0, sizeof(len));37     memset(num, 0, sizeof(num));38     memset(sum, 0, sizeof(sum));39     40     Init(0), Init(1);41     scanf("%d %d", &x, &y);42 43     for (register int i=x; i<=y; i++)44         Pri = (Pri+sum[len[1]+1][i][0][1]+sum[len[1]+1][i][1][1]-sum[len[0]+1][i][0][0]-sum[len[0]+1][i][1][0])%MOD;45 46     long long Ts = 0, Ta = 0;47     for (int i=1; i<=len[0]; i++)48         Ts += a[i][0], Ta = (Ta*10+a[i][0])%MOD;49     if (x<=Ts && Ts<=y) Pri = (Pri+Ta)%MOD;50     while (Pri<0) Pri += MOD;51 52     printf(LL "\n", Pri);53 }

 


联系
我们