A1.

/* 首届高校BBS程序设计大赛 算法项目赛题A By rainarch@smth 2004.4.16 ======================= A1.工作安排 ----------------------- 问题： 有一定数量的夜班警卫保卫当地的仓库以防止抢劫。这些警卫需要成对地进行安排，使每一 对安排在不同的夜晚。仓库主管要求你写一程序， 确定能够安排警卫的最大值。 注意：每 一个警卫人员只能安排一次，警卫人员不能单独工作。 输入： 第一行包含一个整数 N <= 222 ,这是警卫人员的总数。以下的每一行包含一对整数(i,j)意 味着警卫i和j能够在一起工作。输入以EOF结束。 输出： 输出最理想的安排方法。输出一整数，表示能够安排的警卫人员的总数C。然后的C/2行，每 一行2个整数，意味着 i 和 j 能够一起工作。 输入样例： 3 1 2 2 3 1 3 输出样例： 2 1 2 /////////////////////////////////////////////// 主要思想 根据图中上点的度最小优先考虑的原则。 link: 表示每个guard可能的匹配对数目 1. Compute link for each guard 2. while(1){ Select the guard A whose link is the least of all; select a guard_pair that includes the guard A; update; } ////////////////////////////////////////////////// */ #include <string> #include <vector> #include <iostream> #include <assert.h> using namespace std; #define TRACK_INFO const int max_line_size = 1024; void Usage() { cout << "Usage: schedule inputfilename outputfilename" << endl; } int CheckParam(int argc, char *argv[]) { if(argc != 3){ Usage(); return -1; } return 0; } //Load Src file int LoadSrcFile(const char *schedule_file, int &guard_num, vector<pair<int, int > > &guard_pair_list) { assert(schedule_file != NULL ); FILE *fpsrc; char *p1, *p2; char line[max_line_size]; pair<int, int> guard_pair; fpsrc = fopen(schedule_file, "rb"); if(!fpsrc){ cout << "Err: opening file " << schedule_file << endl; return -1; } guard_num = 0; if(!fgets(line, max_line_size, fpsrc)){ cout << "Err: cant find the number of guards" << endl; return -1; } guard_num = atoi(line); p1 = line; while(fgets(line, max_line_size, fpsrc)){ //id1 id2 p2 = strchr(line,' '); if(p2 == NULL){ break; } guard_pair.first = atoi(p1) - 1; guard_pair.second = atoi(p2) - 1; guard_pair_list.push_back(guard_pair); } fclose(fpsrc); // #ifdef TRACK_INFO cout << "Num of guards = " << guard_num << endl; cout << "Num of guard_pairs = " << guard_pair_list.size() << endl; #endif return 0; } void ComputeLinks(vector<pair<int, int > > &guard_pair_list, vector<int > &guard_links) { int guard_num = guard_links.size(); vector<pair<int, int > >::iterator itr, itr_end; itr_end = guard_pair_list.end(); itr = guard_pair_list.begin(); for(; itr != itr_end; ++itr){ guard_links[itr->first] ++; guard_links[itr->second] ++; } } int SelectLeastLink(vector<int > &guard_links) { int guard_no = 0; int least_link_num = 0; if(guard_links.size() == 0) return -1; least_link_num = guard_links[0]; guard_no = 0; for(int i = 1; i < guard_links.size(); ++i){ if(guard_links[i] == -1) continue; if(least_link_num == -1 || least_link_num > guard_links[i]){ least_link_num = guard_links[i]; guard_no = i; } } return guard_no; } int WriteToResult(const int &select_guard_num, const vector<pair<int, int > > &select_guard_pair_list, const char *result_file) { FILE *fpresult; fpresult = fopen(result_file, "wb"); if(!fpresult){ cout << "Err: opening file " << result_file << endl; return -1; } //output guard_num fprintf(fpresult,"%d\r\n",select_guard_num); for(int i = 0; i < select_guard_pair_list.size(); ++i){ fprintf(fpresult, "%d %d\r\n", select_guard_pair_list[i].first +1, select_guard_pair_list[i].second + 1); } fclose(fpresult); return 0; } // int SelectLink(vector<pair<int, int > > &guard_pair_list, const int &guard_no) { for(int i = 0; i < guard_pair_list.size(); ++i){ if(guard_pair_list[i].first == guard_no || guard_pair_list[i].second == guard_no){ return i; } } return -1; } void UpdateLink(vector<int > &guard_links, vector<pair<int, int > > &guard_pair_list, pair<int, int > guard_pair) { for(int i = 0; i < guard_pair_list.size();){ if(guard_pair_list[i].first == guard_pair.first || guard_pair_list[i].second == guard_pair.first || guard_pair_list[i].first == guard_pair.second || guard_pair_list[i].second == guard_pair.second){ guard_links[guard_pair_list[i].first] --; guard_links[guard_pair_list[i].second] --; guard_pair_list.erase(&guard_pair_list[i]); } else{ ++i; } } guard_links[guard_pair.first] = -1; guard_links[guard_pair.second] = -1; } int ScheduleGuard(const char *schedule_file, const char *result_file) { assert(schedule_file != NULL && result_file != NULL); int guard_num = 0, select_guard_num = 0; vector<pair<int, int > > guard_pair_list, select_guard_pair_list; vector<int > guard_links; //Load Src file if(LoadSrcFile(schedule_file, guard_num, guard_pair_list) != 0){ return -1; } //Perhaps, need check input at here?? //Compute the links of guards guard_links.resize(guard_num, 0); ComputeLinks(guard_pair_list, guard_links); int guard_no = 0, guard_pair_no = 0; while(1){ //select the least links of guard guard_no = SelectLeastLink(guard_links); if(guard_no == -1) break; //Get guard_pair guard_pair_no = SelectLink(guard_pair_list, guard_no); if(guard_pair_no == -1) break; //add to selected select_guard_pair_list.push_back(guard_pair_list[guard_pair_no]); // #ifdef TRACK_INFO cout << "Guard_no = " << guard_no +1 << endl; cout << "Guard_Pair = " << guard_pair_list[guard_pair_no].first +1; cout << "+" << guard_pair_list[guard_pair_no].second+1 << endl; #endif //remove select and update the links UpdateLink(guard_links, guard_pair_list, guard_pair_list[guard_pair_no]); //guard_links[guard_pair_list[guard_pair_no].first] = -1; //guard_links[guard_pair_list[guard_pair_no].second] = -1; //guard_pair_list.erase(&guard_pair_list[guard_pair_no]); select_guard_num += 2; } if(WriteToResult(select_guard_num, select_guard_pair_list, result_file) != 0) return -1; return 0; } int main(int argc, char *argv[]) { char *schedule_file,*result_file; if(CheckParam(argc, argv) != 0) return -1; schedule_file = argv[1]; result_file = argv[2]; if(ScheduleGuard(schedule_file,result_file) != 0) return -1; return 0; }

A2.

#include <stdio.h> #define MAXNUM 100 struct NODE { bool state; // 当前节点的状态 int maxmoney; // 从当前节点开始可以取得的最多钱数 int nextx, nexty; // 为了取得最多的钱数下一步应走的位置 }; int n; // 格子的数目 int k; // 一次最多可以跳的格子数 int frame[MAXNUM *MAXNUM]; // 保存各格子钱数的数组 struct NODE state[MAXNUM * MAXNUM]; // 保存当前节点状态的数组 int countnum1, countnum2; // 若节点(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; // 要取到最大的钱数，下一跳的位置 countnum1 ++; // 查找同一列上的点 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; countnum2++; 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; } countnum1 = 0; countnum2 = 0; while (state[0].state == false) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { CalState(i,j); } } } fprintf(fpOut, "%d\n\n", state[0].maxmoney + frame[0]); fprintf(fpOut, "%d\t%d\n\n", countnum1, countnum2); 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; }

A5.

// powerManagement.cpp /* ********************************************************************************** * @ Name : powerManagement * * @ Purpose : to solve the problem of big factories' power management * * when a plan is given , * * a result will be given about whether the plan is feasible * * or about the max power needed * * @ In : a file contains the equipment list of a facory and the plans * * * ************************************************************************************/ #include "powerManagement.h" int main(int argc ,char *argv[]) { if (argc !=2) { cerr <<"usage:powerManagement [inputfile]"<<endl; exit(1); } PowerManagement(argv[1]); return 0; }

// powerManagement.h #ifndef POWERMANAGEMENT #define POWERMANAGEMENT #include <string.h> #include <iostream> #include <fstream> #include <memory.h> #include "StringHashtable.h" using namespace std; class Equipment { public: char key[31]; int need; //Equipment(); /*Equipment(Equipment& one) { strcpy(key,one.key); need = one.need; }*/ void operator = (Equipment& one) { strcpy(key,one.key); need = one.need; } }; void AddPower(long powerList[32769],int openTime,int closeTime, int needed) { int i; for ( i=openTime; i<closeTime; i++) { powerList[i] += needed; } } long maxneed(long powerList[32769] ,int *time) { long m = 0; int i ; for (i =0; i<32768; i++) { if (powerList[i] > m) { m = powerList[i] ; *time = i; } } return m; } void PowerManagement(char* inputFile) { CStringHashtable<Equipment> equipmentList(101); // an array records the equipment infor long powerList[32769]; // an array records the power at each period unsigned int totalNum ; char *start; char *end; unsigned int i; char buffer[81]; Equipment aequipment; ifstream fin; fin.open(inputFile); if ( ! fin.good() ) { cerr <<"can't open file " << inputFile<<endl; cerr <<"please give the correct directory for inputFile" <<endl; exit(1); } fin >> totalNum; fin.getline(buffer,80); //escape '\n' for( i = 0 ; i< totalNum ; i++) { //get a line; fin.getline(buffer,80); // get the key of a equipment and record it in the variable,aequipment start = buffer; while( (*start) !='[') { start++; } end = start +1; while( (*end) !=']') { end++; } *end ='\0'; strcpy(aequipment.key,start+1); // get the power needed of a equipment and record it in the variable,aequipment start = end+1; while(*start!='\0' && *start ==' ') { start ++; } if (!start) { cout << "the power of the equipment is not given"<<endl; exit(1); } end = start +1; while(*end != '\0' && *end !=' ') { end; } *end ='\0'; aequipment.need = atoi(start); // add the equipment in to a hashlist equipmentList.Add(aequipment.key,aequipment); } int count; // to record the count of records of a plan int maxSupply; // to record the max power supply of a plan char key[31]; int openTime; // the time of a equipment to open int closeTime; // the time of a equipment to close while(!fin.eof()) { memset(powerList,0, 32769*sizeof(long)); fin >> count >> maxSupply; fin.getline(buffer,80);//escape '\n' for (i =0; i< count; i++) { fin.getline(buffer,80);//get a line; // get the key of a equipment and record it in the variable,aequipment start = buffer; while( (*start) !='[') { start++; } end = start +1; while( (*end) !=']') { end++; } *end ='\0'; strcpy(key,start+1); // get the power needed of a equipment and record it in the variable,aequipment start = end+1; while(*start!='\0' && *start ==' ') { start ++; } end = start +1; while((*end) != '\0' && *end!=' ') { end++; } *end = '\0'; openTime = atoi(start); start = end+1; while(*start!='\0' && *start ==' ') { start ++; } end =start +1; while(*end != '\0' && *end !=' ') { end++; } *end ='\0'; closeTime = atoi(start); equipmentList.Get(key, aequipment); AddPower(powerList, openTime, closeTime, aequipment.need); } int time; long m = maxneed(powerList,&time); if (m > maxSupply) { cout <<"The power will be out at time " << time <<"because the power is " <<m << " Watts and overloaded."<< endl; } else { cout <<"The maximum power needed is "<<m<<"Watts."<< endl; } } } #endif

#if !defined __STRINGHASHTABLE_H_STRINGHASHTABLE_H__ #define __STRINGHASHTABLE_H_STRINGHASHTABLE_H__ #include <string.h> #include <assert.h> template <class T> class CStringHashtable { public: CStringHashtable(int nInitCapacity = 11, float fLoadFactor = 0.75); //Constructor ~CStringHashtable(); //Destructor private: typedef struct ENTRY //Hashtable collision list { int hash; char *key; T value; struct ENTRY *next; ENTRY(int Hash, const char *Key, T Value, struct ENTRY *Next) { hash = Hash; int nLen = strlen(Key); key = new char[nLen + 1]; strcpy(key, Key); value = Value; next = Next; } ~ENTRY() { if(key) delete key; if(next) delete next; } }ENTRY, *PENTRY; PENTRY *table; //The hashtable data long nCount; //The total number of entries in the hashtable int nCapacity; //The capacity of the hashtable int nThreshold; //The table is rehashed when it's size exceeds this threshold float fLoadFactor; //The load factor for the hashtable int nStringHash; //Cache the hashcode for the string public: long GetSize() { return nCount; } //Return the number of keys in the hashtable bool IsEmpty() { return (nCount == 0); }//Test if the hashtable maps no keys to values void Clear(); //Clear this hashtable so that it contains no keys bool Add(const char *key, T &value);//Maps the specified key to the specified //value in the hashtable //neither the key nor the value can be null bool Get(const char *key, T &value) const;//Return the value to which the specified //key is mapped in this hashtable bool Delete(const char *key); //Remove the key and it's corresponding value //in this hashtable. This function does //nothing if the key is not in the hastable int ResetValue(T value); // Map all the keys in the hash table to the // specific value bool ContainValue(T value) const; //Test if some key maps into the specified //value in this hashtable bool ContainKey(const char *key) const;//Test if the specified key is a key //in the hashtable int HashCode(const char *key) const;//Return the hashcode value for the specified key char **GetKeys(); //Return an array of all the keys in the hashable protected: void ReHash(); //Increases the capacity of and internally //reorganizes the hashtable }; // 构造函数 // nInitCapacity: 哈希表初始大小 // loadFactor: 哈希表装填因子阀值，当装填因子大于此值时，哈希表进行动态扩展 template <class T> CStringHashtable<T>::CStringHashtable(int nInitCapacity, float loadFactor) { if(nInitCapacity == 0) nInitCapacity = 1; fLoadFactor = loadFactor; nCapacity = nInitCapacity; table = new PENTRY[nInitCapacity]; for(int i = 0; i < nCapacity; i ++) table[i] = NULL; nThreshold = (int)(nInitCapacity * loadFactor); nCount = 0; } // 析构函数 template <class T> CStringHashtable<T>::~CStringHashtable() { Clear(); if(table) delete table; } // 求一字符串的哈希值 // key: 要求哈希值的字符串 // 返回值: 求得的哈希值 template <class T> int CStringHashtable<T>::HashCode(const char *key) const { int h = 0; for (int i = 0; i < (int)strlen(key); i++) h = 31 * h + key[i]; return h; } // 判断哈希表中是否有给定的值 // value: 要进行判断的值 // 返回值: 若哈希表中有此值则返回true, 否则返回false template <class T> bool CStringHashtable<T>::ContainValue(T value) const { PENTRY *tab = table; for(int i = nCapacity - 1; i >= 0 ; i--) { for(PENTRY e = tab[i]; e != NULL; e = e->next) { if(e->value == value) return true; } } return false; } // 判断哈希表中是否有给定的关键词 // value: 要进行判断的词 // 返回值: 若哈希表中有此关键词则返回true, 否则返回false template <class T> bool CStringHashtable<T>::ContainKey(const char *key) const { PENTRY *tab = table; int hash = HashCode(key); int index = (hash & 0x7FFFFFFF) % nCapacity; for(PENTRY e = tab[index] ; e != NULL ; e = e->next) { if ((e->hash == hash) && strcmp(e->key, key) == 0) return true; } return false; } // 从哈希表中获取一个键值 // key: 要进行求值的关键词 // value: 键值 // 返回值: 该关键词存在则返回true, 否则返回false template <class T> bool CStringHashtable<T>::Get(const char *key, T &value) const { PENTRY *tab = table; int hash = HashCode(key); int index = (hash & 0x7FFFFFFF) % nCapacity; for(PENTRY e = tab[index]; e != NULL; e = e->next) { if((e->hash == hash) && strcmp(e->key, key) == 0) { value = e->value; return true; } } return false; } // 对哈希表进行动态扩充 // 当装填因子达到阀值时进行本操作 template <class T> void CStringHashtable<T>::ReHash() { int oldCapacity = nCapacity; PENTRY *oldMap = table; int i; nCapacity = oldCapacity * 2 + 1; PENTRY *newMap = new PENTRY[nCapacity]; for(i = 0; i < nCapacity; i ++) newMap[i] = NULL; nThreshold = (int)(nCapacity * fLoadFactor); table = newMap; for(i = oldCapacity - 1; i >= 0; i--) { for(PENTRY old = oldMap[i]; old != NULL; ) { PENTRY e = old; old = old->next; int index = (e->hash & 0x7FFFFFFF) % nCapacity; e->next = newMap[index]; newMap[index] = e; } } delete oldMap; } // 删除哈希表中所有的键值对 template <class T> void CStringHashtable<T>::Clear() { PENTRY *tab = table; for(int i = nCapacity - 1; i >= 0 ; i--) { if(tab[i]) { delete tab[i]; tab[i] = NULL; } } nCount = 0; } // 向哈希表中添加一个键值对 // key: 关键词 // value: 该关键词对应的值 // 返回值: 若该关键词以前不存在则返回false，否则返回true并在value中返回以前的键值 template <class T> bool CStringHashtable<T>::Add(const char *key, T &value) { PENTRY *tab = table; int hash = HashCode(key); int nIndex = (hash & 0x7FFFFFFF) % nCapacity; T nOldValue; PENTRY e; for(e = tab[nIndex]; e != NULL; e = e->next) { if(e->hash == hash && (strcmp(e->key, key) == 0)) { nOldValue = e->value; e->value = value; value = nOldValue; return true; } } if(nCount >= nThreshold) //Rehash the table if the threshold is exceeded { ReHash(); tab = table; nIndex = (hash & 0x7FFFFFFF) % nCapacity; } e = new ENTRY(hash, key, value, tab[nIndex]); assert(e); tab[nIndex] = e; nCount++; return false; } // 从哈希表中删除一个键值对 // key: 要删除的关键词 // 返回值: 若该关键词存在则返回true，否则返回false template <class T> bool CStringHashtable<T>::Delete(const char *key) { PENTRY *tab = table; int hash = HashCode(key); int index = (hash & 0x7FFFFFFF) % nCapacity; for(PENTRY e = tab[index], prev = NULL ; e != NULL ; prev = e, e = e->next) { if((e->hash == hash) && strcmp(e->key, key) == 0) { if (prev != NULL) prev->next = e->next; else tab[index] = e->next; nCount--; e->next = NULL; delete e; return true; } } return false; } // 将哈希表中所有的键值都置为指定的值 // value: 新的键值 // 返回值: 改变的键值对的数目 template <class T> int CStringHashtable<T>::ResetValue(T value) { PENTRY *tab = table; int num = 0; for(int i = nCapacity - 1; i >= 0 ; i--) { for(PENTRY e = tab[i]; e != NULL; e = e->next) { e->value = value; num++; } } assert(num == nCount); return num; } // 返回哈希表中所有关键词的一个集合，放在二维字符数组中 // 返回值: 指向关键词集合的二维字符数组指针，若集合为空，则返回NULL template <class T> char **CStringHashtable<T>::GetKeys() { if (nCount == 0) return NULL; PENTRY *tab = table; char **keys = new char*[nCount]; int num = 0; for(int i = nCapacity - 1; i >= 0 ; i--) { for(PENTRY e = tab[i]; e != NULL; e = e->next) { int nLen = strlen(e->key); keys[num] = new char[nLen + 1]; strcpy(keys[num], e->key); num++; } } assert(num == nCount); return keys; } #endif