poj1837 Balance
自从4.11在sysu预选赛充分地感觉到无力之后，有一个多星期患上了赛后综合症，一直不想或者说，逃避编程。经过啊通和龙兄的帮助，终于在一个多星期后的今天重新做了poj的题，也做了sicily的题，总算从阴影中走出。呵呵。只能怪自己太水了，差点就成了：在哪跌倒，就在哪埋了＝ ＝。
好了，废话少说，这题的主要难点是找状态存储方法（er，据说所有的dp题都是这样，所以这句有点废＝ ＝）。存储方法是m[i][t]表示有i个物品时，总权为t的个数。状态转移方程m[i][t] += m[i-1][j+hook[k]*w[i]]，最后只要找出m[g][N]的数目就可以了。
sicily1702 Robot Roll Call -- Cambot...Servo...Gypsy...Croooow
这题是周赛题，当时我的想法是回溯，当然是超时，但是我还是试了，真是sb。之后就是想到把原来的图换成另外一个图。具体做法是首先把点从1～n^2编号，点（i，j）的编号为i*j。然后由于点（i， j）和它上下左右的点相连，所以i*j就和（i-1）*j，（i+1）*j，i*（j-1），i*（j+1）相连，他们的权值就是（i，j）的权值。之后用dijkstra求出最短路，再加上点（n-1，n-1）的权值就可以了。虽然说这个方法可行，但是很麻烦，超时的可能性很大，而且但是心情不好，所以我当时就没有试，后来在bbs上看到了和我思路差不多的算法，才验证了这个思路的可行性。
但是之后发现了一个更厉害的算法，就是BFS，但是该算法的提出者称之为：激情小广搜。呵呵。主要思路就是：用f[i][j]记录到（i，j）的最短路径，然后对（i，j）进行扩展的条件是找到从某个点到（i，j）这一点的新的最短路小于原来的f[i][j]。这个思路和我之前做过的广搜的不同之处就是加入了剪枝，而且不是不是纯粹的对状态进行搜索，而是对最优解答案进行搜索。从个人感觉上，有点像dp……
sicily1684 Christmas
题意：有n pairs男女参加party，然后每个人身高和年龄不同，所以男女组合的时候难免有不爽。然而不知道为什么，不爽程度居然可以算出来：F(i,j)=(Hi-Hj)^2+(AGEi-AGEj)^2 。然后要求最大不爽程度的最小值。<-(类似poj的frogger)
本题开始时毫无头绪，不过之后看了argo的讨论之后，发现解似曾相似。这题用的是二分+匹配。匹配当然可以理解，但是要用二分又是为什么呢？原来我们要求的是众多匹配方案中，最大的最小不爽值。所以理所当然地想到要枚举所有的匹配方案，然后最终找出符合条件的边。这样固然是可以理解的，但是会超时。所以这里引入搜索技术。通过举出边的上界，来不断逼近目标解。这样就有一个问题：是不是一定能用二分法求出边？即有没有可能求出的边的值不在给出的边集里面呢？答案是不可能。因为考虑一下可以发现，如果我们找到的边值如果不是最优解（即不在给出的边集里面的话，我们可以找到另外的边使得符合条件而且在边集里面）。这个枚举可行解的界从而不断逼近可行解的技术，过去曾经听说过，叫参数搜索。这里又再次遇到，就写下了这篇日志，以作备忘。
另外，再次膜拜一下用此方法做出此题的大牛们～ OTZ
sicily1700 Ping
题目大意就是：有一些点，点与点之间有权值，现在有一个信息，要从源送到终点，问最少时间。如果信息到达A，则下一步，信息会发送给A相连的所有点。假设B和A相连，那么下一步，就会从B发送给所有与B相连的点，包括A。这样一来就会出现一些死循环，所以就有步数限制（10）。问题其实就是一个单源最短路径的问题，但是加上了步数限制。这个问题经过kelefe大牛的指点，终于做出来了～就是把bellman ford算法进行变形。bellman ford算法一共对n-1条边进行松弛而达到求全图最短路径的目的（因为一个有n个点的图，其最短路径的边数一定不会超过n-1）。按照这个思想，我们只要对图进行k次松弛（k是步数限制），就可以求出步数不超过k的最短路，这是主要思想。但是单单有这个思想还是不够的。因为bellman ford算法对边松弛的顺序会导致每次松弛的结果不同。比如说，如果从源开始松弛，则1次松弛就可以松弛到了所有的边（不一定是最短路）。这样一来，我们设置的步数限制意义就不太明显。我们要的是，从原点开始，首先松弛原点，之后松弛和原点相连的所有点，如此下去。一直到超过步数限制。要达到这一目的，我们松弛边的时候，最好是从远离原点的顶点开始松弛（最好是从终点开始），这样一来，就可以保证第一次松弛的是原点相连的边，第二次松弛是松弛与原点相连的顶点，如此类推。
poj2676 sudoku
本题没什么好说的，就是回溯。之所以要写在这里备忘，是因为这里涉及到一些应赛技巧。本题如果从1到9回溯的话会超时，但是如果从9到1回溯的话，会16ms搞掂。这里就涉及测试数据偏好。以后要要注意的是：如果算法涉及选择的话，就要注意选择的次序（即可能存在数据的偏好……）。当然，最好就是涉及一个全面的算法，能应付各种数据，但是对于比赛等时间比较紧的时候，可以考虑一下这些小技巧。