AtCoder Beginner Contest 164

比赛链接：Here

ABC水题，

D - Multiple of 2019 （DP + 分析）

题意：

给定数字串S，计算有多少个子串 ，满足 是 的倍数

思路：

而且 #card=math&code=s%5Bl%2C%20r%5D%20%2A%2010%5E%7Bn-r%7D%20%3D%20s%5Bl%2Cr%5D%5C%252019%2A%2810%5E%7Bn-r%7D%5C%252019%29)

因为 （因为 没有质因子 和 ）

因此只有当 时，式子左边 ，这意味着 没有影响，

那么直接计算 的数量即可，

因为这种情况下一定是

int a[2040] = {1};
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    string s; cin >> s;
    int ans = 0, t = 1, cnt = 0;
    for (int i = s.size() - 1; ~i; i--) {
        cnt = (cnt + t * (s[i] - '0')) % 2019;
        ans += a[cnt]++;
        t = (t * 10) % 2019;
    }
    cout << ans;
}

E Two Currencies (最短路,Good)

题意：

给定 个点， 条无向边，初始状态下手里有 个银币。从 点到 点需要花费 个硬币， 个时间单位。在每个点可以花 个时间单位兑换 个银币，求从起点 到各个点需要的最短时间。

思路：
这题很关键的一个突破口是数据范围： 个点，从 到 花费不超过 银币，所以总花费不超过 .通过一个二维数组 来表示到达 点时还剩下 个银币时需要的时间最小值，然后跑一遍最短路，最后遍历一遍就可以输出最小值。

注意银币最大只需要 ，所以输入 的时候记得判断

struct E {ll to, co, ti;};
struct P {ll ti, id, re;};
bool operator <(const P &a, const P &b) {return a.ti > b.ti;}
ll f[50][5001], c[50], d[50], ans[50];
vector<E>e[50];
priority_queue<P> que;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, s;
    cin >> n >> m >> s;
    while (m--) {
        ll u, v, a, b;
        cin >> u >> v >> a >> b;
        u--, v--;
        e[u].push_back({v, a, b});
        e[v].push_back({u, a, b});
    }
    for (int i = 0; i < n; ++i) cin >> c[i] >> d[i];
    que.push({1, 0, min(s * 1ll, 2500ll)});
    while (que.size()) {
        P p = que.top(); que.pop();
        if (f[p.id][p.re])continue;
        f[p.id][p.re] = p.ti;
        if (!ans[p.id])ans[p.id] = p.ti;
        for (E q : e[p.id])
            if (p.re >= q.co && !f[q.to][p.re - q.co])
                que.push({p.ti + q.ti, q.to, p.re - q.co});
        if (p.re + c[p.id] <= 2500)
            que.push({p.ti + d[p.id], p.id, p.re + c[p.id]});
    }
    for (int i = 1; i < n; ++i) cout << --ans[i] << "\n";
}