A1.

/* * 算法阐述: * 对与警卫A，有两种途径找到同伴：或者直接找到能与自己组对的单独警卫B组对；或者拆散一组警卫（C，D）与其中C组对，然后对余下警卫D重复上述步骤，直到某一步时直接找到能组对的单独警卫，这种情况认为是A组对成功，并按上述途径进行组对；否则A不能找到同伴，。 * 按上方法依次遍历所有警卫，若i能组对成功则按找到的途径组对，最后得到的结果为最优。（详细证明未给出） * 在一次搜索过程某步骤中，若警卫i通过拆开某对警卫(m,n)，并与其中m组对为(i,m)后，最终无法组对成功，则m是稳定的，在这次搜索的以后步骤中单个警卫i不能再与m组对。如此可以大大加快搜索速度。 * 程序复杂度不超过O(n^2)。 */ #define cin infile #define MAX_N 223 #include<iostream> #include<fstream> using namespace std; struct PartnerList{ int p[MAX_N]; int pnum; PartnerList(){for(pnum=MAX_N;pnum>0;)p[--pnum]=0;}//初始化,pnum与p[]都置零 void Add(int i){p[pnum++]=i;}//列表中添加能够组对的同伴编号 bool getPartner(int i,int& x){//x为列表中第i个同伴编号,若超出范围则返回false if(i>=pnum)return false; x=p[i]; return true; } }; bool unChangAble[MAX_N];//unChangAble[i]为true表示i不能再参加组对，初始值都为false，无须再初始化 int n,partner[MAX_N];//partner[i]为i的已组对同伴，初始值都为0，无须再初始化 PartnerList plist[MAX_N]; bool FindPartner(int No){//给警卫No找到同伴 int i,t; unChangAble[No]=true;//把No设为不能再参加配对 for(i=0;plist[No].getPartner(i,t);i++){//得到能与No参加组对的t if(!unChangAble[t]){//t未访问过 unChangAble[t]=true;//t也标识为不能再参加配对 if(partner[t]==0||FindPartner(partner[t])){//如果t尚未组对或者t的同伴能再找到另一个同伴组队 partner[t]=No;//t与No组对 partner[No]=t; return true; } } } unChangAble[No]=false;//把No恢复为能再参加配对 return false;//没有组对成功 } int main(){ ifstream infile("schedule.in"); int i,j,count; cin>>n; while(cin>>i>>j){ plist[i].Add(j);//添加同伴列表 plist[j].Add(i); } count=0; for(i=1;i<=n;i++){ if(partner[i]==0&&FindPartner(i)){ count++;//i组对成功，计数 for(j=1;j<=n;j++)unChangAble[j]=false;//所有警卫能够参加重分配 } } cout<<count*2<<endl; for(i=1;i<=n;i++){ if(partner[i]>i)cout<<i<<' '<<partner[i]<<endl;//partner比自己大时输出，避免重复输出(未能组对的partner为0，不输出) } return 1; }

A2.

/* * 算法阐述： * 类似Dijkstra法求最短路径的算法，从钱数最多的格子开始，由钱多到钱少计算从各格出发总共能拿到的钱数。 * 设任一格p存放的钱数为M(p)，从p开始最多能拿到的钱数为T(p)，由于从p开始能拿到最多的钱的路径就是跳至下一个能拿到最多的钱的格子q(根据题意M(q)必须大于M(p)，且q在从p能跳到的范围内)。因此从存放钱最多的格子开始，由钱多到钱少遍历所有格子m，若发现n能够跳至m且当前从n开始能够拿到的钱T(n)比从n经过m拿到的钱M(m)+T(m)少，则T(n)更新为M(m)+T(m)(所有满足条件的n都要更新)。遍历直至结束。 * 由于只需得到从(0,0)出发最多可拿到的钱，则只需搜索钱数在100到money[0][0]范围内的格子。搜索结束后total[0][0]即从(0,0)出发最多可拿到的钱。 * 算法复杂度为O(k*(n^2))。（n为格子矩阵大小，k为可跳的长度范围） */ #define cin infile #define MAX_YUAN 100//格子中最多放的钱 #define MAX_SIZE 100//格子矩阵大小 #include<iostream> #include<fstream> using namespace std; struct Snode{ int Position;//存放格子坐标，x*MAX_SIZE+y Snode* Next; }; int money[MAX_SIZE][MAX_SIZE],total[MAX_SIZE][MAX_SIZE];//money为该格子内的钱数，total为从该格子出发能拿到的最大钱数 int main(){ ifstream infile("hopscotch.in"); int i,j,m,n,k,x,y; Snode *start[MAX_YUAN+1],*current,*p,*q;//start[i]即存放钱数为i的格子坐标的链表 for(cin>>m;m>0;m--){ for(i=0;i<=MAX_YUAN;i++){start[i]=NULL;} cin>>n>>k;//n为格子数，k为可走步数 for(i=0;i<n;i++){ for(j=0;j<n;j++){ cin>>x; money[i][j]=total[i][j]=x; current=new Snode; current->Position=i*MAX_SIZE+j; current->Next=start[x]; start[x]=current; } } for(i=MAX_YUAN;i>money[0][0];i--){//由钱多到钱少访问格子 for(p=start[i];p!=NULL;p=p->Next){ x=p->Position/MAX_SIZE; y=p->Position%MAX_SIZE;//取出格子坐标，x为横坐标，y为纵坐标 for(j=y-k>0?y-k:0;j<n&&j<=y+k;j++){//在坐标的纵向+-k范围内查找 if(money[x][j]<i&&total[x][y]+money[x][j]>total[x][j]){//若目标格中钱数比当前格少，且目标格经过当前格拿到的钱比原来目标格能拿到的更多 total[x][j]=total[x][y]+money[x][j];//更新目标格所能拿到的钱数 } } for(j=x-k>0?x-k:0;j<n&&j<=x+k;j++){//横向查找，同上 if(money[j][y]<i&&total[x][y]+money[j][y]>total[j][y]){ total[j][y]=total[x][y]+money[j][y]; } } } } cout<<total[0][0]<<endl;//(0,0)出发能得到最多的钱数 if(m>1)cout<<endl; for(i=0;i<=MAX_YUAN;i++){//各链表清零 for(p=start[i];p!=NULL;){ q=p; p=p->Next; delete q; } } } return 1; }

A4.

/* * 算法阐述： * 即是求入栈次数为m，出栈次数为n的不同入栈出栈序列总数。 * 入栈次数为m，出栈次数为n(m>=n)的组合总数为C(m,m+n)-C(m+1,m+n)（具体过程未给出），再分别乘上m，n的全排列m!，n!则化简后可得所有排列总数(m+n)!*(m-n+1)/(m+1)。 * 若把大整数运算看作常数时间，则算法复杂度为O(m+n)。 */ #define cin infile #define MAX_LENGTH 100 #include<iostream> #include<fstream> using namespace std; struct BigInt{//不完整的大整数类，仅提供必要的函数方法 const BigInt& operator*=(int x){ int i,extra=0; for(i=0;i<MAX_LENGTH;i++){ n[i]=n[i]*x+extra;//x不大于200，因此n[i]*x不会溢出 extra=n[i]/10000; n[i]%=10000; } return *this; } const BigInt& operator/=(int x){ int i,rest=0; for(i=MAX_LENGTH-1;i>=0;i--){ n[i]+=rest*10000; rest=n[i]%x; n[i]/=x; } return *this; } const BigInt& operator=(int x){ for(int i=0;i<MAX_LENGTH;i++){ n[i]=x%10000; x/=10000; } return *this; } ostream& Out(ostream& out)const{ int i,j; for(i=MAX_LENGTH-1;n[i]==0&&i>0;i--);//从大到小找到n[]的第一个非零项 out<<n[i--]; for(;i>=0;i--){ for(j=1000;j>n[i]&&j>=10;j/=10)out<<0;//不到4位则在前补零 out<<n[i]; } return out; } int n[MAX_LENGTH]; }; ostream& operator<<(ostream& out,const BigInt& t){ t.Out(out); return out; } int main(){ ifstream infile("ticket.in"); int m,n,i,test=0; BigInt num; while(true){ test++; cin>>m>>n; if(m==0&&n==0)break; if(m<n)cout<<"Test #"<<test<<":\n0\n";//m<n时不存在排列方法 else { for(num=i=1;i<=n+m;i++){num*=i;} num*=m-n+1; num/=m+1;//总排列数为(m+n)!*(m-n+1)/(m+1) cout<<"Test #"<<test<<":\n"<<num<<endl; } } }

此作品头部的算法说明是为了方便网友阅读，由裁判根据作者提交的算法说明加上的。