Codeforces Round #563 (Div. 2)

未分类

D: Ehab and the Expected XOR Problem

链接：http://codeforces.com/contest/1174/problem/D

题意：给定正整数$n,x$，构造一个数列$a_1,a_2,...,a_{len}$使得：$1\leq a_i < 2^n$且所有区间异或和的集合不包含$0$和$x$，同时$len$最大。

假设对数列$a_1,a_2,...,a_{len}$求前缀异或和得到$b_0,b_1,b_2,...,b_{len}$，题意的要求可以转换成：不存在$b_i \oplus b_j=0$且不存在$b_i \oplus b_j=x$，其中$i \not= j$。
容易知道从前缀异或和$\{b_i\}$可以转换得到$\{a_i\}$，接下来求$\{b_i\}$。
首先$b_i \not= b_j,b_i \not= x$，而且$1 \leq b_i < 2^n$。
1、如果$x<2^n$，那么对每个数$y(1\leq y < 2^n)$来说，唯一存在一个$z(1\leq z < 2^n)$使得$y \oplus z = x$，而且$y,z$是成对的，也就是在$[1,x) \bigcup(x,2^n)$这$2^n-2$个数中，有$2^{n-1}-1$对数，每对数只能取一个。所以最后会有$2^{n-1}-1$个数。
2、如果$x\geq 2^n$，那么对每个数$y(1\leq y < 2^n)$，都不存在$z(1\leq z <2^n)$使得$y \oplus z=x$，这样的话$\{b_1,b_2,...,b_{len}\}=\{1,2,3,...,2^n-2,2^n-1\}$是一个可行解。
对$\{b_i\}$倒过来异或一次就可以得到$\{a_i\}$了。

E: Ehab and the Expected GCD Problem

链接：http://codeforces.com/contest/1174/problem/E

题意：$p$是一个$1,2,...,n$的全排列$p_1,p_2,...,p_n$，定义$f(p)$为$p$的前缀$GCD$的不同数的个数，求使$f(p)$取得最大值的$p$的个数。

假设$p_1=\prod a_i^{b_i}$，其中$a_i$是互不相同的质数，那么这个排列能取到的最大的$f(p)$是$\sum b_i$，所以全部排列取得的最大值就是分解质因数后质数个数的和，显然$2^k(2^k\leq n,2^{k+1}>n)$能让质数个数最大，其次，如果$2^{k-1}*3\leq n$，那么$2^{k-1}*3$也能作为一个合格的$p_1$，$p_1$的取值只有以上两种可能。

定义$dp(two,three,i)$表示，前$i$个数的前缀$GCD$是$2^{two}3^{three}$，使全部前缀$GCD$个数最多的全排列个数，那么转移有三种：
1、如果$n/(2^{two}3^{three})>i,dp(two,three,i)+=dp(two,three,i+1)*(n/(2^{two}3^{three})-i)$，表示转移到前$i+1$个数前缀$GCD$仍为$2^{two}3^{three}$的情况，可以取的数有$n/(2^{two}3^{three})-i$个。
2、如果$two>0,dp(two,three,i)+=dp(two-1,three,i+1)*(n/(2^{two-1}3^{three})-n/(2^{two}3^{three}))$，表示转移到前$i+1$个数前缀$GCD$为$2^{two-1}3^{three}$的情况，可以取的数有$n/(2^{two-1}3^{three})-n/(2^{two}3^{three})$个。
3、如果$three>0,dp(two,three,i)+=dp(two,three-1,i+1)*(n/(2^{two}3^{three-1})-n/(2^{two}3^{three}))$，表示转移到前$i+1$个数前缀$GCD$为$2^{two}3^{three-1}$的情况，可以取的数有$n/(2^{two}3^{three-1})-n/(2^{two}3^{three})$个。

初始条件是$dp(two,three,n)=1,dp(0,0,i)=(n-i)!$。

如果$2^k\leq n, 2^k>n,2^{k-1}*3>n$，那么$dp(k,0,n)$是答案。
如果$2^k\leq n, 2^k>n,2^{k-1}*3\leq n$，那么$dp(k,0,n)+dp(k-1,1,n)$是答案。

F: Ehab and the Big Finale

链接：http://codeforces.com/contest/1174/problem/F

题意：交互题，给定一颗有根树，根节点是$1$。数据选定了一个节点$x$，要通过询问得到这个节点，询问最多$36$次，有以下两种询问：
1、d u，后台程序会返回$u$和$x$的距离。
2、s u，后台程序会返回$u$到$x$的路径上的第二个节点，询问的前提条件是$u$是$x$的祖先，如果不符合该条件，直接$Wrong\ Answer$。

先以$1$为根做一个$dfs$，记录所有节点的深度$dep$（$1$的深度是$0$），然后询问d 1，可以知道$x$在这颗树上的深度$D$。再以$1$为根$dfs$一次，记录$sz(u)$表示以$u$为根节点的子树中深度为$D$的节点的个数，记录$son(u)$表示$u$的子节点$\{v\}$中$sz(v)$最大的节点。
记录$down(u,diff)$表示节点$u$沿$son$下降$diff$次之后的节点。
记录$up(u,diff)$表示节点$u$沿父亲上升$diff$次之后的节点。
假设当前在树上的节点$u$，要求的$x$在$u$为根的子树上。
1、如果$dep(u)=D$，那么显然$x=u$。
2、询问d down(u,D-dep(u))，得到的结果记录为$ret$，那么可以肯定$x$在以$up(down(u,D-dep(u)),ret/2)$为根的子树上，递归计算。
3、特别的，如果$up(down(u,D-dep(u)),ret/2)=u$，那么说明$x$不在$son(u)$的子树中，询问s u，记录返回值为$v$，递归计算$v$。

最大的询问次数可以用计算树链剖分复杂度的方法计算，假设$1$到$x$路径经过了$k$条重链，那么最多询问$2\times k$次，$k=O(logn)$。