链接：https://ac.nowcoder.com/acm/contest/120562
题目按照通过人数降序排序。
A – 比赛安排
算法：
模拟。
思路：
连续三场比赛类型不相同，那么就要是形如 \(1\) \(2\) \(3\) \(1\) \(2\) \(3\) 这种循环，容易想到最多的个数不能比最少的个数多两个及以上，因此只需判断最多的个数是不是比最小的个数多 \(1\) 个以内。
关键代码：
void miyan()
{
ll a, b, c;
cin >> a >> b >> c;
if (max({a, b, c}) - min({a, b, c}) <= 1)
cout << "YES" << endl;
else
cout << "NO" << endl;
}B – NCPC
算法：
贪心。
思路：
如果最大值出现了奇数次，那么最后剩余的肯定是最大值，那么答案中只有最大值是 \(1\)。
如果最大值出现了偶数次，那么最大值肯定保留不下（既为 \(0\)），其余的任意元素都可以保留（既为 \(1\)）：
- 选择一个不是最大值的 \(x\)，保留任意一个，其余全部元素（除了保留的一个 \(x\)）轮流与最大值进行对决，由于最大值出现了偶数次，最后剩余的一个元素必然是保留的 \(x\)。
关键代码：
void miyan()
{
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a)
cin >> x;
map<int, int> m;
for (auto x : a)
++m[x];
auto b = a;
ranges::sort(b);
b.erase(unique(all(b)), b.end());
map<int, int> st;
bool ok = 1;
for (int i = b.size() - 1; i >= 0; --i)
{
if (i == b.size() - 1)
{
if (m.count(b[i]) && m[b[i]] % 2 == 1)
{
st[b[i]] = 1;
ok = 0;
}
}
else if (ok)
{
st[b[i]] = 1;
}
}
string ans = string(n, '0');
for (int i = 0; i < n; ++i)
{
if (st.count(a[i]) && st[a[i]])
ans[i] = '1';
}
cout << ans << endl;
}I – 01回文
算法：
贪心。
思路：
结论：如果 \(a[i][j]\) 只出现了 \(1\) 次其必然不存在满足条件的 \((x, y)\)，其余情况全部存在。
证明：由于 \(a[i][j]\) 出现了不止一次且只有 \(0\) 和 \(1\) 两种元素，那么 \(a[i][j]\) 到达距离它最近的相同元素的路径必然是回文的，其中间由 \(k(k >= 0)\) 个非 \(a[i][j]\) 元素组成，结尾是 \(a[x][y](a[x][y] = a[i][j])\)。
关键代码：
void miyan()
{
int n, m;
cin >> n >> m;
vector<string> g(n + 1);
for (int i = 1; i <= n; ++i)
{
cin >> g[i];
g[i] = ' ' + g[i];
}
if (n == 1 && m == 1)
{
cout << 'Y' << endl;
return;
}
int cnt0 = 0, cnt1 = 0;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if (g[i][j] == '1')
++cnt1;
else
++cnt0;
}
}
if (cnt0 == 1 || cnt1 == 1)
{
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
if (g[i][j] == '0' && cnt0 == 1)
cout << 'N';
else if (g[i][j] == '1' && cnt1 == 1)
cout << 'N';
else
cout << 'Y';
}
cout << endl;
}
return;
}
vector<string> ans(n, string(m, 'Y'));
for (auto s : ans)
{
for (auto c : s)
cout << c;
cout << endl;
}
}F – x?y?n!
算法：
贪心，位运算。
思路：
观察题目样例可得出一个 \(guess\)：\(x \oplus y = n, y = x + n\)。
那怎么确定 \(x\) 呢？
已知 \(x \oplus y = n\)，移项得 \(y = x \oplus n\)，那么需要满足 \(y = x + n\) 与 \(y = x \oplus n\) 两个式子，继续展开：
- \(y = x + n \Rightarrow y = x|n + x\text{&}n\)
- \(y = x \oplus n \Rightarrow y = x|n – x\text{&}n\)
那么只需满足 \(x\text{&}n\) 为 \(0\) 即可。
考虑到 \(n\) 为 \(int\) 类型，其最大有 \(31\) 位，只需令 \(x\) 等于 \(n\) 左移 \(31\) 位即可，\(y\) 易得。
关键代码：
void miyan()
{
ll n;
cin >> n;
cout << (n << 31ll) << ' ' << (n << 31ll | n) << endl;
}H – 权值计算
算法：
贡献法，贪心。
思路：
伪代码计算的是：数组中每个前缀中不同元素个数的和。
经典贡献法题目。
考虑对数组所有不同子数组中 \(a[i]\) 的贡献找规律。
对于数组 \(a = {1, 2, 3, 2, 2, 4}\)，\(a[i]\) 在 \(l = [1, n]\)，\(r = [l, n]\) 子数组的贡献为：
| l\r | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 3 | 3 | 4 |
| 2 | 1 | 2 | 2 | 2 | 3 | |
| 3 | 1 | 2 | 2 | 3 | ||
| 4 | 1 | 1 | 2 | |||
| 5 | 1 | 2 | ||||
| 6 | 1 |
容易发现，对于先前从未出现过的元素，其在当前列会相较于上一列增加 \(i\) 的贡献，而出现过的元素会相较于上一列增加 \(i – pos\) 的贡献（\(pos\) 为上一次出现的位置），第 \(i\) 列的总贡献为 \(sum_i * (n – i + 1)\)。
关键代码：
void miyan()
{
ll n;
cin >> n;
vector<ll> a(n + 1);
for (int i = 1; i <= n; ++i)
cin >> a[i];
map<int, int> m;
ll ans = 0;
ll sum = 0;
for (int i = 1; i <= n; ++i)
{
ll last = 0;
if (m.count(a[i]))
last = m[a[i]];
m[a[i]] = i;
sum += i - last;
ans += sum * (n - i + 1);
}
cout << ans << endl;
}E – 01矩阵
算法：
构造。
思路：
难度对于每个人来说差距很大，脑电波对上直接秒的题。
观察以下规律：
/*
2
00
01
3
000
011
010
4
0000
0111
0100
0101
5
00000
01111
01000
01011
01010
*/关键代码：
void miyan()
{
ll n;
cin >> n;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
cout << min(i, j) % 2;
cout << endl;
}
}J – 终于再见
算法：
多源 \(bfs\)。
思路：
对于每个点都 \(bfs\) 找比它等级高的点的时间复杂度为 \(O(n * (n + m))\)。
引入性质：在任意简单无向图中，不同度数的个数 \(k\) 满足 \(k ≤ 2 \sqrt n\)。
此时，我们根据度数对点进行分组，逆序对每个组进行多源 \(bfs\)，每组的复杂度均为 \(O(n + m)\)，因此时间复杂度优化至 \(O(\sqrt n * (n + m))\)。
具体实现：
- 首先根据度数对点进行分组，逆序对每个组进行多源 \(bfs\)；
- 定义 \(dist_u\) 为 \(u\) 点到更高度数点的最短距离；
- 对于当前组的点 \(u\)，如果其 \(dist_u\) 为 \(\infty\)，说明在当前连通分支中，没有比其度数高的点，得 \(u\) 点答案为 \(-1\)；
- 否则其答案就为 \(dist_u\)（因为在先前比它度数高的点都遍历完了，其 \(dist\) 就为答案）；
- 多源 \(bfs\) 时，只向度数更低的点走。
关键代码：
void miyan()
{
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> du(n + 1, 0);
for (int i = 1; i <= m; ++i)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
++du[u], ++du[v];
}
map<int, deque<int>, greater<>> hash;
for (int i = 1; i <= n; ++i)
hash[du[i]].push_back(i);
vector<int> ans(n + 1);
vector<int> dist(n + 1, 1e9);
for (auto [x, q] : hash)
{
for (auto u : q)
{
if (dist[u] == 1e9)
{
ans[u] = -1;
dist[u] = 0;
}
else
{
ans[u] = dist[u];
dist[u] = 0;
}
}
while (q.size())
{
auto u = q.front();
q.pop_front();
for (auto v : g[u])
{
if (du[v] >= x)
continue;
if (dist[v] > dist[u] + 1)
{
dist[v] = dist[u] + 1;
q.push_back(v);
}
}
}
}
for (int i = 1; i <= n; ++i)
cout << ans[i] << ' ';
cout << endl;
}
