有必要写一些div2的EF了,不然代码怎么打都不知道了.
CF969 div2
E
给定一棵 dfs 序标号的树,每条边有不确定的非负整数边权,但你只知道边权和.定义 $f_i$ 为所有安排边权的情况下, $i$ 与 $(i\mod n)+1$ 的距离的最大值.每次告诉你一条边的边权,求此时所有 $f_i$ 之和.
解法：树按 dfs 序标号，所以最终的 $n$ 条路径中，每条边恰好被经过两次。一条路径的权值可能是：已经全部确定，那就确定了；没有全部确定，权值是边权和减去路径外知道的边的权值和。用全局加的 tag 维护即可。
然而…说是这么说,怎么写呢?
首先记录深度dep,fa表示深度和爹.
然后记录len表示 $i$ 到 $i+1$ 的路径长度.
我们知道每条路径会被经过两次,所以记录 $c1$ 和 $c2$ 表示路径两次经过的起始点,然后按照深度去加长度知道碰到一起,总路径和确定,所以复杂度确定.1
2
3
4
5
6
7
8
9
10for(int i=1,u,v;i<=n;++i){
u=i,v=i+1;
if(i==n)v=1;
while(u!=v){
if(dep[u]<dep[v])swap(u,v);
(c1[u]==0?c1[u]:c2[u])=i;
u=ko[u];
len[i]++;
}
}
因为每个边只会被经过两次,所以这个边确定只会让两个路径的len—,也就是不确定的边长度—.如果变成0那么这个边完全确定下来,就减掉自由边.
CF1005 div2
C
Flu发现首先删掉能直接删掉的,然后必然剩下负的和正的想冲,就想比较哪个大取全正的,结果不对.
题解说:不管冲不冲,每次肯定是删最左端的正数,或者最右端的负数,所以可以枚举这个边界点,维护前后缀即可.
D
给一个数列,q次询问,每次从左端开始,如果数字比数列大,那就得分+1,吃掉数列,数字变成抑或这个数字.(多次询问独立),问每个询问的最大得分.
规定 $\mathrm{msb}(a)$ 表示最高位.假如当前msb高于一个数字,一定能吃掉.假如低于则一定不能吃掉.假如相等,可以通过维护抑或前缀和来快速计算能不能吃掉.
同理,发现吃掉这个msb一样的之后就不能再吃msb更高的了,也就是整个数列最多分成log段,直接维护即可.
E
非常色的题.
AB玩一个游戏,在一个01串上,每次A可以选两个连续的0删掉,B可以选至少一个1的连续长度2的串删掉.谁删不掉就输了,问一个01串的所有连续子串中玩家1能赢多少次.
首先假设ab都可以随便选不连续的,那么游戏就变成了对01个数进行统计得出答案.显然玩家2是尽可能删01最后再删11,而且没0可用的轮不会持续很久,所以一轮理论上会删 0010 .我们设0是1,1是-3,这样玩家的胜负可以用01串的数字大小表示了.据此得到4个偏移.
然后我们发现,选连续的串对玩家2是假的,因为字符串上只要存在1必定有01相连.
观察之后还可以发现,选连续的0对玩家1也是假的.什么情况不会形成连续的0?只有 0101010 这种,然而此时就算不连续玩家1也是输的.
所以选连续 00 的这个限制自始至终就是诈骗条件,根本不用管.
问题转化为我们要找到所有子串,然后评估其是否大于1.
前缀和+权值线段树.
CF愚人节赛
非常妙的一场,有很多很新奇的脑洞值得记录.
B
你有一个游戏,你要赌能不能过10个测试点,这个游戏很像伯努利分布,发现在两端概率最高,是1/2,所以10个点就是要赌1/1024的概率,显然不太对劲.
发现输出没有要求一定要在给定的16个格子内,所以输出17或者-1就完事了,,(很仙的题啊),,
C
问你这个题有多少个测试点,,,
题解说告诉大家CF有一个filter功能,能看谁过了多少个测试点,然后对filter二分即可,但是要求必须要有一个过这个题的才行.
D
盒人题.Flu经过测试发现 Google Earth给出的地理坐标有较大的偏差(7km左右),而Google Map精确度很高,是这样.
E pair count
正常的题面,正常的数据范围,不正常的链接.
这个题的XOR的链接并不是维基百科上面的链接,而是一个wordle,解出来发现是MULTIPLY(相乘),于是你要找到任意三次方相乘等于k的下标.
k可以是0,模数只保证是质数并没有其他性质.
在这个题爆了个大bug,非常重要,之前从来没见过的bug
正常求逆元是mod-2,直接快速幂.
然而对0求逆元的时候正好对2取模,会导致出现 qp(0,0,2) 的情况,返回值是1,然而0的逆元显然因为不存在所以是0,就在这狠狠地被肘了.
F 1/3 of the problem
三分之一在题面中,剩下的三分之二在俄文区.
G <绝对是一个图论问题>
乍一看有很高深的算法,又是从n个点选k个又是1e5的,算法很神秘.
然而 最后有一句话: 没有三个点位于一个圆上 .什么意思?任意三点都不构成圆,意味着所有的点都是共线的,排一遍序扫一下就完事了,这个题非常诈骗.诈骗!
H
给一张高斯模糊过的图片,你要逆过来解密高斯模糊(PS大法似乎不顶用),所以这个题偏CTF风格,笔者抄的题解脚本,,
J
题解说视频讲解能够提前”首映”出来,然后听歌识曲得到音乐名的提示,然后从PPT中得到输入输出格式,最后提交类似flag的题目名称.
CF愚人节赛2012
D
非常妙的题,题面是说有5个点,不告诉你输入具体是几,你要猜一个1-3的数(也就是说只要穷举,大家都能作对,只是交多少发的问题,这个题背景就很妙)
Flu采取的类似二分的策略,最后+9过的(中间唐了一发).
首先你可以通过所有未知编号的测试点使用一样的数来确定第一个被卡掉的点不是几,然后对未知的点二分,找到第一个过的点,就能清楚第几个点实际是几以及答案是几,当然这个题本身很有趣,但是很看脸.
E
给你一种未知语言的编译器,让你使用这种语言输出这种语言的名字.
随便做点什么,然后查看报错信息,查到是INTERCAL(在搜索偏门信息方面感觉AI明显不如搜索引擎,不知道咋回事)
C
仍然是一种新编程语言,这次叫做Chef,代码是一句一句类似食谱的步骤.这次是要理解程序在干什么然后去模拟这个过程.
G
给三个数字猜规律.
规律:前两个数字是类斐波那契数列的开始,第三个是需要求的索引…好难猜.
CF愚人节2013
A
给一个数字,猜字符串.
上网搜发现是美国历届总统的名字.
然后交,WA了,看了答案才知道除了那个名字带 Van 的都是只取最后一个单词.
C
一个新的语言理解题,语言叫做lolcode,是一个网络用语写成的语言.
CF愚人节2014
A
看样例猜规则系列,,1
2
3
4[]()[]8< 8<8<()
8<[]()8< []8<[]
TEAM 2 WINS TIE
首先看第一个 [] 应该是小于 8< 的,然后看第二个, [] 应该是介于 () 和 8< 之间的,所以推测 () < [] < 8< .交上去WA了…然后不知道咋做看题解了.
题解说这是石头剪子布…
B
还是猜语言,这次是Fortran.
D
给一堆基本事实,然后给输入猜输出.
题解说有的事实是假的,所以你只需要判断真假就行了.
F 000001
题解说,即使一个问题没有描述,它最起码有一个名称.你要找到一个1-64对应数字的哈希,应该怎么办?显然是上网查.上哪里查?显然是OEIS.所以答案就是oeis A000001,并不是数字-1之后的二进制长度.
G on a plane
在飞机上(一说,在平面上)
非常生草的事情是,,把样例给出的点画在图上发现是 5+AVG Y .
样例才是题干.
破防了,以后再也不做愚人节题目了.
CF2111
E玄学WA,不知道为啥,最后重回蓝名.
E
给一个abc组成的字符串,每次给一个操作 op->oop 字符直接替换,求最后字典序最小的字符串.
首先分情况一下得到只有以下操作是有效的:1
2
3
4b->a
c->a
b->c->a
c->b->a
然后要对 字符串 每一为进行枚举,能变a直接变a不能就对前一个操作二分后一个操作,把所有修改都丢set里即可.
不知道为什么玄学WA,场上大家似乎都在WA…
F
CF2119
E
神秘组合数学题.
首先改变思考方式:对于一个数列的计算权值很困难,我们换一个计算方式:
对每一个token计算是被谁删掉的,得到一个p数组.
这个p数组对答案的贡献是 $\prod p_i$ ,因为每一个p都可能出现在不比p大的位置,所以考虑dp.
倒着考虑:假设f(i,j)表示后i行选了j个的情况.假设这一行不删,那就是f(i+1,j),如果删,那么权重是i(swap一下:每个token选一行,这意味着这个token可以选(n-i+1)-(j-1)个token),而且转移是从f(i+1,j-1)开始.
CF2124
E
给你一个数列a,你每次要构造一个数列b,满足在某一点上前缀和等于不算这个数的后缀和,然后a-b,直到把a减成0.最多进行17次操作,n最大5e4.
居然是巨大的诈骗题,正解只需要3次,甚至能合并成两次…
首先判定无解:存在一个大于一半的数,或者sum是奇数.
然后特判掉存在一个点满足前缀和与剩下的数字一样,这么着是一次就完事.
然后考虑3个元素的情况:设这三个数字分别为[a+b,b+c,c+a],解方程能得到abc的值,然后分别消掉就行了,而且很多个元素可以被归类到这三种情况中.
然而实际上abc可能解出负数,这个时候就需要a+b+b+c大于总和的一半,就能得到正确答案.
CF2130
D
给你一个排列,每个数可以反转为 $2n-p_i$ ,问你最少的逆序对是多少,n方可过.
赛时自己想不出来,队友指点一下秒过.假如一个数很小,那么它rev之后是最大的,所以要倒着枚举,枚举rev和不rev的贡献,然后取最小的即可.
因为从小到大,反转操作没有后效性
不翻,后面无论翻不翻都比你大
翻了,后面无论翻不翻都比你小
所以如果是贪心一定是这样
然后维护个树状数组啥的感觉就差不多了
CF2127
C
赛时居然没想起来???
首先,答案贡献是abs,所以对于任何人,ab以内可以随意swap,我们假设所有a>b.
其次,什么时候第二个人会发力?只有前一个全部大于后一个的时候才能交换,比如(7,5)和(3,1)的时候可以变成(7,3)和(5,1).
考虑线段:所有线段不相交的时候一定会有贡献,答案就很好算了…
所以排个序,然后找一下相交…
D
刚开始我写的做法是枚举对面有什么,然后尝试对这个方法进行反转,x2或者x4.
但是比如1-2的数据反转只有两种情况,所以Flu懵逼了,这个题就没开出来,,
[CF2143]
赛时不会,QianK佬发现了D的规律,然而还是不会DP…
为什么每次想上分都会被神秘DP题卡死…
D1
一个序列被称作”好”当且仅当对于任意 $i
现在给你一个序列a,你只有两种颜色,问a的子序列(可以为空)的好序列的个数.
转化题意:逆序对必须异色->同色元素不能逆序->同色元素非降
所以满足要求序列一定是两条非降序列
根据Dilworth定理,b不存在长度为3的严格下降序列
此事在导弹拦截中亦有记载…
参考这篇题解: $dp[i][j][k]$ 表示当前第i个元素,第一条链最大值是j,第二条链最大值为k的情况:
如果dat[i]不被选中,那么直接从上一层加即可.
如果dat[i]>=j,那么 $dp[i][dat[i]][k]+=dp[i-1][j][k]$
如果 $dat[i]
D2
上面程序的加强版,n被放大到了2000.
我们注意到,上面的程序更新的时候是这样:假设有这么多格子,在dat=3的时候这么更新:1
2
3
4
5
6 1 2 3
1 1 2 3
2 4 5 6
3 7 8 9
4 10 11 12
首先是7这个格子,会把整列求前缀和(1+4+7),然后加到7.
8同理:(2+5+8)加到7.因为一个数字能加第一条链就绝对不会加进第二条链,所以不会更新9(也就是两条链末尾一样).
然后关键来了:我们会求行的前缀和(10+11+12),然后加到12.
这启发我们建2n棵树状数组,维护横行数列的前缀和情况.
直接更新就可以了…
E
感觉是被e的位置吓怕了,根本不敢写…
但是这个题实际上似乎没那么难.
给一个括号串,你一次操作能让两个连续且符号相同的括号反向( ))->(( , ((->)) ),然后问你下面指定的括号序列能不能操作成一个能被括号匹配的序列.
题解非常妙:首先奇数无解.
然后对于两个连续的括号,他们可以随意移动,ie )(( -> ))) -> (()
所以我们先提取出来所有的连续两个括号(注意要用栈匹配,因为 ())( -> (()) )
那么剩下的串只可能是:1.空串2. ()()()() 3. )()()()(
因为剩下的串不含两个连续的,所以奇数个 )) 这种二连串无解.
如果二连串为0,那么3无解.
剩下的情况都有解,考虑 ((((中间剩下的串)))) 即可.
[CF2150]
C
alice和bob在一个商店选购商品.每个商品有dat i的价值,同时alice和bob各有一个排列a和b,每个人进商店会优先按照排列取需要拿的物品.最后问你合理安排顺序后alice能拿到的物品的和的最大值.
ref.在滚动的时候强制pos[a[i]]以前的区间加a[i]表示必须选a[i],然后这个时候不选a[i]的最大值会被转移到pos[a[i]]+1表示bob这个时候选到了a[i],所以能拿到最大值.
D
[CF2162]
Flu几乎每次碰到div3必上分，可能是菜完了…
F
给定区间,你要构造一个排列满足m个子区间[l,r]的mex(mex([l1,r1]),mex[l2,r2]…)最小.
nm都是3000,就是神秘构造.
G
构造一棵树满足两个边节点乘积的和是一个完全平方数.
答案是这么构造的:1
2
3
4
5
6
7 5 ... n-1
\ | /
2
/ \
1 3
/ \
n 4
非常神秘的题.