A alice and path
实况
想了一堆骚操作之后去想其他题了,然后队友用很复杂的操作A了.
与AC的距离
一开始其实有想到,同方向走5步之后就能回到上一步,但是看错了数据范围,以为输入和输出的数量都是100000,所以这个念头一下子就抛弃了,也没有提出来.
题解
输出的长度可以是输入的10倍,所以:
遇到L,就输出5个L,绕地球一圈回到上一步;
遇到R,就输出5个R,绕地球一圈回到上一步;
遇到B,就输出一个B,直接回头;
E cion and tournament
实况
一下子就秒了
题解
一开始在[1,x]的位置上站的都是a队的人,[x+1, x+y]位置上站的都是b队的人;
所以开始先把F[1-x]初始化为0,F[x+1..x+y]初始化为1;
然后号码大的先行动,所以对于i for x+y to 1 ;
当前位于i的人是b队的概率是F[i],他替代掉F[i/2]的概率是1/2;
所以F[i/2]在这次行动之后站着b队队员的概率是(F[i]+F[i/2])/2
F fizz and buzz
实况
已经算出了了15的占比和Fizz在15的倍数里的占比了,但是脑子秀逗了,越想越歪.
和AC的距离
明明冲上去就赢了
题解
如果是Fizz行动,他会在3333个数字中选一个数字,其中5的倍数有666个,所以他选择15的倍数的概率是666/3333;
如果是Buzz行动,他会在2000个数字中选一个数字,其中3的倍数有666个,所以他选择15的倍数的概率是666/2000;
那么出现15的倍数的概率是
当出现一个15的倍数时,这个数字由Fizz选择的概率是
期望:10000个数字中,会出现2660个15的倍数,其中有998个是Fizz选择的.
所以我们把全部15的倍数看成的Buzz的,那也才错误998个,远小于1200.
H jack and jill
实况
一开始就想了二分,考虑l==r的时候,直接输出=了没考虑,对方的输入不一定是答案.
白WA一发
题解
30次猜测,就算是二分在极端情况下也猜不出[1-1e9]里的一个数字.
所以我们制造一点极端情况
一开始假设l=1和r=1e9,答案未知(反正l<=ans<=r),看对方的输入.
假设对方输入是m,判断m和l,r的关系.
如果l==r并且l==m,那么输出等于号
如果l <= m <= r之间,那么更新答案所在的区间为[l,m-1]和[m+1,r]中比较长的一段,然后输出大于或小于.
否则就比较m和l,r,输出大于或小于.
I laws
实况
想到了bfs,但是每次往队列里塞入下一步,不是按代价大小的,所以很叼难写.
和AC的距离
莫名奇妙的忘记了优先队列,用了优先队列就秒了
题解
类似dijkstra,用map来存上一步的位置,到当前这一步的距离.
找下一步的时候注意,数字增加的时候只会连续增加1-3点,如果要增加很多,那还不如先除再加.
所以下一步只会是((x+ad)/2, adin[0,2)) 或者 ((x+ad)/3, adin[0,3))
然后从dis[1]开始找上一步(记录上一步的时候要记录除数),放到一个栈里.
然后输出栈里的内容.