比赛链接：Here
AB水题，跳过
C - Swappable
在数组中找到满足条件的数对 \((i,j)\)
- \(1 \le i < j \le N (N\in[2,3e5])\)
- \(A_i \not= A_j\)
一道经典利用 map 减少搜索规模的题，
先假设每个数互不相同：ans = n * (n - 1) / 2
map 存每个数出现的次数，然后减去相同的情况 ans -= x * (x - 1) / 2
【AC Code】
void solve() {
ll n;
cin >> n;
ll ans = n * (n - 1) / 2;
map<ll, ll>mp;
for (int i = 1; i <= n; ++i) {
ll x; cin >> x;
mp[x]++;
}
for (auto x : mp)
ans -= x.second * (x.second - 1) / 2;
cout << ans;
}
D - KAIBUNsyo
在数组 \(A\) 中有 \(n\) 个正整数，给定一种操作：
- 选择 \(x\) 和 \(y\) ，将数组中全部 \(x\) 替换为 \(y\)
请问最少次数是多少可以使得数组$A $ 回文
首先一个重要的点：
- 对于每一个 \(A_i \not= A_{N+1-i}\) 的数对，最终都会被某一个相同的数替代
让我们将其视为连接无向图中顶点 \(A_i , A_{N + 1 ? i}\) 之间的边。
然后，我们可以看到以下事实：
- 对于每个整数对 \((i,j)\) ，如果 \(i\) 和 \(j\) 属于图的同一个连通分量，则 \(i\) 和 \(j\) 都应该用相同的整数代替。
现在，我们如何最小化操作次数以使连通分量中的所有整数都相同？
如果一个连通分量有 \(k\) 个整数，显然我们需要 \(k ? 1\) 次或更多次操作才能使它们成为相同的整数。 即目标可以在 \(k-1\) 次替换中实现，如下所述：
在连通分量中固定一个整数，并将连通分量中的所有其他整数更改为固定整数。
因此，该问题的解决方案是（\(A\) 中不同整数的数量）-（图的连通分量的数量）。
有几种方法可以找到这个值； 两种典型的方法是：
- 对每个连接的组件执行 DFS 或 BFS。\(\mathcal{O}(N)\)
- 使用并查集。\(\mathcal{O}(N\ log\ N)\)
这里采用 DFS 解决问题
【AC Code】
using G = vector<vector<int>>;
void dfs(int u, vector<bool> &f, G &g) {
if (!f[u]) {return;}
f[u] = false;
for (auto &v : g[u]) dfs(v, f, g);
}
void solve() {
int n; cin >> n;
vector<int>a(n);
vector<bool>f(2e5 + 10, false);
G g(2e5 + 10);
int cnt = 0;
for (auto &x : a) {
cin >> x;
if (!f[x]) {f[x] = true, cnt++;}
}
int p = 0, q = n - 1;
while (p < q) {
g[a[p]].emplace_back(a[q]);
g[a[q]].emplace_back(a[p]);
p++, q--;
}
for (int i = 1; i <= 2e5; ++i)
if (f[i]) { cnt--; dfs(i, f, g); }
cout << cnt << "\n";
}
F - Interval Game 2
Alice 和 Bob 又在玩游戏了，
他们有 \(N\) 个半开区间 \([L_i,R_i)\) 来进行 Game：
-
Alice 和 Bob 交替进行以下操作，Alice 先行。
从 \(N\) 个间隔中，选择一个不与任何已选择的间隔相交的间隔。
无法进行操作的玩家失败，其他玩家获胜。
如果两个玩家都以最佳操作，哪个玩家会获胜？
https://drken1215.hatenablog.com/entry/2021/06/19/224100
const int N = 100;
int n;
vector<int>L, R;
vector<vector<int>>dp;
int solve(int l = 0, int r = N) {
if (l == r) return 0;
if (dp[l][r] != -1)return dp[l][r];
set<int>s;
for (int i = 0; i < n; ++i) {
if (l <= L[i] and R[i] <= r) {
int tmp = solve(l, L[i]) ^ solve(R[i], r);
s.insert(tmp);
}
}
int grundy = 0;
while (s.count(grundy)) ++grundy;
return dp[l][r] = grundy;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int _; for (cin >> _; _--;) {
cin >> n;
L.resize(n), R.resize(n);
for (int i = 0; i < n; ++i) {
cin >> L[i] >> R[i];
L[i]--, R[i]--;
}
dp.assign(N, vector<int>(N + 1, -1));
cout << (solve() > 0 ? "Alice\n" : "Bob\n");
}
}