Manthan, Codefest 19

Manthan, Codefest 19
题号开头为CF1208

A XORinacci

code

B Uniqueness

code

C Magic Grid

请先思考后再展开

这题把节奏打崩了,真心教做人
n是4的倍数,而0~15组成一个矩形的解很简单,然后二进制前面加上同样的数字都没有问题
所以枚举每个$4*4$的方格,按顺序填就好了,因为长度为4前面的数字会被抵消
code

D Restore Permutation

请先思考后再展开

$$
我想了个很蠢的做法,考虑从后往前递推,S_n=\sum1 \to p_n-1 从而求出pn \\
类似的 S_{n-1}=\sum1 \to p_{n-1}-1并去掉p_n,考虑这个“去掉”怎么搞 \\
维护后面每个S在当前1 \to i范围内的值(去掉i+1 \to n的影响,可以用bit+差分) \\
这样就可以根据当前S_i与后面S_j的大小关系(bit上二分),判断出后面哪些p_j比我小 \\
从而在当前S_i中去掉这些p_j的贡献(可以另外维护一个bit,存p_j的前缀和) \\
(注意后面S_j的大小关系与p_j大小关系一样,以p_j为下标存S的差分找到对应位置即可)
$$
然后这个做法想了半天才想到,写起来也不太好写,有一些细节需要考虑

时间复杂度下界也是log,不过比赛写的是log方的:code

比较好想好写的做法是,每次找最后一个0,第一次找到1,更新后面,第二次找到的就是2了,经典线段树即可,长但无脑不易错

upd:现在冷静下来想想,发现我sb了……泥萌还是看官方题解的代码吧(Approach 2),很简短……

E Let Them Slide

请先思考后再展开

当时看完题第一想法想到就写了,因为只剩15min,最后也没调出来
就是从大到小处理每条直线,然后用一个set维护已经被覆盖的区间,然后每次这个新区间,用while找到能贡献的地方
不过直接这样显然复杂度不对,因为可能有很多中间没有空隙的地方被反复枚举
但很好改,稍微思考一下就会发现,每次碰到这种就把 两个合并起来,这样复杂度就是对的了
因为set不能用stl的lower_bound研究了一上午为啥tle
code

F Bits And Pieces

请先思考后再展开

考虑求答案我们需要什么,从高到低枚举每一位,设当前期望答案为ans,考虑的位置掩码为mask;考虑枚举i,则要求另一边(两数与)是 $(a_i \ xor \ ans)\&mask$ 的超集(当ans某个位=0,则一定找不到一个合法方案使得ai某个位=1,所以对做法正确性没有影响)
对于每种$a_i\&a_j$的结果,发现只需要存最后两个ai和aj,以这个为状态做一个类似fwt的简单dp即可
code

G Polygons

请先思考后再展开

显然选择了num,就会选择num的所有约数,那么不妨设 $f(num)$ 表示选择num新产生的点数,考虑把点表示成 $\frac{1}{num}+\frac{2}{num}…\frac{num-1}{num}$ ,显然 $f(num)=\varphi(num)$ ,再考虑到 $\varphi(num) \geq \varphi(d|num)$ ,故把1到n的phi排序然后对前k+2个求和+1就好了;然而当k=1时并不会选择2的倍数,特判

1
2
3
4
5
6
void main()
{
pre();
int n=qread(),k=qread()+2;if(k==3) {write(3);return;}
sort(phi+1,phi+n+1);ll ans=0;for(int i=1;i<=k;i++) ans+=phi[i];write(ans+1);
}

H Red Blue Tree

咕咕咕

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/ed65.html
转载请注明出处,谢谢!