我的计划就从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