本文正體字版由OpenCC轉換
我的計劃就從NOI1997開始。NOI1997一共有6道題，分別是[衛星覆蓋][積木遊戲][競賽排名][最佳遊覽][最優乘車][文件匹配]。這一年的6個題難易分佈均衡，做完後收穫不小。
其中[競賽排名]和[最佳遊覽]是兩個最簡單的題，但是往往細節是容易忽視的。[積木遊戲]和[最優乘車]難度屬於中等，分別是動態規劃和構造最短路徑解題。[衛星覆蓋]和[文件匹配]屬於較難題，用到了[衛星覆蓋]離散化或者立體切割的方法，而[文件匹配]是搜索中的難題，需要很多的優化。
做這些題我花了4天的時間，進度還算正常，希望能繼續保持下去。今後做題的宗旨是“不求多，不求快，但求精”。
[最佳遊覽]
這是一道非常簡單的題，讀懂題後，發現方法就是統計出每一列的最大值，存爲一個數列A。求A的連續最大子序列即可。
/*
* Problem: NOI1997 perfecttour
* Author: Guo Jiabao
* Time: 2009.2.14 14:01
* State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=20001;
int M,N,i,j,t,T,Ans;
int A[MAXN];
int main()
{
freopen("perfecttour.in","r",stdin);
freopen("perfecttour.out","w",stdout);
scanf("%d%d",&M,&N);
N--;
for (j=1;j<=N;j++)
A[j]=-0x7FFFFFFF;
for (i=1;i<=M;i++)
for (j=1;j<=N;j++)
{
scanf("%d",&t);
if (t>A[j])
A[j]=t;
}
for (i=1,T=0;i<=N;i++)
{
T+=A[i];
if (T<0)
T=0;
if (T>Ans)
Ans=T;
}
printf("%dn",Ans);
return 0;
}
[競賽排名]
這也是一道送分題，數據很小方法很明確，就是排序。關鍵在於看清式子，注意關係算出各個量後直接排序就行了。
/*
* Problem: NOI1997 competitionsort
* Author: Guo Jiabao
* Time: 2009.2.13 14:09
* State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=1001;
int sum[MAXN],S[MAXN][9];
double avg[9],pos[MAXN],y[MAXN][9];
struct inf{int id,sum;double pos;} P[MAXN];
int N;
void init()
{
freopen("competitionsort.in","r",stdin);
freopen("competitionsort.out","w",stdout);
scanf("%d",&N);
for (int i=1;i<=N;i++)
for (int j=1;j<=8;j++)
scanf("%d",&S[i][j]);
}
inline double ABS(double A)
{
return A<0?-A:A;
}
inline int cmp(const void *a,const void *b)
{
if (((inf *)a)->pos > ((inf *)b)->pos) return -1;
if (((inf *)a)->pos < ((inf *)b)->pos) return 1;
if (((inf *)a)->sum > ((inf *)b)->sum) return -1;
if (((inf *)a)->sum < ((inf *)b)->sum) return 1;
if (((inf *)a)->id < ((inf *)b)->id) return -1;
return 1;
}
void statistics()
{
int i,j;
double m[8];
for (j=1;j<=8;j++)
{
for (i=1;i<=N;i++)
{
avg[j]+=S[i][j];
sum[i]+=S[i][j];
}
avg[j]/=N;
}
for (j=1;j<=8;j++)
{
m[j]=0;
for (i=1;i<=N;i++)
m[j]+=ABS(S[i][j]-avg[j]);
m[j]/=N;
}
for (i=1;i<=N;i++)
{
for (j=1;j<=8;j++)
{
if (m[j]==0)
y[i][j]=0;
else
y[i][j]=(S[i][j]-avg[j])/m[j];
}
for (j=1;j<=3;j++)
pos[i]+=y[i][j];
for (j=4;j<=8;j++)
pos[i]+=y[i][j]*0.8;
P[i].pos=pos[i];
P[i].sum=sum[i];
P[i].id=i;
}
qsort(P+1,N,sizeof(P[0]),cmp);
for (i=1;i<=N;i++)
printf("%dn",P[i].id);
}
int main()
{
init();
statistics();
return 0;
}
[積木遊戲]
由於把積木分成M堆，每堆中積木的編號都是嚴格劃分的，可以看作把積木按編號順序劃分爲M份。可以動態規劃，狀態轉移時只需考慮第i個放置相鄰兩對的決策。
設定F[i,j,k]表示放置第i個積木時，把它放在第j堆，用第k種方式放置的總最大高度。
第k种放置方式(0<=k<=2)，分別表示了用積木的哪一面作爲底。
狀態轉移方程
-
F[i,j,k]=Max{ F[a,j,b]|(i,k)能放置在(a,b)上 ,F[a,j-1,b] (0<=a<=i-1,0<=b<=2) } + height(i,k)
-
height(i,k)爲第i個積木以方式k放置的高。
初始條件爲
- F[i,j,k]=負無窮大;(0<=i<=N,0<=j<=M,0<=k<=2)
- F[0,0,0]=0;
/*
* Problem: NOI1997 buildinggame
* Author: Guo Jiabao
* Time: 2009.2.12 13:53
* State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAX=101,INF=0x7FFFFFFF;
struct block{int a,b,c;}B[MAX];
int F[MAX][MAX][3];
int N,M,Ans;
void init()
{
int i,j,k;
freopen("buildinggame.in","r",stdin);
freopen("buildinggame.out","w",stdout);
scanf("%d%d",&N,&M);
for (i=1;i<=N;i++)
scanf("%d%d%d",&B[i].a,&B[i].b,&B[i].c);
for (i=0;i<=N;i++)
for (j=0;j<=M;j++)
for (k=0;k<3;k++)
F[i][j][k]=-INF;
F[0][0][0]=0;
}
inline block roll(block A,int k)
{
int t;
if (k==1){t=A.b;A.b=A.c;A.c=t;}
if (k==2){t=A.a;A.a=A.b;A.b=A.c;A.c=t;}
return A;
}
inline bool available(block A,int k1,block B,int k2)
{
A=roll(A,k1);B=roll(B,k2);
return (B.a>=A.a && B.b>=A.b) || (B.a>=A.b && B.b>=A.a);
}
void dynamic()
{
int i,j,k,a,b;
block T;
for (i=1;i<=N;i++)
for (j=1;j<=M;j++)
for (k=0;k<3;k++)
{
for (a=0;a<i;a++)
for (b=0;b<3;b++)
{
if (available(B[i],k,B[a],b) && F[a][j][b] > F[i][j][k])
F[i][j][k] = F[a][j][b];
if ( F[a][j-1][b] > F[i][j][k] )
F[i][j][k] = F[a][j-1][b];
}
if ((F[i][j][k] += (T=roll(B[i],k)).c) >Ans)
Ans=F[i][j][k];
}
}
int main()
{
init();
dynamic();
printf("%dn",Ans);
return 0;
}
[最優乘車]
可以構造最短路徑求解。對於不同線路上的相同編號的車站，應該看作不同的頂點，而且這兩個點之間互相連接一條邊權爲1的有向邊。同一條線路上的所有 車站，按照順序連接邊權爲0的有向邊。爲了方便，我們增設一個超級源S和超級匯T。S向所有代表車站1的頂點連接一條邊權爲0的有向邊，所有代表車站N的 頂點向T連接一條邊權爲0的有向邊。
圖構造好以後，只需求從S到T的最短路徑即可。建議用SPFA，在這種特殊的01圖上，SPFA會比Dijkstra(堆)快得多。
/*
* Problem: NOI1997 bustravel
* Author: Guo Jiabao
* Time: 2009.2.14 19:10
* State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXM=101,MAXN=501,INF=0x7FFFFFF;
struct edge{edge *next;int t,v;};
struct adjl{edge *f,*l;};
int M,N,Total,Target,EC=-1,Queue_cnt,Queue_head,Queue_tail;
int BusLine[MAXM][MAXN]; //第i行第j個點的原始編號
int BusHash[MAXM][MAXN]; //第i行原始編號爲j的點正式編號
int sp[MAXM*MAXN],Queue[MAXM*MAXN];
bool inQueue[MAXM*MAXN];
edge ES[MAXM*MAXN];
adjl Adjl[MAXM*MAXN];
void init()
{
int i,j,k,c;
freopen("bustravel.in","r",stdin);
freopen("bustravel.out","w",stdout);
scanf("%d%d",&M,&N);
for (i=1;i<=M;i++)
{
do c=getchar(); while(c==10 || c==13);
for (j=0;(c!=10 && c!=13 && c!=EOF);)
{
ungetc(c,stdin);
scanf("%d",&k);
BusLine[i][++j]=k;
BusHash[i][k]=++Total;
c=getchar();
}
BusLine[i][0]=j;
}
Target=++Total;
}
void addedge(int a,int b,int v)
{
edge *p=&ES[++EC];
if (Adjl[a].l)
Adjl[a].l=Adjl[a].l->next=p;
else
Adjl[a].f=Adjl[a].l=p;
p->next=0;p->t=b;p->v=v;
}
void makegraph()
{
int i,j,k,p,a,b;
for (i=1;i<=M;i++)
{
for (j=1;j<=BusLine[i][0]-1;j++)
{
a=BusHash[i][ BusLine[i][j] ];
b=BusHash[i][ BusLine[i][j+1] ];
addedge(a,b,0);
if (BusLine[i][j]==1)
addedge(0,a,0);
else if (BusLine[i][j]==N)
addedge(a,Target,0);
}
if (BusLine[i][j]==1)
addedge(0,b,0);
else if (BusLine[i][j]==N)
addedge(b,Target,0);
}
for (i=1;i<=M-1;i++)
{
for (j=1;j<=BusLine[i][0];j++)
{
p=BusLine[i][j];
a=BusHash[i][p];
for (k=i+1;k<=M;k++)
{
b=BusHash[k][p];
if (b)
{
addedge(a,b,1);
addedge(b,a,1);
}
}
}
}
}
void Queue_ins(int p)
{
if (++Queue_head==MAXM*MAXN) Queue_head=0;
Queue[Queue_head]=p;
inQueue[p]=true;
Queue_cnt++;
}
int Queue_pop()
{
int p=Queue[Queue_tail];
if (++Queue_tail==MAXM*MAXN) Queue_tail=0;
inQueue[p]=false;
Queue_cnt--;
return p;
}
void spfa()
{
int i,u,v;
for (i=1;i<=Total;i++)
sp[i]=INF;
Queue_head=-1;Queue_tail=0;
Queue_ins(0);
while (Queue_cnt)
{
u=Queue_pop();
for (edge *k=Adjl[u].f;k;k=k->next)
{
v=k->t;
if (sp[u] + k->v < sp[v])
{
sp[v]=sp[u] + k->v;
if (!inQueue[v])
Queue_ins(v);
}
}
}
}
int main()
{
init();
makegraph();
spfa();
if (sp[Target]==INF)
printf("NOn");
else
printf("%dn",sp[Target]);
return 0;
}
[衛星覆蓋]
經典的分治問題，方法爲立方體切割。和USACO中的Shaping Regions的做法相似，只不過是從二維推廣到了三維。
具體方法是，對於第i個立方體，判斷大於i的每個立方體是否與之有公共部分，如果有公共部分，把該長方體非公共部分切割成幾個規則的長方體，然後遞歸處理每一個長方體。直到沒有公共部分了，體積就是長寬高。
對於兩個矩形（每條邊都平行於座標軸），我們判斷它們相交，有一種簡單的方法。兩個矩形A和B，定義(A.x1,A.y1)爲A的左下角頂 點，(A.x2,A.y2)爲A的右上角頂點，同理B，只要滿足 A.x1 < B.x2 且 A.y1 < B.y2 且 B.x1 < A.x2 且 B.y1 < A.y2，則A、B一定相交。
相似地，對於兩個長方體A、B，只要滿足
A.x1 < B.x2 && A.y1 < B.y2 && A.z1 < B.z2 && B.x1 < A.x2 && B.y1 < A.y2 && B.z1 < A.z2
則A、B相交。
上述方法的時間複雜度是O(N^3)，是很寬鬆的。
/*
* Problem: NOI1997 satellitecover
* Author: Guo Jiabao
* Time: 2009.2.11 21:17
* State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=201;
struct cube{int x1,y1,z1,x2,y2,z2;};
int N;
cube Cubes[MAXN];
void init()
{
int i,a,b,c,r;
freopen("satellitecover.in","r",stdin);
freopen("satellitecover.out","w",stdout);
scanf("%d",&N);
for (i=1;i<=N;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&r);
Cubes[i].x1=a-r; Cubes[i].y1=b-r; Cubes[i].z1=c-r;
Cubes[i].x2=a+r; Cubes[i].y2=b+r; Cubes[i].z2=c+r;
}
}
inline bool cross(cube A,cube B)
{
return A.x1 < B.x2 && A.y1 < B.y2 && A.z1 < B.z2 && B.x1 < A.x2 && B.y1 < A.y2 && B.z1 < A.z2;
}
cube mcube(int x1,int y1,int z1,int x2,int y2,int z2)
{
cube A;
A.x1=x1;A.y1=y1;A.z1=z1;A.x2=x2;A.y2=y2;A.z2=z2;
return A;
}
int devide(cube A,int pos)
{
cube B;
int volume=0;
while (pos<=N && !cross(A,B=Cubes[pos])) pos++;
if (pos>N)
volume=(A.x2-A.x1)*(A.y2-A.y1)*(A.z2-A.z1);
else
{
if (A.x1 < B.x1)
{
volume+=devide(mcube(A.x1,A.y1,A.z1,B.x1,A.y2,A.z2),pos+1);
A.x1=B.x1;
}
if (A.x2 > B.x2)
{
volume+=devide(mcube(B.x2,A.y1,A.z1,A.x2,A.y2,A.z2),pos+1);
A.x2=B.x2;
}
if (A.y1 < B.y1)
{
volume+=devide(mcube(A.x1,A.y1,A.z1,A.x2,B.y1,A.z2),pos+1);
A.y1=B.y1;
}
if (A.y2 > B.y2)
{
volume+=devide(mcube(A.x1,B.y2,A.z1,A.x2,A.y2,A.z2),pos+1);
A.y2=B.y2;
}
if (A.z1 < B.z1)
volume+=devide(mcube(A.x1,A.y1,A.z1,A.x2,A.y2,B.z1),pos+1);
if (A.z2 > B.z2)
volume+=devide(mcube(A.x1,A.y1,B.z2,A.x2,A.y2,A.z2),pos+1);
}
return volume;
}
int main()
{
int i,totalvolume=0;
init();
for (i=N;i>-1;i--)
totalvolume+=devide(Cubes[i],i+1);
printf("%dn",totalvolume);
return 0;
}
[文件匹配]
這是NOI1997中最難的一道題，我在這道題上花費了一天時間才通過了。基本框架就是搜索，搜索出匹配串，對所有文件名按照規則匹配，判斷是否可行，算出匹配的數目，更新最優值。
暴力的搜索連樣例都過不了，我們需要深入分析，進行優化和剪枝。我的搜索順序是從匹配串的第一位到最後一位(所有文件名長度最大值)。我們定義正文件爲標記’+‘的文件，負文件爲標記’-‘的文件。
優化1.記錄下所有用過的字符，順序存入線性表，以備搜索時使用。
優化2.去除多餘的狀態，例如多個在一起是浪費的，?和?是一樣的(但是和不一樣)，在產生狀態時應避免出現。
優化3.關於判斷文件名是否匹配，在搜索出一位時，不需要把整個串與文件名匹配，如果前面都是匹配的，只需判斷最後一位是否 成立，我們需要記錄每個文件名已經前綴匹配到了哪一位。但是由於的存在，使這個判斷複雜性大大增加。例如當前的匹配串AA對A1A2A前綴匹 配，A*A可以匹配到第3位(A1A)，也可以匹配到第5位(A1A2A)。而且由於後面擴展出的狀態未知，我們也無法知道究竟匹配到哪一位是合適的，所 以必須都記錄下。即對每個文件名開闢一個數組空間，存儲該文件名可能匹配到的所有位置。在狀態的擴展中，也需要對所有的可能分別擴展。在最終判斷時，一個 文件名只要有一種可能使得完全匹配，就算是匹配成功。
優化4.在搜索完匹配串的每一位，計算完全匹配的數目時，需要判斷是否還有必要搜索下一位。對於以下三種情況，
- 如果所有的正文件全部不能嚴格匹配，則再搜索下一位已經沒有意義，剪枝；
- 如果前綴匹配的正文件的個數小於已有答案，再搜索下一位答案一定不會增加，剪枝；
- 如果匹配串末字符是*，當前答案小於最優答案，繼續搜索一定是不會使答案增加，剪枝。
上述5個優化，其中優化3是核心，也是算法的重要內容，大量編程的工作都是優化3；而優化4是關鍵，優化4的三個強力剪枝可以去除許多無用的狀態，大大減少運行時間。
這道題雖然寫了一天才搞定，收穫卻是非同一般得大。我個人認爲這類題很好，很能考驗構造思維能力和編程能力，甚至意志力，但近些年不論在 NOI還是NOIP，卻都銷聲匿跡了。我預測如果今年NOI考這類題，仍然是個難題，能拿到高分的人不會多的。搜索+優化永遠是一個萬能算法，即使不爲了 競賽，真正掌握它也是很困難，確是很重要的。
/*
* Problem: NOI1997 wildcard
* Author: Guo Jiabao
* Time: 2009.2.15 20:17
* State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=251,MAXS=62;
const char CharSet[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
struct File{int name[10],len,matchpre[10],precnt;bool permission;};
int N,N_p,pattern[10],Apt[10],Max_Length,Ans,Nowlen,Al,ccnt;
File F[MAXN];
bool used[200];
int chas[62];
void dfs(int len);
inline int CharToID(char c)
{
if (c>='0' && c<='9')return c-'0';
return (c>='A' && c<='Z')?c-'A'+10:c-'a'+36;
}
inline int cmp(const void *a,const void *b)
{return ((File *)a)->permission==false?-1:1;}
void init()
{
int i,k;
char c,Name[10];
freopen("wildcard.in","r",stdin);
freopen("wildcard.out","w",stdout);
c=getchar();
while (c!=EOF)
{
ungetc(c,stdin);
scanf("%s",Name);
N++;
for (i=0;Name[i];i++)
{
F[N].name[i+1]=k=CharToID(Name[i]);
used[k]=true;
}
F[N].len=i;
if (i>Max_Length)
Max_Length=i;
c=getchar();c=getchar();
if (c=='+')
{
N_p++;
F[N].permission=true;
}
else
F[N].permission=false;
F[N].precnt=1;
c=getchar();c=getchar();
}
qsort(F+1,N,sizeof(F[0]),cmp);
for (i=0;i<MAXS;i++)
if (used[i])
chas[++ccnt]=i;
}
bool update(int k)
{
int i,j,Newans=0,Pans=0;
bool np=false,tb;
for (i=1;i<=N;i++)
{
tb=false;
for (j=1;j<=F[i].precnt;j++)
tb|=F[i].matchpre[j]==F[i].len || ( F[i].matchpre[j]>=0 && pattern[k]==-1 );
if (tb)
{
if (F[i].permission )
Newans++;
else
np=true; //匹配了負串
}
if (F[i].permission && F[i].precnt==0)
Pans++; //記錄正串不匹配的個數
}
if (Pans==N_p || (N_p-Pans<Ans)) //若正串全部不匹配 或者 前綴匹配串的個數小於已有答案 剪枝
return false;
if (pattern[k]==-1 && Newans<Ans) //如果匹配串末字符是*，當前答案小於最優，繼續添加一定是多餘的 剪枝
return false;
if (!np)
{
if (Newans>Ans)
{
Ans=Newans;
for(i=1;i<=k;i++)
Apt[i]=pattern[i];
Al=k;
}
else if (Newans==Ans && k<Al)
{
for(i=1;i<=k;i++)
Apt[i]=pattern[i];
Al=k;
}
}
return true;
}
void match(File &F,int len)
{
bool newpre[10]={false};
int k,i;
if (pattern[len-1]!=-1)
{
for (k=1;k<=F.precnt;k++)
if (F.matchpre[k]+1<=F.len && (pattern[len]==-2 || F.name[F.matchpre[k]+1]==pattern[len]))
newpre[F.matchpre[k]+1]=true;
}
else
{
for (k=1;k<=F.precnt;k++)
for (i=F.matchpre[k]+1;i<=F.len;i++)
if (F.name[i]==pattern[len] || pattern[len]==-2)
newpre[i]=true;
}
F.precnt=0;
for (k=1;k<9;k++)
if (newpre[k])
F.matchpre[ ++F.precnt ]=k;
}
void goon(int len,int p)
{
if (p==N+1)
{
if (update(len))
dfs(len+1);
return;
}
int i,tprecnt,tmatch[10];
if (F[p].precnt==0)
goon(len,p+1);
else
{
/*backup*/
for (i=1;i<=F[p].precnt;i++)
tmatch[i]=F[p].matchpre[i];
tprecnt=F[p].precnt;
/*backup*/
if (pattern[len-1]==-1)
{
match(F[p],len);
goon(len,p+1);
}
else
{
if (pattern[len]!=-1)
match(F[p],len);
goon(len,p+1);
}
/*restore*/
F[p].precnt=tprecnt;
for (i=1;i<=F[p].precnt;i++)
F[p].matchpre[i]=tmatch[i];
/*restore*/
}
}
void dfs(int len) //-1:* -2:?
{
if (len>Max_Length)
return;
int i;
if (pattern[len-1]!=-1)//**不連用 但允許?*
{
pattern[len]=-1;
goon(len,1);
}
if (pattern[len-1]!=-1)//不允許*?
{
pattern[len]=-2;
goon(len,1);
}
for (i=1;i<=ccnt;i++)
{
pattern[len]=chas[i];
goon(len,1);
}
}
void print()
{
printf("%dn",Ans);
for (int i=1;i<=Al;i++)
if (Apt[i]>=0)
putchar(CharSet[Apt[i]]);
else if (Apt[i]==-1)
putchar('*');
else
putchar('?');
putchar('n');
}
int main()
{
init();
dfs(1);
print();
return 0;
}
順便還說下，這道題SpecialJudge很有意思，由於可能沒有唯一解，需要自己編寫一個評測插件來判斷解的正確性。在給 CmYkRgB123 Online Judge System編寫評測插件時，我想到了用正則表達式的方法來判斷，因爲php中就有preg_match函數，但是這道題中的匹配串並不是真正的正則表達 式。可算讓我想了一大會，纔想到轉化的方法。例如題中E*，轉化爲正則表達式就是/^E[a-zA-Z0-9]{0,8}$/，^表示必須從開頭匹 配，$表示匹配到結尾[a-zA-Z0-9]{0,8}代表*，*只能匹配字母和數字，而且長度在[0,8]之間，很顯然?就是[a-zA-Z0-9] {1}了。於是我寫出了轉化函數
function getz($Ab)
{
$str='/^';
$Ab=str_replace('*','[a-zA-Z0-9]{0,8}',$Ab);
$Ab=str_replace('?','[a-zA-Z0-9]{1}',$Ab);
$str.=$Ab.'$/';
return $str;
}
判斷函數就是
function plugin_compare($fin,$fout,$fans)
{
$score=0;
fscanf($fout,"%s",$As);
fscanf($fout,"%s",$Ab);
fscanf($fans,"%s",$Bs);
fscanf($fans,"%s",$Bb);
if ($As==$Bs)
{
$score=0.5;
if (strlen($Ab)==strlen($Bb))
{
$zab=getz($Ab);
$score=0.6;
$pcnt=0;$wrong=false;
while (!feof($fin))
{
fscanf($fin,"%s %sn",$subject,$method);
$r=preg_match($zab,$subject);
if ($r && $method=='+')
$pcnt++;
if ($r && $method=='-')
$wrong=true;
}
if ($As==$pcnt && !$wrong)
$score=1;
}
}
return $score;
}
附上原題
最佳遊覽
有一座旅遊城，它的街道成網格狀．其中東西向的街道是“風景線、兩旁分佈着許多景觀：南北向的街道都是林蔭道，兩旁沒有任何建築物。由於遊客衆多，風最線被規定爲單行道，遊客在風景線上只能從西走到東，林蔭道上則可以任意行走。
一名遊客將到這座旅遊城旅遊。他根據自己對景觀的喜好給所有的風景線打了分，分值是從-100到+100的整數，分值越大表示我們的旅遊者越喜歡這條風最線上的景緻。顯然這位遊客不可能給這座旅遊城的所有風景線都打負分。
<pre>-50 –47 –36 –30 –23
17 –19 34 –13 –8
-42 –3 43 34 -45</pre>
遊客可以從旅遊城的任一個十字路口開始遊覽，在任一個十字路口結束遊覽。我們的旅遊者希望一路上游覽的所有風最線的分值之和能夠儘可能地大。請你寫一個程序，幫助這位遊客尋找一條最佳的遊覽路線。
輸入輸出
輸入文件是INPUT.TXT。文件的第一行是兩個整數M和N，之間用一個空格符隔開，M表示旅遊城南北向林蔭道的段數，N表示東西向風景 線的段數，1<=M<=100，1<=N<=20000。接下來的M行依次給出了由北向南各條風景線的分值信息。每行有N個整 數，依次表示了自西向東每段風景線的分值。同一行相鄰兩個數之間用一個空格隔開。
輸出文件是OUTPUT.TXT。文件只有一行，含一個整數，表示你的程序所找到的最佳遊覽路線的總分值。
樣例
INPUT.TXT
<pre>3 6
50 -47 -36 -30 -23
17 -19 34 -13 -8
-42 -3 43 34 -45</pre>
OUTPUT.TXT
<pre>124</pre>
<h2><span class="mw-headline">競賽排名 </span></h2>
某市組織了一次中學生科技全能競賽，每個選手要參加數學、物理、化學、天文、地理、生物、計算機和英語共八項競賽,最後綜合八項競賽的成績排出總名次。選手編號依次爲：1,2...N（N爲參賽總人數）。
設<a class="image" title="Image:Competitionsort 1.gif" href="http://www.ruvtex.cn/wiki/Image:Competitionsort_1.gif"><img src="http://www.ruvtex.cn/mw/images/8/82/Competitionsort_1.gif" alt="Image:Competitionsort 1.gif" width="19" height="25" /></a>分別表示編號爲i的選手第j項競賽的成績<a class="image" title="Image:Competitionsort 2.gif" href="http://www.ruvtex.cn/wiki/Image:Competitionsort_2.gif"><img src="http://www.ruvtex.cn/mw/images/f/fd/Competitionsort_2.gif" alt="Image:Competitionsort 2.gif" width="137" height="21" /></a>。其它指標如下：
-
第j項競賽的平均分
-
選手i的總分
-
選手i第j項競賽的位置分
-
選手i的總位置分
排名規則如下:
- 總位置分高的選手名次在前：
- 若兩個或兩個以上的選手總位置分相同，則總分高的選手名次在前：
- 若兩個或兩個以上的選手總位置分和總分均相同，則編號在前的選手名次在前。
輸入輸出
輸入文件爲INPUT.TXT。文件的第一行爲參賽總人數N
，從第二行到第N行依次爲編號爲1到編號爲N的選手的成績，每行有8個0～100之間的整數，代表該選手的8項競賽成績
。同一行相鄰兩個數之間用一個空格符隔開。輸出文件爲OUTPUT.TXT. 文件有N行，從第1行到第N行依次爲排名第1的選手的編號，排名第2的選手的編號，…，排名第N的選手的編號。
樣例
INPUT.TXT
3 72 82 73 68 95 86 82 90 72 90 50 60 80 70 65 80 72 82 73 68 95 86 82 90
OUTPUT.TXT
1 3 2
積木遊戲
SERCOI 最近設計了一種積木遊戲。每個遊戲者有N塊編號依次爲1 ，2，…，N的長方體積木。對於每塊積木,它的三條不同的邊分別稱爲”a邊”、“b邊”和”c邊”，如下圖所示：
遊戲規則如下：
1.從N塊積木中選出若干塊，並將它們分成M（l<=M<=N） 堆，稱爲第1堆，第2 堆…，第M堆。每堆至少有1塊積木，並且第K堆中任意一塊積木的編號要大於第K+1堆中任意一塊積木的編號(2<=K<=M)。
2.對於每一堆積木,遊戲者要將它們垂直摞成一根柱子,並要求滿足下面兩個條件：
(1)除最頂上的一塊積木外，任意一塊積木的上表面同且僅同另一塊積木的下表面接觸，並且要求下面的積木的上表面能包含上面的積木的下表面，也就是說，要求下面的積木的上表面的兩對邊的長度分別大於等於上面的積木的兩對邊的長度。
(2)對於任意兩塊上下表面相接觸的積木，下面的積木的編號要小於上面的積木的編號。
最後，根據每人所摞成的M根柱子的高度之和來決出勝負。
請你編一程序，尋找一種摞積木的方案，使得你所摞成的M根柱子的高度之和最大。
輸入輸出
輸入文件是INPUT.TXT。文件的第一行有兩個正整數N和M（1<=M<=N<=100），分別表示積木總數和要求 摞成的柱子數。這兩個數之間用一個空格符隔開。接下來N行依次是編號從1到N的N個積木的尺寸，每行有三個1至1000之間的整數，分別表示該積木a 邊,b邊和c邊的長度。同一行相鄰兩個數之間用一個空格符隔開。
輸出文件是OUTPUT.TXT。文件只有一行，爲一個整數，表示M根柱子的高度之和。
樣例
INPUT.TXT
4 2 10 5 5 8 7 7 2 2 2 6 6 6
OUTPUT.TXT
24
最優乘車
H城是一個旅遊勝地，每年都有成千上萬的人前來觀光。爲方便遊客，巴士公司在各個旅遊景點及賓館，飯店等地都設置了巴士站並開通了一些單程巴上線路。每條單程巴士線路從某個巴士站出發，依次途經若干個巴士站，最終到達終點巴士站。
一名旅客最近到H城旅遊，他很想去S公園遊玩，但如果從他所在的飯店沒有一路巴士可以直接到達S公園，則他可能要先乘某一路巴士坐幾站，再下來換乘同一站臺的另一路巴士, 這樣換乘幾次後到達S公園。
現在用整數1,2,…N 給H城的所有的巴士站編號，約定這名旅客所在飯店的巴士站編號爲1,S公園巴士站的編號爲N。
寫一個程序，幫助這名旅客尋找一個最優乘車方案,使他在從飯店乘車到S公園的過程 中換車的次數最少。
輸入輸出
輸入文件是INPUT.TXT。文件的第一行有兩個數字M和N(1<=M<=100 1<N<=500），表示開通了M條單程巴士線路，總共有N個車站。從第二行到第M+1行依次給出了第1條到第M條巴士線路的信息。其中第 i+1行給出的是第i條巴士線路的信息，從左至右按運行順序依次給出了該線路上的所有站號相鄰兩個站號之間用一個空格隔開。
輸出文件是OUTPUT.TXT，文件只有一行。如果無法乘巴士從飯店到達S公園，則輸出"N0"，否則輸出你的程序所找到的最少換車次數，換車次數爲0表示不需換車即可到達
樣例
INPUT.TXT
3 7 6 7 4 7 3 6 2 1 3 5
OUTPUT.TXT
2
衛星覆蓋
Cover
SERCOI（Space-Earth Resource Cover-Observe lnstitute）是一個致力於利用衛星技術對空間和地球資源進行覆蓋觀測的組織。現在他們研製成功一種新型資源觀測衛星-SERCOI-308。這種 衛星可以覆蓋空間直角座標系中一定大小的立方體空間，衛星處於該立方體的中心。
其中（x,y,z）爲立方體的中心點座標，r爲此中心點到立方體各個面的距離（即r爲立方體高的一半）．立方體的各條邊均平行於相應的座標軸。我們可以用一個四元組(x,y,z,r)描述一顆衛星的狀態，它所能覆蓋的空間體積 。 由於一顆衛星所能覆蓋的空間體積是有限的，因此空間中可能有若干顆衛星協同工作。它們所覆蓋的空間區域可能有重疊的地方，如下圖所示（陰影部分表示重疊的區域）。
寫一個程序，根據給定的衛星分佈情況，計算它們所覆蓋的總體積。
輸入輸出
輸入文件是INPU.TXT。文件的第一行是一個正整數N（1<=N<=100）：表示空間中的衛星總數。接下來的N行每行給 出了一顆衛星的狀態，用空格隔開的四個正整數x,y,z,r依次表示了該衛星所能覆蓋的立方體空間的中心點座標和半高，其中 -1000<=x,y,z<=1000, 1<=r<=200。
輸出文件是OUTPUT.TXT。文件只有一行,包括一個正整數，表示所有這些衛星所覆蓋的空間總體積。
樣例
INPUT.TXT
3 0 0 0 3 1 -1 0 1 19 3 5 6
OUTPUT.TXT
1944
文件匹配
在計算機的日常操作中，經常需要對當前回錄下的所有文件中的一部分文件進行操作。例如，將當前目錄下的所有文本文件複製至另一個目錄下：將當前目錄下所有以a 打頭的文件刪除; 等等。
很多操作系統都採用正則表達式來實現文件匹配功能。一種簡單的正則表達式由英文字母（區分大小寫）。數字及通配符””和”?”組成，”?”代表任意一個字符，”””則可以代表零個或任意多個字符。
例如：
-
a*b可以匹配acb(*代表c)
-
- 可以匹配aabb (*代表ab）
-
可以匹配asdsfdfdb (*代表sdsfdfd)
-
可以匹配ab (*不代表任何字符)
-
a*b不可以匹配ac（缺少最右邊的字母b)
-
- 不可以匹配bb（缺少最左邊的字母a )
-
不可以匹配 abbc（最右邊的字母不是b)
-
a?b可以匹配acb（？代表c)
-
- 不可以匹配ab（缺少中間的一個字符）
-
不可以匹配accb（？只能代表一個字符）
現要對某目錄下的部分文件進行操作。寫一個程序,尋找一個正則表達式，使其能匹配的待操作文件最多，但不能匹配任何不進行操作的文件。注意你所找到的最優正則表達式的長度應當是最短的。如果有多個長度最短的最優正則表達式，則其中任意一個都是允許的。
輸入輸出
輸入文件是INPUT.TXT.文件由N（1<=N<=250）行組成。每行給出了一個文件名（由英文字母和數字組成：英文字 符要區分大小寫，文件名長度不超過8個字符），其後是一個空格符和一個字符（“+”或"-"）.“+”表示要對該行給出的文件進行操作，"-”表示不進行 操作。
輸出文件是OUTPUT.TXT ，文件由兩行組成。第一行是一個整數，給出了你的程序所找到的最優正則表達式所能匹配的文件數目．在第二行給出你的程序所找到的最優正則表達式。
樣例
INPUT.TXT
EXCHANGE + EXT + HARDWARE + MOUSE - NETWORK -
OUTPUT.TXT
2 E*
上次修改時間 2017-05-22