1030 JSOI2007 文本生成器
AC自动机加DP即可。
1031 JSOI2007 字符加密Cipher
后缀数组即可。
1032 JSOI2007 祖码Zuma
数据有问题。
设(f(l,r))为消去([l,r])的石子的次数。
错（biao)误(cheng)的做法，没有考虑以下情况：
5
1 2 1 3 1
正确答案：
4
错(biao)误(cheng)答(shu)案(chu)：
7
1033 ZJOI2008 杀蚂蚁antbuster
这题做到我眼泪狂奔，大约用了6小时！
不过也透露出了许多问题！！总结如下：
atan2的用法，注意，是atan2(y, x)！
2.注意细节
错误代码1
double p = ant[i].x - x, q = ant[i].y - y;
p = p * cos(at) + q * sin(at);
q = q * cos(at) - p * sin(at);
不要告诉我看不出来哪里错了。
错误代码2
void clearAnt() {
int i = 0;
while (i < cntAnt) {
if (ant[i].hp < 0) {
if (i == withCake) withCake = -1;
// if (withCake != -1 && withCake >= i) withCake --; // 加上这句就对了
mapAnt[ant[i].x][ant[i].y] = false;
cntAnt --;
for (int j = i; j < cntAnt; j ++)
ant[j] = ant[j + 1];
}
else i ++;
}
}
以后写程序要不要把每个变量都过一遍呢？
还有一些题目中的细节：
- 注意是“顺时针”还是“逆时针”。
- 注意
如果将每只蚂蚁在洞口出现的时间作为它的活动时间的第1秒和所有蚂蚁的年龄加1。是两回事，也就是说活动时间和年龄是不同的。 - 一只蚂蚁不能移动却在蛋糕上，也会扛上蛋糕。
题外话：
hwd在冬令营说几何题不要在乎时间复杂度，于是我在判断线段和圆是否有交时用了旋转的方法，结果在本地测超了0.1s。
1034 ZJOI2008 泡泡堂BNB
QAQ
贪心的方法如下：
int solve(int A[], int B[]) {
sort(A, A + n);
sort(B, B + n);
int ret = 0;
int low = 0, high = n - 1;
int low2 = 0, high2 = n - 1;
while (low <= high) {
// step 1
while (low <= high && A[low] > B[low2]) {
low ++, low2 ++;
ret += 2;
}
// step 2
while (low <= high && A[high] > B[high2]) {
high --, high2 --;
ret += 2;
}
// step 3
if (low <= high) {
if (A[low] == B[high2]) ret ++;
low ++, high2 --;
}
}
return ret;
}
这题我不会做，在网上找题解都是只有代码（如上，是求A队最大得分的），个个都说是简单的贪心，为什么我就不觉得呢。
后来，根据这个贪心的方法，脑补出了证明：
首先按能力排序，这时候可以从能力弱的开始贪心。下面小写字母表示A队的，大写就是B队的。
设(x)、(X)是能力最弱的，(y)、(Y)是最强的。
如果$ x > X $，那么必然让他们对打，得(2)分。
如果$ x < X (，那么就让)x(和)Y(打。
上面两个贪心都很显然，头疼的是)x=X$的情况：
假如我们让(x)和(X)对打得(1)分。
....接着如果$ x'>X' $，那么必然让他们对打，得(2)分。继续，直到$ x' leq X' (。
....如果) x'<X' (，那么就让)x'(和)Y(打。这个时候我们可以调整为)x(和)Y(打，)x'(和)X(打，这样更优！
....如果相等，如果打的话，那么可以调整为)x(和)X'(打，)x'(和)X(打，这样更优！如果不打的话，假设)x'(最后和)Z(打，可以调整为)x(和)Z(打，)x'(和)X$打，这样更优！也就是说，不管打不打，经过调整后都变得更优！
综上，如果除去(x)和(X)后，能够一直赢下去就让他们打，否则让(x)和(Y)打。得证。
1035 ZJOI2008 Risk
这题对着数据该才过TAT。
首先求出每个军队的外围的轮廓，这个可以枚举每一条边然后不断求下一条边，直到形成一个环。
至于如何求下一条边，扫描一下atan2的值就好。
黑色是当前的边，紫色是下一条边，灰色是其他边，我们按照红色箭头的方向扫描到的第一条边就是下一条边。
除此之外，我居然忘记了一个特殊情况，就是一个国家包含另外一个国家（其实这个情况应该很显然啊，为什么我会忘记呢？）。
假设我们要判断国家A被哪个国家包含且发生战争，我们只要找到一个面积最小的包含国家A的国家就可以了。
调到这里，心想要A了吧，发现还有特殊情况：
按照上面的算法，A和B是要发生战争的，但事实上不是这样的。于是又加了一个特判：如果国家的四周都有国家，那么它是不会被其他国家包含的。
虽然最后A了，但是总觉得还有什么特殊情况没考虑到，有人能告诉我吗，谢谢。
1036 ZJOI2008 树的统计Count
直接树链剖分，不过source那里写着分治，不知道是怎么做的？
1037 ZJOI2008 生日聚会
把男生看成(1)，女生看成(-1)，得到部分和(s_i)。如果存在(i,j)，(j < i)，使得$k < |s_i - s_j| $ 或者(k < |s_i|)那么就是不合法的方案。
然后DP，记(dp(i, s, min, max))。
1038 ZJOI2008 瞭望塔
直接半平面交即可。
1039 ZJOI2008 无序运动Movement
数据有误，偷懒不做。