7.9模拟赛赛后总结

早上等了很久还没发题。看了会儿交互（毕竟老师说今天要考）。

九点十分，终于发下了题目，这个时候由于较长时间的放空，我有些困了。

十点十分，脑子开始清醒了，开始能够思考了。思前想后，T1一直都感觉难，于是去看了T2。

仔细一看，发现前30分非常水，于是赶紧码了码，稍微调了一下，用它的样例测试了一下感觉没问题了。

这个时候是大概十一点，还有三个小时。

思考了一番T3，想到了一个DP，大概是记录 \(f[i][x]\) 为走到 \(i\) 而代价是 \(x\) 的最大收益。然后分析了一会儿并且调试了一会儿，有了30分。这个时候大概过去了40分钟还是一个小时了，已经十二点了，有点饿。

然后想了想 T1，还是不贪了，看起来这道题也不简单，搞到20分就好！然后码了一百多行的20分暴力，花了挺长的时间的(为什么二十分的暴力会这么长？)

这个时候思考还能拿什么分，还有一个小时出头，现在大概是20+30+30，80分了，感觉T3的DP应该是最好搞的吧。那就想想这个，一般这种DP想优化到\(O(n)\) 或者 \(O(nlogn)\) 那大概率是一维的状态以及单调性什么的，似乎可以设计两个状态 \(f_i ,g_i\) 分别表示 \(i\) 这个位置最大的收益以及对应的代价，然后这个转移可以拆开，然后这个拆开代价的代价可以放到set里边，然后考虑每次选先前的最大代价的，应该就是最大收益的了，嗯不错，那每次lowerbound代价然后取对应位置的贡献来更新当前状态，似乎就OK了？woc不会吧。直接把我原本想写的基础的\(n^2\) (不用set维护而已，还是这个思路)给划掉，直接干正解了芜湖。

10分钟写完，是不是过于轻松了？500的小样例测一发，对了，开始对拍。

结果发现错了，似乎不能直接从最高的转移，那，从所有合适的代价来转移吧，相当于带优化的 \(n^2\) ，对拍了一会也没拍出来错误，那应该是对了吧，正好也快到点了，检查一波freopen就交了。

赛后发现

1 挂分了。本来想着105的，变成了60。挂在了T2的第二个sub，没有判长的前导0，T3的那个 \(n^2\) 写假了。

2 T2 的第三个sub是延续着第二个sub的，不过对于没有发现长前导0的我，估计打了也会炸，虽然炸不炸，耽误不耽误时间都不会影响我后来T3写假就是了。

3 冀队T1T3都A了，T2的三个sub也打满了 /fad 不说了，还是冀队神啊。

技术总结

T1

感觉T1就是个大水题 ——zwj

T1考虑把图分成树和其它部分，对两张图分别进行黑白染色(给01)，如果都能染色成功，那么把第一张图的颜色x2(即变为0，2)，然后把两个图的颜色编号加起来，就能够不冲突的产生一个四染色的状态；如果不能染色成功，那一定是剩余的部分存在奇环，那么把这个奇环给输出就好。

T2

正解的话，a=57,b=50，同样是分组，把两个数分成一组，每次对一组询问 \(\{0...1,10^{49}...0\}\),这样能够准确得到第一个数的最后49位，对于前8位就会和第二个数重合，但是只要知道第二个数的后八位即可作差得到这前8位，那么考虑再问一次\(\{0,10^8,0,10^{16}...\}\) 这样就能提取出每组第二个的后8位，不过看到总共有 \(8\) 组，所以说最后指数会超过 \(50\) ，再分一次组就好了，这样整好 \(10\) 次询问就好了。

T3

正解是另一个DP，设 \(f[i][j]\) 为 \(1\)~\(i-1\) 个店铺不选，收益为 \(j\) 的最小代价。这种把要求的东西作为状态，附加的东西作为属性的DP思路似乎是头一回见，长见识了。。 然后，考虑转移 \(f[i][j]=min(f[i+1][j-a[i]]+a[i]*i,f[i+1][j])\) ,这个转移是比较好理解的，就是这次如果选了这个店，那么代价就要加上 \(a[i]*i\) ，对于 \(f[i][a[i]]\) 它的代价一定是 \(a[i]+2*i\) ,显然这个东西可以滚动来求。

转移是倒着转移，然后考虑每次的转移,暴力转移的话肯定是 \(O(nm)\) 的，但是有一点考虑就能A掉，一般这种东西都只能在第二维动手脚，考虑后边已经选择的 \(k\) ，它们贡献的代价是 \(\sum a[k]*k\) 我们知道 \(i<k\) ，那么 \(\sum a[k]*i\) 一定小于这个值，也就是说，考虑的前边的收益就是 \(j=\sum a[k]\) ，代价$\sum a[k]*k $ 需要小于 \(X\) ,所以考虑收益 \(j\) ，那么如果\(j\) 满足\(i*j\le X\) 的话，那前面已经考虑过的合法收益一定是都被枚举到了，所以每次枚举第二维只需要到 \(m/i\) 即可，第二维的期望复杂度是 \(logX\) 的。