2007暑期集训队练习赛（3） 解题报告


1001 Earn more money
博弈
通过考虑每一组策略组合来确定Nash均衡很麻烦。
可以使用启发式方法，将两个收益表可以合并为一个收益表，可以看出Nash点的存在是当两者都是最大收益。
则可以对每行每列标记出各自的最大值，当有一个分配满足两个人的最大值，即一个Nash点。
时间复杂度为O（N^2）

1002 Luck and Love
RMQ
二维线段树
也可做成一维，身高和活泼度，可以将两者表示成一个数，再枚举下查询。
浮点数都可以*10先变成整数再处理
最坏复杂度为O（M * 100 * logN）

1003 Let's go home
2-SAT
A，B，C是一个队的，则 A || (B && C) = (A || B) && (A || C)
一对队员X和Y，则 ~X || ~Y
再用2-SAT判定即可
时间复杂度为O（E）

1004 Work, work
DP
设函数sum(z)表示Z轴z坐标平面为下底面的长方体最大花费体力数
z = 0 :  sum(z) = 0;
z > 0 :  sum(z) = max(sum(z-1), 0) + V;
    V = rec[x2][y2][z] + rec[x1-1][y1-1][z] - rec[x2][y1-1][z] - rec[x1-1][y2][z];
answer = max(answer, sum(z));
时间复杂度为O（N^5）

TJU-Tornado 竟然在随机，汗下-_-|||
其实答案是差不多交替的，看RP了哈

1005 Happy Birthday
笛卡尔树
造树时间复杂度O（N）
空间复杂度O（N）
再先序遍历即可

区间排序，区间RMQ都有人过了

1006 Summer Holiday
顶点数最小点基和权最小点基
求出强连通后，再拓扑排序即可
时间复杂度为O（E+N）


今天的题目只是为检验上阶段的专题训练，考验的是特定的算法基础
但中文描述有点歧义
1002的数据在暴力下不同编译器结果竟然不同，让2个队WA
实在抱歉~~
每题卡时都比较紧
C++的IO或者过多的STL使用导致有好几支队TLE
还有编译器的选择，我们oj的编译器两者运行速度差异较大

如果还有什么疑问和纰漏，欢迎来我们论坛讨论，也可以发邮件给我(huangwei@stu.hdu.edu.cn)。
                        By Wiskey