Educational Codeforces Round 67

CF1187B Letters Shop

二分

直接构造

这题等System Test后更吧。。。

直接换根搜一遍

有(n)个数，每个数(x_i)等概率取([l_i,r_i])中一个值。

设(B(x))是(x)相等连续段的数量

问(E(B(x)^2))

神仙题Orz

(E(B(x)^2)=E((1+sum_{i=1}^{n-1}[x_i eq x_{i+1}])^2))

(=E(1+sum_{1leq i,jleq n-1,i eq j}[x_i eq x_{i+1}][x_j eq x_{j+1}]+3sum_{i=1}^{n-1}[x_i eq x_{i+1}]))

用期望线性性做即可。

注意(sum_{1leq i,jleq n-1,i eq j}[x_i eq x_{i+1}][x_j eq x_{j+1}])，相邻的两个单独算，否则相互独立，直接乘

有一个(n)个点(m)条边的无向连通图上有(k)人，这些人要到(1)点van♂you♂xi。每个时刻一个人可以走一条边，也可以不走。

一个人如果过了(t)时刻才到(1)号点，要付出(ccdot t)的代价。

如果一条边在一个时刻一个方向上同时被(a)个人走，要付出(dcdot a^2)的代价。

求最小代价。

显然分层图费用流。。。

可以发现最多只有(n+k)个时刻（我是sb以为有(ncdot k)个就TTTTTTTTTTTTTTTTT）

平方费用直接拆边

分层直接建图跑费用流就行了。。。