【cf715X】Codeforces Round #372 (Div. 1)

2016年9月19日1,4260

A. Plus and Square Root

推公式可得,可构造每次按完的数为 i * (i+1)

B. Complete The Graph

给一张无向图,要求赋值一些边的边权,使得最终S到T的最短路为L

用f(i,j)表示从S到点i,经过j条无边权的边的最短路

选择一个最小的j,使得f(T,j) + j <= L

更改这条路径上的边权,使得最短路为L,将其它无边权的边赋值为L

可以证明不会产生其它的最短路

似乎还可以采取一些暴力调整的做法,写起来会短一些