华科2020算法设计与分析 (POJ)做(shua)题(shui)记录（未完）

课程还没结束为避免不必要的麻烦代码就先不贴了，以后补（有想要代码对拍啥的可以评论或私信

[POJ1000] A+B Problem

题目大意

~

解题思路

别吧，代码都给你了hhh

代码

[POJ1005] I Think I Need a Houseboat

题目大意

半圆面积每年增长50，给一个点坐标问几年之后这个坐标被半圆覆盖。

解题思路

二分年数，算距离，判断。

代码

[POJ1753] Flip Game

题目大意

有 4x4 的正方形，每个格子要么是黑色，要么是白色，当把一个格子的颜色改变(黑-> 白或者白->黑)时，其周围上下左右(如果存在的话)的格子的颜色也被反转，问至少反转几 个格子可以使 4x4 的正方形变为纯白或者纯黑？

解题思路

裸广搜，4x4的棋盘可以转换成16位二进制数。
第一个状态不能忘了啊md。

代码

[POJ3295] Tautology

题目大意

输入由 p、q、r、s、t、K、A、N、C、E 共 10 个字母组成的逻辑表达式，问这个逻辑表达式是否为永真式。 具体的运算规则看表格。

解题思路

这个还是有点技术含量的一道题。
枚举是一定的，但要是真搞成表达式求值就太顶了；因为都是前缀表达式，一个单向指针是个好东西。
这方法还蛮巧妙的。
（亲测我的代码只有G++能过哈哈哈哈哈哈哈哈哈xswl

代码

[POJ2366] Sacrament of the sum

题目大意

已知两个给定的序列，一个升序排列，一个降序排列，在这两个序列中各找一个数，它们加起来恰好等于 10000

解题思路

枚举一个序列二分另一个序列，O(nlogn)
序列有序的话总感觉两个指针扫一下O(n)应该也可以？
（然而我先用map水过去了hhh）

代码

[POJ2503] Babelfish

题目大意

输入一个字典，字典格式为 n 行“英语 外语”的对照表。然后是若干个外语单词，让你翻 译，输出它们对应的英语单词。如果字典中不存在这个单词，则输出“eh”。

解题思路

其实用分治也好写，但还是用map写的（或许排序+分治比用map更好些？
刚开始用string结果T了，闷头改char（
map的话是个long long->char* 的映射，把外语单词映射成27进制的数即可（注意不能是26进制，要把aa和aaa区分开）

代码

[POJ3714] Raid

题目大意

有两组坐标，一组是 n 个发电站的坐标，一组是 n 个士兵的坐标。求哪个士兵离发电站的距离最短。

解题思路

最近点对问题，要求分别在两个组别。
按x坐标排序之后分治。得到两边子问题的最小值了之后，枚举左右两边的点对，只有小于最小值才有可能更新答案，否则就break。
数据应该还是比较水的hhh，感觉把两部分完全分开的话是有可能卡掉的。注意实时更新最小值应该会缓解一点，但没有严格的时间复杂度证明。

代码

[POJ3233] Matrix Power Series

题目大意

已知一个 NxN 的矩阵 A，计算$S=A+A^2+...+A^k$，对m取模。

解题思路

构造矩阵是个很好的思路：https://www.cnblogs.com/hadilo/p/5903514.html（一看就明白
分治的话也比较好想：
$S=A+A^2+...+A^{now}=A+A^2+...+A^{mid}+A^{mid}(A+A^2+...+A^{now-mid})$
刚开始写了暴力超时了，加了个map记录一下就过了，空间的话log(1e9)的应该也不会爆。

代码

[POJ2506] Tiling

题目大意

用1x2和2x2的方块填满2xn的格子有多少种方法。

解题思路

裸递推。。（加个高精度

代码

[POJ1723] SOLDIERS

题目大意

一些士兵站在矩阵的一些方格内，现要把他们移动到一横排，并连续地排成一队，问最少需要移动多少步。

解题思路

隔了几天来写发现都快忘了咋做了真tmd完蛋
很显然xy可以分开考虑，移动到同一列的话就是说y就直接中位数对吧，移动到连续的n行的话，假设第一个人站在第i行，那么最终所有人的位置就是i+1，…，i+n-1，并且相对顺序不会变的，可以首先把这个偏移量减去再求中位数，相当于求第一个人站在哪里是最优的。

代码

[POJ3269] Building A New Barn

题目大意

已知 N 头牛的位置，问牛舍建在哪里，牛到牛舍的距离和最小。

解题思路

看不到题目里的这句话“The hungry cows never graze in spots that are
horizontally or vertically adjacent.”就完蛋了哈哈哈哈哈哈
乍一看距离和当然用中位数求一下就好了，不过万一中位数那个点有牛咋办（有牛是不能建牛舍的），然后怎么统计个数？
很显然xy可以分开统计，并且xy的可选择的值是有个范围的（牛的个数为偶数时中间两个数形成的区间）。题目里说了任意两头牛不相邻，于是如果xy分开统计了之后中位数集中在一个点，那么枚举相邻的四个点即可；如果不是一个点的话，就在可选的范围内枚举。

代码

[POJ3579] Median

题目大意

给出一个数列，然后计算数列里各个数之间的差值的绝对值，形成一个新数列，求新数列的中位数。

解题思路

二分答案再判断。判断的标准是计算差分数列中比该答案小的数的个数，和n(n-1)/2/2比较。
写的时候想清楚就没什么难度了hhh

代码

[POJ1050] To the Max

题目大意

求一个最大为 100*100 矩阵中的子矩阵中元素之和的最大值。

解题思路

光想二维dp去了差点没想出来hhh
首先这道题是基于“最长连续子序列和”这个问题。枚举子矩阵的左端和右端，然后在枚举到的范围内用前缀和做一次最长连续子序列和就可以了。

代码

[POJ1088] 滑雪

题目大意

一片区域，每次可以向上下左右四个方向中高度小于当前高度的地方走，可以在任意地方开始任意地方结束，问最长的路有多长。

解题思路

记忆化搜索
f[x][y]表示从(x,y)最远能走多少
f[x][y]=max{f[nx][ny]+1} (nx,ny)满足条件

代码

[POJ1185] 炮兵阵地

题目大意

NOI2001的题hhh

解题思路

m很小并且山地和平原、放置与不放置可以用01表示，所以一看就是状压dp。
但是炮可以打到上下两个格子这一点很烦人，这样的话不能用前一行向当前行转移，因为有可能在前一行的前一行存在一个炮和当前行的冲突。
那么我们在状态表示里至少要存两行的状态。但是$2^{10}\ast 2$不是有点太大了么？有趣的是，每一行的炮与炮之间至少要留两个空格，所以每一行实际的方案数要比$2^{10}$要小很多，即使是最大的m=10也不过只有169个，这些合法的状态是可以预处理出来的。
设f(i,j,k)表示前i行，其中最后两行为第j个和第k个状态的最大数量。然后就可以分别判断是否合法然后转移了。
理论时间复杂度是O(n(2m)^3)。但是由于我们已经预处理了最多169个合法方案，中间各种判断又会砍掉很多冗余的状态，极限数据也是完全可以在2s内出解的。

代码

[POJ1636] Prison rearrangement

题目大意

有两个监狱，每个监狱里面有 n 个囚犯，现在希望交换 n/2 对囚犯。但是考虑有一些原本在不同监狱的囚犯对在一起是很危险的，所以希望经过交换后他们还是不在一个监狱里面。那么如果保证这个条件，希望尽可能多的交换囚犯。

解题思路

确实有点难想这道题。
首先要转化为一个背包问题可行性的问题，类似有n个物品，每个物品有个大小，装到背包里问能不能有装出某个大小的组合。
dp(i,j)表示有没有一种方案使第一个里面的i个和第二个里面的j个交换（dp过程中ij可以不相等，可以先认为可以出现数量不等的交换）
有互斥关系的一组囚犯要换的话只能全部都换，所以要用并查集缩成一个点，并且统计这个点中的囚犯个数，交换的时候全部交换。
最后用背包问题的可行性算法求解。

代码

[POJ2228] Naptime

题目大意

题目大意： 一天由 n 个小时构成，在第 i 个小时睡觉能够恢复 Ui 点体力。有一头牛要 休息 b 个小时，可以不连续，但休息的第 1 个小时无法恢复体力。前一天的最 后一个小时和第二天的第一个小时是连在一起的，求这头牛能恢复的体力最大值。

解题思路

f(i,j,0/1/2,0/1/2)表示前i个小时，休息j个，其中第i个小时没休息/入睡/睡着，第1个小时没休息/入睡/睡着的最大值
根据题目规则转移即可。
最终的答案要考虑第n个小时入睡或睡着并且第一个小时睡着的情况。
这题空间有点小，要加个滚动数组。

代码

[POJ1042] Gone Fishing

题目大意

有n个池塘，在这个池塘里钓5分钟鱼可以获得fi条鱼，再钓5分钟可以获得fi-di条，再5分钟fi-2*di条，以此类推。从第i个池塘走到第i+1个池塘需要ti个5分钟。从第一个池塘出发，可以在任意池塘结束，问最多能获得多少条鱼。

解题思路

题目还是要仔细读一下，有一些约束，比如答案相同时要保证在编号小的池塘呆的时间最长。
贪心，枚举最终在第i个池塘结束钓鱼，先加上走路的时间，然后用一个大根堆保存各个池塘中能获得的鱼的数量，每一次弹出最大的，然后把这个池塘的下个5分钟能获得的鱼重新压入堆。

代码

[POJ1328] Radar Installation

题目大意

假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧，而海洋在另一侧。每一个 小的岛屿是海洋上的一个点。雷达坐落于海岸线上，只能覆盖 d 距离，所以如果小岛能够 被覆盖到的话，它们之间的距离最多为 d。计算出能够覆盖给出的所有岛屿的最少雷达数目。

解题思路

对每一个点计算出它能被覆盖到的最右的点，之后按照这个点排序，从左至右选，每选一个点更新其后面所有能被这个点覆盖到的点。
正确性显然吧。
没读完数据不要break掉啊啊啊啊啊啊啊啊卡死我了

代码

[POJ3040] Allowance

题目大意

农夫要给奶牛 Bessie 每周津贴。农夫有 N 种不同面额不同数量的硬币，而且相邻大小的硬币面额存在整除关系（1 分、5 分、10 分、50 分）。他每周至少要给奶牛 C 分钱，计算他所有的钱最多可以给奶牛多少周。

解题思路

首先面值比C大的全部一天一张。
比C小的面值，先从大到小凑，凑得接近C；再从小到大凑，凑得超过C，为一天。
容易TLE，每次计算的时候计算出来每个面值的章数，再计算出来每个面值这个张数最多能有多少天，然后取min，答案加这个天数。再进行下一次贪心。

[POJ1700] Crossing River

题目大意

每个人过河都有自己的过河时间。有 n 个人想过河，但只有一只小船，最多只能装 2 个人。每一次过河，过河时间为用时最多的那人过河时间，如果还有人没有过河，那么过 去一个用时最少的送回船。问 n 人过河最少要多少时间。

解题思路

听说这题非常经典但刚开始我还是懵了一下。。
最容易想到的是时间最小的人来回当司机，但这样不一定是最优的，样例就是这样。还有一种可能是最小和次小的分别回来，为的是保证最大和次大的可以一次过去。
很显然最小和次小的一定是呆到最后过去的，所以只需要对每一组最大和次大的选择最小的方案就可以了。

代码

[POJ2586] Y2K Accounting Bug

题目大意

有一个公司由于 Y2K 病毒使公司赢亏数据丢失，但该公司每月的赢亏是一个定数，要么 一个月赢利 s，要么一月亏 d。现在 ACM 只知道该公司每五个月有一个赢亏报表，而且每次 报表赢利情况都为亏。在一年中这样的报表总共有 8 次（1 到 5，2 到 6，…，8 到 12），现 在要编一个程序确定当赢 s 和亏 d 给出，并满足每张报表为亏的情况下，全年公司最高可赢 利多少，若存在，则输出多多额，若不存在，输出"Deficit"。

解题思路

贪心。在连续的5个月内在保证总体为负的情况下盈利的月份最多，然后计算一下12个月的就行了。如果12个月总体盈利的话直接输出答案，否则就是Deficit。

代码

[POJ1860] Currency Exchange

[POJ2380] Til the Cows Come Home

题目大意

无向图求1-n最短路

解题思路

spfa板子

代码

[POJ1062] 昂贵的聘礼

题目大意

读题吧中问题面hhh

解题思路

若i可用j替代，则i向j连边，权值为代替后的花费
枚举长度为m的区间（以第一个人的地位为标准其实只有m个，做m次dijkstra）
每次做完dijkstra之后枚举节点，要加上最后一个节点的非替代花费
使用堆优化dijkstra

代码

[POJ3660] Cow Contest

题目大意

有 N 头奶牛在比赛，给出一系列条件，形如 A 战胜了 B。若 A 战胜 B，B 战胜 C， 则我们认为 A 也能战胜 C。问，根据这一系列条件，有多少牛的排名是可以确定的？

解题思路

floyed求出传递闭包后，入度+出度=n-1的点排名才可以被确定。

代码

[POJ1324] Holedox Moving

[POJ2449] Remmarguts’ Date

题目大意

给出一个图，然后给出一个起点个一个终点，求这两点间的第 K 短路。

解题思路

spfa+A*，k短路模板题

代码