C - Candies

题意

求左上角走到右下角最大的数字和。

思路

直接$dp$

Code

#include <bits/stdc++.h>

#define maxn 110

using namespace std;

int a[3][maxn], dp[3][maxn];

typedef long long LL;

int main() {

    int n;

    scanf("%d", &n);

    for (int i = 1; i <= 2; ++i) {

        for (int j = 1; j <= n; ++j) scanf("%d", &a[i][j]);

    }

    for (int i = 1; i <= n; ++i) dp[1][i] = dp[1][i-1] + a[1][i];

    for (int i = 1; i <= 2; ++i) dp[i][1] = dp[i-1][1] + a[i][1];

    for (int j = 2; j <= n; ++j) {

        dp[2][j] = max(dp[1][j], dp[2][j-1]) + a[2][j];

    }

    printf("%d\n", dp[2][n]);

    return 0;

}

D - People on a Line

题意

给定 $n$ 个未知数 $x_1,...x_n$ 与 $m$ 个等式 $x_{p_i}-x_{q_i}=d_i$，问是否可能成立？（即是否存在矛盾）

思路

神似 poj 2492 A Bug's Life 二分图染色 || 种类并查集

对于并查集中的元素，用 $off[\ ]$ 数组记录它比它的祖先大多少，合并的时候注意一下。

有条件$$l-fl=off[l]\ &&\ r-fr=off[r]\ &&\ r-l=d$$

于是有

\[off[fr]=fr-fl=d-off[r]+off[l]
\]

Code

#include <bits/stdc++.h>

#define maxn 100000

using namespace std;

typedef long long LL;

int fa[maxn], off[maxn];

int find(int x) {

    if (fa[x] == x) return x;

    int temp = fa[x];

    fa[x] = find(fa[x]);

    off[x] += off[temp];

    return fa[x];

}

int main() {

    int n, m;

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; ++i) fa[i] = i;

    for (int i = 0; i < m; ++i) {

        int l, r, d;

        scanf("%d%d%d", &l, &r, &d);

        int fl = find(l), fr = find(r);

        if (fl == fr) {

            if (off[r] - off[l] == d) continue;

            else { puts("No"); return 0; }

        }

        else {

            fa[fr] = fl;

            off[fr] = d - off[r] + off[l];

        }

    }

    puts("Yes");

    return 0;

}

E - Avoiding Collision

题意

给定一张图，甲乙两人分别从 $s$ , $t$ 出发，甲要到 $t$，乙要到 $s$，且两人均走最短路。

问在途中不相遇的方案数。

思路

跑两遍 $dijkstra$，跑的时候记录最短路长度$dist[\ ]$和方案数$way[\ ]$。

显然，两人不能走同样的路，所以如果没有 在途中不相遇 的条件约束，则答案为 $$ans = ways1[t]*(ways1[t]-1])$$

然而，题目要求 在途中不相遇，这蕴含了两层含义，在点上不相遇，在边上不相遇。

// 千万别忘了边Orz

在点上不相遇：

枚举点，判断是否 $$dist1[i]2==dis\ &&\ dist2[i]2==dis$$

在边上不相遇：

枚举边，判断是否 $$dist1[u] + edge[id].w + dist2[v] == dis\ &&\ (dist1[u]<<1) < dis\ &&\ (dist2[v]<<1) < dis$$

用总答案减去这两部分 $ans - ans1 - ans2$ 即为答案

Code

#include <bits/stdc++.h>

#define maxn 100010

#define maxm 200010

#define inf 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef long long LL;

const LL mod = 1e9 + 7;

int ne[maxn], tot;

bool vis[maxn];

LL dist1[maxn], dist2[maxn], ways1[maxn], ways2[maxn];

struct Edge { int from, to, ne; LL w; }edge[maxm<<1];

void add(int u, int v, LL w) {

    edge[tot] = {u, v, ne[u], w};

    ne[u] = tot++;

}

struct node {

    int v; LL c;

    bool operator < (const node nd) const { return c > nd.c; }

};

int n;

void dfs(int src, LL* dist, LL* ways) {

    memset(vis, 0, sizeof vis);

    for (int i = 1; i <= n; ++i) dist[i] = inf;

    vis[src] = true; dist[src] = 0; ways[src] = 1;

    priority_queue<node> q;

    while (!q.empty()) q.pop();

    while (true) {

        for (int j = ne[src]; ~j; j = edge[j].ne) {

            int v = edge[j].to;

            if (vis[v]) continue;

            LL now = edge[j].w + dist[src];

            if (now == dist[v]) (ways[v] += ways[src]) %= mod;

            else if (now < dist[v]) {

                dist[v] = now; ways[v] = ways[src];

                q.push({v, now});

            }

        }

        while (!q.empty() && vis[q.top().v]) q.pop();

        if (q.empty()) break;

        vis[src = q.top().v] = true;

    }

}

int main() {

    memset(ne, -1, sizeof ne);

    int m, s, t;

    scanf("%d%d%d%d", &n,&m,&s,&t);

    for (int i = 0; i < m; ++i) {

        int u, v; LL w;

        scanf("%d%d%lld", &u,&v,&w);

        add(u, v, w), add(v, u, w);

    }

    dfs(s, dist1, ways1);

    dfs(t, dist2, ways2);

    assert(dist1[t] == dist2[s]);

    assert(ways1[t] == ways2[s]);

    LL ww = ways1[t];

    LL ans = ww * (ww-1) % mod;

    LL dis = dist1[t];

    if (!(dis & 1)) {

        LL half = dis >> 1;

        for (int i = 1; i <= n; ++i) if (dist1[i] == half && dist2[i] == half) {

            LL temp = ways1[i] * ways2[i] % mod;

            ans = (ans - (temp * (temp-1)) % mod + mod) % mod;

        }

    }

    for (int i = 0; i < m; ++i) {

        int id = i<<1,

            u = edge[id].from, v = edge[id].to;

        if (dist1[u] > dist1[v]) swap(u, v);

        if (dist1[u] + edge[id].w + dist2[v] == dis && (dist1[u]<<1) < dis && (dist2[v]<<1) < dis) {

            LL temp = ways1[u] * ways2[v] % mod;

            ans = (ans - (temp * (temp-1)) % mod + mod) % mod;

        }

    }

    printf("%lld\n", ans);

    return 0;

}

F - Number of Digits

见 http://www.cnblogs.com/kkkkahlua/p/8400712.html

巴特西

AtCoder Regular Contest 090 C D E F

C - Candies

题意

思路

Code

D - People on a Line

题意

思路

Code

E - Avoiding Collision

题意

思路

Code

F - Number of Digits

最新文章

热门文章