7月12日
1.classic
总时间限制:
20000ms
内存限制:
256000kB
描述
今天讲的数据结构题在后面。
Classic是一个极富创意的成果。
还记得我曾经给你们讲过的东西吗？
求L到R之间各位数字和在x到y之间的数的和对1,000,000,007取模的值。
输入
第一行一个整数L。
第二行一个整数R。
第三行两个整数x、y。
输出
一行一个整数代表答案。
样例输入
1
100
4 13
样例输出
3575
提示
对于30%的数据，0≤L≤R≤10^3。
对于50%的数据，0≤L≤R≤10^9。
对于80%的数据，0≤L≤R≤10^18。
对于100%的数据，0≤L≤R≤10^50，0≤x≤y≤500。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#define PROC "classic"
#define LL long long
using namespace std;
const int maxlen = 70;
const int maxsum = 505;
const LL mo = 1000000007;
LL cnt[maxlen][maxsum][2];
LL dp[maxlen][maxsum][2];
int l[maxlen],r[maxlen],lenl,lenr,x,y;
long long deal(int now[maxlen],int len)
{
LL ans = 0;
memset(cnt,0,sizeof(cnt));
memset(dp,0,sizeof(dp));
for (int i = 0;i<now[1];i++)
cnt[1][i][0] = 1,dp[1][i][0] = i % mo;
cnt[1][now[1]][1] = 1,dp[1][now[1]][1] = now[1] % mo;
int nowsum = 0;
for (int i = 1;i<len;i++)
{
nowsum +=now[i];
for (int k = 0;k<=i*9;k++)
for (int j = 0;j<10;j++)
cnt[i+1][k+j][0]=(cnt[i+1][k+j][0] % mo+cnt[i][k][0] % mo) % mo;
for (int j = 0;j<now[i+1];j++)
cnt[i+1][nowsum+j][0]=(cnt[i+1][nowsum+j][0] % mo+cnt[i][nowsum][1]) % mo;
cnt[i+1][nowsum+now[i+1]][1]=(cnt[i+1][nowsum+now[i+1]][1] % mo+cnt[i][nowsum][1]) % mo;
}
nowsum = 0;
for (int i = 1;i<len;i++)
{
nowsum +=now[i];
for (int k = 0;k<=9*i;k++)
for (int j = 0;j<=9;j++)
dp[i+1][k+j][0]=(dp[i+1][k+j][0] % mo+((LL)dp[i][k][0]*10 % mo + j*cnt[i][k][0]%mo) % mo) % mo;
for (int j = 0;j<now[i+1];j++)
dp[i+1][nowsum+j][0]=(dp[i+1][nowsum+j][0]% mo+((LL)dp[i][nowsum][1]*10%mo+j)%mo) % mo;
dp[i+1][nowsum+now[i+1]][1]=(dp[i+1][nowsum+now[i+1]][1] % mo+(LL)(dp[i][nowsum][1]*10%mo+now[i+1]) % mo)% mo;
}
for (int i = x;i<=y;i++)
ans +=(dp[len][i][0]%mo + dp[len][i][1]%mo)%mo;
return ans%mo;
}
int main()
{
char ch;
LL sumwei = 0,sum = 0;
ch = getchar();
while (ch!=' ')
{
l[++lenl] = (int)(ch - '0');
sumwei+=l[lenl];
ch = getchar();
}
ch = getchar();
while (ch!=' ')
{
r[++lenr] = (int)(ch - '0');
ch = getchar();
}
scanf("%d%d",&x,&y);
LL ans1 = deal(l,lenl),ans2 = deal(r,lenr);
if (sumwei>=x && sumwei<=y)
for (int i = 1;i<=lenl;i++)
sum = (sum*10+l[i]) %mo;
cout<<((ans2 - ans1+sum)%mo+mo)%mo;
return 0;
}
正解：做时大体思路即正解。
做：还是费了两小时，大抵是担心写错，因而很慢，战战兢兢。
简单数位dp
Cnt[i][j][k]表示从最高位为1计起，至第i位数位和为j时，抵上界（k=1）|未抵上界（k=0）的数的个数。
Dp[i][j][k]字母含义同cnt，但是记录当前满足条件数之和。
由此写出方程即可求解。
主要错因（从AC到WA 10）：检查代码时发现l木有-1，于是添上，殊不知l是数组，怎能如此作为。
改：本人不才，若代码看上去繁杂即是修改半小时，加了无数（% mo） 的结果，这也说明数据规模的重要性，凿凿的“wa”希望能带给自己思考——严谨。另外对于删去l的处理思虑很久，最终选择特别计算l，判断满足条件否进行结果的修改，后来发现标称亦是如此，更是警醒自己要深思熟虑才可着手去做。
得：数据类型毁终生
2.justice
总时间限制:
25000ms
内存限制:
256000kB
描述
还在后面一些。
Justice是少见的一款长篇。
求1-N的第K短路。（非严格，详见样例）
输入
第一行两个整数N、M、K代表图的点数、边数和要求的K。
接下来M行，每行三个整数S、E、D，代表S与E之间有一条长度为D的无向边。
输出
一行一个整数代表第K短路。
样例输入
【样例输入1】
2 1 2
1 2 1
【样例输入2】
2 2 2
1 2 1
1 2 1
样例输出
【样例输出1】
3
【样例输出2】
1
提示
对于20%的数据，1≤N,M≤10^2。
对于另外30%的数据，K=1。
对于另外20%的数据，K=2。
对于100%的数据，1≤N,M≤10^5，1≤K≤20，边的权值在103以内。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 100005;
const int MAXK = 21;
int dis[MAXN][MAXK],n,m,k,ne;
int q1[MAXN * MAXK],q2[MAXN * MAXK];
bool in[MAXN][MAXK];
struct Edge
{
int f,t,d;
Edge * next;
} e[MAXN * 2],* head[MAXN];
void addedge(int f,int t,int d)
{
e[++ne].t = t;
e[ne].d = d;
e[ne].next = head[f];
head[f] = e + ne;
}
void spfa(int x)
{
int l = 1,r = 1;
dis[x][0] = 0;
q1[r] = x;
q2[r] = 0;
r++;
if (r==n * k) r = 0;
in[x][0] = true;
while (r-l)
{
int now = q1[l];
int kth = q2[l];
l++;
if (l==n * k) l = 0;
in[now][kth] = false;
for (Edge * p = head[now];p;p=p->next)
{
int t = p->t;
int newd = dis[now][kth];
for (int i = 0;i<k;i++)
if (dis[t][i] > newd + p->d)
{
for (int j = k-1;j>i;j--)
dis[t][j] = dis[t][j-1];
dis[t][i] = newd + p->d;
for (int w = i;w<k;w++)
if (!in[t][w])
{
q1[r] = t;
q2[r] = w;
r++; if (r==n * k) r=0;
in[t][w] = true;
}
break;
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
int f,t,d;
for (int i = 1;i<=m;i++)
{
scanf("%d%d%d",&f,&t,&d);
addedge(f,t,d);
addedge(t,f,d);
}
memset(in,false,sizeof(in));
memset(dis,0x3f3f,sizeof(dis));
spfa(1);
printf("%d",dis[n][k-1]);
return 0;
}
正解：这是一道极好的题目
基本思路仍然是最短路，着手修改过程，找最短路无非就是逐渐更新的过程，
倘若记录下所有更新的节点及更新的路的排名，并用改更新的点去继续更新所有与之相连点的上述两个变量，即可求出the Kth shortest road
因此队列需要两个，相辅相成，齐头并进。
更新一个点也变成了更新一整行（即该点编号所在的记录最短路排名的那一行（in【定点】【0~k-1】））
做：被样例一吓到了，没有考虑到每一个点都有最短路排名，包括起点。
改：1.没有机智地想到用两个队列来记录，因此在以一个点去更新另一个点时有小纠结。
2.所有更新的点，包括同一个点的多条路径排名都需要加入队列。
得：对于已知的算法绝不满足 对基本算法理解不深呐~~~~