初看这道题的时限就很警觉，暴力枚举铁定超时。于是在想如何优化。枚举的五层循环最内层其实是多余的，因为x5可以直接求出来。于是弄出了108的算法，无奈常系数太大，依然超时。其实如果我能放弃掉解方程的思想，转而去重视移项，应该就会很快得到正解。正解是用哈希（Hash），将方程左边的后三项移到右边，然后枚举x1和x2得到此式左边的值，做哈希。预处理过后就枚举右边三个变元求和，如果能与左边出现过的值相等则存在某些数量的相应解。规模是106，系数再大都超不了时了。我实现的时候偷了懒，没有做哈希（O(1)），直接用了STL里的map（O(lg n)），速度也还可以。
转化的思想依然很重要。这让我联想到SRM 440的那道物理题，我推了半天公式没弄出来最后放弃掉。实际上二分枚举就可以了。这就是需要思维的变换，不能直接顺着题意走，有时候需要重新从另一个角度建模，进行转化。二分确实是一个很有用的东西，对于可以构造出单调性的优化问题很有效。当然本题与二分无关……扯远了……
点击这里查看poj_1840.cpp（780K，2766MS）
PKU Campus 2009结束了，我也很自然而华丽地考挂了。从赛前到赛后状态一直很差（因为她……），今天开始在一片纠结中改题。D题是全场最早出的题，我当时确实把公式推出来了，可惜一个小的细节没有注意到，结果答案有一点点偏差。这直接导致了我出的第一题居然是G而不是D（话说当时出G的时候题目描述还有问题，所以2Y……）。
其实思路很简单，从N个里取出k个，让k是偶数表示红的和绿的之和，其中红的又设出来是r个，剩下的N-k个直接作为2的指数求幂。这样我们得到：S = ∑k( ∑r( C(N,k) × C(k,r) × 2N-k ) )，其中k和r都是满足相应限制条件的偶数。把S整理一下，将求和式中的公共项提出来，得到：S = ∑k( C(N,k) × 2N-k × ∑r( C(k,r) ) )，其中∑r( C(k,r) ) = 2k-1（根据二项式展开系数性质易得）。但到这里需要注意，k可以等于零！我比赛时就是这里忽略了，所以得到了错误的结果。k = 0时，C(k,r)是没有意义的，所以我们需要把k = 0的情况单独弄出来，是2N，然后整理合并其余的式子，得到：S = 2N + 2N-1 × ∑k( C(N,k) )；这里的k是从2开始的。于是最终整理一下就得到：S = 2N + 2N-1 × ( 2N-1 – 1 ) = 4N-1 + 2N-1。
有了公式，程序就很好写了。为了保证不越界，令T = 2N-1，则S = T2 + T = T × (T + 1)，同时对10007取模就可以了。另外，求幂的时候我用了快速幂取模加速，实践结果也很好（16MS）。
点击这里查看poj_3734.cpp（220K，16MS）
这题的难点大概就两个。首先需要读出来名字后面的那些不定长的数字。其次是求解（废话……）。
看了Shanghai 2004给的Solution，用C++析取Token再atoi，很麻烦，而且效率必然也不高。我输入输出都是用stdio.h，这道题顺理成章就想到了用getc和ungetc实现一个peek的功能。数据是按行给出的，如果下一个字符是换行符，那就结束这一组的输入，否则继续。细节可以参考本文末尾的源代码链接。
然后就是求解。很直接地想到用最大流，但试了一下TLE了。看Discuss说有人用最大流过了，目前还不知道怎么做的。最后用Solution的方法，多重匹配。原理跟普通的Edmonds匈牙利匹配类似，只不过对右部添加了一个匹配计数，其正确性不言而喻。
今天是找最大流的练习题做到这个的，没打算继续把Regional做完。蓦然想到今年如果走“正轨”的话，大一我是进不了集训队了；仿佛校选就在5月，而我，没有“提前进校”……
不说了，大翻盘不需要常理，SJTU自己会想明白的。
点击这里查看poj_2289.cpp（3184K，266MS）
最大流问题，我用50行代码解决掉了。第一次这么写代码，感觉还不错。算法题就应该这么写，单独的算法聚集着写操控感觉也方便一些。也就是说，我可能又要改变一下编码风格了……
题目很好理解，一个容易忽略的地方是边是双向的（bidirectional），我在这里WA无数次调了一下午才发现这个问题。
大概的思路是二分枚举答案（最长边长度）然后建图，把长度超过这个数的边都删掉，每条边容量是单位容量（重边计多次），最后求一次最大流就可以了。如果最大流小于T，则方案不可行应该放宽限制，否则寻找是否有更小的答案。
建模有点间接，不过题目很容易看出来是用最大流解。我用的方法很朴素，BFS寻找增广路然后扩充流。
点击这里查看poj_2455.cpp（1184K，391MS）
刚刚灵光突现瞅了一眼清明节Monthly的Problem H，发现AC的人还是很少（10个）。比赛当天因为数据有问题，所以我一直交一直WA……罚时无数最后决定放弃比赛，唉~
为什么我一直交呢，因为我确信这个题很简单，就是贪心而已。注意题目中说“Facer always memorize all the wordlist in sequence”，这就决定了贪心是必然的（因为我快吃饭了就偷懒不写证明了）。我们只需要记录上一次“放置”背单词第一天的位置（last），然后从这开始往后找，如果能“放置”在当前位置就放，放不了就接着往后（多简单直接的贪心啊~）。没过的可能是因为题目没看懂，那我就没辙了，你自个儿好好看吧……
同刚刚发过的题解，这篇也不直接贴代码，换成导出的HTML。但编码风格不是现在的风格了，我传的是比赛时候写的（水题懒得再写了~）。
点击这里查看poj_3730.cpp（125MS）
NOI复习的名题了；重做了一遍，用了不同的方法，因为以前的方法忘了。
首先需要明确题目的意思：“如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易”。也就是说，整个交易过程中的等级极差不能超过m，而不是相邻两个人之间的差。这一点一定要理解好，我就WA了一次……
明确了这一点可能发现题目突然就不好做了。我以前写过一个巨复杂的Dijkstra就是求最短路的同时还考虑极差。这回打不出来了就换了个方向思考：n只有100，完全可以枚举等级区间多次建图再求最短路。于是问题迎刃而解。
有的朋友不太明白怎么建图怎么用最短路解，这里简单说一下，就是把探险家一步一步交易物品最终得到酋长的女儿这一过程看作是一条用钱铺出来的路。探险家一开始处在标号为零的顶点，目的地是标号为一的顶点。图中的非零顶点都代表一个物品；如果物品A可以用物品B以C数量的金币换得，则从B连一条有向边到A，边的权值为C。这样就将问题转化为最短路了。
以往直接把代码贴在文章里的做法感觉很不好，以后把代码放在单独导出的HTML文件中便于大家查看。另外，最近受到JavaScript的影响再次改变了编码风格，感觉还不错，以后准备坚持下去，这样在不同的类似的语言之间切换习惯一些。
点击这里查看poj_1062.cpp（412K，32MS）
这道题我就不多说了，周源在集训队论文里讲的很明白了，重点就是数形结合，只贴一下代码吧，具体的请看论文。
// 1060K 719MS
#include <iostream>
using namespace std;
int n, f, a[100001], s[100001];
int main()
{
cin >> n >> f;
for (int i = 1; i <= n; ++ i)
{
cin >> a[i];
s[i] = a[i] + s[i-1];
}
int ans = 1000*s[f]/f;
int last = 1;
for (int i = f+1; i <= n; ++ i)
{
int lastval = 1000*(s[i]-s[last-1])/(i-last+1);
int fval = 1000*(s[i]-s[i-f])/f;
if (lastval >= fval)
{
ans = max(ans, lastval);
}
else
{
ans = max(ans, fval);
last = i-f+1;
}
}
cout << ans << endl;
return 0;
}