Codeforces Round #813 (Div. 2)(A~C)
本文最后更新于 903 天前,其中的信息可能已经有所发展或是发生改变。

A. Wonderful Permutation


题目大意

Origional Link

  • 给定长度为 nn 的数组 aa,元素互不相同
  • 每次可选择 ai,aja_i,a_j 进行交换
  • 求使得长度为 kk 的子序列之和达到最小的交换次数

思想

  • 对于子序列的和最小,应遵循最小排列
  • 即判断原序列中,前 kk 个元素,有多少满足 aika_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


题目大意

Origional Link

  • 给定元素为 1n1\sim n 的数组 aa
  • 求使得 lcm(1,a1)+lcm(2,a2)+lcm(i,ai)lcm(1,a_1)+lcm(2,a_2)+\dots lcm(i,a_i) 最大的子序列

思想

  • 已知 lcm(a,b)=a×bgcd(a,b)lcm(a,b) = \frac{a\times b}{gcd(a,b)}
  • 若使得 lcm(a,b)lcm(a,b) 最大,则应尽可能使得 gcd(a,b)=1gcd(a,b) = 1
  • 对于序列中的元素 ai=ia_i=i
  • 则有 gcd(i,ai+1)=1gcd(i,a_i + 1) = 1
  • 故 $ai = i +1, a{i + 1} = i$ 时,满足题意
  • 即:
    • nn 为偶数时,遵循排列:2,1,4,3,6,5,,n,n12,1,4,3,6,5,\dots ,n,n-1
    • nn 为奇数时,遵循排列:1,3,2,5,4,7,6,n,n11,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


题目大意

Origional Link

  • 给定长度为 nn 的数组 aa
  • 每次操作,可以将所有 ai=xa_i = x 的元素操作变为 ai=0a_i = 0
  • 求最少操作多少次,可以使得原数组元素不严格单调递增

思想

  • int a[N]存储数组元素,set<int> b存储当前枚举到i之前,需要将 aia_i 变为 00xx
  • 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]的元素更新为 00,且在更新时,要将a[j] != 0的元素也加入b
  • 由于我们按顺序枚举,故在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;
}

后记

  • AA 没有什么难度,但是做的太急(permutation是无重复元素的排列数组),没有思考好规律
  • BB 真的是 WA\color{red}{WA} 到飞起,怎么会有我这种笨比推出来 gcd(i,ai+1)=1gcd(i,a_i + 1) = 1 规律还解不出来的人,建议自己remake
  • CC 一开始思路很乱,后来发现模拟就好了,写完直接交一发就过,没什么算法难度
  • 手速场狂 WA\color{red}{WA}两道 A,BA,B nt题的我真是没救了,前几场着实给我打破防了,这回还好最后没放弃,继续努力吧
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇