2020-2021:teams:farmer_john:jjleo:codeforces_round_647_div._2_virtual_participation
这是本文档旧的修订版！
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| + | + | + | + | + | O |
rank:39
A
- 题意:每次可以对$a$乘以$2,4,8$或者在整除的情况下除以$2,4,8$，问最少多少步可以变成$b$或判断无解。
- 题解:不妨设$a \le b$，那么如果有解必须满足$a|b$而且$\frac{b}{a}$是$2$的次幂，然后只需要对$8,4,2$分别试除即可。
B
- 题意:给出一个$n$个元素的集合$s$，求最小的正整数$k$使得所有元素异或$k$组成的新集合和原集合相同，或判断无解。$(1 \leq n \leq 1024, 0 \leq s_i < 1024)$
- 题解:数据范围很小，暴力枚举$1$到$2047$即可。
C
- 题意:求$\sum_{i=1}^{n}{\text{pop_count}(i \oplus (i-1))}$。$(1 \leq n \leq 10^{18})$
- 题解:设$f(n)=\sum_{i=1}^{n}{\text{pop_count}(i \oplus (i-1))}$，有递推式$f(n)=2f(2^{i-1})+1+f(n-2^i)$，其中$2^i$是$n$的最高位$1$对应的次幂，边界为$f(0)=0$。
D
- 题意:$n$个博客和$n$个主题，按照顺序写这$n$个博客，每个博客和其它一些博客会有一些联系，每个博客的主题就是所有与它有联系且已经写过的主题的$mex$。现在给定每个博客希望写哪个主题，问是否存在一个写博客的顺序使得这个条件满足。
- 题解:建图，根据目标主题从小到大以此考虑每个博客，相同主题的顺序无所谓，因为显然它们如果不相互独立一定无解。然后每写一个博客更新所有与它相连的博客的$mex$值，只需要维护每个点现在$mex$是多少，然后一但中断就不更新即可。中途如果某个博客的主题与题目给出的不符即无解，否则有解。
E
- 题意:
- 题解:
F
- 题意:
- 题解:
2020-2021/teams/farmer_john/jjleo/codeforces_round_647_div._2_virtual_participation.1591961647.txt.gz · 最后更改: 2020/06/12 19:34 由 jjleo
