|
更好的阅读体验
\color{red}{更好的阅读体验}
更好的阅读体验
A. Wonderful Permutation
题目大意
Origional Link
- 给定长度为
n
n
n 的数组
a
a
a，元素互不相同
- 每次可选择
a
i
,
a
j
a_i,a_j
ai?,aj? 进行交换
- 求使得长度为
k
k
k 的子序列之和达到最小的交换次数
思想
- 对于子序列的和最小，应遵循最小排列
- 即判断原序列中，前
k
k
k 个元素，有多少满足
a
i
≤
k
a_i\le k
ai?≤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(){
int _;
cin >> _;
while(_ --){
solve();
}
return 0;
}
B. Woeful Permutation
题目大意
Origional Link
- 给定元素为
1
～
n
1\sim n
1～n 的数组
a
a
a
- 求使得
l
c
m
(
1
,
a
1
)
+
l
c
m
(
2
,
a
2
)
+
…
l
c
m
(
i
,
a
i
)
lcm(1,a_1)+lcm(2,a_2)+\dots lcm(i,a_i)
lcm(1,a1?)+lcm(2,a2?)+…lcm(i,ai?) 最大的子序列
思想
- 已知
l
c
m
(
a
,
b
)
=
a
×
b
g
c
d
(
a
,
b
)
lcm(a,b) = \frac{a\times b}{gcd(a,b)}
lcm(a,b)=gcd(a,b)a×b?
- 若使得
l
c
m
(
a
,
b
)
lcm(a,b)
lcm(a,b) 最大，则应尽可能使得
g
c
d
(
a
,
b
)
=
1
gcd(a,b) = 1
gcd(a,b)=1
- 对于序列中的元素
a
i
=
i
a_i=i
ai?=i
- 则有
g
c
d
(
i
,
a
i
+
1
)
=
1
gcd(i,a_i + 1) = 1
gcd(i,ai?+1)=1
- 故
a
i
=
i
+
1
,
a
i
+
1
=
i
a_i = i +1, a_{i + 1} = i
ai?=i+1,ai+1?=i 时，满足题意
- 即：
-
n
n
n 为偶数时，遵循排列：
2
,
1
,
4
,
3
,
6
,
5
,
…
,
n
,
n
?
1
2,1,4,3,6,5,\dots ,n,n-1
2,1,4,3,6,5,…,n,n?1
-
n
n
n 为奇数时，遵循排列：
1
,
3
,
2
,
5
,
4
,
7
,
6
…
,
n
,
n
?
1
1,3,2,5,4,7,6\dots ,n,n-1
1,3,2,5,4,7,6…,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(){
int _;
cin >> _;
while(_ --){
solve();
}
return 0;
}
C. Sort Zero
题目大意
Origional Link
- 给定长度为
n
n
n 的数组
a
a
a
- 每次操作，可以将所有
a
i
=
x
a_i = x
ai?=x 的元素操作变为
a
i
=
0
a_i = 0
ai?=0
- 求最少操作多少次，可以使得原数组元素不严格单调递增
思想
int a[N]存储数组元素，set<int> b存储当前枚举到i之前，需要将
a
i
a_i
ai? 变为
0
0
0 的
x
x
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]的元素更新为
0
0
0，且在更新时，要将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(){
int _;
cin >> _;
while(_ --){
solve();
}
return 0;
}
后记
-
A
A
A 没有什么难度，但是做的太急(permutation是无重复元素的排列数组)，没有思考好规律
-
B
B
B 真的是
W
A
\color{red}{WA}
WA 到飞起，怎么会有我这种笨比推出来
g
c
d
(
i
,
a
i
+
1
)
=
1
gcd(i,a_i + 1) = 1
gcd(i,ai?+1)=1 规律还解不出来的人，建议自己
remake -
C
C
C 一开始思路很乱，后来发现模拟就好了，写完直接交一发就过，没什么算法难度
- 手速场狂
W
A
\color{red}{WA}
WA两道
A
,
B
A,B
A,B
nt题的我真是没救了，前几场着实给我打破防了，这回还好最后没放弃，继续努力吧
|