第一次評(píng)測后 是第二，而且分?jǐn)?shù) 奇低，不想說了。感覺和昨天的數(shù)學(xué)一樣悲劇了～
然后發(fā)現(xiàn)各種問題，第二題全場爆零，第四題數(shù)據(jù)是原設(shè)計(jì)的10倍，標(biāo)程只能過一個(gè)點(diǎn)。。。
糾正了這些后復(fù)測：300+，勉強(qiáng)比汪同學(xué)高一點(diǎn)。
話說麻同學(xué)來上課了，于是吵了很多，但大家發(fā)揮都不錯(cuò)，
汪同學(xué)300+，吳天舒279，陸瑾聰200。。后面的普遍100左右。
我們發(fā)現(xiàn)是學(xué)c的人多了。。。。。然后又慫恿了兩個(gè)人轉(zhuǎn)c。。。。
說說題目，
第一題:忽略了全是0的情況。。。。90
第二題:flood-fill，（題目描述的就是flood。。。）AC
第三題:數(shù)學(xué)題，因式基本定理及其推論。。AC
第四題：求逆序?qū)?shù)，經(jīng)典分治就不說了，于是想標(biāo)新立異。
一上來想到平衡樹，SBT不會(huì)寫，SPLAY又覺得太長了。于是想線段樹，好像用不起來。
最后剩下時(shí)間不多了，忽然蒙出了樹狀數(shù)組，于是狂寫。
本來題目設(shè)計(jì)的是兩種方法都能過的，由于復(fù)測時(shí)，數(shù)據(jù)沒改（原設(shè)計(jì)的10倍），所以只能拿一半分。。。。
后來發(fā)現(xiàn)經(jīng)典分治1.08s ，樹狀數(shù)組2.73s（最大點(diǎn)），其實(shí)也不是很大的差距。
試題
1、最大數(shù)和最小數(shù)
（maxmin.pas/c/cpp; 時(shí)限:1s; 64MB）
【問題描述】
輸入一個(gè)數(shù)（不超過200位），將其重新排列后組成一個(gè)最大數(shù)和一個(gè)最小數(shù)。
【輸入格式】
第1行：一個(gè)整數(shù)N，不超過200位。
【輸出格式】
分兩行輸出一個(gè)最大整數(shù)和一個(gè)最小整數(shù)（去除前導(dǎo)零）。
【輸入樣例】
56214841966300510687
【輸出樣例】
98876666554432111000
11123445566667889
2. 安全區(qū)域（已修改）
（area.pas/c/cpp; 時(shí)限:1s; 64MB）
【問題描述】
Dark船長帶領(lǐng)船員駕駛潛水艇在深海執(zhí)行科考任務(wù)，不幸的是，潛水艇觸礁進(jìn)水。潛水艇內(nèi)部有些重要區(qū)域有密封艙門，用*號(hào)表示，對(duì)于一個(gè)封閉的*號(hào)區(qū)域水是進(jìn)不去的。Dark船長急需知道沒進(jìn)水的重要區(qū)域（用”0”表示）有多少？
【輸入格式】
第一行：是兩個(gè)整數(shù)，x和y（x,y≤500）
第二行開始是一個(gè)由*和0組成的x*y的圖。
【輸出格式】
輸出沒被水淹沒的“0”的數(shù)量。
【輸入樣例1】
4 5
00000
00*00
0*0*0
00*00
【輸出樣例1】
1
【輸入樣例2】
5 5
*****
*0*0*
**0**
*0*0*
*****
【輸出樣例2】
5
3. 探險(xiǎn)家
（explorer.pas/c/cpp; 時(shí)限:1s; 64MB）
【問題描述】
十個(gè)數(shù)學(xué)家乘氣球飛行在太平洋上空。當(dāng)橫越赤道時(shí)，他們決定慶祝一下這一壯舉。于是他們開了一瓶香檳。不幸的是，軟木塞在氣球上打了一個(gè)洞，氫氣泄漏，氣球開始下降，眼看就要落入海中，所有人將要被鯊魚吃掉。
但是尚有一線生機(jī)--若其中一人犧牲自己跳下去的話，那他的朋友們還能多活一會(huì)兒。但仍然有一個(gè)問題存在--誰跳下去？所以他們想了一個(gè)非常公平的辦法來解決這個(gè)問題--首先，每人寫一個(gè)整數(shù)ai（1≤ai≤10000）；然后計(jì)算出a1×a2×a3×a4×……×a10的積的約數(shù)的個(gè)數(shù)N。例如，6的約數(shù)有4個(gè)（1、2、3、6），則N為4。這位犧牲自己的英雄將由N的個(gè)位數(shù)來決定（編號(hào)為N的個(gè)位數(shù)加1的人要跳下去）。你的任務(wù)是求出N。
【輸入格式】
十個(gè)整數(shù)(用一個(gè)空格隔開)
【輸出格式】
N的個(gè)位數(shù)
【輸入樣例】
1
2
6
1
3
1
1
1
1
1
【輸出樣例】
9
【注釋】
1×2×6×1×3×1×1×1×1×1=36，約數(shù)有1,2,3,4,6,9,12,18,36，共9個(gè)。
4、逆序?qū)?br />（negsort.pas/c/cpp; 時(shí)限:1s; 64MB）
【問題描述】
NEG公司是一家專門提供數(shù)據(jù)服務(wù)的公司，其中數(shù)據(jù)排序工作是他們非常重要的一項(xiàng)業(yè)務(wù)。他們的工作是通過一系列移動(dòng)，將某些物品按順序擺好。他們的服務(wù)是通過工作量來計(jì)算的，即移動(dòng)?xùn)|西的次數(shù)。所以，在工作前必須先調(diào)查數(shù)據(jù)處理的工作量，以便向用戶提出合理的收費(fèi)價(jià)格。
排序數(shù)據(jù)前，大部分用戶都是憑感覺來認(rèn)定這一列物品的混亂程度，實(shí)際上不需要知道精確的移動(dòng)次數(shù)。而NEG公司往往是根據(jù)“逆序?qū)?#8221;的數(shù)目多少來判斷這一序列的混亂程度。假設(shè)我們將序列中第i件物品的參數(shù)定義為Ai，那么排序就是指將Ai，…，An從小到大排序。若i<j且Ai>Aj，則<i,j>就為一個(gè)“逆序?qū)?#8221;。
例如，數(shù)組（3,1,4,5,2）的“逆序?qū)?#8221;有<3,1>,<3,2>,<4,2>,<5,2>,共4個(gè)。
NEG公司請(qǐng)你寫一個(gè)程序，在盡量短的時(shí)間內(nèi)，統(tǒng)計(jì)出“逆序?qū)?#8221;的數(shù)目。
【輸入格式】
n，A1，…，An，1<n<1000000，Ai為小于1000000的正整數(shù)。
【輸出格式】
數(shù)列A1，…，An的“逆序?qū)?#8221;數(shù)目，即“逆序數(shù)”。
【輸入樣例】
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行的基礎(chǔ)代碼)
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下測得最大點(diǎn)時(shí)間0.604s，完全AC)
negsort(50,樹狀數(shù)組)
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下測得最大點(diǎn)時(shí)間1.093s，還說的過去。)
最終結(jié)論：由于有重復(fù)相等的問題，所以SBT和SPLAY不能很好的解決這個(gè)問題