看蒟蒻是怎么把一道傻逼题写傻逼的
D.BZOJ3611: [Heoi2014]大工程
虚树裸题。考前还在群里浪：“知道做过还放上去？”“锻炼码力？”然后考完就TM被打脸。。。身败名裂
too young too naive
我犯了3个sb错误：
1）原图的边和虚树中的边写成了一个函数，所以就成了单向边QAQ
2）在虚树上连边的时候最后的将f入栈出了点儿问题，最后应该是add(f,sta[top--]),if(sta[top]!=f)sta[++top]=f
然后我写成了 add(sta[top-1],sta[top],if(sta[top]!=f)sta[++top]=f
然后导致边就跨越了。。。
3）CH上输出long long是lld。我这么多年来一直记得是I64d。。。
B.BZOJ3612: [Heoi2014]平衡
其实这题也不难，但是我直接看到题就想到背包上来了，而之后就在一直思考如何优化背包。
实际上我们要求的是f[i][j]表示用不相同的不超过n的j个数装满i的方案数。应该很有规律（其实应该算是组合经典模型吧，还是多记点儿比较好。），这类问题一般是不需要背包的。
（以后看到这种式子，要么想一下递推式，然后再用背包。）
f[i][j]=f[i-j][j]+f[i-j][j-1]-f[i-(n+1)][j-1]
第一部分是最小的不是1，第二部分是最小的是1（之所以不用f[i-1][j-1]是因为这个方案可能已经用过1了）。
然后最后一部分是最大的是n+1的方案数，所以要减掉。（最大不会是n+2，因为这个不合法是由f[i-j][j]和f[i-j][j-1]加出来的，而这些方案里最大都只可能是n）
C.3610: [Heoi2014]林中路径
刚看见想了想矩阵乘法么，100分到手。。。然后扭过头来写发现构造不出矩阵QAQ。
于是写了暴力的矩阵乘法。。。
啦啦
来补正解啦
我看的是这里的题解
我们发现这道题直接维护 路径条数*长度*长度 的前缀和是不太好维护的，
这种情况下我们一般需要多记录几个值，比如此题就是 同时维护 路径条数*长度*长度 路径条数*长度 以及 路径条数的前缀和。
这样三个矩阵，当然还有路径条数（不是前缀和）
是可以相互递推的。
还有什么情况下可以使用矩阵乘法&快速幂呢？
如果我们由k的情况可以推出k+1的情况和2*k的情况，就可以用矩阵乘法加速。
想一想，是不是这样。我们从最高位开始搞，然后每次让k+=1，或者让k<<=1，这样总会得到n。
然后这题就搞完了。
A.BZOJ3609: [Heoi2014]人人尽说江南好
没想到我胡策补的最后一道题居然是胡策正式开始的第一题
，可能我比较傻逼。打表找规律这种太靠智商的东西实在搞不来。。。
但是我们直接打表还是看不出什么规律的。实际上一个状态是黑手还是白手只取决于当前石子的总堆数。因为一堆数量为x的石子需要合并x-1次。
而k堆石子我们只需要合并n-k次就可以了。而由合并的次数奇偶就可以推出当前是黑手操作还是白手操作。
那么也就是说，起始状态的输赢只与终状态的石子堆数的奇偶有关。
那么我们打表发现最后剩下的石子堆数就是（n-1）/m+1。（这个表还是不太好打的QAQ）
然后直接判断就好了。
评论 (0)
