HDU 4322 Candy
题意：有N颗糖果和M个小孩，老师现在要把这N颗糖分给这M个小孩。每个小孩i对每颗糖j都有一个偏爱度Aij，如果他喜欢这颗糖，Aij = k，否则Aij = 1。小孩i觉得高兴当且仅当ΣCij×Aij >= Bi，j=1,2,…,N，若他分得了糖j，Cij = 1，否则Cij
= 0。问能否合理分配这N颗糖，使得每个小孩都觉得高兴。
体会：一开始看M、N都小于13，而且大家都wa爆虽然想到了费用流做法但是一次构图的做法没敢继续想下去，于是在想2^13枚举构图的做法。后来证明一开始的方向是正确的，不应该被坑爹的数据范围吓住。
解法：由于每块糖都与1和k两种欢乐值，因此应该尽可能分配欢乐值为k的糖果，对于剩余的值可随意选择填满（与是否喜欢无关），对于每个人要尽可能分配bi/k块喜欢的糖，这个容量就是bi/c，对结果的贡献为k。对于剩余的bi%k可选择一块喜欢的糖或者bi%k块不喜欢的糖（这里怎么控制没有想到）。bi%c（>1）的也是可以用一个能让这个小孩欢喜的糖来贡献，但是其贡献只为bi%c。对于小孩来说，最大费用最大流后，糖分配的贡献值为最大费用，剩余糖就是（n-最大流），然后用这些糖去填不满的，只要满足总和大于Σbj。就可以分配了。
具体建模方案：
(s,i,1,0);
(i,j,1,0);
(j,t,bj/k,k);
If(bj%k>1)
(j,t,1,bj%k)
Ans = 费用 + N – 最大流 >= Σbj 则满足要求
费用不仅仅可以表示耗费，也可以表示贡献，或许还可以表示其它属性，要灵活使用。
HDU 4324 Triangle Love
题意：2000个点的竞赛图，保证任意两点间仅有一条有向边，问是否存在一个三元环。
解法很多，一一列举：
如果把任意有公共顶点的两边构成的图形看做一个角，可将角分为是b的和不是b的（用a类表示），把任意三条边看做一个三角形，可将三角形分为x、y两种。对于每个顶点入度为in出度为out则共有in*out种b种角，由于是竞赛图，因此有C(n,2)-in*out种a种角,根据3x+y=b，2y=a，因此x=（b-a/2）/3，即可求出三元环的个数。
对于有向三元环，我们知道找到：A->B->C->A ，B->C->A->B ，C->A->B->C 是一样的，这给0(n^2)的算法提供了基础。
对于每次枚举i，我们在(0~i-1)的范围看下有多少个i指向的点(剩下的就是指向i的点)，同时算下i指向的点的出度和。就可以知道这些 i指向的点 指向 指向i的点（剩下的点）的数目，如果 num * (num - 1) / 2 < sumout 那么就是被指向的点有指出去了，这样就形成了3元环。否则，剩下的就是更新下出度即可，继续执行下一个节点。
结论：对于一个竞赛图，若存在n元环，一定存在一个n-1元环或者三元环，此题可以一遍拓扑排序判环求解即只需要找到一个环，就必定存在三元环。证明如下：
假设存在一个n元环，因为a->b有边，b->a必定没边，反之也成立 所以假设有环上三个相邻的点a-> b-> c,那么如果c->a间有边，就已经形成了一个三元环，如果c->a没边，那么a->c肯定有边，这样就形成了一个n-1元环。。。。 所以只需证明n为4时一定有三元环即可，显然成立
Hdu 4323 Magic Number
给出一个字典，查询某个词与字典中编辑距离小于k的单词的个数。
普通的dp就可搞，这里顺便学了个BKTree，此数据结构的用处暂时没想出来，所以只是随便实现了一下，没有仔细研究。
参考资料:Matrix67的《编辑距离、拼写检查与度量空间：一个有趣的数据结构》
class BK {
int maxn = 12;// 最大距离
class node {
node ch[];
String key;
int count;
node(String s) {
key = s;
count = 1;
ch = new node[maxn];
}
}
node root;
int dp[][] = new int[maxn][maxn];
int dis(String a, String b) {
int n = a.length();
int m = b.length();
for (int i = 0; i < maxn; i++)
dp[0][i] = dp[i][0] = i;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int flag = 1;
if (a.charAt(i - 1) == b.charAt(j - 1))
flag = 0;
dp[i][j] = Math.min(
Math.min(dp[i - 1][j], dp[i][j - 1])+1,
dp[i - 1][j - 1] + flag);
}
}
return dp[n][m];
}
void init() {
root = null;
}
void insert(String s, node r) {
int d = dis(r.key, s);
if (d == 0){
r.count++;
}
else if(r.ch[d]==null)
r.ch[d]=new node(s);
else
insert(s, r.ch[d]);
}
void insert(String s) {
if(root==null)
root= new node(s);
else
insert(s, root);
}
int query(String s, int n) {
return query(root, s, n);
}
int query(node r, String s, int n) {
int ans = 0;
if (r == null)
return 0;
int d = dis(r.key, s);
if (d <= n)
ans += r.count;
int a = Math.max(d - n, 1), b = Math.min(maxn-1, d + n);
for (int i = a; i <= b; i++)
ans += query(r.ch[i], s, n);
return ans;
}
}