D - Multiple of 2019
题目大意：一大串数字S（a1a2 ... an)，求其子串中能整除2019的个数。
思路：dp，真不太好想。
可以想到的dp是假设<n的答案我们知道，那dp(n) = dp(n-1) + 以an结尾的子串中整除2019的个数，但n太大，第二项无法求出。
既然直接思路不行我们就间接，a整除2019 <=> (x+a - x)整除2019，也就是说x+a和x模2019同余。设(i,j) =aiai+1...aj，我们取字符串好取，但串值难办，顶多能取aiai+1...aj00...0，也就是10n-i+1aiai+1...an，重点是10n-i+1aiai+1...anaiai+1...an(mod 2019)，因为2、5都不是2019的因子，因此10n-(j+1)+1不能整除2019，因此要使10n-i+1aiai+1...an能整除2019，(aiai+1...aj)必须能整除2019，也就是题目问题等价于子串00..0中能整除2019的个数。
后面就相对简单了，设Tk = an + 101an-1 +102an-2 + ... + 10n-kak，Ti - Tj+1 =10n-(j+1)+1(aiai+1...aj) ，这样(i,j)00...0整除2019 <=> (Ti-Tj+1)整除2019，即Ti和Tj+1同余即可，那求(i,j)的个数就变成了求Tk中模2019同余（余数0~2018）的个数m，然后m*(m-1)/2即为所求。下一个问题就是Tk怎么求？利用递推式：Tk = Tk+1 + 10n-（k+1）+1ak。
实现：10x太大怎么办？按照取余运算规则取余啊，不会影响答案，(a*b)%p = ((a%p)*(b%p))%p。
代码：
#include<iostream>
#include<cmath>
#define LL long long
using namespace std;
const int MAXN = 2e5+10;
LL T[MAXN];
int mod[2019];
LL ans = 0;
inline LL count(int n) {
return 1LL*n*(n-1)/2;
}
int main() {
ios::sync_with_stdio(false);
string S;
cin >> S;
int n = S.length();
T[n] = 0;
int pre = 1;
mod[0] = 1;
for(int i=n-1; i>=0; i--) {
pre *= 10;
T[i] = T[i+1]+pre*(S[i]-'0');
T[i] %= 2019;
mod[T[i]]++;
pre %= 2019;
}
ans = 0;
for(int i=0; i<2019; i++) {
if(mod[i])
ans += count(mod[i]);
}
cout << ans << endl;
return 0;
}
E - Two Currencies
题目大意: N个城市M条路，每条路都需要花银子和时间，每个城市都可以把金子换银子（因为路费只能用银子），但需要花费一定时间，求你从城市1（带了无穷金子，S银子）出发到达其他城市的最小时间。
思路：dp。设dp[i][j]为到达顶点i有j银子的最小时间，其转移状态：dp[i][j] = min{dp[i][j-C[i]]+D[i], dp[i][j+G[k][i].A]+G[k][i].B}。然后类似bellman-ford更新dp，更新或者设置update标记，或者更新2*M次，网上有些题解是更新N+1次，虽能AC，但下面的test过不了。
7 6 1
4 7 25 1
1 2 1 1
1 3 2 1
2 4 5 1
3 5 11 1
1 6 50 1
1 10000000
1 3000000
1 700000
1 100000
1 1000
100 1
1 1
正确答案是：
1
9000003
14600006
16500010
16544100 <-- n+1次错误答案是16563013
16544015
实现：犯了两个错误：一个边数不是M而是2*M（或者直接edge.size()），因为无向图；另一个是INF设的有些小，导致ans没有更新到，最后设1e18解决。
代码：
// 犯了两个错误，一个是循环用M而不是edge.size()，一个是INF设置0x3f3f3f3f太小
#include <iostream>
#include <vector>
#include <cstring>
#include<cmath>
#define LL long long
using namespace std;
#define MAXN 60
#define MAXA 60
int N, M, S;
struct e
{
int u, v, a, b;
};
vector<e> edge;
int C[MAXN], D[MAXN];
LL dp[MAXN][MAXA * MAXN];
LL ans;
int main()
{
scanf("%d%d%d", &N, &M, &S);
int u, v, a, b;
for (int i = 1; i <= M; i++)
{
scanf("%d%d%d%d", &u, &v, &a, &b);
edge.push_back({u, v, a, b});
edge.push_back({v, u, a, b});
}
for (int i = 1; i <= N; i++)
{
scanf("%d%d", &C[i], &D[i]);
}
memset(dp, 0x3f, sizeof(dp));
if (S > 2500)
S = 2500;
dp[1][S] = 0;
while (true)
{
bool update = false;
for (int i = 0; i < edge.size(); i++)
{
int u = edge[i].u;
int v = edge[i].v;
int a = edge[i].a;
int b = edge[i].b;
for (int j = 0; j <= 2500; j++)
{
if (j >= C[v])
{
if (dp[v][j] > dp[v][j - C[v]] + D[v])
{
update = true;
dp[v][j] = dp[v][j - C[v]] + D[v];
}
}
if (dp[v][j] > dp[u][j + a] + b)
{
update = true;
dp[v][j] = dp[u][j + a] + b;
}
}
}
if (!update)
break;
}
for (int i = 2; i <= N; i++)
{
LL ans = 1e18;
for (int j = 0; j <= 2500; j++)
{
if (dp[i][j] < ans)
{
ans = dp[i][j];
}
}
cout << ans << endl;
}
return 0;
}
bellman-ford和dijkstra的区别：
参考：
