A
题面
给定一个 \(n \times n\) 的网格, 每个格子有一个颜色值 \(a_{i,j}\). 问能否重排整个网格中的元素, 使得没有任何一行或一列的所有 \(n\) 个元素颜色相同.
\(\sum n \le 500\)
\(1 \le a_{i,j} \le n^2\)
解析
考虑最极端的情况, 我们可以构造出有 \(n \cdot (n - 1)\) 个相同颜色的网格而没有任何一行或一列的所有 \(n\) 个元素颜色相同, 但是对于有 \(n \cdot (n - 1) + 1\) 个相同颜色的网格由抽屉原理可以得到必定存在一行或一列的所有 \(n\) 个元素颜色相同, 因此只需要判断网格中是否有颜色的出现次数大于 \(n \cdot (n - 1)\).
时间复杂度 \(O(n^2)\).
代码
#include <bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t;cin >> t;while(t--){int n;cin >> n;vector <int> v(n * n + 11, 0);for(int i = 1; i <= n * n; i++){int x;cin >> x;v[x]++;}bool tag = 1;for(int i = 1; i <= n * n; i++)if(v[i] > n * (n - 1)){tag = 0;break;}cout << (tag ? "Yes\n" : "No\n");}return 0;
}
B
题面
有 \(n\) 张卡牌排成队列, 每次只能从前 \(k\) 张中选一张打出同时消耗对应能量, 然后将其移到队尾. 目标卡牌初始在第 \(p\) 位, 每张卡牌打一次消耗 \(a_i\) 能量, 总能量上限为 \(m\). 问在总花费不超过 \(m\) 的前提下, 最多能打出多少次目标卡牌.
\( \sum n \le 5000 \\ 1 \le k,p \le n \le 5000 \\ 1 \le m \le 5000 \\ 1 \le a_i \le m \)
解析
贪心加模拟即可.
代码
#include <bits/stdc++.h>
using namespace std;struct pii{int first, second;bool operator< (const pii y) const{return ((first == y.first) ? (second > y.second) : (first < y.first));}
};int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int tt;cin >> tt;while(tt--){int n, k, p, m;cin >> n >> k >> p >> m;priority_queue <pii> pq;queue <pii> q;for(int i = 1; i <= n; i++){int x;cin >> x;pii y;if(i == p)y = {1, x};else y = {0, x};if(i <= k)pq.push(y);elseq.push(y);}int ans = 0;while(m > 0){auto t = pq.top();pq.pop();if(t.second <= m){q.push(t);m -= t.second;pq.push(q.front());q.pop();if(t.first == 1)ans++;}else break;}cout << ans << '\n';}return 0;
}
C
题面
你有 \(n\) 个任务, 按顺序处理 (从 1 到 \(n\)). 初始体力 \(S = 1\). 对每个任务 \(i\), 可选:
- 放弃: 无影响
- 完成: 获得 \(S \cdot c_i\) 分, 但体力变为 \(S \cdot (1 - \frac{p_i}{100})\)
求最大化总得分.
\(\sum n \le 10^5\)
\(1 \le c_i \le 100\)
\(0 \le p_i \le 100\)
解析
按顺序完成任务获取积分损失体力, 比较典型的动态规划问题. 注意到每次获取的积分和损失的体力都是按比例缩放的, 因此无论当前的体力 \(S\) 是多少, 后续任务中得到的最大积分都是 \(S \times (当前体力为 \ 1 \ 时后续能得到的最大积分)\), 因此我们从后往前做 \(dp\).
设 \(dp[i]\) 表示如果在面临第 \(i\) 个任务时, 我们的体力值为 1, 那么从第 \(i\) 个任务到第 \(n\) 个任务最多可以得到的积分. 状态转移方程 \(dp[i] = \max(dp[i + 1], c[i] + (1 - \frac{p_i}{100}) \cdot dp[i + 1])\). 最后答案为 \(dp[1]\).
时间复杂度 \(O(n)\).
代码
#include <bits/stdc++.h>
using namespace std;int main(){int t;scanf("%d", &t);while(t--){int n;scanf("%d", &n);vector <int> c(n + 1), p(n + 1);for(int i = 1; i <= n; i++)scanf("%d %d", &c[i], &p[i]);vector <double> dp(n + 1, 0.0);dp[n] = 1.0 * c[n];for(int i = n - 1; i; i--)dp[i] = max(dp[i + 1], 1.0 * c[i] + (1.0 - 1.0 * p[i] / 100.0) * dp[i + 1]);printf("%.9lf\n", dp[1]);}return 0;
}
D1
题面
这是该问题的简单版本, 版本区别在 \(n\) 的大小.
给定一个 \(n\) 个节点的有向图的可达性矩阵 \(a_{i, j}\) (\(n \times n\) 的 0/1 字符串, 第 \(i\) 行第 \(j\) 列为 '1' 表示从 \(i\) 能到达 \(j\)), 问是否存在一棵无向树, 在对每条边定向后, 其可达关系恰好匹配该矩阵.
\(\sum n^3 \le 500^3\)
\(2 \le n \le 500\)
解析
我们关心的是两个点是否可以直接到达 (即这两个点在树中连有边), 不妨设 \(i\) 可以到达 \(j\), 即 \(a_{i, j} = 1\), 那么如果这两个点不是直接相连的, 那么就存在若干个中间点将 \(i\) 和 \(j\) 连起来, 也就是存在点 \(k\), 使得 \(a_{i, k} = 1\) 且 \(a_{k, j} = 1\), 因此我们得到了一个必要条件. 通过三次循环可以将所有满足这个条件的边选出来, 然后判断合法性即可.
时间复杂度 \(O(n^3)\).
代码
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;struct DSU{int n;vector <int> f;DSU(int _n) : n(_n){f = vector <int> (n + 1, 0);for(int i = 1; i <= n; i++)f[i] = i;}int find(int x){return (f[x] == x ? x : find(f[x]));}void join(int x, int y){int fx = find(x), fy = find(y);if(fx != fy) f[fx] = fy;}
};void solve(){int n;cin >> n;vector <vector <bool>> v(n + 1, vector <bool> (n + 1, 0));for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){char c;cin >> c;v[i][j] = (c - '0');}for(int i = 1; i <= n; i++)if(!v[i][i]){cout << "No\n";return;}vector <pii> ans;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(i != j && v[i][j]){bool tag = 1;for(int k = 1; k <= n; k++)if(k != i && k != j && v[i][k] && v[k][j]){tag = 0;break;}if(tag) ans.push_back({i, j});}if(ans.size() == n - 1){vector <vector <int>> to(n + 1);DSU dsu = DSU(n);for(auto [x, y] : ans){to[x].push_back(y);dsu.join(x, y);}int num = 0;for(int i = 1; i <= n; i++)if(dsu.f[i] == i) num++;if(num > 1){cout << "No\n";return;}for(int i = 1; i <= n; i++){queue <int> q;q.push(i);while(!q.empty()){int x = q.front();if(!v[i][x]){cout << "No\n";return;}// v[i][x] = 0;q.pop();for(auto l : to[x])q.push(l);}}// for(int i = 1; i <= n; i++)// for(int j = 1; j <= n; j++)// if(v[i][j]){// cout << "No\n";// return;// }cout << "Yes\n";for(auto [x, y] : ans)cout << x << ' ' << y << '\n';}elsecout << "No\n";
}int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t;cin >> t;while(t--) solve();return 0;
}
D2
题面
这是该问题的困难版本, 版本区别在 \(n\) 的大小.
给定一个 \(n\) 个节点的有向图的可达性矩阵 \(a_{i, j}\) (\(n \times n\) 的 0/1 字符串, 第 \(i\) 行第 \(j\) 列为 '1' 表示从 \(i\) 能到达 \(j\)), 问是否存在一棵无向树, 在对每条边定向后, 其可达关系恰好匹配该矩阵.
\(\sum n^2 \le 8000^3\)
\(2 \le n \le 8000\)
解析
很显然这个版本限制了复杂度最多在平方级别, 因此我们在 \(D1\) 的策略就不能用了, 但是我们的基本目标还是一样的, 就是找出直接相连的边.
考虑和 \(D1\) 中一样的情况: \(a_{i, j} = 1, a_{i, k} = 1, a_{k, j} = 1\), 设 \(s_i\) 表示 \(i\) 可以到达的点的个数, 那么有序关系 \(s_i > s_k > s_j\). 因此我们可以将数组 \(s\) 进行排序后从大到小的处理, 设排序后为 \(p\).
考虑节点 \(u\), 取空数组 \(vis\), 我们按照序列 \(p\) 枚举 \(u\) 可能的直接子节点 \(v\), 如果 \(v\) 不在 \(vis\) 中, 那么 \(v\) 就是 \(u\) 的一个直接子节点, 我们将 \(v\) 的所有可达点放到 \(vis\) 中. 原因是如果 \(v\) 不是 \(u\) 的直接子节点, 不妨设中间存在一个 \(u\) 的直接节点 \(w\), 那么有序关系 \(s_u > s_w > s_v\), 因此我们会先处理节点 \(w\), 此时 \(w\) 的所有可达点(其中包括节点 \(v\))都会被放入 \(vis\) 中, 与 \(v\) 不在 \(vis\) 中矛盾.
时间复杂度 \(O(n^2)\).
代码
#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;struct DSU{int n;vector <int> f;DSU(int _n) : n(_n){f = vector <int> (n + 1, 0);for(int i = 1; i <= n; i++)f[i] = i;}int find(int x){return (f[x] == x ? x : find(f[x]));}void join(int x, int y){int fx = find(x), fy = find(y);if(fx != fy) f[fx] = fy;}
};void solve(){int n;cin >> n;vector <vector <bool>> v(n + 1, vector <bool> (n + 1, 0));vector <vector <int>> to(n + 1);vector <pii> num(n + 1, {0, 0});for(int i = 1; i <= n; i++){num[i].first = i;for(int j = 1; j <= n; j++){char c;cin >> c;v[i][j] = (c - '0');num[i].second += (c - '0');if(v[i][j])to[i].push_back(j);}}sort(num.begin() + 1, num.end(), [&](pii x, pii y){return x.second > y.second;});vector <int> vis(n + 1, 0);vector <pii> ans;int siz = 0;for(int i = 1; i <= n; i++){vis = vector <int> (n + 1, 0);int u = num[i].first;for(int j = i + 1; j <= n; j++){int w = num[j].first;if(v[u][w] && !vis[w]){ans.push_back({u, w});siz++;if(siz > n - 1)goto END;for(auto l : to[w])vis[l] = 1;}}}END:;// for(auto [x, y] : ans)// cout << x << ' ' << y << '\n';if(siz == n - 1){vector <vector <int>> to(n + 1);DSU dsu = DSU(n);for(auto [x, y] : ans){to[x].push_back(y);dsu.join(x, y);}int num = 0;for(int i = 1; i <= n; i++)if(dsu.f[i] == i) num++;if(num > 1){cout << "No\n";return;}for(int i = 1; i <= n; i++){queue <int> q;q.push(i);while(!q.empty()){int x = q.front();if(!v[i][x]){cout << "No\n";return;}v[i][x] = 0;q.pop();for(auto l : to[x])q.push(l);}}for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)if(v[i][j]){cout << "No\n";return;}cout << "Yes\n";for(auto [x, y] : ans)cout << x << ' ' << y << '\n';}elsecout << "No\n";
}int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t;cin >> t;while(t--) solve();return 0;
}