111qqz的小窝

老年咸鱼冲锋!

Codeforces eductional round 29

比赛链接

10个月没写题了,菜啊。进行一点恢复性训练好了。

A: 给一个数,可以在填写若干(或者0)个前缀0,问能否变成回文数。

思路是直接删掉后面可能的出现的0再判断回文数就好。

 

B: 2*n个人,每个人的重量为w[i],要分成n-1组,每组2个人,以及2个单独的人。单独的人的不稳定性为0,每组的不稳定是该组的2个人的重量的差的绝对值。总的不稳定为所有组的不稳定性之和。问可能的最小不稳定性是多少。

思路:由于n才50,100个人,暴力枚举单独的人,复杂度O(nnnlg(n)),很稳。 注意n给的是组数,所以数组最大值应该为100而不是50.

 

C: Ali和Bob两个机器人进行一个类似”石头剪子布”的游戏,每次2个机器人同时出{1,2,3}中的一个。 2 beats 1, 3 beats 2 , 1 beats 3. 赢的得1分,输的得0分。数字一样2人都不得分。2个机器人当前回合的策略(也就是出哪个数字)只取决于上一回合2个机器人出的数字。并且规则完全已知,会用2张3*3的表的形式给出。现在要进行k场游戏,问最后的分数是多少。

思路:由于k比较大,所有可能的分数序列(x,y)又非常有限,因此显然是求个循环节搞。

需要注意几点:

  1. k的大小太小,比循环节开始的第一个位置还小
  2. K是LL类型,各种和k有关的变量也要记得是LL类型
  3. 为了寻找循环节第一次出现的位置,将循环节第二次的开始存了进去,但是在算一个循环节的分数以及其他的时候,记得不要把这个多余的一次算进去。

D:有n(2e5)个数的序列,q(2E5)个区间操作,操作有2种类型,一种是将区间[L,R]循环右移一位。另一种是将区间[L,R]中的数整体反转。最后m(100)个询问,每个询问问b[j] (j属于1..m,b[j]属于1..n)位置上的数是多少。

思路:观察发现m比较小,可以暴力。对于所有操作进行完,b[i]位置上的数是多少, 因为所有的数只是位置改变,大小没有改变.我们想要还原,到最后的b[i]位置,应该对应的是初始序列中的哪个位置。
如果当前位置是pos,那么在进行上一个反转操作之前的位置就是(L+R)-pos, 进行上一个移位操作的位置就是pos-1(注意边界)

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz