一句话紫书简单题

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

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

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]\) 的数一定有序。再者从操作是影响前缀来看也可以想到从后缀开始确定。