CCF-CSP认证考试 202312-5 彩色路径 20/50/100分题解
时间：2024-04-01 18:20:43 来源：网络cs 作者：言安琪 栏目：卖家故事 阅读：
更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解
原题链接： 202312-5 彩色路径
时间限制： 2.0s
内存限制： 512.0MB
问题描述
西西艾弗岛的路线图可以看作是一个具有 N N N 个节点和 M M M 条有向边的图。
第 i i i 个节点（ 0 ≤ i < N 0 \le i < N 0≤i<N）有一个颜色标签 C [ i ] ∈ 0 , 1 , ⋯ , K − 1 C[i] \in {0, 1, \cdots, K-1} C[i]∈0,1,⋯,K−1，第 j j j 条边（ 0 ≤ j < M 0 \le j < M 0≤j<M）从节点 U [ j ] U[j] U[j] 指向节点 V [ j ] V[j] V[j]，长度为 D [ j ] D[j] D[j]。
对于游客顿顿来说，理想的观光路线应满足以下条件：
是一条从节点 0 0 0 到节点 N − 1 N-1 N−1 的简单路径；是一条彩色路径，即路径上每个节点的颜色标签均不相同；并且包含的节点数小于或等于 L L L。具体而言，理想的观光路线是一个节点序列，例如 ( t 0 , t 1 , ⋯ , t q − 1 ) (t_0, t_1, \cdots, t_{q-1}) (t0,t1,⋯,tq−1)，满足以下所有要求：
对于每个 i i i（ 0 ≤ i < q − 1 0 \le i < q-1 0≤i<q−1），存在一条从节点 t i t_i ti 到节点 t i + 1 t_{i+1} ti+1 的有向边。 t 0 = 0 t_0 = 0 t0=0 且 t q − 1 = N − 1 t_{q-1} = N-1 tq−1=N−1对于每对 i , j i, j i,j（ 0 ≤ i < j < q 0 \le i < j < q 0≤i<j<q），都有 C [ t i ] ≠ C [ t j ] C[t_i] \neq C[t_j] C[ti]=C[tj]。 q ≤ L q \le L q≤L一条路径的长度定义为边的总长度。你的任务是找到满足游客顿顿所有要求的最长观光路线。
输入格式
从标准输入读入数据。
输入共五行。
输入的第一行包含四个正整数 N N N、 M M M、 L L L 和 K K K，分别表示图的节点数、边数、理想观光路线的节点数上限和颜色标签范围。
输入的第二行包含 N N N 个整数 C [ 0 ] , C [ 1 ] , ⋯ , C [ N − 1 ] C[0], C[1], \cdots, C[N-1] C[0],C[1],⋯,C[N−1]，表示图中每个节点的颜色标签。
接下来输入边的信息。
输入的第三行包含 M M M 个整数 U [ 0 ] , U [ 1 ] , ⋯ , U [ M − 1 ] U[0], U[1], \cdots, U[M-1] U[0],U[1],⋯,U[M−1]，表示每条有向边的起点；
输入的第四行包含 M M M 个整数 V [ 0 ] , V [ 1 ] , ⋯ , V [ M − 1 ] V[0], V[1], \cdots, V[M-1] V[0],V[1],⋯,V[M−1]，表示每条有向边的终点；
输入的第五行包含 M M M 个整数 D [ 0 ] , D [ 1 ] , ⋯ , D [ M − 1 ] D[0], D[1], \cdots, D[M-1] D[0],D[1],⋯,D[M−1]，表示每条有向边的长度。
输入数据保证不存在起点终点相同的边，如 ( u , u ) (u, u) (u,u)；每条有向边 ( u , v ) (u, v) (u,v) 仅会出现一次，但不排除 ( u , v ) (u, v) (u,v) 和 ( v , u ) (v, u) (v,u) 可能同时存在。
输出格式
输出到标准输出。
输出一个数，表示理想观光路线的最大长度。
样例输入
6 9 4 100 2 2 3 3 90 0 0 1 1 1 2 3 41 2 4 3 4 5 4 5 51 2 4 3 2 8 5 3 1样例输出
9样例解释
以下是示例图，其中黑色和红色数字分别表示节点编号和边的长度。
样例解释
如下表所示，在不超过四个节点的限制下，共有五条从节点 0 0 0 到节点 5 5 5 的彩色路径。其中最长的一条是 ( 0 , 1 , 5 ) (0, 1, 5) (0,1,5)，长度为 9 9 9。
| 彩色路径 | 节点数 | 长度 |
|---|---|---|
| ( 0 , 1 , 3 , 5 ) \left(0, 1, 3, 5\right) (0,1,3,5) | 4 | 7 |
| ( 0 , 1 , 4 , 5 ) \left(0, 1, 4, 5\right) (0,1,4,5) | 4 | 4 |
| ( 0 , 2 , 4 , 5 ) \left(0, 2, 4, 5\right) (0,2,4,5) | 4 | 8 |
| ( 0 , 1 , 5 ) \left(0, 1, 5\right) (0,1,5) | 3 | 9 |
| ( 0 , 4 , 5 ) \left(0, 4, 5\right) (0,4,5) | 3 | 5 |
子任务
20 % 20\% 20% 的测试数据满足：对于每个 i i i（ 0 ≤ i < N − 1 0 \le i < N-1 0≤i<N−1），有 C [ i ] ≤ C [ i + 1 ] C[i] \le C[i + 1] C[i]≤C[i+1]，以及对于每个 j j j（ 0 ≤ j < M 0 \le j < M 0≤j<M），有 U [ j ] < V [ j ] U[j] < V[j] U[j]<V[j]。
另有 30 % 30\% 30% 测试数据满足： K ≤ 15 K \le 15 K≤15。
全部的测试数据满足：
2 ≤ N ≤ 100 2 \le N \le 100 2≤N≤100 1 ≤ M ≤ 5000 1 \le M \le 5000 1≤M≤5000 2 ≤ L ≤ 9 ≤ K ≤ 30 2 \le L \le 9 \le K \le 30 2≤L≤9≤K≤30 C [ 0 ] = 0 C[0] = 0 C[0]=0 且 C [ N − 1 ] = K − 1 C[N-1] = K-1 C[N−1]=K−1对于每个 i i i（ 1 ≤ i ≤ N − 2 1 \le i \le N-2 1≤i≤N−2）： 1 ≤ C [ i ] ≤ K − 2 1 \le C[i] \le K-2 1≤C[i]≤K−2对于每个 j j j（ 0 ≤ j < M 0 \le j < M 0≤j<M）： 0 ≤ U [ j ] , V [ j ] < N 0 \le U[j], V[j] < N 0≤U[j],V[j]<N C [ U [ j ] ] ≠ C [ V [ j ] ] C[U[j]] \neq C[V[j]] C[U[j]]=C[V[j]] 1 ≤ D [ j ] ≤ 1 0 6 1 \le D[j] \le 10^6 1≤D[j]≤106至少存在一条从节点 0 0 0 到节点 N − 1 N-1 N−1 的彩色路径，节点数不超过 L L L。20 分题解
根据题目中所给的限制条件，找到的任意路径必定不会存在重复的颜色，只需要求节点数不超过 L L L 的最长路即可。
使用 dp 的方法，记 dis[i][j] 表示经过 j j j 条边，最终到达 i i i 号节点的最长路的长度。
转移为 dis[v][i] = max(dis[v][i], dis[u][i - 1] + d) （存在 u u u 到 v v v 的长度为 d d d 的边），最终结果为 dp[n - 1] 中的最大值。
时间复杂度： O ( M L ) \mathcal{O}(ML) O(ML)。
20 分参考代码（15ms，3.027MB）
/* Created by Pujx on 2024/2/4.*/#pragma GCC optimize(2, 3, "Ofast", "inline")#include <bits/stdc++.h>using namespace std;#define endl '\n'//#define int long long//#define double long doubleusing i64 = long long;using ui64 = unsigned long long;using i128 = __int128;#define inf (int)0x3f3f3f3f3f3f3f3f#define INF 0x3f3f3f3f3f3f3f3f#define yn(x) cout << (x ? "yes" : "no") << endl#define Yn(x) cout << (x ? "Yes" : "No") << endl#define YN(x) cout << (x ? "YES" : "NO") << endl#define mem(x, i) memset(x, i, sizeof(x))#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]#define cinstl(a) for (auto& x : a) cin >> x;#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl#define all(x) (x).begin(), (x).end()#define md(x) (((x) % mod + mod) % mod)#define ls (s << 1)#define rs (s << 1 | 1)#define ft first#define se second#define pii pair<int, int>#ifdef DEBUG #include "debug.h"#else #define dbg(...) void(0)#endifconst int N = 100 + 5;const int M = 5000 + 5;const int mod = 998244353;//const int mod = 1e9 + 7;//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }int c[N], U[M], V[M], D[M];vector<pii> g[N];int n, m, t, l, k, q;void work() { cin >> n >> m >> l >> k; for (int i = 0; i < n; i++) cin >> c[i]; cinarr(U, m); cinarr(V, m); cinarr(D, m); for (int i = 1; i <= m; i++) { if (V[i] == 0) continue; if (U[i] == n - 1) continue; g[U[i]].emplace_back(V[i], D[i]); } vector<vector<int>> dis(n, vector<int>(l, -inf)); dis[0][0] = 0; for (int u = 0; u < n - 1; u++) for (auto tem : g[u]) { int v = tem.first, w = tem.second; for (int i = 1; i < l; i++) { if (dis[u][i - 1] == -inf) continue; dis[v][i] = max(dis[v][i], dis[u][i - 1] + w); } } cout << *max_element(dis.back().begin(), dis.back().end()) << endl;}signed main() {#ifdef LOCAL freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin); freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);#endif ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int Case = 1; //cin >> Case; while (Case--) work(); return 0;}/* _____ _ _ _ __ __ | _ \ | | | | | | \ \ / / | |_| | | | | | | | \ \/ / | ___/ | | | | _ | | } { | | | |_| | | |_| | / /\ \ |_| \_____/ \_____/ /_/ \_\*/50 分题解
考虑 K ≤ 15 K\leq 15 K≤15 的情况。
使用状压 dp。记 dp[i][j] 表示经过颜色编号为 j j j 的若干条边，最终到达 i i i 号节点的最长路的长度。其中，如果最长路径中经过了颜色为 c c c 的节点，那么 j j j 的二进制表示中，从右往左第 c c c 位 1，否则为 0。
总共迭代 L − 1 L-1 L−1 轮，在第 i i i 轮迭代时，是有 j j j 的二进制表示中有 i i i 个 1 的参与该次迭代，迭代后会有 i + 1 i+1 i+1 个 1。如果不进行判断 1 的个数，可能有元素在一轮中参与多次迭代，从而最终节点数超过 L L L。计算一个数 x x x 二进制表示中 1 1 1 的个数可以用 __builtin_popcount(x) 函数直接计算。
转移为 dp[v][i ^ (1 << c[v])] = max(dp[v][i ^ (1 << c[v])], dp[u][i] + w) （存在 u u u 到 v v v 的长度为 d d d 的边），最终结果为 dp[n - 1] 中的最大值。
这种情况下，当 K > 15 K>15 K>15 时，直接使用 20 20 20 分代码的求解过程即可把较为简单的 50 50 50 分拿到。
时间复杂度： O ( 2 K M L ) \mathcal{O}(2^KML) O(2KML)。
50 分参考代码（93ms，16.00MB）
/* Created by Pujx on 2024/2/4.*/#pragma GCC optimize(2, 3, "Ofast", "inline")#include <bits/stdc++.h>using namespace std;#define endl '\n'//#define int long long//#define double long doubleusing i64 = long long;using ui64 = unsigned long long;using i128 = __int128;#define inf (int)0x3f3f3f3f3f3f3f3f#define INF 0x3f3f3f3f3f3f3f3f#define yn(x) cout << (x ? "yes" : "no") << endl#define Yn(x) cout << (x ? "Yes" : "No") << endl#define YN(x) cout << (x ? "YES" : "NO") << endl#define mem(x, i) memset(x, i, sizeof(x))#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]#define cinstl(a) for (auto& x : a) cin >> x;#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl#define all(x) (x).begin(), (x).end()#define md(x) (((x) % mod + mod) % mod)#define ls (s << 1)#define rs (s << 1 | 1)#define ft first#define se second#define pii pair<int, int>#ifdef DEBUG #include "debug.h"#else #define dbg(...) void(0)#endifconst int N = 100 + 5;const int M = 5000 + 5;const int mod = 998244353;//const int mod = 1e9 + 7;//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }int c[N], U[M], V[M], D[M];vector<pii> g[N];int n, m, t, l, k, q;int dp[N][1 << 15];void work() { cin >> n >> m >> l >> k; for (int i = 0; i < n; i++) cin >> c[i]; cinarr(U, m); cinarr(V, m); cinarr(D, m); for (int i = 1; i <= m; i++) { if (V[i] == 0) continue; if (U[i] == n - 1) continue; g[U[i]].emplace_back(V[i], D[i]); } if (k <= 15) { for (int i = 0; i < N; i++) for (int j = 0; j < 1 << 15; j++) dp[i][j] = -inf; dp[0][1] = 0; l--; for (int _ = 1; _ <= l; _++) for (int u = 0; u < n; u++) for (int i = 0; i < 1 << k; i++) { if (dp[u][i] == -inf) continue; if (__builtin_popcount(i) != _) continue; for (auto tem : g[u]) { int v = tem.first, w = tem.second; if (i & (1 << c[v])) continue; dp[v][i ^ (1 << c[v])] = max(dp[v][i ^ (1 << c[v])], dp[u][i] + w); } } int ans = 0; for (int i = 0; i < 1 << k; i++) ans = max(ans, dp[n - 1][i]); cout << ans << endl; } else { vector<vector<int>> dis(n, vector<int>(l, -inf)); dis[0][0] = 0; for (int u = 0; u < n - 1; u++) for (auto tem : g[u]) { int v = tem.first, w = tem.second; for (int i = 1; i < l; i++) { if (dis[u][i - 1] == -inf) continue; dis[v][i] = max(dis[v][i], dis[u][i - 1] + w); } } cout << *max_element(dis.back().begin(), dis.back().end()) << endl; }}signed main() {#ifdef LOCAL freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin); freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);#endif ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int Case = 1; //cin >> Case; while (Case--) work(); return 0;}/* _____ _ _ _ __ __ | _ \ | | | | | | \ \ / / | |_| | | | | | | | \ \/ / | ___/ | | | | _ | | } { | | | |_| | | |_| | / /\ \ |_| \_____/ \_____/ /_/ \_\*/100 分题解
与 50 50 50 分代码的区别是 K K K 变大了， 2 30 2^{30} 230 无法直接存储和遍历。
考虑使用折半的方法，将所需的 L L L 分成两部分 L 1 = ⌊ L − 1 2 ⌋ , L 2 = L − 1 − L 1 L_1=\left\lfloor\dfrac{L-1}{2}\right\rfloor,L_2=L-1-L_1 L1=⌊2L−1⌋,L2=L−1−L1，对第一部分，求从 0 0 0 号节点开始的边数不超过 L 1 L_1 L1 正向状压 dp，对第二部分，求从 n − 1 n-1 n−1 号节点开始的边数不超过 L 2 L_2 L2 反向状压 dp（起点终点交换，有向边交换方向）。状压的方式与 50 50 50 分的一致，只是这里不是直接开 2 30 2^{30} 230 的数组，而是用到哪个状态存储那个状态，可以使用 STL 中的 map。
最终合并时，遍历 0 ∼ n − 1 0\sim n-1 0∼n−1 结点，对于每个结点 i i i，同时比较正向 dp 和反向 dp，对于每个正向 dp 中的状态 j 1 j_1 j1 和反向 dp 中的状态 j 2 j_2 j2，如果 (j1 & j2) == (1 << c[i])，即两个状态仅有 i i i 的颜色是重复的，那么 j 1 , j 2 j_1,j_2 j1,j2 状态所对应的最长路的长度和即为一种可能的答案。对所有可能的答案取 max \max max 即为最终答案。
在最终合并的过程中，稍微卡了一下常数，随便加点剪枝什么的就能过了。
时间复杂度： O ( C K L ) \mathcal{O}(\mathrm{C}_K^L) O(CKL)。
100 分参考代码（843ms，32.22MB）
/* Created by Pujx on 2024/2/4.*/#pragma GCC optimize(2, 3, "Ofast", "inline")#include <bits/stdc++.h>using namespace std;#define endl '\n'//#define int long long//#define double long doubleusing i64 = long long;using ui64 = unsigned long long;using i128 = __int128;#define inf (int)0x3f3f3f3f3f3f3f3f#define INF 0x3f3f3f3f3f3f3f3f#define yn(x) cout << (x ? "yes" : "no") << endl#define Yn(x) cout << (x ? "Yes" : "No") << endl#define YN(x) cout << (x ? "YES" : "NO") << endl#define mem(x, i) memset(x, i, sizeof(x))#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]#define cinstl(a) for (auto& x : a) cin >> x;#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl#define all(x) (x).begin(), (x).end()#define md(x) (((x) % mod + mod) % mod)#define ls (s << 1)#define rs (s << 1 | 1)#define ft first#define se second#define pii pair<int, int>#ifdef DEBUG #include "debug.h"#else #define dbg(...) void(0)#endifconst int N = 100 + 5;const int M = 5000 + 5;const int mod = 998244353;//const int mod = 1e9 + 7;//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }int c[N], U[M], V[M], D[M];vector<pii> g[N], gg[N];int n, m, t, l, k, q;map<int, int> dp[N], dpp[N];void work() { cin >> n >> m >> l >> k; for (int i = 0; i < n; i++) cin >> c[i]; cinarr(U, m); cinarr(V, m); cinarr(D, m); for (int i = 1; i <= m; i++) { g[U[i]].emplace_back(V[i], D[i]); gg[V[i]].emplace_back(U[i], D[i]); } l--; int ll = l / 2, lr = l - ll; dp[0][1 << c[0]] = 0; for (int _ = 1; _ <= ll; _++) for (int u = 0; u < n; u++) for (auto it = dp[u].begin(); it != dp[u].end(); it++) { int i = it->first; if (__builtin_popcount(i) != _) continue; for (auto tem : g[u]) { int v = tem.first, w = tem.second; if (i & (1 << c[v])) continue; dp[v][i ^ (1 << c[v])] = max(dp[v][i ^ (1 << c[v])], it->second + w); } } dpp[n - 1][1 << c[n - 1]] = 0; for (int _ = 1; _ <= lr; _++) for (int u = 0; u < n; u++) for (auto it = dpp[u].begin(); it != dpp[u].end(); it++) { int i = it->first; if (__builtin_popcount(i) != _) continue; for (auto tem : gg[u]) { int v = tem.first, w = tem.second; if (i & (1 << c[v])) continue; dpp[v][i ^ (1 << c[v])] = max(dpp[v][i ^ (1 << c[v])], it->second + w); } } int ans = 0; for (int i = 0; i < n; i++) { if (dp[i].empty() || dpp[i].empty()) continue; vector<pii> v, vv; for (auto it = dp[i].begin(); it != dp[i].end(); it++) v.emplace_back(it->second, it->first); for (auto it = dpp[i].begin(); it != dpp[i].end(); it++) vv.emplace_back(it->second, it->first); sort(v.begin(), v.end(), greater<pii>()); sort(vv.begin(), vv.end(), greater<pii>()); for (auto it1 : v) { if (it1.first + vv[0].first <= ans) break; for (auto it2 : vv) { if (it1.first + it2.first <= ans) break; if ((it1.second & it2.second) == (1 << c[i])) ans = max(ans, it1.first + it2.first); } } } cout << ans << endl;}signed main() {#ifdef LOCAL freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin); freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);#endif ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int Case = 1; //cin >> Case; while (Case--) work(); return 0;}/* _____ _ _ _ __ __ | _ \ | | | | | | \ \ / / | |_| | | | | | | | \ \/ / | ___/ | | | | _ | | } { | | | |_| | | |_| | / /\ \ |_| \_____/ \_____/ /_/ \_\*/阅读本书更多章节>>>>关于代码的亿点点说明：
代码的主体部分位于void work()函数中，另外会有部分变量申明、结构体定义、函数定义在上方。#pragma ...是用来开启 O2、O3 等优化加快代码速度。中间一大堆#define ...是我习惯上的一些宏定义，用来加快代码编写的速度。"debug.h"头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义DEBUG宏），在程序中如果看到dbg(...)是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);这三句话是用于解除流同步，加快输入cin输出cout速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用scanf和printf，但使用了这句话后，cin和scanf、cout和printf不能混用。将main函数和work函数分开写纯属个人习惯，主要是为了多组数据。
本文链接：https://www.kjpai.cn/gushi/2024-04-01/152234.html，文章来源：网络cs，作者：言安琪，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！