SRM615[题解已补完]

最近又颓废了一周。
今天看到xyz在拉人tc开黑,才发现今天晚上七点有srm。
看了一下自己的rating,有点犹豫……因为最近表现太颓,估计是要掉rating。
然后出门买了个茶叶蛋回来,拿到了5毛的找零,然后我决定通过抛硬币决定要不要打这场——数字面朝上就打。
然后我连扔了两次数字面都朝上(别吐槽我为什么扔两次)……觉得是天意不让我颓废,就开了arena。
结果出现了这种情况:


连续三次没有登进去后。
感觉是天意让我颓废保rating……就继续打轩辕剑了

level 1
稍微思考一下发现是道傻逼题。得不到的数字一定是这给定的n个数产生的集合中。
暴力枚举检验就好。
level 2
当时gwj拉我看这题怎么做,结果当时弄出来了个让我觉得挺搞笑的做法。结果tm居然是正解。
因为路径可以不是简单路径,那么我们可以一条边来回走若干次。
我们随便取0节点练出来的一条边,以它的长度的两倍作为mod,
然后设状态f[i][j]表示从0到j,长度模mod为j的最短路长度。
然后spfa暴力更新。
然后把f[n-1][t%mod]和t比较一下大小就好。
想想也挺显然的,因为可以开局先1->x->1->x->1->x这样来回走嘛。
gwj这题fst了……为她点蜡烛。
level 3
第一次看到这么简单的level3。
分析一下发现那个blue是个废条件。
简化一下问题:
有一段01序列,然后中间有一些问号——比如010??0?111之类的。
然后?处可能是空白或者0或者1。
如果把?处的数值都确定后,能再分成m个等长合法子序列……那么这个序列就是可接受的。

然后我们注意一下一个可接受的序列要满足的必要条件。
首先我们把red的权值设为1,green的权值设为-1.
那么求前缀和之后,Si一定要大于等于0,而且Si一定要小于等于m。
这显然是必要条件,但是还是不够。
我们再观察一下后,发现如果一个01序列的前缀和满足了这些条件后,red出现的次数是m的倍数的话,那么这个就合法了,容易发现这个是必要充分条件。

那么显然就有dp状态f[i][j][k]——前i个位置,前缀和为j,出现的red的次数模m是k的序列个数。
然后转移显然。

当时不打这场真是太颓了……这么好的涨rating的机会。

Comments

comments powered by Disqus