比赛链接:Here
1541A. Pretty Permutations
给定 \(1,2,3,4,...n\) 序列,让每一个数字都不处于原来的位置,但总的移动距离要最小
- \(n\) 为偶数的情况 \(1,2,3,4 \to 2,1,4,3\)
- \(n\) 为奇数的情况 \(1,2,3,4,5 \to 2,1,4,5,3\)
【AC Code】
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int a[110];
for (int i = 1; i <= 101; ++i)a[i] = i;
for (int i = 1; i <= 101; i += 2) swap(a[i], a[i + 1]);
int _; for (cin >> _; _--;) {
int n; cin >> n;
if (n & 1) {
for (int i = 1; i <= n - 2; ++i)
cout << a[i] << " ";
cout << n << " " << a[n - 1];
} else {
for (int i = 1; i <= n; ++i)
cout << a[i] << " ";
}
cout << '\n';
}
}
1541B. Pleasant Pairs
问有多少对数 \((i,j)\) 满足以下条件:
- \(i < j\)
- \(a_i * a_j = i + j\)
相同题型:ABC206 C - Swappable
枚举所有 \(a_i\) 的倍数加以判断
注意点:\(i \not = j\)
时间复杂度:\(\mathcal{O}(n·log(n))\)
【AC Code】
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int _; for (cin >> _; _--;) {
ll n; cin >> n;
vector<ll>a(n + 1);
for (int i = 1; i <= n; ++i)cin >> a[i];
ll cnt = 0;
for (int i = 1; i <= n; ++i)
for (int j = a[i] - i; j <= n; j += a[i]) {
if (j <= i) continue;
else if (a[i] * a[j] == i + j)cnt++;
}
cout << cnt << "\n";
}
}
1541C. Great Graphs
\(n\) 个点和 \(d\) 数组,表示第 \(i\) 个点到第一个点的最短距离。
现在需要进行加边,然后使得所有边权和最小(可加负边)
思路转自码尔泰
很明显其实, \(d[i]\) 其实可以排个序,对于最后结果并没有影响,之后我们可以考虑对于每个点,只建一条正向道路,使得满足题目条件,然后在满足题目条件的情况下尽可能多地建反向道路,这样可以减小总的边权和。
【AC Code】
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int _; for (cin >> _; _--;) {
int n; cin >> n;
vector<ll>d(n + 1), sum(n + 1);
for (int i = 1; i <= n; ++i)cin >> d[i];
ll b = 1e9 + 7;
sort(d.begin() + 1, d.end());
for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + d[i];
ll ans = 0;
for (int i = 3; i <= n; ++i)
ans -= d[i] * (i - 2) - sum[i - 2];
cout << ans << "\n";
}
}