2020-2021:teams:farmer_john:jjleo:codeforces_round_655_div._2_virtual_participation
这是本文档旧的修订版！
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| + | + | + | + | O | O |
rank:737
A
- 题意:水。
- 题解:摸。
B
- 题意:给出$n$，求$a,b$使得$a + b = n$且$LCM(a, b)$最小。$(2 \leq n \leq 10^{9})$
- 题解:显然$LCM(a, b) \geq max(a,b)$，盲猜一手$a,b$成倍数关系时最小，$O(\sqrt{n})$枚举$n$的约数即可。
C
- 题意:给定一个$1$到$n$的排列，每次可以选择一个连续的子区间对其进行错位排序，问最少进行几次错位排序可以使得序列有序。
- 题解:如果本身就是有序的需要零次。否则，首先把有序的前缀和后缀全扔掉，中间部分如果本身就是一个错位的，那么只需一次，否则如果有在正确位置上的，就要两次。
D
- 题意:给出一个长度为$n$的环，保证$n$为奇数，每个位置有一个元素，每次操作选定一个元素，将其替换为相邻两个元素的和并删除相邻的两个元素，直到只剩一个元素。求最后剩下这个元素的最大值。$(1 \leq n < 2 \cdot 10^5)$
- 题解:一开始用合并果子的方法优先队列各种限制（甚至pair套pair套pair）直接wa飞了。后来发现每次最少会删掉$\dfrac{n-1}{2}$个互不相邻的数，因此分类讨论dp一下就可以。
E
- 题意:给出一个$n \times m$的方格，每一行被分为了$k_i$个连续的区域，每个区域只能放一个物品，现在设$a_i$为第$i$列的物品个数，求$\sum{i=1}{m}{{a_i}^2}$的最大值。$(1 \le n,m \le 100)$
- 题解:区间dp，设$f_{i,j}$为区间$[i,j]$的物品数量平方和最大值，转移时考虑将尽量多的物品放到同一列上：$f_{i,j}=f_{i,k-1}+x+f_{k+1,j}$，其中$x$为所有包含第$k$列的区域中被完全包含于$[i,j]$的数量。
F
- 题意:
- 题解:
2020-2021/teams/farmer_john/jjleo/codeforces_round_655_div._2_virtual_participation.1594958447.txt.gz · 最后更改: 2020/07/17 12:00 由 jjleo
