2018.7.4——codeforces #470 div2 比赛小结

第一次做这种神奇的比赛,好激动,也有点不适应,然后就GG了。
英文比赛,读题稍稍困难。我太菜了。
先放成绩:
这里写图片描述
死得灿烂。
然后呢,我们来看看题。
T1(a)
xc说太水了,没让我们做。
T2(b)
给出一个数字x0,然后选出一个比x0小的质数p,乘上一个最小的k,使得p*k刚好大于等于x0,然后计p*k为x1……以此类推。现在,给你一个x2,要求求出最小的x0。
T3(c)
有n天。每天会堆一个雪人,雪人生命值为a[i],然后每天每个存在的雪人都会减去b[i]的生命力,最少为0。要求每天可以减去多少的生命。
T4(d)
给两个序列a[i],b[i]然后序列c[i]为a[i] xor b[j] (b[j]不能重复出现),要求c的字典序最小。
T5(e)
给两个字符串s,t由A、B、C三个字母组成。然后每次询问s的区间l1~r1和t的区间l2~r2.然后有四种操作——
“A”→“BC”
“B”→“AC”
“C”→“BC”
“AAA”→“(空的)”
每次询问要求问s的区间是否可以通过四种操作转为t的区间。

好吧,比赛时我只懂T2T3,T4只草草看了样例,本来很有想法,但是题面极大,觉得我的想法不对,于是弃疗(其实我的想法是对的)。

然后T3很愉快,T2死杠,然后就good game
来谈谈题解——
T1都说了太水了。
T2也就是把x2分解——p1^q1*p2*q2*……*pn^qn
然后枚举p,那么x1的范围就为
(x2/pi)+1<=x1<=x2
同样的枚举x1,即可得到x0
但是暴力搞会时超(我就中招了)
然后需要一些神奇的优化。
T3首先n log n的时间求出每个雪人在第天被融化,然后记录下来,那么对于每一天就是加入一个点,然后把今天融化的雪人的剩余生命值给取出来,丢进答案,其他的照常计算,这个就可以用线段树来维护。
T4就是一个trie,然后暴力贪心即可,空间要小心。还我满分!!!
T5神奇的结论题。
首先B→AC→AAB→AAAC→C
那么B与C是一样的。
我们计A为0,BC为1
那么操作就可以变为:
000→空
1→01
1→11
然后对于每次询问,我们记下——s1(区间内的1的个数) s0(后缀0的个数) t1(同上) t0(同上)
然后我们经过繁琐精细的分析,可以得到下面几个情况——
看代码:

if (s1=t1) and (s0=t0) then write(1)
else
if (s1>t1) then write(0)
else
if (s0<t0) then write(0)
else
if (t1 mod 2<>s1 mod 2) then write(0)
else
if (t1 mod 2<>s1 mod 2) and (s0=t0) and (s1=0) then write(0)
else
if (t1 mod 2<>s1 mod 2) and (s0>t0) and (s1+2<=t1) then write(1)
else
if (t1 mod 2<>s1 mod 2) and (s0 mod 3=t0 mod 3) then write(1)
else write(0);

吐槽一下:
比赛时间真心短,2个小时怎么码题?咳,还是要多联系联系。
吐槽:
这里写图片描述

我活在这夜里。无论周围多么黑暗,我都要努力发光!我相信着,终有一天,我会在这深邃的夜里,造就一道最美的彩虹。
原文地址:https://www.cnblogs.com/RainbowCrown/p/11148415.html