2020-2021:teams:farmer_john:jjleo:codeforces_round_651_div._2_virtual_participation
这是本文档旧的修订版！
| A | B | C | D | E | F1 | F2 |
|---|---|---|---|---|---|---|
| + | + | + | + | + | + | O |
rank:26
A
- 题意:给定$n$，求最大的$gcd(a,b)$，其中$1 \leq a < b \leq n$。$(2 \leq n \leq 10^6)$
- 题解:
我太菜了，去线性筛最小质因子。因为$a,b$不同，所以肯定要丢掉一个质因子，最小的质因子是$2$，因此只需要取$\lfloor{\frac{n}{2}}\rfloor$和$2 \cdot \lfloor{\frac{n}{2}}\rfloor$，答案为$\lfloor{\frac{n}{2}}\rfloor$。
B
- 题意:将$2n$个元素扔掉两个，剩下的两两一组，要求每组的和两两不互质，求分组方案。
- 题解:扔掉两个后一定可以让每组的和都是偶数。
C
- 题意:玩游戏。给定数字$n$，每次有下面两种操作，如果数字不为$1$可以$-1$，或除以一个不为$1$的奇数因数，两人轮流操作，无法操作的人输，问先手是否必胜。
- 题解:$n=1$直接输了，$n$为奇数直接变成$1$就赢了。如果$n$没有奇质因子，显然只能$-1$变成奇数就输了。否则如果有$1$个奇质因子，那么可以除掉这个奇质因子，如果结果是$2$就输了，否则就赢了；如果有多个奇质因子，可以人为操控除以一个奇因数使得结果是$2$和一个奇质因子的乘积，必胜。
D
- 题意:给定长度为$n$的序列，求一个长度为$k$的子序列，最大化$min(max(s_1, s_3, s_5, \ldots), max(s_2, s_4, s_6, \ldots))$。$(2 \leq k \leq n \leq 2 \cdot 10^5)$
- 题解:求最大的最小值，二分答案。分奇数位最大值是最小值和偶数位最大值是最小值两种情况，以奇数位为例，奇数位只能选$\ge mid$的值，偶数位随便选一个，而且必须选一个，最后看能不能选够$k$个即可。
E
- 题意:给定两个$01$串$s$和$t$，每次可以将$s$的一个子序列顺时针循环同构一次，问最少要多少次操作可以将$s$变成$t$，或判断无解。
- 题解:如果$01$数量不同则无解。否则每次操作相当于交替选择$s0t1$和$s1t0$的位置偶数次，并将相同位置的$s$和$t$变为一样。答案变为给定一个$01$串，选择最少的$01$交替且长度为偶数的子序列将其完全覆盖，设$f_{0,1}$为结尾$0,1$的子序列个数，dp扫一遍即可。
F
- 题意:
- 题解:
2020-2021/teams/farmer_john/jjleo/codeforces_round_651_div._2_virtual_participation.1593069989.txt.gz · 最后更改: 2020/06/25 15:26 由 jjleo
