一句话紫书简单题

自己没办法独立想出来的会打*

思维训练以及算法巩固都是很重要的。

UVA11054

一眼网络流。

看 /(a/) 看着很难受，先取反，这样变成了 /(a>0/) 就有 /(a/) 的酒要给出，反之就是要收到 /(-a/) 的酒。

左右运输通常不大好搞，考虑能否都换成从左到右，若 /(i<j/),且 /(i/) 要运到 /(j/)，即可以类图论的转为 /(i/to i+1/to i+2…/to j/) 的形式，其中权值为 /(+1/)。

若 /(i<j/)，且 /(j/) 运到 /(i/)，显然可以转为 /(i/) 运到 /(j/) 权值为 /(-1/) 的形式。

扫描线，记录正权和以及负权和，对当前是 /(a/) 的正负性，若 /(a>0/)，那就说明需要从左边运过来 /(-a/) 的权值，倘若不够，就从转为正权值，即到右边再给出。负同理。在当前指针的增长时，正权和以及负权和都要通过一次运输，那么就要贡献上。。

UVA11134 传说中的车 Fabled Rooks

写出来限制式子，一眼分开来变成裸贪心。。

UVA1605 联合国大楼 Building for UN

拆行拆列的图论那一套想想。不难让 /((i,j)/) 变得有意义，即我们期望 /((i,j)/) 是能够满足让 /(i/) 匹配 /(j/) 的，弄成 /(2/) 层即可。

UVA120 煎饼 Stacks of Flapjacks

翻转都是翻转前缀，且对次数无最优限制。

不难想到第一个一定是最后一个翻转（其实不用），推过去，最大的就第一个翻转到最后一位。

于是想到从大到小确定后缀。其实这有点冒泡排序的思想在里面，在经过 /(i/) 轮后，/([n-i,n]/) 的数一定有序。再者从操作是影响前缀来看也可以想到从后缀开始确定。