虽然是用了10小时来打5小时的比赛，但也弱爆了。神马都不会啊。
A zoj 3539
搜索+字符串，连暴力都不会写
B zoj 3540
竟然是矩形并！！！。。不过就算是“矩形并”，也不会写。。线段树神马的，都不会哇。。
C zoj 3541
好巧妙好经典的N^2DP，我不会啊。
D zoj 3542
纯模拟。。。善用cctype和%x
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cctype>
#include <map>
#include <set>
#include <bitset>
#include <vector>
#include <algorithm>
#include <cmath>
#define PB push_back
using namespace std;
const int inf = ~0u >> 1;
const double eps = 1e-8;
const double pi = acos(-1.0);
int sgn(double x)
{
return fabs(x) < eps ? 0:x < -eps?-1:1;
}
char str[5000];
int main()
{
while(cin.getline(str,5000))
{
int l = strlen(str);
int i = 0;
char opt[20];
int cnt = 0;
while(1)
{
char row[5];
sprintf(row,"%x",i);
for(int j = 0;j < 4 - strlen(row);j++)
putchar('0');
printf("%s: ",row);
bool mark = true;
for(int j = 0;j < 16;j++)
{
opt[j] = mark?str[i]:-1;
i++;
if(i == l)
mark = false;
}
for(int j = 0;j < 16;j++)
{
if(opt[j] != -1)
printf("%x",opt[j]);
else
printf(" ");
if(j%2)
printf(" ");
}
for(int j = 0;j < 16;j++)
{
if(opt[j] == -1)
break;
if(islower(opt[j]))
opt[j] = toupper(opt[j]);
else if(isupper(opt[j]))
opt[j] = tolower(opt[j]);
printf("%c",opt[j]);
}
puts("");
if(!mark)
break;
}
}
}
Up
backward paragraph
E zoj 3543
N^2 dp，claire大神想了个神做法N^3，结果TLE了，哈哈～
F zoj 3544
200棵线段树，O(q * n * log(m))，ykwd大神去玩了，结果线段树部分没人敲了，不会啊。shi哥说有O(n*m)的做法，不会啊。
shi哥的路径压缩的方法场上想到了，不会敲；到现在也不会敲。拿stl企图骗过去，果断TLE。好紧啊。
历时3天，终于AC了。链表路径压缩，orz。果断就是并查集的写法。
题解：
正着做就是裸体有lazy tag的线段树，竟然在zoj上可以过，太orz了。
刷板报什么的，有这样一个性质，后面的涂色不会被前面的覆盖，果断倒着做。
倒着做也可以某种线段树，不需要重复覆盖的，应该会比正着做要快。
（ps，既然正着做倒着做在zoj上都能过，为啥10.2的时候就只有那么点人过了F？不解）
说一下正解吧，太orz shi哥了。
我只想到了路径压缩，没有想到shi哥的并查集式路径压缩。（好像路径压缩就是在并查集里才常用的吧？我这个蒟蒻为毛没想到？！）
既然是不会重复覆盖，那么只要把已经覆盖过的删除了就好了，再覆盖的时候对删除的跳过去就行。这样最多删除O(m*n)次。
但是怎样快速查找呢？就是并查集的做法了，并查集路径压缩之后的复杂度在整数范围内最大为O(5)。
本题中的并查集：
删除[l,r]区间：
1.假如起始点未被删除过，那么就从这个点开始逐次删除，并统计删除的点数，返回删除的点数即可。
删除的过程中，记得将刚刚被删除的点的skip域指向本次删除区间的左端点。
2.假如起始点已经被删除过，那么就找这个点的skip域，直到找到一个可删除节点或者到本段的段尾为止(m)。
而接下来逐次删除的时候，删完的点的skip应该指向这个新的节点。
记得查找的时候，附带路径压缩，并查集的路径压缩各位大神肯定都会写吧？
删完了一个区间之后，把区间开始删除的点的skip域指向最后的点（不在本次删除范围内的可删除节点或者段末）。
牢记：路径压缩的时候是把所有儿子都指向父亲。
最后更新“最后节点“的时候，是将删除区间的起始点指向最后节点（根）。
以上说得很乱，画图解释就是：
这是naive的并查集，a exists in (l,r],a -> l,l -> (r+1)。
路径压缩的时候，l1 -> l2 -> l3 -> r => l1 -> r ,l2 -> r , l3 -> r。
关键代码在51～69行。（因为带了行号，所以复制不方便了哈。。）
数据结构神马的太神奇了。
代码如下：
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <string>
5 #include <cstdlib>
6 #include <cctype>
7 #include <map>
8 #include <set>
9 #include <bitset>
10 #include <vector>
11 #include <algorithm>
12 #include <cmath>
13 #define PB push_back
14 #define sqr(x) ((x) * (x))
15 using namespace std;
16 const int inf = ~0u >> 1;
17 const double eps = 1e-8;
18 const double pi = acos(-1.0);
19 int sgn(double x)
20 {
21 return fabs(x) < eps ? 0:x < -eps?-1:1;
22 }
23 #define maxn 205
24 #define maxm 50005
25 int n,m,q;
26 inline int ab(int x)
27 {
28 return x >= 0?x:-x;
29 }
30 struct method
31 {
32 int type;
33 int cnt;
34 int in[7];
35 }mth[maxm];
36 int ans[10];
37 struct skiplist
38 {
39 int skip[maxm];
40 bool tr[maxm];
41 void init(int m)
42 {
43 fill(tr,tr + m,1);
44 }
45 int jump(int pos)
46 {
47 if(pos >= m)
48 return m;
49 return tr[pos]?pos:skip[pos] = jump(skip[pos]);
50 }
51 int erase(int l,int r)
52 {
53 int now = jump(l),pos = now;//
54 int num = 0;
55 while(pos <= r)
56 {
57 if(tr[pos])
58 {
59 tr[pos] = false;
60 skip[pos] = now;
61 pos++;
62 num++;
63 }
64 else
65 pos = jump(pos);
66 }
67 skip[now] = pos;
68 return num;
69 }
70 }skip[maxn];
71 void gao(int row,int le,int ri,int co)
72 {
73 ans[co] += skip[row].erase(le,ri);
74 }
75 int main()
76 {
77 while(scanf("%d %d %d",&n,&m,&q) == 3)
78 {
79 for(int i = 0;i < n;i++)
80 skip[i].init(m);
81 memset(ans,0,sizeof(ans));
82 for(int i = 0;i < q;i++)
83 {
84 char opt[20];
85 int a[10];
86 scanf("%s",opt);
87 switch(opt[0])
88 {
89 case 'C':
90 mth[i].type = 1;
91 mth[i].cnt = 4;
92 break;
93 case 'D':
94 mth[i].type = 2;
95 mth[i].cnt = 4;
96 break;
97 case 'R':
98 mth[i].type = 3;
99 mth[i].cnt = 5;
100 break;
101 case 'T':
102 mth[i].type = 4;
103 mth[i].cnt = 4;
104 break;
105 }
106 for(int j = 0;j < mth[i].cnt;j++)
107 scanf("%d",&mth[i].in[j]);
108 }
109 for(int i = q - 1;i >= 0;i--)
110 {
111 int hi,lo,le,ri,c,cnt = mth[i].cnt,type = mth[i].type;
112 int in[10];
113 for(int j = 0;j < cnt;j++)
114 in[j] = mth[i].in[j];
115 c = in[cnt-1];
116 if(mth[i].type == 1)
117 {
118 hi = max(0,in[0] - in[2]);
119 lo = min(n - 1,in[0] + in[2]);
120 for(int j = hi;j <= lo;j++)
121 {
122 int offset = floor(sqrt(sqr(in[2]) - sqr(j - in[0])));
123 le = max(0,in[1] - offset);
124 ri = min(m - 1,in[1] + offset);
125 gao(j,le,ri,c);
126 }
127 }
128 else if(mth[i].type == 2)
129 {
130 hi = max(0,in[0] - in[2]);
131 lo = min(n - 1,in[0] + in[2]);
132 for(int j = hi;j <= lo;j++)
133 {
134 int offset = in[2] - ab(j - in[0]);
135 le = max(0,in[1] - offset);
136 ri = min(m - 1,in[1] + offset);
137 gao(j,le,ri,c);
138 }
139 }
140 else if(mth[i].type == 3)
141 {
142 hi = in[0];
143 lo = min(n - 1,in[0] + in[2] - 1);
144 for(int j = hi;j <= lo;j++)
145 {
146 le = in[1];
147 ri = min(m - 1,in[1] + in[3] - 1);
148 gao(j,le,ri,c);
149 }
150 }
151 else
152 {
153 hi = in[0];
154 lo = min(n - 1,in[0] + in[2] / 2);
155 for(int j = hi;j <= lo;j++)
156 {
157 int offset = (in[2] - (j - in[0]) * 2) / 2;
158 le = max(0,in[1] - offset);
159 ri = min(m - 1,in[1] + offset);
160 gao(j,le,ri,c);
161 }
162 }
163 }
164 for(int i = 1;i <= 9;i++)
165 printf("%d%c",ans[i],i==9?'\n':' ');
166 }
167 }
168
G zoj 3445
状态dp+ac自动机，orz ykwd大神。
H zoj 3546
因为有凹多边形的存在，我只能想到N!的做法。这，旋转路径规划？怎么想起了昨晚的rujia几何场的最后一题，谁更难真不好说。
I zoj 3547
四次方和公式+暴力容斥，orz claire_大神
J zoj 3548
推个式子再dp，式子推出来了，dp没人做，弱爆了。
推完式子剩下的就是二分图匹配。。。这场竟然有图论，我tmd竟然没看出来。弱爆了。
弱爆了弱爆了。