不可能的任务 BZOJ 50题(上)

in 代码 read (67)

1.bzoj2563:将边权均摊至端点,若两个端点分属两个人,相减时会抵消;若同属一人,则获得边权收益,依此贪心。#include <cstdio> #include <cstdlib> #include <cstring> #inclu...

继续阅读

BZOJ2127: happiness

in 代码 read (64)

题目大意:每个人都有两个选择,选择文科会获得$w_i$的收益,选择文科会获得$l_i$的收益。有些特定的一对,如果他们同时选择某一科目,又会有相应的收益。求收益最大。题解:这里用到了网络流二元组建图。所谓网络流其实也就是线性规划转成图论,二元组建图也同样是这样。这题建图如下...

继续阅读

BZOJ 3436: 小K的农场

in 代码 read (59)

题目大意:有 $n$ 个数,然后有一些诸如 $x_1-x_2\le c$ 或 $x_1-x_2\ge c$ 或 $x_1=x_2$ 的限制条件,问是否存在一组数满足条件。解题牢骚:啊,一道裸的差分约束系统,$x_1-x_2\ge c$ 可以转化为 $x_2-x_1\le -...

继续阅读

bzoj3156: 防御准备

in 代码 read (47)

$$S_i = \sum_{j=1}^{n-i+1}j$$$$dp_i = min(dp_j + S_{j+1} - S_{i+1} - (i-j)\times(n-i+1)+a_i)\ \ j\in [1,i-1]$$$$dp_i = min(dp_j + S_{j+1}...

继续阅读

核糖核酸

再见,OI,我爱你,OI