CODE FESTIVAL 2016 Qualification Round A

题目链接代码链接

还是那句话吧,好好思考,并且希望自己能坚持下去。

A - CODEFESTIVAL 2016

题意是给一个长度为12的字符串,输出前4个字符+空格+后四个字符。

B - 仲良しうさぎ / Friendly Rabbits

题意是给出N个兔子,每个兔子有自己喜欢的兔子$A_i$,问互相喜欢的兔子有多少对。

直接模拟计算。

C - 次のアルファベット / Next Letter

题意是给出一个字符串,字符串中的每一个字符可以循环向后移,但是一共必须循环向后移动K次,问改变后的字典序最小的字符串。

对每一个字符贪心搞,剩下的操作在最后一个字符上。

D - マス目と整数 / Grid and Integers

题意是给出了R*C的格子,然后有N个格子($r_i,c_i$)已经有值了$a_i$,现在要求让你判断是否每一个格子在都是大于等于零的情况下,满足在任意一个2*2的格子中,两个对角线的和是相等的。

又是这种要你将题目转化的题。

首先对于任意一个2*2的方格,要满足
$$
b_{i,j}+b_{i+1,j+1}=b_{i+1,j}+b_{i,j+1}
$$
等式挪一下变成差的形式,会发现对于固定的一行i来说,其差值是要相等的。对于固定的一列j来说,其差值也是相等的。那么这个时候思考,可以将上述条件转变为是否存在两个数列$(x_1,x_2,…,x_R)$和$(y_1,y_2,…,y_C)$,使得$x_{rk}+y_{ck}=a_k$。

所以根据题中所给的条件可以构建图,每一个边的权值就是$a_k$,当形成环的时候判断是否相等。

最后,要判断是否都满足是大于等于0,我们先假设最开始的值x是最小值0,根据这个基准,算其余点的值,计算最小正值与最小负值,如果最小负值的绝对值大于了最小正值,画图可知,这个时候就到了不可调和的地步,不符合要求。

E - LRU パズル / LRU Puzzle

题意是有N个1到M递增的数组,给出了一系列的操作,每次操作将从N个数组中选出一个数组,并将这个数组中的$a_i$拿到最前面。现在题目是问是否满足在进行Q次操作之后,得到的结果是相等的。

假设操作在(1,2,…,M)上,那么在进行了Q次操作之后得到的结果,就是从后往前看,当这个数第一次出现的时候,将这个数放到结果的队列末尾,如果出现过,忽略掉。之后将没有出现在结果队列中的数字依次插入到结尾。

那么问题现在相当于将这个操作的数组a,分成N个子串,要求这N个子串在1..M上的操作是相等的结果。问是否可能。

那首先考虑N=2的情况。贪心去取,碰到没出现过的,给第一个。碰到第一个出现的,给第二个。都出现的,忽略掉。最终看两个数组得到的是否相等。

当N大于2的时候,思路也是一样的,类似于推箱子。。。

首先记长度为0的有N个数组,然后得到一个数字判断当前面临的状态,往下面推,最后看箱子有没有剩下的。。。