bzoj 1030-1039 1030 JSOI2007 文本生成器 1031 JSOI2007 字符加密Cipher 1032 JSOI2007 祖码Zuma 1033 ZJOI2008 杀蚂蚁antbuster 1034 ZJOI2008 泡泡堂BNB 1035 ZJOI2008 Risk 1036 ZJOI2008 树的统计Count 1037 ZJOI2008 生日聚会 1038 ZJOI2008 瞭望塔 1039 ZJOI2008 无序运动Movement
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
数据有误，偷懒不做。