今天是钟神出的题，也是他讲的课，简直是，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())!='
')
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 "
", Pri);
53 }
-----------------------------------------------------------------------------
Justice!
(justice.pas/c/cpp)
【题目描述】
还在后面一些。
Justice是少见的一款长篇。
求1-N的第K短路。（非严格，详见样例）
【输入格式】
第一行两个整数N、M、K代表图的点数、边数和
要求的K。
接下来M行，每行三个整数S、E、D，代表S与E之间有一条长度为D的无向边。
【输出格式】
一行一个整数代表第K短路。
【样例输入1】
2 1 2
1 2 1
【样例输出1】
3
【样例输入2】
2 2 2
1 2 1
1 2 1
【样例输出2】
1
【数据范围与规定】
对于20%的数据，1≤N,M≤102。
对于另外30%的数据，K=1。
对于另外20%的数据，K=2。
对于100%的数据，1≤N,M≤105，1≤K≤20，边的权值在103以内。
题解：钟神大法好呀！
用dis[i][k]表示到i点的第k短路，更新的时候都更一次就好了
1 #define NOMBRE "justice"
2 #include <cstdio>
3 #include <cstring>
4
5 const int MAXK = 20+10;
6 const int MAXN = 1e5+10;
7 const int MAXQ = 2*1e6;
8
9 int n, m, k, dis[MAXN][MAXK], q[MAXQ+10][2];
10 bool use[MAXN][MAXK];
11
12 struct Edge{
13 int to, d;
14 Edge *next;
15 }e[MAXN*2], *head[MAXN];
16
17 int ne = 0;
18 inline void AddEdge(int f,int to, int d){
19 e[ne].to = to, e[ne].d = d;
20 e[ne].next = head[f];
21 head[f] = e+ne++;
22 }
23
24 inline int SPFA(){
25 memset(dis, 0x3f, sizeof(dis));
26 dis[1][1] = 0, q[1][0] = q[1][1] = 1;
27
28 int _Tail = 2, _Head = 1, Now, Kth, New;
29 while (_Head!=_Tail){
30 Now = q[_Head][0], Kth = q[_Head][1], use[Now][Kth] = false;
31 if (++_Head==MAXQ) _Head = 0;
32
33 for (register Edge *p=head[Now]; p; p=p->next){
34 New = p->d+dis[Now][Kth];
35 for (register int i=1; i<=k; i++)
36 if (New<=dis[p->to][i]){
37 //Recover
38 for (register int j=k; j>i; j--)
39 dis[p->to][j] = dis[p->to][j-1];
40 dis[p->to][i] = New;
41
42 for (register int j=i; j<=k; j++)
43 if (not use[p->to][j]){
44 use[p->to][j] = true;
45 q[_Tail][0] = p->to, q[_Tail][1] = j;
46 if (++_Tail==MAXQ) _Tail = 0;
47 }
48 break;
49 }
50 }
51 }
52 return dis[n][k];
53 }
54
55 int main(){
56 freopen(NOMBRE ".in", "r", stdin);
57 freopen(NOMBRE ".out", "w", stdout);
58
59 scanf("%d %d %d", &n, &m, &k);
60 int u, v, d;
61 while (m--)
62 scanf("%d %d %d", &u, &v, &d),
63 AddEdge(u, v, d), AddEdge(v, u, d);
64
65 printf("%d
", SPFA());
66 }