Codeforces Edu R43

今天又又又又延时了!!这不道德!!

好菜啊只水了ABC三道不带脑子题……E最后结束的时候还没改对……

废话不多说了……

A. Minimum Binary Number

一个有趣的故事:我一开始把minimum看成maximum然后写了一个maximum版本的做法……

然而并没有啥用……

关于minimum,显然是

1.数位最少

2.只有最高位是1

那么我们的策略是把低位的1都向最高位移动并合并。

B. Lara Croft and the New Game

模拟+数数

并没有太大技巧,注意分两种情况,第二种的时候用除法直接锁定在哪一行(row)。

C. Nested Segments

转化一下问题,使得处理更简单一些

我们按照l_i为第一升序关键字,r_i为第二降序关键字排序,这时候就只需要判r_i \leq r_{i-1}就行了。

我们考虑答案是取了r_i序列的一个不降的部分,可知序列前面都是降的。这时候只需要判ii-1的关系即可。

D. Degree Set

不会呢,留坑吧

E. Well played!

贪心。有一个结论是2^a一定会乘到一个数上面去,不会分散开。

F. Minimal k-covering

看起来很难,yzy大佬刚了差不多1h都没刚动,我还是暂时咕咕咕吧。

Codeforces Edu R42 细节决定Rating

提示:题解正文前超长啰嗦部分

我活到现在,还没这么惨过,NOIp都没有。

比赛开始4min的时候,切掉A

 

 

 

嗯没有什么毛病

最后

 

 

用实力告诉你什么叫没带脑子比赛


开始切B

下面两段程序只有这里不一样

为啥第二个会WA?????


C 35min找错

尝试cout某些变量,发现去掉cout和不去掉,结果不一样

你猜哪错了?

35min找这一个字母 我怕不是学文化课学傻了写出i=i来??

然后 忘记判前导零 WA一发

最后,最后还fst了!!

10^9是10位数,我***……

我持盾,持盾。。


D 手速打完

seq[100010] -> WA 一发

改对,交上,Ac。

最后还是fst了!!!!

我***……

我持盾,持盾。。


然后我们愉悦的比赛就结束了。

我都不知道我的脑子飞哪去了……找到和我说一声‘

细节决定Rating啊!

凉凉。


我们还是来扯题解吧

A. Equator

这题巨没意思,加一遍扫一遍完事

注意sum/2还要上取整,也就是+sum%2

B. Students in Railway Carriage

我们貌似其实好像大概一定可以说明贪心是对的

这样,如果有一些空段,它们\geq 2且是一个偶数,

那你无论什么顺序安排反正都一样,填满的格子不能变多。(二元组证一下……)

对于奇数那些,……呃, \geq 3的拆成一段偶数空位和一个空位这样两个空段

这就变成了若干由一个空位,2N个空位组成的空段。

对于一个的那些你怎么放也是固定结果的。

(注意其实\geq 3的,拆出的一个空位,你放黑或白都可以,并不受后面偶数段的影响)

然后你每次挑大的放进那一个就行。挨着放就行,反正次序安排与解的优劣无关

对于一个B这样好像很啰嗦了……

C. Make a Square

解法1,枚举最终状态,每次判断可行并更新答案

解法2,从0到9枚举步数,DFS出终态并判断合法与否

特别注意判终态不含前导零(终态不含即可,非终态?含也行。为什么呢?)

D. Merge Equals

从左向右扫一遍然后开map记录位置,找到一个二元组,递归地消除即可。

特别注意long long

E. Byteland, Berland and Disputed Cities

交了几发,WA了。

所以思路是错的,并不会,留坑了。

F. Simple Cycles Edges

并没来得及看,留坑了。

G. Visible Black Areas

瞅了一眼图好像是个计算几何?并没细看题面,咕咕咕。

Codeforces R473

我这个代码能力下降到\rm{-INF}

并查集板子打了15分钟 还有谁??

气死了

算了赶紧写完赶紧睡觉

A. Mahmoud and Ehab and the even-odd game(真长)

就这题!!!卡了我五分钟!!我觉得它长的像SG,是它的错还是我的?!

一定注意a \leq n!!

然后你就会发现这游戏最多就一轮

B. Mahmoud and Ehab and the message(这个更长?)

然后并查集板子+map……能这个点打Cf的都能看出来也不说了……

C. Mahmoud and Ehab and the wrong algorithm(哇,还是这么长)

送分(ming)构造题

两问分别长这样

注意第一问只有n \geq 5才有解……原因是层数和两个点的解的限制(也就是说第二层最少3个点然后第三层必须有两个点及以上((一个点的话那个算法也是正确的)))

D. Mahmoud and Ehab and another array construction task(最长!)

这题,扫一下然后质因数分解

如果分解有重那么立即断开,前面的原样输出,后面的贪心地选一个质数输出

注意特判

E. Mahmoud and Ehab and the xor-MST(哈!变短了吧!)

我们考虑……有什么好考虑的。。。

那就……从高位来考虑?

当前考虑的,要求mst的点集的所有点权,在目前位上, 必然是n_1 \text{ — } n_x这一部分是0,然后n_{x+1} \text{ — } n_{last}1,那么点 x+1 \text{ — } last之间独立连边,1 \text{ — } x之间独立连边,这么做,可以保证对答案贡献都是0,是最优的。

·

但是如果当前确实有一个满足上述条件的x存在的话,

(其实也就是现在考虑的点集的最大点权的点,点权模掉2^{w-1}大于等于2^w,其中w是当前考虑的位数)

(也就是这一位上有1的出现,所以点被划成了这一位是0 \; , \; 1两个子点集)

那么还要把左右两个点集联通。先加上这样的代价 :2^w

·

我们其实并不关心这两个点集是怎么内部联通的,因为这个可以递归求解。把两个点集的点权模掉2^w之后就成为子问题了,对吧?

但是0集那个子问题是可以预处理的,要不然会T。

f[i]表示从02^i-1的贡献和。怎么转移?这个其实就是……你把它按照上面我说的拆一下点集就好了。然后方程在这儿:f[i]=2*f[i-1]+(1LL<<w-1)这个不难理解吧……

我希望我这题说明白了.

(我怕我long long的位运算出锅于是打了快速幂……)

F. Mahmoud and Ehab and yet another xor task

留坑

Codeforces Edu R40

手残比赛系列 +3 +3 +3 +3 +3……

话不多说进入正题

A. Diagonal Walking

瞎dp一波即可 贪心也对(当时没仔细想直接开始敲dp)

B. String Typing

枚举终点然后判断能不能复制即可。

记得倒序,要不会被aaaaaaaaa这种卡掉

C. Matrix Walk

尝试能不能通过上下的移动确定一行的宽度y

然后fixed宽度,把不合法的上下移动,左右移动判掉即可

特判不动的情况和没有上下移动的情况

x轴直接设置10^9

D. Fight Against Traffic

两遍SPFA然后枚举左右端点判定距离即可

注意有两种情况,还有就是ans要除2

E. Water Taps

把式子移一下就会发现是贪心

还没写出来,写出来再说

F. Runner’s Problem

时间不够了,没看题目

G. Castle Defense

先差分一遍把初始的\rm defense指数算出来

然后二分最小值,用贪心的方法判定

区间影响那就差分一下,假设判定的时候当前不足,还要让i+1加上补充的数目,i+2 \times \rm Range -1减去数目,然后从左到右扫就行

H. Path Counting

留坑

I. Yet Another String Matching Problem

留坑

Codeforces R470 (Based on VKcup R1)

和dkw组队 敲开心!

明天早自习请假了但是还要七点半起床 好痛苦QAQ

大概上午要睡过去

A. Protect Sheep

送分(ming)构造题(?)

把羊四周全围上狗就行

别像我一样没判羊挨着羊的情况然后连WA两发QAQ

B. Primal Sport

留坑

C. Producing Snow

对于每个雪堆二分哪一天最早化到负数

对温度做个前缀和,每次二分,假设cac天化到负数,当前是第i天

差分答案,化的=温度的区间,也就是i~cac-1差分一下,最后可以得知每天化了多少雪

加上化的小于温度的那一天,这个单独统计

最后加起来就ok

D. Perfect Security

一颗Trie树题,挺好玩的

带删除Trie树,每个结点记录有多少个数在这上面

递归删除并且贪心就行了

如果还不明白:

尽量让密钥和文本不匹配的那几位在低位上,这样才能字典序小,

也就是把数看成一个二进制字符串,带权匹配。

对于询问Trie树,如果能走同0或同1的当然好,那就贪心的走就是了,递归回来删除

E. Picking Strings

留坑

Codeforces R469

临时改时间了结果我失了智打了后半场……rk2700全程被碾压

A. Left-handers, Right-handers and Ambidexters

一道略微简单的题

答案讨论下左右撇子哪个多就行,不够就Ambidexters凑,Ambidexters还有剩余就一边分一个

B. Intercepted Message

贪心.两边取,相等就消掉,不相等继续取

C. Zebras

从前往后扫,vector维护序列们

每次维护两个集合,末尾是0的序列的集合,和末尾是1的,如果空了就新建序列

但是如果末尾是0的序列的集合空了而还有1的话不就无解了嘛

D. A Leapfrog in the Array

留坑

Codeforces Round #441 Div.2

第一场校队的集体Cf比赛QAQ

排名不是很高,到最后只切掉了ABD,C本来很简单,当时时间不多了于是就慌了。

果然,“比赛中的15分钟和比赛快要结束时的15分钟是不一样的啊”。

Rank1742,这次zzy大佬ABCD全都做出来了,然而A被Hack了(?)KVMC大佬只做了ABC……(貌似整个校队就我A题做的最慢???!!)

yts1999一小时切ABCD,Rank277,强啊。

大概这一场算是数论题+思考题吧,AB也不难,也就是PJ第二第三题难度。//然而并不能靠手速上分。

这儿是ABCD翻译&简短的题解。

A

大意就是维尼会去依次访问三个朋友家(这三个房子是三角形的三个顶点),并给出访问次数。一开始在其中一个顶点,给出三条边的边权,求给定次数的最少边权和。

//Solution

因为访问次数并不多,考虑dp

f[a][i]表示前a次访问,且第a次在顶点i时的最小边权和。 从f[a-1][j],f[a-1][k]取min转移即可。

B

给定一个数集A,要求构建一个含有k个元素的子集S,要求S中任意一个元素与其他元素的差的绝对值%m都为0。

若有多组解,任意输出一组。

//Solution

稍微思考一下,若|i-j|%m的余数为0的话,只需要i%m=j%m即可,移项并根据膜法结合律可知(i-j+m)%m=0

那么开m个对应的计数器编号1~m,碰到数就相应的+1,最后找一个数值>k的,记录下编号,扫一遍输入,然后判断、输出就行了。

C

给定一个数m,求所有满足以下条件的数x (m,x均为positive integer,也就是正整数)

x加上十进制下的x所有位上的数字的和等于m

例:m=21 x=15     解释: 15+1+5=21

1≤m,x≤109

 

//Sulotion

考虑到数据范围于是考虑一个最大的x:99999999

那它对应的m就是100000071。很容易发现x≥ [m-(8*9)] (也就是这个x八位全是9)如此考虑从m-100枚举到m然后判断即可。

D

D大概是我唯一正经翻译的题了吧……这种思考题题面很毒啊???

最近,Dima在集邮店遇见了Sasha,从此他们一起收集硬币。他们最喜欢的职业是分类硬币的集合。萨沙喜欢井然有序,所以她希望她的硬币排成一排,这样一来,首先是不能流通的硬币,然后是仍在流通的硬币。

为了安排硬币,Dima使用以下算法。他的算法的一个循环如下:

1.他从左到右看着所有的硬币;

2.如果他看到第i个硬币还在流通中,并且(i + 1)硬币已经不流通,他会交换这两个硬币,继续从第(i + 1)个硬币看硬币。

Dima重复上述步骤,直到这一过程中没有交换任何两枚硬币。 Dima所谓的硬币排序困难度,是根据上述算法,对硬币序列进行排序的次数。

也就是说,他从序列起始位置开始查看硬币的次数。

例如,对于有序序列,困难度等于1。

 

今天Sasha邀请Dima玩一个游戏。首先,他把没有流通的n个硬币连在一起,然后萨沙选择一个硬币,替换成正在流通的硬币。一共替换n次。在这个过程中,Sasha不断地问Dima把此硬币序列排序的困难度是多少?

这个任务比较复杂,因为Dima不应该碰硬币,他应该心算将硬币序列变为有序的困难度。帮助Dima完成这个任务。

//Sulotion

这个很像牛顿摆。我们把正在流通的硬币看成一种球体,不流通的硬币看作空气。

我们用手撞击最左面的正在流通的硬币:

(注:运动规则

1.当一个硬币从左运动到它右面的硬币并撞击它的时候,这个硬币停止运动,被它撞击的硬币开始运动。

2.运动到硬币序列末尾则停止。

并把它撞到最右面的[正在流通的硬币]的硬币堆里去

根据1、2得到:这个硬币堆必须在硬币序列的最末尾

那这个问题可以O(N)解决了。

每一次更新硬币堆,就统计一下流通硬币的数量,并减去末尾硬币堆的硬币数量。维护末尾硬币堆的最左端指针p,判断seq[p-1]是不是被换成了流通硬币。

详见代码吧。

就这些了,立个不太稳当的Flag,有时间做完EF再来更新EF的翻译题解。

Codeforces Round#124B Infinite Maze

题目描述

We’ve got a rectangular n × m-cell maze. Each cell is either passable, or is a wall (impassable). A little boy found the maze and cyclically tiled a plane with it so that the plane became an infinite maze. Now on this plane cell (x, y) is a wall if and only if cell  is a wall.

In this problem  is a remainder of dividing number a by number b.

The little boy stood at some cell on the plane and he wondered whether he can walk infinitely far away from his starting position. From cell (x, y) he can go to one of the following cells: (x, y - 1)(x, y + 1)(x - 1, y) and (x + 1, y), provided that the cell he goes to is not a wall.

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 1500) — the height and the width of the maze that the boy used to cyclically tile the plane.

Each of the next n lines contains m characters — the description of the labyrinth. Each character is either a “#“, that marks a wall, a “.“, that marks a passable cell, or an “S“, that marks the little boy’s starting point.

The starting point is a passable cell. It is guaranteed that character “S” occurs exactly once in the input.

Output

Print “Yes” (without the quotes), if the little boy can walk infinitely far from the starting point. Otherwise, print “No” (without the quotes).

什么玩意……还是看看翻译

幻象迷宫可以认为是无限大的,不过它由若干个N*M的矩阵重复组成。矩阵中有的地方是道路,用’.’表示;有的地方是墙,用’#’表示。LHX和WD所在的位置用’S’表示。也就是对于迷宫中的一个点(x,y),如果(x mod n,y mod m)是’.’或者’S’,那么这个地方是道路;如果(x mod n,y mod m)是’#’,那么这个地方是墙。The Little Boy可以向上下左右四个方向移动,当然不能移动到墙上。

请你告诉他能否走出幻象迷宫,如果他能走到距离起点无限远处,就认为能走出去。

也是好久之前做的题了,一开始被题意卡了好久,果然语文不好毁一生啊……

大概就是说给出一个01迷宫类的地图,按照这个地图来扩展新地图,类似这样

然后问你是不是可以走无限远。

那么,我们可以很清晰的意识到,如果可以从点(x,y)出发,达到比如(-x,y)或者(x,-y) , (-x,-y) , (x+m,y+n) [假设宽m高n]  , 就可以从这个点再次达到相同的点(即可以从(x,y)出发,达到(i,j)且|i|%n=x , |j|%m=y。),一直这么走下去。

那就搜好了。开一个三维vis数组第一维记录有无被访问,第二维记录被访问时横坐标,第三维纵坐标。

判断重复到达且横纵坐标不同即可。应该注意先判什么后判什么。如果是同一个分矩阵走过去的话自然tx==vis[x][y][0]此处x为|tx|%n,y为|ty|%m,即映射到中心矩阵的位置),就会被判掉。

而且注意tx!=vis[x][y][0]ty!=vis[x][y][1]满足一个即可。

没啥好说的了。。。数据很大注意搜索优化。