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;
}