A1.

/* * 题目分析： * 　　本题是一个图的最大匹配问题 */ #include <stdio.h> #include <stdlib.h> #include <limits.h> #include <string.h> const int MAXN = 222+1; // 最大警卫数目 const int MAXINT = INT_MAX; int graph[MAXN][MAXN]; // 图的邻接矩阵 int lvtype[MAXN][2]; // [i][0]与i顶点相连的盖点序号 // [i][1]与i顶点相连的未盖点序号 int vtype[MAXN]; // 0为未盖点，非0为盖点，<i,vtype[i]>为匹配边 int vnum; // 顶点数 // 图矩阵初始化，并从文件中读入邻接矩阵 int Initialize(const char *sFileName) { memset(graph, 0, sizeof(int) * MAXN * MAXN); FILE *fp = fopen(sFileName, "r"); if (fp == NULL) { printf("Can't open input file %s\n", sFileName); return -1; } fscanf(fp, "%d", &vnum); // 第一行是警卫总数，即图中顶点的个数 int m, n; while (!feof(fp)) { fscanf(fp, "%d %d", &m, &n); graph[m][n] = graph[n][m] = 1; } fclose(fp); return 0; } // 将可扩展路上的匹配边与非匹配边对换 void findway(int i, int j) { int q, k; q = i; k = j; vtype[j] = i; while (lvtype[q][1] != MAXINT) { vtype[q] = k; k = lvtype[q][1]; vtype[k] = lvtype[k][0]; q = lvtype[k][0]; } vtype[q] = k; } // 判断扩展路是否存在 bool tree_isexpandable() { int i, j, q, k, v; bool bMore; // 扩展路搜索成功标志 bool vset[MAXN]; // 顶点构成的一个集合，false不在集合内，true在集合内 do { bMore = false; for (i = 1; i <= vnum; i++) { if (lvtype[i][1] > 0) // 若已确定与vi相连的一条匹配边 { for (j = 1; j <= vnum; j++) { if (graph[i][j] > 0 && vtype[i] != j) {// vi与vj有未检查的边且非匹配边 if (lvtype[j][0] == 0 && lvtype[j][1] == 0) { // 若未确定vj的匹配边和非匹配边 if (vtype[j] == 0) // 若vj是未盖点，找着可扩展路 { findway(i, j); // 将该路上的匹配边与非匹配边对换 return true; } else // vj是盖点 { // 设非匹配边vivj检查标志 graph[i][j] = -graph[i][j]; graph[j][i] = -graph[j][i]; // 将匹配边<j, vtype[j]>投入T中，设该边检查标志 lvtype[j][0] = i; lvtype[vtype[j]][1] = j; // 继续搜索扩展路 graph[j][vtype[j]] = -graph[j][vtype[j]]; graph[vtype[j]][j] = -graph[vtype[j]][j]; bMore = true; } } else if (lvtype[j][0] == 0 && lvtype[j][1] > 0) {// 若与vi相连的匹配边确定而非匹配边未确定 // 即找到一条不属于T且连接T上两个外点的边<vi,vj> bMore = true; // 继续搜索扩展路 graph[i][j] = -graph[i][j]; graph[j][i] = -graph[j][i]; // 搜索收缩顶点k memset(vset, 0, sizeof(bool) * MAXN); vset[i] = true; k = i; v = 1; while (lvtype[k][v] != MAXINT) { k = lvtype[k][v]; vset[k] = true; v = 1 - v; } k = j; v = 1; while (vset[k] == false) { k = lvtype[k][v]; v = 1 - v; } if (lvtype[i][0] == 0) { lvtype[i][0] = j; q = i; v = 1; while (q != k) { lvtype[lvtype[q][v]][v] = q; q = lvtype[q][v]; v = 1 - v; } } lvtype[j][0] = i; q = j; v = 1; while (q != k) { lvtype[lvtype[q][v]][v] = q; q = lvtype[q][v]; v = 1 - v; } } } } } } } while (bMore); return false; } int main(int argc, char *argv[]) { int i, j, k, tot; bool b; // 初始化图 if (Initialize(argv[1]) < 0) { return -1; } // 寻找最大匹配 memset(vtype, 0, sizeof(int) * MAXN); tot = 0; do { i = 0; do { i++; if (vtype[i] == 0) { memset(lvtype, 0, sizeof(int) * MAXN * 2); lvtype[i][1] = MAXINT; b = tree_isexpandable(); for (j = 1; j <= vnum; j++) { for (k = 1; k <= vnum; k++) { graph[j][k] = abs(graph[j][k]); } } } else b = false; } while (i <= vnum && !b); if (i < vnum) { tot ++; } }while (i <= vnum && tot != vnum / 2); // 输出匹配结果 FILE* fp = fopen(argv[2], "w"); fprintf(fp, "%d\n", tot * 2); for (i = 1; i <= vnum; i++) { if (vtype[i] > 0) { fprintf(fp, "%d %d\n", i, vtype[i]); vtype[vtype[i]] = 0; vtype[i] = 0; } } fclose(fp); return 0; }

A2.

/* * 题目分析： * 　　1.在图中存在一些状态固定的点，即从该点开始可以取得的钱数是已知的；如在 * 　放最大钱数的那一格，由于无处可跳，从这一格开始所能取得的钱数不变。 * 　　2.另外，当一个未知点所有能到达的点的状态已知时，可以推出该点的状态：其 * 　所有能到达的点中能取得的最大钱数加上该点的钱数最大者即为当前点所能取得的 * 　最大钱数。再由所有已知状态的点可以推出新的一部分点的状态……从而可以推出所 * 　有点的状态，此时所能取得的最大钱数也就知道了。 * 　　3.当一个点的状态改变时，只有那些能跳到该点的点的状态才有可能改变。 */ #include <stdio.h> #define MAXNUM 100 // 保存一个节点状态的结构 struct NODE { bool state; // 当前节点的状态 int maxmoney; // 从当前节点开始可以取得的最多钱数 int nextx, nexty; // 为了取得最多的钱数下一步应走的位置 }; // 保存一个状态可能改变的点的结构 struct CNODE { int x,y; // 状态可能改变的点的坐标 struct CNODE *next; // 下一个点 }; int n; // 格子的数目 int k; // 一次最多可以跳的格子数 int frame[MAXNUM *MAXNUM]; // 保存各格子钱数的数组 struct NODE state[MAXNUM * MAXNUM]; // 保存当前节点状态的数组 struct CNODE cList; // 保存状态可能改变的节点的链表 // 计算一个点(x,y)的状态 // 若状态可计算，则计算其状态，同时将可能改变状态的点加入到链表中 bool CalState(int x, int y) { int current = x * n + y; // 当前点在数组中的位置 int minRow = ((x-k) > 0) ? (x-k) : 0; // 列的最小数目 int maxRow = ((x+k) < n) ? (x+k+1) : n; // 列的最大数目 int minCol = ((y-k) > 0) ? (y-k) : 0; // 行的最小数目 int maxCol = ((y+k) < n) ? (y+k+1) : n; // 行的最大数目 int maxmoney = 0; // 当前点可以取到的最大的钱数 int maxx=0, maxy=0; // 要取到最大的钱数，下一跳的位置 if (state[current].state == true) return true; // 查找同一列上的点 for (int i = minRow; i < maxRow; i++) { int num = i * n + y; // 第i行x列的点在数组中的位置 if (frame[num] <= frame[current])// 跳过不能去的点 { continue; } if (state[num].state == false) { // 在能去的点中有状态不确定的点，则当前点状态亦不能确定 return false; } if (frame[num] + state[num].maxmoney > maxmoney) { maxmoney = frame[num] + state[num].maxmoney; maxx = i; maxy = y; } } // 查找同一行上的点 for (int i = minCol; i < maxCol; i++) { int num= x * n + i; // 第y行i列的点在数组中的位置 if (frame[num] <= frame[current])// 跳过不能去的点 { continue; } if (state[num].state == false) { // 在能去的点中有状态不确定的点，则当前点状态亦不能确定 return false; } if (frame[num] + state[num].maxmoney > maxmoney) { maxmoney = frame[num] + state[num].maxmoney; maxx = x; maxy = i; } } // 当前点状态已定，记录之 state[current].state = true; state[current].maxmoney = maxmoney; state[current].nextx = maxx; state[current].nexty = maxy; // 把状态可能改变的点放入链表中 for (int i = minRow; i < maxRow; i++) { int num = i * n + y; if (state[num].state == false && frame[num] < frame[current]) { struct CNODE *tmp = new struct CNODE; tmp->x = i; tmp->y = y; tmp->next = cList.next; cList.next = tmp; } } for (int i = minRow; i < maxRow; i++) { int num= x * n + i; if (state[num].state == false && frame[num] < frame[current]) { struct CNODE *tmp = new struct CNODE; tmp->x = x; tmp->y = i; tmp->next = cList.next; cList.next = tmp; } } return true; } int main(int argc, char *argv[]) { // 打开输入输出文件 FILE *fpIn = fopen(argv[1], "r"); if (fpIn == NULL) { printf("Can't open input file %s\n", argv[1]); return -1; } FILE *fpOut = fopen(argv[2], "w"); if (fpOut == NULL) { printf("Can't open output file %s\n", argv[2]); fclose(fpIn); return -1; } int testNum = 0; fscanf(fpIn, "%d", &testNum); // 从文件中读取测试样本数 for (int testNo = 1; testNo <= testNum; testNo++) { printf("Processing testcase %d\n", testNo); // 读取一个测试样本的数据 fscanf(fpIn, "%d %d", &n, &k); int square = n * n; for (int i = 0; i < square; i++) { fscanf(fpIn, "%d", frame+i); state[i].state = false; state[i].maxmoney = 0; state[i].nextx = 0; state[i].nexty = 0; } // 计算表中所有点的状态 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { CalState(i,j); } } // 逐步计算所有的点，直至状态不再改变 while (cList.next != NULL) { struct CNODE *next; struct CNODE *tmp = cList.next; cList.next = NULL; while (tmp != NULL) { CalState(tmp->x, tmp->y); next = tmp->next; delete tmp; tmp = next; } } // 输出结果 fprintf(fpOut, "%d\n\n", state[0].maxmoney + frame[0]); /* // 输出取钱所应该走的步骤 i = 0; while (state[i].maxmoney != 0) { fprintf(fpOut, "%d %d\n", state[i].nextx, state[i].nexty); i = state[i].nextx * n + state[i].nexty; } */ } fclose(fpIn); fclose(fpOut); return 0; }

A4.

/* * 题目分析： * 　　本题是一个Catalan数的问题。其解为(m+1-n)/(m+1) * (m+n)! * 　由于当m和n的值较大时，计算出的结果数值超出了整数类型的表示范围， * 　因此要用到高精度的乘法。 */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <fstream> #include "HighPrecision.h" // 要给定m和n的情况下计算可能的排队的数目 HighPrecision CalPass(int m, int n) { HighPrecision hp(400); if (n == 0) // n=0时，结果为m! { hp = 1; for (int i = 2; i <= m; i++) { hp = hp * i; } } else // 此时式子可变为(m+1-n)*m!*(m+2)...(m+n) { int i; hp = m + 1 - n; for (i = 2; i < m+1; i++) { hp = hp * i; } for (i = m+2; i <= m+n; i++) { hp = hp * i; } } return hp; } int main() { int nNo = 0; // 测试用例编号 int m, n; // 50元和100元人员的数目 ifstream ifs; // 输入文件流 ofstream ofs; // 输出文件流 // 打开输入文件流 ifs.open("ticket.in", ios::in); if (ifs.fail()) { printf("Can't open input file.\n"); return -1; } // 打开输出文件流 ofs.open("ticket.out", ios::out); if (ofs.fail()) { printf("Can't open output file.\n"); ifs.close(); return -1; } // 处理测试用例 ifs >> m >> n; while (m != 0 || n != 0) { nNo ++; // 测试用例编号加一 // 对输入进行检查 if (m < 0 || m > 100 || n < 0 || n > 100) { cout << "Error input" << endl; break; } ofs << "Test #" << nNo << endl; if (m >= n) { ofs << CalPass(m, n) << endl; } else // n>m 时无解 { ofs << 0 << endl; } ifs >> m >> n; } // 关闭输入输出流 ifs.close(); ofs.close(); return 0; }

//HighPrecision.h /* * 高精度整数的加减乘除运算 * * 日期: 2004-04-05 */ #ifndef _HIGHPRECISION_H_ #define _HIGHPRECISION_H_ #include <fstream> #include <string.h> using namespace std; class HighPrecision { typedef char DataType; // 数据单元的类型 private: int bufLen; // 缓冲区的长度 int dataLen; // 数值的长度 DataType *data; // data[0] 是符号位，1为+，0为-，0的符号为正 // data[1] 为低位，data[dataLen] 为高位 public: // 缺省构造函数 HighPrecision() { bufLen = 0; dataLen = 0; data = NULL; } // 带缓冲区长度的构造函数 HighPrecision(int nBufLen) { bufLen = nBufLen; dataLen = 0; data = new DataType[bufLen]; memset(data, 0, sizeof(DataType) * bufLen); data[0] = 1; } // 拷贝构造函数 HighPrecision(const HighPrecision& hp); // 析构函数 ~HighPrecision() { if (data != NULL) { delete[] data; data = NULL; } bufLen = dataLen = 0; } // 赋值运算符重载 HighPrecision& operator = (int nData); HighPrecision& operator = (const HighPrecision& hp); // 乘法运算符重载 HighPrecision operator * (int multiplier) const; // 流输出运算符重载，是ostream类的友元函数 friend ostream& operator << (ostream& out, HighPrecision& hp) { if (hp.data[0] == 0) out << "-"; for (int i = hp.dataLen; i> 0; i--) out << (int)hp.data[i]; return out; } }; // 拷贝构造函数 HighPrecision::HighPrecision(const HighPrecision& hp) { bufLen = hp.bufLen; dataLen = hp.dataLen; data = new DataType[bufLen]; memcpy(data, hp.data, sizeof (DataType) * bufLen); } // 赋值运算符重载 HighPrecision& HighPrecision::operator = (int nData) { char tmp[20]; int len; ltoa(abs(nData), tmp, 10); len = strlen(tmp); if (bufLen <= len) { if (data != NULL) delete[] data; bufLen = len + 1; data = new DataType[bufLen]; } memset(data, 0, sizeof(DataType) * bufLen); for (int i = 1; i <= len; i++) data[i] = tmp[len - i] - '0'; data[0] = (nData>=0) ? 1 : 0; while (len > 0 && data[len] == 0) len --; dataLen = len; return *this; } HighPrecision& HighPrecision::operator = (const HighPrecision& hp) { if (this != &hp) { if (bufLen < (hp.dataLen+1)) // The old buffer is not enough { if (data != NULL) delete[] data; bufLen = hp.dataLen+1; data = new DataType[bufLen]; } memset(data, 0, sizeof(DataType) * bufLen); dataLen = hp.dataLen; memcpy(data, hp.data, sizeof (DataType) * (dataLen + 1)); } return *this; } // 乘法运算符重载 HighPrecision HighPrecision::operator *(int multiplier) const { long lTmp; // Store HP[i] * multiplier int len = dataLen + 20; HighPrecision product(len); for (int i = 1; i <= dataLen; i++) { lTmp = data[i] * multiplier; int j = i; while (lTmp > 0) { lTmp += product.data[j]; product.data[j] = (DataType)(lTmp % 10); lTmp = lTmp / 10; j ++; } } len --; while (len > 0 && product.data[len] == 0) len --; product.dataLen = len; if (data[0] == 1 && multiplier >= 0) product.data[0] = 1; else product.data[0] = 0; return product; } #endif