CFR580

CFR580 div1

CF1205A Almost Equal

code

CF1205B Shortest Cycle

请先思考后再展开

显然考虑每一位是1的集合如果>=3,已经得到了无向图环大小的下界;否则边数只有60,直接floyd求最小环

code

CF1205C Palindromic Paths

请先思考后再展开

定义$(x,y),x+y为偶的是偶点,为奇的是奇点$,因为已知$a_{1,1}=1,a_{n,n}=0且n奇$,可以通过询问$1*3或2*2$得到所有偶点,当然也能知道所有奇点的$a_{1,2} \oplus a_{x,y}$,接下来就是考虑怎么沟通奇点和偶点

既然题面一脸有解的样子 ,将两种情况的所有询问回答,不可能所有询问都相同,找到不同的位置询问来判断是哪一种,这样肯定是能过的,比较莽夫就是了

这时候其实很自然的想法是,不能用$1*3、2*2,那就2*3或1*4$嘛,其实这本质上都是在分析长度为4的路径

因为我们已经获得$a_1 \oplus a_3、a_2 \oplus a_4$,对于一条异或和=0的路径,询问其两端,若1则一定相同,若0则一定不同

后者不显然,反证一手发现其实显然(病句);那这样的路径一定存在吗?注意到题目中$a_{n,n}=0$还没用过

存在性问题还是反证,考虑$(1,1)到(n,n)$的任意路径,如果任意长度为4的路径异或和都是1,则一定有$a_i=a_{i+4}$,而n是奇数,$a_{1,1}=1,a_{n,n}=0,(1,1)与(n,n)的曼哈顿距离为2n-2是4的倍数$

CF1205D Almost All

请先思考后再展开

考虑链和菊花,很容易回忆起bsgs的$1,2,…T-1,T,2T,3T,..?*T$的策略,那么找到一个根,划分出若干个子树为A,另外的为B

然后我们就是希望从根出发,在A内能得到$1..T-1$,在B内能得到$T…?$,这样能拼出的数就是$1..(n-T+1)T-1$

那现在不是链或菊花就会分叉,其实很好解决,给分叉的那条边加上以前siz和

这里找根和T我是给每个点背包做的,因为物品数为当前相邻的边数所以复杂度是$O(n^2)$,code

事实上可以稍加推导,已知重心的各个子树大小$\le \frac{n}{2}$,当至少四个时最小两个合并起来一定不会$>\frac{n}{2}$

剩下三个的时候设$a \le b \le c,c \ge \frac{n}{3}$,取$T=a+b$,再结合高一均值不等式那套理论可知下界是可以达到的

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