CFR528

CFR528 div1

前期感觉海星,10min过A,20min过B,1h就写完C了,并花了10min仔细检查了break等问题,wa3

然后就自闭了1h,没法写拍,最后2min绝杀,就改了个break……

实际代码部分是60行,1.5k的样子,我感觉我已经是很冷静很慢很仔细地去写了,还是这个结果

好像nb选手,也难免会wa几下,问题在于几分钟就精准地debug完了,我觉得这次比赛自己应该debuff不大了,也不知道是不是运气不好,更不知道如何减少发生……蛋疼

不过这题出得是真的烂,思维难度相当于没有

CF1086A Connect Three

请先思考后再展开

想了好一会,过得时候百来名,可以接受吧

策略就是先考虑x再考虑y,都是两侧向中间的走

code

CF1086B Minimum Diameter Tree

题意:$n \le 1e5$点树,给出整数s,给每条边分配非负实数,使得和为s,最小化其直径

请先思考后再展开

这题也挺有趣的,先想到既然是实数,如果有k个叶子总和为s,可以让每个叶子到根距离都是s/k

于是把直径画成一条横线,条件就是$\sum_{路径上点x} x其他方向子树中叶子个数和*min(L1,L2) \ge s-L$,想了想发现最优策略是两端那两条边都设为L/2(先别考虑n=2),于是$L \ge 2s/叶子个数$,code

CF1086C Vasya and Templates

题意:多组数据的字符串总长不超过3e6,求一个字符串排列,使得将s映射后,字典序$\in [a,b]$

这题就别看题解了,好好再想想吧,思维难度比前面都低

因为预感到不好写,写的时候特意慢慢写,所以应该写的比较好看

code

CF1086D Rock-Paper-Scissors Champion

题意:剪刀石头布,一行n人的手势给出,每次选相邻两人,如果是相同的可决定谁赢,输的滚粗,问有多少人,能存在一种对战顺序使得最后留下他。q次单点修改,每次都要回答询问

请先思考后再展开

请允许我认为这题比C更容易通过,diff虚高

枚举每个人,左右显然独立,将同色的记作0,设1为能干它的,2为它能干的,那我们先把2旁边0干了,然后发现,只有两侧都满足,如果有1就必须有2,这个人就能当冠军。暴力

那么讨论一下最左、右的1、2大小关系,得到一些区间限制,用个bit求这种颜色哪些合法即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int solve()
{
int ret=0;
fo(now,0,2)
{
if(!sz(hh[(now+1)%3])){ret+=sz(hh[now]);continue;}
if(!sz(hh[(now+2)%3])) continue;
int al=*hh[(now+1)%3].begin(),ar=*(--hh[(now+1)%3].end());
int bl=*hh[(now+2)%3].begin(),br=*(--hh[(now+2)%3].end());
if(al<bl and br<ar) ret+=bit[now].ask(bl,br)+bit[now].ask(1,al)+bit[now].ask(ar,n);
else if(al<bl) ret+=bit[now].ask(1,al)+bit[now].ask(bl,n);
else if(br<ar) ret+=bit[now].ask(1,br)+bit[now].ask(ar,n);
else ret+=sz(hh[now]);
}return ret;
}

code

CF1086E Beautiful Matrix

题意:定义一个大小为n的方阵合法:n个n的排列,且$p_{i,j} \ne p_{i+1,j}$。给定一个合法方阵,求它在所有合法方阵中字典序的排名(字典序比较方式为逐行,从0开始编号)

请先思考后再展开

看到计数题嘿嘿嘿,不过我花了至少30min(做计数的速度日常不太行

容易得到暴力:先枚举第i行首次不同,那么就是要统计字典序<pi且是$p_{i-1}$的错排的排列数,然后乘上$D_n^{n-i}$(后面n-i行直接错排)

枚举这个排列在第j位首次不同,$sum+=\sum_{now=1}^{p_{i,j}-1} [now \ne p_{i-1,j}且前面未用过]*(\sum_{t=0}^{lef} (-1)^{t} C_{lef}^t (n-j-t)! )$,其中lef表示在$p_{i-1}和p_i$的前i个(将$p_{i,j}$替换为now后)之外的数字个数,暴力

后面的式子用组合数递推搞一搞,发现就是$g(a,0)=a!,g(a,lef)=g(a,lef-1)-g(a-1,lef-1)$

树状数组搞一搞就是$O(n^2log)$了,code

gloid直接ntt很nb,题解好像是我这做法

感觉组合数递推式txdy,最近做的大部分化式子的时候都能用上

CF1086F Forest Fires

咕咕咕

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