1030 JSOI2007 文本生成器

AC自动机加DP即可。

1031 JSOI2007 字符加密Cipher

后缀数组即可。

1032 JSOI2007 祖码Zuma

数据有问题。

设$f(l,r)$为消去$[l,r]$的石子的次数。

错（biao)误(cheng)的做法，没有考虑以下情况：

51 2 1 3 1

正确答案：

错(biao)误(cheng)答(shu)案(chu)：

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$打。得证。