2019 ICPC 银川题解（A）

本文主要是介绍2019 ICPC 银川题解（A），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

赛时没发挥好6题金尾（rank38），剩下很多能写的题，其中四个dp，傻眼ing

A Girls Band Party（背包）

有点迷惑的题，当时看只要 $5$ 张牌一下子想到暴力枚举，结果发现是不太能行的，导致浪费很多时间。

题意

$n$ 张牌，每张牌有名称，颜色，价值。再给定 $5$ 个特殊的牌的名称，和一个特殊的牌的颜色。要求从 $n$ 张牌中选出 $5$ 张名称不同的卡牌，基础分数为 $5$ 张牌的价值之和 $s u m$ ，在此基础上每多一张牌是特殊颜色最终价值加上 $0.2 * s u m$ ，每多一张特殊名字牌最终价值加上 $0.1 * s u m$ ，最终价值向下取整，求选出的卡牌最大可能的价值。

思路

对于复杂的题目我们先从简单的问题开始考虑。

若是对于该问题只考虑价值之和不考虑附加价值和不能同名的问题是否能解决？就是一个简单的背包，容量为 $5$ 求最大值的问题。

接下来增加新的信息，若是要求 $5$ 张牌不能重名如何解决？也很简单，分组背包，同名的牌视作一组，一组内的物品只能选一样的背包问题。

再增加新的信息，普通颜色和普通名称对答案没有任何影响，特殊颜色和名称也只有数量对答案有影响，和具体是什么无关。我们是否能在背包时顺便统计特殊颜色和特殊名称？，也很简单，因为只要选出 $5$ 张牌，将特殊颜色和特殊名称也当做价值的一种算进dp方程，给两个各多开一维维护即可。

到此问题已经顺利解决，给出dp方程： $d p [i] [j] [k] [p] ：$ 前 $i$ 张卡牌，选出 $j$ 张卡牌， $k$ 张是特殊颜色， $p$ 张是特殊名字卡牌的合法方案中的最大基数价值。

具体实现可以看代码，有注释和解析。

#include <bits/stdc++.h>
using namespace std;#define ll long longconst int N = 1e5 + 10;int n;string s[10], color;
map<string, bool> mp;struct node{string d, c;int val;
}cd[N];bool cmp(node& A, node& B){return A.d < B.d;
}int f[N][6][6][6]; // 前 i 张卡牌，选出 j 张卡牌，k 张是特殊颜色，p 张是特殊名字卡牌的 最大基数价值void cmax(int& a, int b){ a = max(a, b); }
void solve(){int n;cin >> n;for(int i = 1; i <= n; i ++){cin >> cd[i].d >> cd[i].c >> cd[i].val;}mp.clear();for(int i = 0; i < 5; i ++){cin >> s[i];mp[s[i]] = 1;}cin >> color;sort(cd + 1, cd + 1 + n, cmp);  // 按名称排序，方便进行类似分组背包的dpfor(int i = 1; i <= n; i ++){for(int j = 0; j < 6; j ++){for(int k = 0; k < 6; k ++){for(int p = 0; p < 6; p ++) f[i][j][k][p] = 0;}}}int last = 0; // 记录最近的上一个不同名的卡牌为止for(int i = 1; i <= n; i ++){if(cd[i].d != cd[i - 1].d) last = i - 1; int c_v = (cd[i].c == color), s_v = mp.count(cd[i].d); // 这张牌是否是特殊颜色和名称for(int j = 0; j <= 5; j ++){for(int k = 0; k <= j; k ++){for(int p = 0; p <= j; p ++){// 不取这张牌cmax(f[i][j][k][p], f[i - 1][j][k][p]); // 可以从同名的卡牌转移 也可以从不同名的转移// 取这张牌if((j != 0 && f[last][j][k][p] == 0) || j == 5) continue ; // j = 5 时注意不要越界了cmax(f[i][j + 1][k + c_v][p + s_v], f[last][j][k][p] + cd[i].val); // 取这一张牌，那么只能从不同名的卡牌转移}}}}ll ans = 0;for(int i = 0; i <= 5; i ++){ // 枚举特殊颜色数量for(int j = 0; j <= 5; j ++){ // 枚举特殊名字数量double mul = 0.2 * (double)i + 0.1 * (double)j; // 系数ans = max(ans, (ll)(mul * (double)f[n][5][i][j]) + f[n][5][i][j]);}}cout << ans << "\n";
}int main(){ ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);int t;cin >> t;while(t --){solve();}return 0;
}

H Delivery Route（最短路+拓扑排序）

题意

给定一个有向图 $G$ ， $x$ 条双向边 $y$ 条单向边，可能有负边（保证是单向边）但保证走过单向边 $u\rightarrow v$ 后一定走不回 $u$ ，求起点 $s$ 到所有点的最短路，如果到不了输出 “NO PATH”.

思路

乍一看仿佛很简单，跑个迪杰斯特拉（后文简称djs）最短路不就行了吗？但是写完准备交的时候就发现有坑，因为djs算法是每次从优先队列取出目前为止到起点最近的点 $u$ 进行扩展，但是这样的扩展不一定是最优的，但之前扩展过一次下次再想用该点 $u$ 扩展就不行了。
考虑这样一个图： $1$ 是起点
在这里插入图片描述

从 $1\rightarrow2\rightarrow4\rightarrow5$ 显然是第一轮扩展，在这几个点取出队列之前队首都不会轮到 $3$ ，因为此时 $d i s [3] = 2 > d i s [2] = 1 > d i s [4] = 0 > d i s [5] = 1$ ，因为此时这几个点都已经作为过一次扩展点了，之后就不能再次扩展，但是发现当最后点 $3$ 进行扩展时， $3\rightarrow4\rightarrow5$ 会更优秀。

由于题目保证没有负环，我们考虑使用拓扑排序进行优化，先将双向边连接起的连通块用并查集合并，再将单向边连接的这些连通块点集度数 $+ 1$ ，但要注意若是有单向边 $u\rightarrow v$ ，且 $u$ 点是不可从起点到达的，就不用记录该度数。

接下来就是普通的djs算法 + 拓扑排序了，只有当度数为 $0$ 时才将一个连通块加入优先队列。具体见代码和注释。

#include <bits/stdc++.h>
using namespace std;#define ll long long
typedef pair<ll, int> pli;const int N = 25010;
const ll inf = 1e18;vector<pair<int, int> > g[N], e[N];int n, m1, m2, s;priority_queue<pli, vector<pli>, greater<pli>> q;ll dis[N];
bool vis[N];struct DSU {std::vector<int> f, siz;DSU() {}DSU(int maxn) {init(maxn);}void init(int maxn) {f.resize(++ maxn); // 重构容器大小到 nstd::iota(f.begin(), f.end(), 0); // 批量递增赋值// siz.assign(maxn, 1); // 赋值n个1}int find(int x) {while (x != f[x]) {x = f[x] = f[f[x]];}return x;}bool same(int x, int y) {return find(x) == find(y);}bool merge(int x, int y) {x = find(x);y = find(y);if (x == y) {return false;}f[y] = x;return true;}
};DSU dsu;
int d[N];
vector<int> ID[N];
void djs_top(){for(int i = 1; i <= n; i ++) dis[i] = inf, vis[i] = 0;dis[s] = 0;q.push({0, s});while(!q.empty()){auto [di, u] = q.top(); q.pop();if(vis[u]) continue ;vis[u] = 1;// djsfor(auto [v, w] : g[u]){if(dis[v] > dis[u] + w){dis[v] = dis[u] + w;q.push({dis[v], v});}}// 拓扑排序for(auto [v, w] : e[u]){ // 单向边int id = dsu.find(v);d[id] --;if(dis[v] > dis[u] + w) dis[v] = dis[u] + w;ID[id].push_back(v); // 存入连通块if(!d[id]){ // 当连通块度数为0，再将所有块内之前出现过的点存入队列for(auto x : ID[id]) q.push({dis[x], x});}}}
}void dfs(int u){if(vis[u]) return ;vis[u] = 1;for(auto [v, w] : g[u]) dfs(v);for(auto [v, w] : e[u]) dfs(v);
}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m1 >> m2 >> s;dsu.init(n);for(int i = 1; i <= m1; i ++){int u, v, w;cin >> u >> v >> w;dsu.merge(u, v); // 并查集合并g[u].push_back({v, w});g[v].push_back({u, w});}for(int i = 1; i <= m2; i ++){int u, v, w;cin >> u >> v >> w;e[u].push_back({v, w});}dfs(s); // 将不可达的点判除for(int i = 1; i <= n; i ++){if(!vis[i]) continue ;for(auto [v, w] : e[i]) d[dsu.find(v)] ++; // 连通块的度数 ++}djs_top();for(int i = 1; i <= n; i ++){if(!vis[i]) cout << "NO PATH\n";else cout << dis[i] << "\n";}return 0;
}