Codeforces Round #692 (Div. 2, based on Technocup 2021 Elimination Round 3)
C. Peaceful Rooks
题意
给你一个n*n的表格和m个(m<n)棋子，棋子不会在同一行或同一列中出现两个，问你最少要多少步才能将其全部移到主对角的位置
思路
起初想的是我去判断少量的点，来判断他的特殊性，然后我发现(2,3),(3,2)这样的坐标点需要3次，然后如果不是横纵坐标刚好相反的点，但是其所在位置的对角线位置横纵坐标均有棋子存在，那么这样的点需要移动棋子个数+1次。如果我去前后均考虑少量的点而且画在一个平面，我可能是会看出来这种规律，也就是说以后需要去考虑少量的点的排列组合比如说2种点然后组合到一起观察
正解：
形成环则+1
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int find(int x) {
if (x != f[x]) f[x] = find(f[x]);
return f[x];
}
void solve() {
int n, m; cin >> n >> m;
for (int i = 1; i <= n; ++i) f[i] = i;
int cnt = 0, ans = m;
for (int i = 1; i <= m; ++i) {
int x, y; cin >> x >> y;
if (x == y) {
--ans; continue;
}
int fx = find(x), fy = find(y);
if (fx == fy) ++cnt;
f[fx] = fy;
}
cout << ans + cnt << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
}
错误代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
bool row[N], col[N];
bool is_row[N], is_col[N];
void solve() {
int n, m; cin >> n >> m;
for (int i = 0 ; i <= n; ++i){
row[i] = col[i] = is_row[i] = is_col[i] =false;
}
int cnt = 0;
vector<pair<int,int>>op;
map<pair<int,int>, bool>mt;
int f1 = 0;
int q = m;
while (m--) {
int x, y; cin >> x >> y;
mt[{x, y}] = 1;
op.push_back({x, y});
if (mt[{y, x}] == 1 && x != y) {
f1++;continue;
}
if (row[y])is_row[x] = 1;
if (col[x])is_col[y] = 1;
row[x] = 1, col[y] = 1;
if (x == y) ++ cnt;
}
int f = 0;
for (auto i : op) {
if (is_row[i.first] && is_col[i.second])f++;
}
if (f1 == 0 && f){
cout << (q - cnt + 1) << endl;
}else if (f1 && f == 0) cout << f1 * 3 << endl;
else if (f1 && f) cout << (f1 * 3 + (q - cnt - 2 * f1 + 1)) << endl;
else cout << q - cnt << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
}