本文最后更新于 903 天前,其中的信息可能已经有所发展或是发生改变。
Origional Link
- 给定长度为 n 的数组 a,元素互不相同
- 每次可选择 ai,aj 进行交换
- 求使得长度为 k 的子序列之和达到最小的交换次数
- 对于子序列的和最小,应遵循最小排列
- 即判断原序列中,前 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; |
| |
| } |
Origional Link
- 给定元素为 1∼n 的数组 a
- 求使得 lcm(1,a1)+lcm(2,a2)+…lcm(i,ai) 最大的子序列
- 已知 lcm(a,b)=gcd(a,b)a×b
- 若使得 lcm(a,b) 最大,则应尽可能使得 gcd(a,b)=1
- 对于序列中的元素 ai=i
- 则有 gcd(i,ai+1)=1
- 故 $ai = i +1, a{i + 1} = i$ 时,满足题意
- 即:
- n 为偶数时,遵循排列:2,1,4,3,6,5,…,n,n−1
- n 为奇数时,遵循排列: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; |
| |
| } |
Origional Link
- 给定长度为 n 的数组 a
- 每次操作,可以将所有 ai=x 的元素操作变为 ai=0
- 求最少操作多少次,可以使得原数组元素不严格单调递增
int a[N]
存储数组元素,set<int> b
存储当前枚举到i
之前,需要将 ai 变为 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]
的元素更新为 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 没有什么难度,但是做的太急(permutation是无重复元素的排列数组),没有思考好规律
- B 真的是 WA 到飞起,怎么会有我这种笨比推出来 gcd(i,ai+1)=1 规律还解不出来的人,建议自己
remake
- C 一开始思路很乱,后来发现模拟就好了,写完直接交一发就过,没什么算法难度
- 手速场狂 WA两道 A,B
nt
题的我真是没救了,前几场着实给我打破防了,这回还好最后没放弃,继续努力吧