对以下简单题，我同时给出一个我主观认为的难度值（0.1~1.0之间）。
(1). ZOJ 1072: Microprocessor Simulation. (Difficulty: 0.2)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1072
微处理器模拟，它含有两个累加器，代码和内存统一寻址，即冯诺依曼结构，比较简单。
ZOJ1072_cpp
#include <stdio.h>#include <string.h>
char mem[256]; /* 256 words 内存 */char A; /* A 累加器 */char B; /* B 累加器 */
int PC; /*程序计数器，code取址用*/
void Run(){int flag_STOP = 0;int code, addr;char tmp; PC = 0;
do {/* reset PC */if(PC >= 0xF0)break;
/* 取指令 */ code = mem[PC]; ++PC;
switch(code) {/* LD: Load accumulator A with the contents of memory at the specified argument.*/case 0: addr = mem[PC] * 16 + mem[PC+1]; PC += 2; A = mem[addr];break;
/* ST: Write the contents of accumulator A to the memory location specified by the argument.*/case 1: addr = mem[PC] * 16 + mem[PC+1]; PC += 2; mem[addr] = A;break;
/* SWP: Swap the contents of accumulators A and B. */case 2: tmp = A; A = B; B = tmp;break;
/* ADD: Add the contents of accumulators A and B. The low word of the sum is stored in A, and the high word in B. */case 3: tmp = A + B; A = (tmp & 0x0F); B = (tmp >> 4);break;
/* INC: Increment accumulator A. Overflow is allowed; that is, incrementing F yields 0. */case 4:if(A == 0x0F) A = 0;else A++;break;
/* DEC: Decrement accumulator A. Underflow is allowed; that is, decrementing 0 yields F.*/case 5:if(A == 0) A = 0x0F;else A--;break;
/* BZ: If accumulator A is zero, the next command to be executed is at the location specified by the argument. If A is not zero, the argument is ignored and nothing happens. */case 6: addr = mem[PC] * 16 + mem[PC+1]; PC += 2;if(A == 0) { PC = addr; }break;
/* BR: The next command to be executed is at the location specified by the argument. */case 7: addr = mem[PC] * 16 + mem[PC+1]; PC = addr;break;
/* STP: Stop execution of the program. */case 8: flag_STOP = 1;break; } }while(!flag_STOP);}
char CharToNum(char c){if(c >= '0' && c <= '9') return (c - '0');else return (c - 'A' + 10);}
char NumToChar(char c){if(c >= 0 && c <= 9) return (c + '0');else return (c + 'A' - 10);}
int main(int argc, char* argv[]){char line[264];int i, j;
do {/* 读取一次完整的输入 */ i = 0;do { gets(line);for(j = 0; j < strlen(line); j++) { mem[i] = CharToNum(line[j]); i++; } }while(i < 256);
/*结束输入的标志*/if(mem[0] == 8)break;
Run();
/* output */for(j = 0; j < 256; j++) { printf("%c", NumToChar(mem[j])); } printf("\n"); }while(1);return 0;}
(2). ZOJ 1414: Num Steps. (Difficulty: 0.2)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1414
一个网格如下图所示，给出一个坐标（x，y），要求输出其数字，如果没有数字则输出 "No Number”;
ZOJ1414_cpp
#include <stdio.h>int main(int argc, char* argv[]){int count, i;int x, y, num; scanf("%d", &count);for(i = 0; i < count; i++) { scanf("%d %d", &x, &y);if(x - y == 0 || x - y == 2) { num = ((x >> 1) << 2) + (x & 1) - (x - y); printf("%d\n", num); }else printf("No Number\n"); }return 0;}
(3). ZOJ 1170: String Matching. (0.3)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1170
求出两个字符串的相似值（一个化简后的分数）。
ZOJ1170_cpp
#include <stdio.h>#include <string.h>
char szLine[512];
//得到两个字符串的相同字符个数int SameLetterCount(const char* s1, const char* s2){int count = 0;const char *p1 = s1;const char *p2 = s2;while(*p1 && *p2) {if(*p1 == *p2) count++; ++p1; ++p2; }return count;}
//此方法的时间复杂度应该是O(n ^ 2)void GetAppx(const char* s1, const char* s2, int* pAppx, int* pTotalLen){int appx = 0, tmp_appx = 0, index;
int len1 = strlen(s1);int len2 = strlen(s2);
*pTotalLen = len1 + len2;
if(strcmp(s1, s2) == 0) { *pAppx = *pTotalLen;return; }
for(index = -(len2 - 1); index <= len1 - 1; ++index) {if(index <= 0) tmp_appx = SameLetterCount(s1, s2 - index);else tmp_appx = SameLetterCount(s2, s1 + index);
if(tmp_appx > appx) appx = tmp_appx; } *pAppx = appx * 2;}
// 辗转相除法，求最大公约数int GetGcd(int a, int b){int tmp;while(b > 0) { tmp = a % b; a = b; b = tmp; }return a; }
int main(int argc, char* argv[]){char* pBlank = NULL;int totalLen = 0, appx = 0, gcd = 0;while( 1 ) { gets(szLine);if(strcmp(szLine, "-1") == 0)break;
//在空格处截断字符串 pBlank = strchr(szLine, ' '); *pBlank = 0;
GetAppx(szLine, pBlank + 1, &appx, &totalLen);
if(appx == 0) printf("appx(%s,%s) = 0\n", szLine, pBlank + 1);else if(appx == totalLen) printf("appx(%s,%s) = 1\n", szLine, pBlank + 1);else {//化简分数 gcd = GetGcd(totalLen, appx); totalLen /= gcd; appx /= gcd;
printf("appx(%s,%s) = %d/%d\n", szLine, pBlank + 1, appx, totalLen); } }return 0;}
(4). ZOJ 1240: IBM Minus One (0.1)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1240
超级简单，把字符串中每个字符用其字母序后面的字符替换。
ZOJ1240_cpp
#include <stdio.h>#include <string.h>
//把每个字母向后旋转一格，c = c + 1, Z->Avoid Transfer(char* s){char* p = s;while(*p) {if(*p == 'Z') *p = 'A';else *p = *p + 1; ++p; }}
int main(int argc, char* argv[]){char line[56];int count = 0, i;
scanf("%d\n", &count);for(i = 0; i < count; i++) { gets(line); Transfer(line); printf("String #%d\n%s\n\n", i+1, line); }return 0;}
(5) ZOJ 1295: Reverse Text (0.1)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1295
反转字符串，即 CRT 中的 strrev。
ZOJ1295_cpp
#include <string.h>#include <stdio.h>
void reverse(char* str){char tmp;int left = 0;int right = strlen(str) - 1;while(left < right) { tmp = str[left]; str[left] = str[right]; str[right] = tmp; ++left; --right; }}
int main(int argc, char* argv[]){char str[256];int n, i; scanf("%d\n", &n);for(i=0; i<n; i++) { gets(str);/*scanf("%s", str);*/ reverse(str); printf("%s\n", str); }return 0;}
(6). ZOJ 1383: Binary Numbers (0.2)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1383
输出一个数字二进制表示中 1 所在的位。（注意输出格式）
ZOJ1383_cpp
#include <stdio.h>
int main(int argc, char* argv[]){int count = 0, i, num, iDigit;//是否需要在该位前输出一个空格 int bNeedSpace;
scanf("%d", &count);for(i = 0; i < count; i++) { scanf("%d", &num); iDigit = 0; bNeedSpace = 0;while(num != 0) {if(num & 1) {if(bNeedSpace) printf(" "); printf("%d", iDigit); bNeedSpace = 1; } num = (num >> 1); ++iDigit; }if(i < count - 1) printf("\n"); }return 0;}
(7). ZOJ 1814: Candy Sharing Game (0.2)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1814
分糖果游戏，学生围成一圈，每次把手里的一半糖果分给右侧的人，如果任何人糖果为奇数，则再分给他一颗，直到所有人持有糖果数相同。模拟法。
ZOJ1814_cpp
#include <stdio.h>
//students: 每个学生持有的糖果数（逆时针方向）//n: 学生个数//rounds：游戏轮次//candy：游戏结束时每个学生手里的糖果数void Play(int* students, int n, int* rounds, int* candy){int i, students0, tmp_candy, left_candy;int bGameOver; *rounds = 0;while(1) { students0 = students[0]; bGameOver = 1;for(i = 0; i < n; i++) { left_candy = (i == (n-1))? students0 : students[i+1]; students[i] = (students[i] + left_candy)/2;//如果是奇数，立即再给他一个糖果 if(students[i] & 1) students[i]++;
if(i == 0) tmp_candy = students[0]; //初始化 else if(bGameOver && students[i] != tmp_candy) { bGameOver = 0; } } (*rounds)++;if(bGameOver) break; }
//最终结果 *candy = students[0];}
int main(int argc, char* argv[]){int students[1024];int n, i;int rounds, candy;
while(1) { scanf("%d", &n);if(n == 0) break;for(i=0; i<n; i++) scanf("%d", (students + i));
Play(students, n, &rounds, &candy); printf("%d %d\n", rounds, candy); }return 0;}
(8). ZOJ 2680: Clock (0.3)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2680
给出 5 个时刻，按时钟的时针，分针夹角从小到大排序，输出中间的时刻。显然，整数分钟（不考虑秒）时刻，时针分针的夹角是 0.5 角度的整数倍，因此为回避浮点数，采用 0.5 度为指针夹角的基本单位（一个圆周为 360 度）。由于需要输出的只是排序后的中间元素，排序时只要排好一半即可。
ZOJ2680
#include <stdio.h>
typedef struct tagTime{int angle; //夹角以0.5度为单位 int hour;int minute;} TIME;
typedef TIME Item;
Item items[5];
int lessthan(Item t1, Item t2){if (t1.angle < t2.angle) return 1;else if(t1.angle > t2.angle) return 0;else if(t1.hour < t2.hour) return 1;else if(t1.hour > t2.hour) return 0;else if(t1.minute < t2.minute) return 1;else return 0;}
/*交换a[]的i，j项*/void exchange(Item a[], int i, int j){int _angle = a[i].angle;int _hour = a[i].hour;int _minute = a[i].minute;
a[i].angle = a[j].angle; a[i].hour = a[j].hour; a[i].minute = a[j].minute;
a[j].angle = _angle; a[j].hour = _hour; a[j].minute = _minute;}
/*选择排序*/// stopIndex: 当排序到索引stopIndex，即可停止排序void SelectionSort(Item a[], int left, int right, int stopIndex){int i, j, min;//for(i = left; i < right; i++) //完整排序 for(i = left; i <= stopIndex; i++) { min = i;for(j = i + 1; j <= right; j++)if(lessthan(a[j], a[min])) min = j; exchange(a, i, min); }}
//以 0.5度 为单位（eg. 180 units = 90 度，720 units = 360 度）int GetAngle(int hour, int minute){int hour2 = (hour > 12) ? (hour - 12) : hour;int a1 = 60 * hour2 + minute;int a2 = minute * 12;int result = a2 - a1;if(result < 0) result = -result;if(result > 360) result = 720 - result;return result;}
int main(int argc, char* argv[]){int i, j, count;char line[48]; scanf("%d\n", &count);for(i = 0; i < count; i++) { gets(line);for(j = 0; j < 5; j++) { items[j].hour = ( line[j*6] - '0' ) * 10 + ( line[j*6+1] - '0' ); items[j].minute = ( line[j*6 + 3] - '0' ) * 10 + ( line[j*6+4] - '0' ); items[j].angle = GetAngle(items[j].hour, items[j].minute); } SelectionSort(items, 0, 4, 2); printf("%02d:%02d\n", items[2].hour, items[2].minute); }return 0;}
(9). ZOJ 3191: Strange Clock (0.2)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3191
给出时针的角度，输出该时刻处于几点钟。
ZOJ3191_cpp
#include <stdio.h>
int main(int argc, char* argv[]){int hourBig, hourSmall;int bExactly; //注意 gcc 没有定义过 bool 类型 int degree;
while( 1 ) { scanf("%d", °ree);if(degree == -1) break;
bExactly = (degree - (degree / 30 * 30) == 0); hourBig = (degree < 120 ? 3 : 15) - (degree / 30); hourSmall = (hourBig == 0) ? 11 : (hourBig - 1);
if(bExactly) printf("Exactly %d o'clock\n", hourBig);else printf("Between %d o'clock and %d o'clock\n", hourSmall, hourBig); }return 0;}
(10). ZOJ 3247: Hello World (0.3)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3247
给出一个点阵，要求输出字符图形（每一行输入由 5 个字节组成，代表一个字符，每个字节代表该字符的一列，即每个字符实际上7 * 5 像素，注意行和 bit 之间的对应关系，低位对应的是上方像素，高位对应下方像素，所有字节的最高位为 0，表示最后一行没有任何像素，注意最后一行不能输出一长串空格，而是要输出成空行即直接换行，否则将导致 PE），备注：可使用 strtol 把16进制字符串转换成整数。
ZOJ3247_cpp
#include <stdio.h>
char map[80][5];
char CharToInt(char c){if(c >= '0' && c <= '9')return (c - '0');else if(c >= 'A' && c <= 'F')return (c + 10 - 'A');elsereturn 0;}
int main(int argc, char* argv[]){char line[24];int test_count, char_count, i, j, k, col; scanf("%d", &test_count);for(i = 1; i <= test_count; i++) { scanf("%d\n", &char_count);for(j = 0; j < char_count; j++) { gets(line);for(k = 0; k < 5; k++) { map[j][k] = CharToInt( line[k*3] ) * 16 + CharToInt( line[k*3+1] ); } }
//output the string printf("Case %d:\n\n", i);
//j: rows index for(j = 0; j < 8; j++) {if(j < 7) {for(k = 0; k < char_count; k++) {//输出一个字符的某一行（五列） for(col = 0; col < 5; col++) {if( map[k][col] & (1 << j) ) printf("#");else printf(" "); }//字符和字符之间的空列 if(k < char_count - 1) printf(" "); } }//一行结束，换行 printf("\n"); } }return 0;}
(11). ZOJ 3322: Who is older ? (0.1)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3322
给出两个人的生日，比较年龄谁大，超级简单，直接比较字符串即可。
ZOJ3322_cpp
#include <stdio.h>#include <string.h>
int main(int argc, char* argv[]){char line[36];int n, i, result; scanf("%d\n", &n);for(i = 0; i < n; i++) { gets(line); line[10] = 0; result = strcmp(line, line + 11);if(result < 0) printf("javaman\n");else if(result > 0) printf("cpcs\n");else printf("same\n"); }return 0;}
(12). ZOJ 3487: Ordinal Numbers (0.1)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3487
给出一个数字，根据规则，给出其序数后缀表示。
ZOJ3487_cpp
#include <stdio.h>#include <string.h>
void GetPostfix(const char* line, char* postfix){int len = strlen(line);//十位上的字符 char c = '0';if(len > 1) c = line[len-2];
//If the tens digit of a number is 1, then write//"th" after the number. For example: 13th, 19th, 112th, 9311th. if(c == '1') { strcpy(postfix, "th"); }else {//If the tens digit is not equal to 1, then use//"st" if the units digit is 1, //"nd" if the units digit is 2, //"rd" if the units digit is 3, and //"th" otherwise: //For example: 2nd, 7th, 20th, 23rd, 52nd, 135th, 301st.
switch(line[len-1]) {case '1': strcpy(postfix, "st"); break;case '2': strcpy(postfix, "nd"); break;case '3': strcpy(postfix, "rd"); break;default: strcpy(postfix, "th"); break; } }}
int main(int argc, char* argv[]){int count = 0, i;char line[48], postfix[4];
scanf("%d\n", &count);for(i = 0; i < count; i++) { gets(line); GetPostfix(line, postfix); printf("%s%s\n", line, postfix); }return 0;}
(13). ZOJ 3542: Hexadecimal View (0.1)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3542
给出一行字符串（全部是可打印字符），输出 16 进制视图。备注：字符大小写的互相转换也可使用 touppder / tolower 。
ZOJ3542_cpp
#include <stdio.h>#include <string.h>
void OutputHexView(char* s){char *p = s;int i, linenum = 0;char line[16];int len = strlen(s);int linecount = (len + 15)/16; //需要打印的总行数for(linenum = 0; linenum < linecount; ++linenum) { memset(line, 0, 16); strncpy(line, p, 16); p += 16; printf("%04x: ", (linenum << 4) & 0xffff);for(i = 0; i < 16; i++) {if(line[i] == 0) printf(" "); //没有字符（最后一行的 padding 部分）else printf("%02x", line[i]);
if(i & 1) printf(" "); //每两个字符之间有一个空格间隔 }for(i = 0; i < 16; i++) {if(line[i] == 0) {break; }else if(line[i] >= 'a' && line[i] <= 'z') // islower( line[i] ) { printf("%c", line[i] + 'A' - 'a'); // toupper( line[i] ) }else if(line[i] >= 'A' && line[i] <= 'Z') { printf("%c", line[i] + 'a' - 'A'); // tolower; }else { printf("%c", line[i]); } } printf("\n"); }}
int main(int argc, char* argv[]){char line[4100];while( gets(line) != NULL ) { OutputHexView(line); }return 0;}
(14). ZOJ 3317: Murder in Restaurant (0.3)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3317
给出一个旅馆的入住信息表，客人数和房间数，给出每个客人的试图入住日期和离店日期（都用整数表示），尝试给客人分配一个最小房号（从1开始计数）的房间，要求输出每个客人的入住房号，如果该客人来时没有房间则输出 0。
解法：把客人按照入住时间升序排序，然后依次分配房间号。（有些类似贪心法中的申请会议室）
ZOJ3317_cpp
#include <stdio.h>
int Rooms_Leave[100]; /* 每个元素表示第 i 个房间退房的日期 */int Renters_RoomNo[100]; /* 每个元素分配给第 i 个客人的房间号 */
typedef struct tagRENTER{int index; //客人索引（0 base） int EnterDate; //入住日期 int LeaveDate; //离店日期} RENTER, *PRENTER;
typedef RENTER Item;
Item items[100];
int less_than(Item t1, Item t2){if (t1.EnterDate < t2.EnterDate) return 1;else return 0;}
/*交换a[]的i，j项*/void exchange(Item a[], int i, int j){if(i != j) {int _index = a[i].index;int _EnterDate = a[i].EnterDate;int _LeaveDate = a[i].LeaveDate;
a[i].index = a[j].index; a[i].EnterDate = a[j].EnterDate; a[i].LeaveDate = a[j].LeaveDate;
a[j].index = _index; a[j].EnterDate = _EnterDate; a[j].LeaveDate = _LeaveDate; }}
/*选择排序*/void SelectionSort(Item a[], int left, int right){int i, j, min;for(i = left; i < right; i++) { min = i;for(j = i + 1; j <= right; j++)if(less_than(a[j], a[min])) min = j; exchange(a, i, min); }}
int main(int argc, char* argv[]){int renter_count, room_count, i, j;
while( 1 ) { scanf("%d %d", &renter_count, &room_count);
if(renter_count == 0)break;
for(i = 0; i < renter_count; i++) { Rooms_Leave[i] = 0; Renters_RoomNo[i] = 0; items[i].index = i; scanf("%d %d", &items[i].EnterDate, &items[i].LeaveDate); }
/* 给每个客人分配房间 */ SelectionSort(items, 0, renter_count - 1);for(i = 0; i < renter_count; i++) {for(j = 0; j < room_count; j++) {if(Rooms_Leave[j] <= items[i].EnterDate) { Rooms_Leave[j] = items[i].LeaveDate; Renters_RoomNo[ items[i].index ] = j + 1;break; } } }
/* output result */for(i = 0; i < renter_count; i++) { printf("%d\n", Renters_RoomNo[i]); } }return 0;}
(15). ZOJ 2850: Beautiful Meadow ( 0.1 )
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2850
给出一个 N * M 的网格，每个 cell 的值是 0 或 1。如果所有 cell 都是1，或有任何为 0 的 cell 相邻（即共享某条边），则输出No，否则输出Yes。
zoj2850_cpp
#include <stdio.h>
int main(int argc, char* argv[]){int row, col, i, j, tmp, sum;int bMowedAdjacent;char map[100][100];while(1) { scanf("%d %d", &row, &col);if(row == 0)break;
bMowedAdjacent = 0; sum = 0;for(i = 0; i < row; i++) {for(j = 0; j < col; j++) { scanf("%d", &tmp); map[i][j] = tmp;if(tmp == 0) {if(j > 0 && map[i][j-1] == 0) bMowedAdjacent = 1;else if(i > 0 && map[i-1][j] == 0) bMowedAdjacent = 1; }else sum += tmp; } }if(bMowedAdjacent || sum == row * col) printf("No\n");else printf("Yes\n"); }return 0;}
(16). ZOJ 1094: Matrix Chain Multiplication ( 0.3 )
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1094
虽然题目是算法经典命题-矩阵乘法链，但是此题目考察的绝不是动态规划（DP），而是给出一个矩阵乘法加括号的表达式，求该方案所需的乘法运算数。如果矩阵乘法不相容，则输出 "error"。此题目的输入非常标准，无需考虑表达式的括号不匹配等问题。也无需考虑例如 "ABC" 这种没有加括号的表达式（输入一定给出的是 "((AB)C)" ）。如果是只有单个矩阵，则一定没有括号。这种输入的标准化使我们无需检测特殊情况（例如 "(A)", "ABC", ")AB" 等），可以仅仅用表达式中的括号去推动表达式的解析。
解法是：准备两个辅助栈，一个装入矩阵信息（操作数），一个装入括号（由于输入表达式一定括号匹配，因此第二个辅助栈实际上不需要，但为了保持逻辑完整性依然保留），每次遇到“）”符号，则从操作数栈中弹出两个矩阵，如果相容，则累加这两个矩阵相乘的代价，然后把结果信息 (row, col) 再次入栈。
zoj1094_cpp
#include <stdio.h>
typedef struct _tagMatrixInfo{int row;int col;} MatrixInfo;
MatrixInfo matrix[26];
/* szExpression: 形如"(A(BC))"; 返回值：乘法次数，-1 代表不相容 */int GetResult(char* szExpression){char *p = szExpression;char c;
char brackets[512]; /* 括号的栈 */int pBrackets = -1; /* 栈顶指针 */
MatrixInfo nums[512]; /* 操作数栈 */int pNums = -1; /* 栈顶指针 */
int row0, col0, row1, col1;int count = 0; /* 返回的结果：总乘法次数 */while(*p) { c = *p; ++p;if(c >= 'A' && c <= 'Z') /* push in stack */ { ++pNums; nums[pNums].row = matrix[c-'A'].row; nums[pNums].col = matrix[c-'A'].col; }else if(c == '(') { brackets[++pBrackets] = c; }else if(c == ')') {/* 从栈中弹出两个操作数 */ row0 = nums[pNums - 1].row; col0 = nums[pNums - 1].col; row1 = nums[pNums].row; col1 = nums[pNums].col; pNums -= 2; pBrackets--; /* 弹出一个'(' */
/* 两个操作数是否相容？ */if(col0 != row1)return -1;
count += row0 * col0 * col1;
/* 结果信息 push 到操作数栈中 */ ++pNums; nums[pNums].row = row0; nums[pNums].col = col1; } }return count;}int main(int argc, char* argv[]){int n, i, result;char cNum, line[1024]; scanf("%d\n", &n);for(i = 0; i < n; i++) { scanf("%c ", &cNum); scanf("%d %d\n", &matrix[cNum-'A'].row, &matrix[cNum-'A'].col); }while(gets(line) != NULL) { result = GetResult(line);if(result < 0) printf("error\n");else printf("%d\n", result); }return 0;}
时间： 2024-11-13 04:18:17