第一次评测后 是第二，而且分数 奇低，不想说了。感觉和昨天的数学一样悲剧了～
然后发现各种问题，第二题全场爆零，第四题数据是原设计的10倍，标程只能过一个点。。。
纠正了这些后复测：300+，勉强比汪同学高一点。
话说麻同学来上课了，于是吵了很多，但大家发挥都不错，
汪同学300+，吴天舒279，陆瑾聪200。。后面的普遍100左右。
我们发现是学c的人多了。。。。。然后又怂恿了两个人转c。。。。
说说题目，
第一题:忽略了全是0的情况。。。。90
第二题:flood-fill，（题目描述的就是flood。。。）AC
第三题:数学题，因式基本定理及其推论。。AC
第四题：求逆序对数，经典分治就不说了，于是想标新立异。
一上来想到平衡树，SBT不会写，SPLAY又觉得太长了。于是想线段树，好像用不起来。
最后剩下时间不多了，忽然蒙出了树状数组，于是狂写。
本来题目设计的是两种方法都能过的，由于复测时，数据没改（原设计的10倍），所以只能拿一半分。。。。
后来发现经典分治1.08s ，树状数组2.73s（最大点），其实也不是很大的差距。
试题
1、最大数和最小数
（maxmin.pas/c/cpp; 时限:1s; 64MB）
【问题描述】
输入一个数（不超过200位），将其重新排列后组成一个最大数和一个最小数。
【输入格式】
第1行：一个整数N，不超过200位。
【输出格式】
分两行输出一个最大整数和一个最小整数（去除前导零）。
【输入样例】
56214841966300510687
【输出样例】
98876666554432111000
11123445566667889
2. 安全区域（已修改）
（area.pas/c/cpp; 时限:1s; 64MB）
【问题描述】
Dark船长带领船员驾驶潜水艇在深海执行科考任务，不幸的是，潜水艇触礁进水。潜水艇内部有些重要区域有密封舱门，用*号表示，对于一个封闭的*号区域水是进不去的。Dark船长急需知道没进水的重要区域（用”0”表示）有多少？
【输入格式】
第一行：是两个整数，x和y（x,y≤500）
第二行开始是一个由*和0组成的x*y的图。
【输出格式】
输出没被水淹没的“0”的数量。
【输入样例1】
4 5
00000
00*00
0*0*0
00*00
【输出样例1】
1
【输入样例2】
5 5
*****
*0*0*
**0**
*0*0*
*****
【输出样例2】
5
3. 探险家
（explorer.pas/c/cpp; 时限:1s; 64MB）
【问题描述】
十个数学家乘气球飞行在太平洋上空。当横越赤道时，他们决定庆祝一下这一壮举。于是他们开了一瓶香槟。不幸的是，软木塞在气球上打了一个洞，氢气泄漏，气球开始下降，眼看就要落入海中，所有人将要被鲨鱼吃掉。
但是尚有一线生机--若其中一人牺牲自己跳下去的话，那他的朋友们还能多活一会儿。但仍然有一个问题存在--谁跳下去？所以他们想了一个非常公平的办法来解决这个问题--首先，每人写一个整数ai（1≤ai≤10000）；然后计算出a1×a2×a3×a4×……×a10的积的约数的个数N。例如，6的约数有4个（1、2、3、6），则N为4。这位牺牲自己的英雄将由N的个位数来决定（编号为N的个位数加1的人要跳下去）。你的任务是求出N。
【输入格式】
十个整数(用一个空格隔开)
【输出格式】
N的个位数
【输入样例】
1
2
6
1
3
1
1
1
1
1
【输出样例】
9
【注释】
1×2×6×1×3×1×1×1×1×1=36，约数有1,2,3,4,6,9,12,18,36，共9个。
4、逆序对
（negsort.pas/c/cpp; 时限:1s; 64MB）
【问题描述】
NEG公司是一家专门提供数据服务的公司，其中数据排序工作是他们非常重要的一项业务。他们的工作是通过一系列移动，将某些物品按顺序摆好。他们的服务是通过工作量来计算的，即移动东西的次数。所以，在工作前必须先调查数据处理的工作量，以便向用户提出合理的收费价格。
排序数据前，大部分用户都是凭感觉来认定这一列物品的混乱程度，实际上不需要知道精确的移动次数。而NEG公司往往是根据“逆序对”的数目多少来判断这一序列的混乱程度。假设我们将序列中第i件物品的参数定义为Ai，那么排序就是指将Ai，…，An从小到大排序。若i<j且Ai>Aj，则<i,j>就为一个“逆序对”。
例如，数组（3,1,4,5,2）的“逆序对”有<3,1>,<3,2>,<4,2>,<5,2>,共4个。
NEG公司请你写一个程序，在尽量短的时间内，统计出“逆序对”的数目。
【输入格式】
n，A1，…，An，1<n<1000000，Ai为小于1000000的正整数。
【输出格式】
数列A1，…，An的“逆序对”数目，即“逆序数”。
【输入样例】
5 3 1 4 5 2
【输出样例】
4maxmin
1 #include<cstdio>
2
3 #include<cstring>
4
5 #include<iostream>
6
7 char c[255];
8
9 int main(){
10
11 freopen("maxmin.in","r",stdin);
12
13 freopen("maxmin.out","w",stdout);
14
15 int l;
16
17 scanf("%s ",c);
18
19 l=strlen(c);
20
21 for(int i=0;i<=l-1;i++)
22
23 for(int j=i+1;j<=l-1;j++)
24
25 if(c[i]>c[j]){
26
27 c[i]^=c[j];
28
29 c[j]^=c[i];
30
31 c[i]^=c[j];
32
33 }
34
35 if(c[l-1]=='0')
36
37 {
38
39 printf("0\n0");
40
41 return 0;
42
43 }
44
45 for(int i=l-1;i>=0;i--)
46
47 printf("%c",c[i]);
48
49 printf("\n");
50
51 for(int i=0;i<=l-1;i++)
52
53 if(c[i]!='0')
54
55 printf("%c",c[i]);
56
57 return 0;
58
59 } area
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 char p[501][501];
5 int h[501][501];//1 flooded 2 rock 0;safe
6 int A[501*501],B[501*501],Head,Tail;
7 int x[4]={0,0,1,-1};
8 int y[4]={1,-1,0,0};
9 int count=0;
10 int main(){
11 freopen("area.in","r",stdin);
12 freopen("area.out","w",stdout);
13 int n,m;
14 memset(h,0,sizeof(h));
15 scanf("%d %d ",&n,&m);
16 for(int i=1;i<=n;i++)
17 for(int j=1;j<=m;j++){
18 scanf("%c ",&p[i][j]);
19 if(p[i][j]=='*')
20 h[i][j]=2;
21 }
22 for(int i=1;i<=m;i++){
23 if(!h[1][i]){
24 Head=Tail=1;
25 A[Head]=1;
26 B[Head]=i;
27 h[1][i]=1;
28 while(Head<=Tail){
29 for(int j=0;j<=3;j++)
30 if(!h[A[Head]+x[j]][B[Head]+y[j]])
31 if(A[Head]+x[j]>=1&&A[Head]+x[j]<=n)
32 if(B[Head]+y[j]>=1&&B[Head]+y[j]<=m){
33 Tail++;
34 A[Tail]=A[Head]+x[j];
35 B[Tail]=B[Head]+y[j];
36 h[A[Tail]][B[Tail]]=1;
37 }
38 Head++;
39 }
40 }
41 //
42 if(!h[n][i]){
43 Head=Tail=1;
44 A[Head]=n;
45 B[Head]=i;
46 h[n][i]=1;
47 while(Head<=Tail){
48 for(int j=0;j<=3;j++)
49 if(!h[A[Head]+x[j]][B[Head]+y[j]])
50 if(A[Head]+x[j]>=1&&A[Head]+x[j]<=n)
51 if(B[Head]+y[j]>=1&&B[Head]+y[j]<=m){
52 Tail++;
53 A[Tail]=A[Head]+x[j];
54 B[Tail]=B[Head]+y[j];
55 h[A[Tail]][B[Tail]]=1;
56 }
57 Head++;
58 }
59 }
60 }
61 for(int i=1;i<=n;i++){
62 if(!h[i][1]){
63 Head=Tail=1;
64 A[Head]=i;
65 B[Head]=1;
66 h[i][1]=1;
67 while(Head<=Tail){
68 for(int j=0;j<=3;j++)
69 if(!h[A[Head]+x[j]][B[Head]+y[j]])
70 if(A[Head]+x[j]>=1&&A[Head]+x[j]<=n)
71 if(B[Head]+y[j]>=1&&B[Head]+y[j]<=m){
72 Tail++;
73 A[Tail]=A[Head]+x[j];
74 B[Tail]=B[Head]+y[j];
75 h[A[Tail]][B[Tail]]=1;
76 }
77 Head++;
78 }
79 }
80 //
81 if(!h[i][m]){
82 Head=Tail=1;
83 A[Head]=i;
84 B[Head]=m;
85 h[i][m]=1;
86 while(Head<=Tail){
87 for(int j=0;j<=3;j++)
88 if(!h[A[Head]+x[j]][B[Head]+y[j]])
89 if(A[Head]+x[j]>=1&&A[Head]+x[j]<=n)
90 if(B[Head]+y[j]>=1&&B[Head]+y[j]<=m){
91 Tail++;
92 A[Tail]=A[Head]+x[j];
93 B[Tail]=B[Head]+y[j];
94 h[A[Tail]][B[Tail]]=1;
95 }
96 Head++;
97 }
98 }
99 }
100 for(int i=1;i<=n;i++)
101 for(int j=1;j<=m;j++)
102 if(!h[i][j])
103 count++;
104 printf("%d",count);
105 return 0;
106 }
107 explorer(25行的压缩版)
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 bool p[10001];
5 int pp[10001],ph[10001],pt=0,t,count=1;
6 int main(){
7 freopen("explorer.in","r",stdin);
8 freopen("explorer.out","w",stdout);
9 memset(p,true,sizeof(p));
10 memset(ph,0,sizeof(ph));
11 p[0]=p[1]=false;
12 for(int i=2;i<=10000;i++)if(p[i])
13 for(int j=2*i;j<=10000;j+=i)p[j]=false;
14 for(int i=1;i<=10000;i++)if(p[i])
15 {pt++;pp[pt]=i;}
16 for(int i=1;i<=10;i++)
17 {scanf("%d",&t);
18 for(int j=1;j<=pt&&t>1;j++)
19 while(t%pp[j]==0&&t>1)
20 {t/=pp[j];ph[j]++;}}
21 for(int i=1;i<=pt;i++)
22 {count*=(ph[i]+1);count%=10;}
23 printf("%d",count);
24 return 0;
25 }
26 negsort(AC,43行的基础代码)
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 long long C=0;
5 long a[1000001];
6 long c[1000001];
7 int m;
8 void sort(int low,int high);
9 int main(){
10 freopen("negsort.in","r",stdin);
11 freopen("negsort.out","w",stdout);
12 scanf("%d",&m);
13 for(int i=1;i<=m;i++)
14 scanf("%d",&a[i]);
15 sort(1,m);
16 printf("%I64d",C);
17 return 0;
18 }
19 void sort(int low,int high)
20 {
21 if(low==high)
22 return ;
23 int t=(low+high)>>1;
24 int l=low,r=t+1;
25 sort(low,t);
26 sort(t+1,high);
27 for(int i=low;i<=high;i++)
28 {
29 if(l<=t&&(a[l]<=a[r]||r>high))
30 {
31 c[i]=a[l];
32 l++;
33 }
34 else
35 {
36 c[i]=a[r];
37 r++;
38 C+=t-l+1;
39 }
40 }
41 for(int i=low;i<=high;i++)
42 a[i]=c[i];
43 }
44 (最新，在linux下测得最大点时间0.604s，完全AC)
negsort(50,树状数组)
1 #include<cstdio>
2
3 #include<cstring>
4
5 #include<iostream>
6
7 long long C=0;
8
9 int c[1000005];
10
11 long long a[1000005];
12
13 int m,t;
14
15 int maxm=0;
16
17 int inline lowbit(int x){return x&-x;}
18
19 void add(int i);
20
21 long long sum(int i);
22
23 int main(){
24
25 freopen("negsort.in","r",stdin);
26
27 freopen("negsort.out","w",stdout);
28
29 memset(a,0,sizeof(a));
30
31 scanf("%d",&m);
32
33 for(int i=1;i<=m;i++)
34
35 {
36
37 scanf("%d",&c[i]);
38
39 if(c[i]>maxm)
40
41 maxm=c[i];
42
43 }
44
45 maxm++;
46
47 for(int i=1;i<=m;i++)
48
49 {
50
51 C+=sum(maxm-c[i]+1);
52
53 add(maxm-c[i]+2);
54
55 }
56
57 printf("%I64d",C);
58
59 return 0;
60
61 }
62
63 void add(int i)
64
65 {
66
67 while(i<=maxm)
68
69 {
70
71 a[i]++;
72
73 i+=lowbit(i);
74
75 }
76
77 }
78
79 long long sum(int i)
80
81 {
82
83 long long count=0;
84
85 while(i>=1)
86
87 {
88
89 count+=a[i];
90
91 i-=lowbit(i);
92
93 }
94
95 return count;
96
97 } (最新，在linux下测得最大点时间1.093s，还说的过去。)
最终结论：由于有重复相等的问题，所以SBT和SPLAY不能很好的解决这个问题