Codeforces Round #813 (Div. 2)(A~C)
Codeforces Round #813 (Div. 2)(A~C)
浪漫主义狗
发布于 2022-09-21 15:05:12
发布于 2022-09-21 15:05:12
A. Wonderful Permutation
题目大意
- 给定长度为 n 的数组 a，元素互不相同
- 每次可选择 a_i,a_j 进行交换
- 求使得长度为 k 的子序列之和达到最小的交换次数
思想
- 对于子序列的和最小，应遵循最小排列
- 即判断原序列中，前 k 个元素，有多少满足 a_i\le k，满足该条件则不需要交换，否则需要交换
代码
#include <bits/stdc++.h>
using namespace std;
#define re register
const int N = 1e6 + 3;
int a[N];
void solve(){
int n, k;
cin >> n >> k;
for(re int i = 1; i <= n; i ++) cin >> a[i];
int cnt = 0;
for(re int i = 1; i <= k; i ++) if(a[i] > k) cnt ++;
cout << cnt << endl;
}
int main(){
// solve();
int _;
cin >> _;
while(_ --){
solve();
}
return 0;
}B. Woeful Permutation
题目大意
- 给定元素为 1\sim n 的数组 a
- 求使得 lcm(1,a_1)+lcm(2,a_2)+\dots lcm(i,a_i) 最大的子序列
思想
- 已知 lcm(a,b) = \frac{a\times b}{gcd(a,b)}
- 若使得 lcm(a,b) 最大，则应尽可能使得 gcd(a,b) = 1
- 对于序列中的元素 a_i=i
- 则有 gcd(i,a_i + 1) = 1
- 故 ai = i +1, a{i + 1} = i 时，满足题意
- 即： n 为偶数时，遵循排列：2,1,4,3,6,5,\dots ,n,n-1 n 为奇数时，遵循排列：1,3,2,5,4,7,6\dots ,n,n-1
代码
#include <bits/stdc++.h>
using namespace std;
#define re register
void solve(){
int n;
cin >> n;
if(n % 2 == 0){
for(re int i = 2; i <= n; i += 2) cout << i << " " << i - 1 << " ";
}
else{
cout << 1 << " ";
for(re int i = 3; i <= n; i += 2) cout << i << " " << i - 1 << " ";
}
cout << endl;
}
int main(){
// solve();
int _;
cin >> _;
while(_ --){
solve();
}
return 0;
}C. Sort Zero
题目大意
- 给定长度为 n 的数组 a
- 每次操作，可以将所有 a_i = x 的元素操作变为 a_i = 0
- 求最少操作多少次，可以使得原数组元素不严格单调递增
思想
- int a[N]存储数组元素，set<int> b存储当前枚举到i之前，需要将 0 的 x 值
- 从i = 2开始枚举a[i]： 先判断a[i]是否在b中，若存在，则更新a[i] = 0 若a[i - 1] > a[i]，说明需要将a[i - 1]更新，将b.insert(a[i - 1])，且要使得i之前所有的a[j] == a[i - 1]的元素更新为
- 由于我们按顺序枚举，故在
i之前的序列一定满足不严格单调递增，在枚举结束之后，b中元素个数即为操作次数
代码
#include <bits/stdc++.h>
using namespace std;
#define re register
const int N = 1e6 + 3;
int a[N];
set<int> b;
void solve(){
int n;
cin >> n;
for(re int i = 1; i <= n; i ++) cin >> a[i];
for(re int i = 2; i <= n; i ++){
if(b.count(a[i]) > 0) a[i] = 0;
if(a[i - 1] > a[i]){
b.insert(a[i - 1]);
a[i - 1] = 0;
for(re int j = i - 1; a[j] != 0 && j >= 1; j --){
b.insert(a[j]);
a[j] = 0;
}
}
}
cout << b.size() << endl;
b.clear();
}
int main(){
// solve();
int _;
cin >> _;
while(_ --){
solve();
}
return 0;
}后记
- A 没有什么难度，但是做的太急(permutation是无重复元素的排列数组)，没有思考好规律
- B 真的是 \color{red}{WA} 到飞起，怎么会有我这种笨比推出来 gcd(i,a_i + 1) = 1 规律还解不出来的人，建议自己remake
- C 一开始思路很乱，后来发现模拟就好了，写完直接交一发就过，没什么算法难度
- 手速场狂 \color{red}{WA}两道 A,B nt题的我真是没救了，前几场着实给我打破防了，这回还好最后没放弃，继续努力吧
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022-8-14 1，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录