这次比赛炸了。

T1：首先我们枚举i、j两种试剂，然后我们发现这两种试剂对所有k影响呈一个梯形（即一段递增、一段相同、再一段递减），这个自己推一推就知道了。那么有了这个性质以后，我们可以用差分套差分来维护答案。这样这道题就做完了。

 

总结：考试时我没有想到差分套差分。对于这种要给序列的某一段加上一个等差数列的题目可以采用这种套路。

 

T2：首先把树转换成图，然后根据图来列随机游走的方程。

具体方程就是对于一个x，设f[x]表示从x走到1的期望步数。那么对于与x有连边的点y，我们可以从x走到y，再从y走到1，那么就有：，d[x]表示x的度数。

化简后有：，然后我们可以得到n-1条方程（因为f[1]=0），这时就可以高斯消元了。

 

但是这样消元的复杂度是O(n^3)的。此时我们可以改变消元顺序，从n消到1。那么对于一个i，当消到i的时候，i的所有儿子已经消完了，所以i只需要和fa[i]以及fa[fa[i]]消，所以复杂度就变成了O(n^2)了。

 

总结：这种期望问题在树上一般是树形dp，而在图上一般是列方程+高斯消元。

 

T3：首先对于一个d和i，若i<=d，那么就会获得d-i的贡献；若i>d，那么就会获得i-d的贡献（自己加上i，同时把选择权交给对方，那么对方就会期望领先自己d，所以是i-d）。

于是我们得出了方程：。

化简就是：。

现在我们要求一个d使方程成立。

于是设f(x)=，那么现在就是求f(x)的零点。

显然f(x)是减函数（x增大时前半部分比后半部分增加的少），那么我们首先二分求出d的整数部分k（即f(k)>0,f(k+1)<0）。然后我们就可以把方程中的绝对值去掉，这时剩下来的就是解方程了。