（1）ZOJ 1045. HangOver (0.1)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1045
在桌子边码扑克牌，给出表示扑克牌延伸出桌子的距离的浮点数，问需要多少张牌。
zoj1045_cpp
#include <stdio.h>
int GetCardCount(double c)
{
int result = 1;
double dx = 0.5;
while(dx < c)
{
result++;
dx += 1.0/(result + 1.0);
}
return result;
}
int main(int argc, char* argv[])
{
double c;
int result;
while(1)
{
scanf("%lf", &c);
if(c < 0.001) break;
result = GetCardCount(c);
printf("%d card(s)\n", result);
}
return 0;
}
（2）ZOJ 1061. Web Navigation (0.2)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1061
模拟浏览器的前进后退功能，给出初始时刻的当前页面，然后经过一系列命令：访问某个url，前进，后退，如果命令有效，输出当前页面。
zoj1061
#include <stdio.h>
#include <string.h>
char sForw[100][72];
int pForw;
char sBack[100][72];
int pBack;
int main(int argc, char* argv[])
{
int n, i;
char curUrl[72], line[96];
scanf("%d", &n);
for(i = 0; i < n; i++)
{
//case和case之间的空行
gets(line);
strcpy(curUrl, "http://www.acm.org/");
pForw = -1;
pBack = -1;
while(1)
{
gets(line);
if(strcmp(line, "BACK") == 0)
{
//If the backward stack is empty, the command is ignored.
if(pBack < 0) printf("Ignored\n");
else
{
//Push the current page on the top of the forward stack.
++pForw;
strcpy(sForw[pForw], curUrl);
//Pop the page from the top of the backward stack,
//making it the new current page.
strcpy(curUrl, sBack[pBack]);
--pBack;
printf("%s\n", curUrl);
}
}
else if(strcmp(line, "FORWARD") == 0)
{
//If the forward stack is empty, the command is ignored.
if(pForw < 0) printf("Ignored\n");
else
{
//Push the current page on the top of the backward stack.
++pBack;
strcpy(sBack[pBack], curUrl);
//Pop the page from the top of the forward stack,
//making it the new current page.
strcpy(curUrl, sForw[pForw]);
--pForw;
printf("%s\n", curUrl);
}
}
else if(strncmp(line, "VISIT", 5) == 0)
{
//Push the current page on the top of the backward stack,
++pBack;
strcpy(sBack[pBack], curUrl);
//and, make the URL specified the new current page.
strcpy(curUrl, line + 6);
//The forward stack is emptied.
pForw = -1;
printf("%s\n", curUrl);
}
else if(strcmp(line, "QUIT") == 0)
{
break;
}
}
//case 和 case 之间用空行隔开
//注意这个if条件，如果没有，则导致PE！（多打印一个空行）
if(i < n - 1) printf("\n");
}
return 0;
}
（3）ZOJ 1067. Color Me Less (0.1)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1067
给出16个RGB值作为关键颜色，对后续给出的颜色，要求用欧几里德距离最短的方式，被映射到哪个关键颜色上。
zoj1067
include <stdio.h>
typedef struct _tagColor
{
int r;
int g;
int b;
} Color;
Color colors[16];
int GetMappedIndex(int r, int g, int b)
{
unsigned int distance = 0xFFFFFFFF;
unsigned int temp;
int i, index = -1;
for(i = 0; i < 16; i++)
{
temp = (r-colors[i].r) * (r-colors[i].r);
temp += (g-colors[i].g) * (g-colors[i].g);
temp += (b-colors[i].b) * (b-colors[i].b);
if(temp < distance)
{
distance = temp;
index = i;
}
}
return index;
}
int main(int argc, char* argv[])
{
int i, r, g, b;
for(i = 0; i < 16; i++)
{
scanf("%d %d %d",
&colors[i].r, &colors[i].g, &colors[i].b);
}
while(1)
{
scanf("%d %d %d", &r, &g, &b);
if(r == -1) break;
i = GetMappedIndex(r, g, b);
printf("(%d,%d,%d) maps to (%d,%d,%d)\n",
r, g, b, colors[i].r, colors[i].g, colors[i].b);
}
return 0;
}
（4）ZOJ 1123. Triangle Encapsulation（0.5）
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1123
依次给出一个三角形按逆时针方向排列的三个顶点的坐标（所有坐标范围在 -9 ~ 9 之间），要求求平面上被这个三角形完全围在内部的所有整数坐标的点。而且这道题目对输出格式有特别要求，不好描述，就是输出的点排列的就像他们在笛卡尔座标中的位置那样。
解法：首先这道题目求解一个点是否在三角形，可以用常规的点在多边形内的射线法。但还可以用线段旋转方向（即叉积）来判断，如果点P在三角形ABC内部，则AB，BC，CA旋转到P的时针方向必然全都相同。如果在外部，则必定不满足这个条件。而且此题还明确说明，三个点ABC是逆时针排列的，所以三条边从逆时针转过去，转到P点如果都是“右转”，则说明点P在三角形内。如果P在三角形的边上，叉积为0。因此只要遍历三角形的外接矩形内的所有整数坐标点，依次判断即可。最后为了按题目要求的格式进行输出，采用一个辅助队列缓存所有解，最后得到了最左侧的点的位置以后，所有解的打印位置也就确定了。
zoj1123
#include <stdio.h>
#ifndef __min
#define __min(a, b) ((a)<(b)? (a):(b))
#endif
#ifndef __max
#define __max(a, b) ((a)>(b)? (a):(b))
#endif
//
typedef struct _tagPOINT
{
char x;
char y;
} POINT;
POINT pts[90];
int pts_top; //Queue 指针
// (Pi->Pk) * (Pi->Pj) 从 PI-PK 转向 PI-PJ 的方向
// > 0: 左转
// < 0: 右转
// = 0: 共线
int Direction(int xi, int yi,
int xj, int yj,
int xk, int yk)
{
return (xk-xi)*(yj-yi) - (xj-xi)*(yk-yi);
}
int main(int argc, char* argv[])
{
//三角形的三个顶点（逆时针方向）
int x0, y0, x1, y1, x2, y2, x, y;
int left, top, right, bottom;
int min_x, i, j, cur_y;
printf("Program 4 by team X\n");
while(scanf("%d %d %d %d %d %d",
&x0, &y0, &x1, &y1, &x2, &y2) != EOF)
{
//初始化case
pts_top = -1;
min_x = 10;
left = __min(__min(x0, x1), x2);
top = __max(__max(y0, y1), y2);
right = __max(__max(x0, x1), x2);
bottom = __min(__min(y0, y1), y2);
//在矩形整数阵列中搜寻三角形内部的点
for(y = top; y >= bottom; y--)
{
for(x = left; x <= right; x++)
{
if( Direction(x0, y0, x1, y1, x, y) <= 0) continue;
if( Direction(x1, y1, x2, y2, x, y) <= 0) continue;
if( Direction(x2, y2, x0, y0, x, y) <= 0) continue;
//这是一个内部的点
++pts_top;
pts[pts_top].x = x;
pts[pts_top].y = y;
//更新最左的点
if(x < min_x) min_x = x;
}
}
//打印输出结果！
cur_y = -10; //当前y坐标
for(i = 0; i <= pts_top; i++)
{
//换行了?
if(pts[i].y != cur_y)
{
cur_y = pts[i].y;
//不是第一行，则换行！
if(i > 0) printf("\n");
//本行前面的前导打印多少个空格？
for(j = 0; j < ( pts[i].x - min_x ) * 9; j++)
printf(" ");
}
else
{
//没有换行，则在两个点之间打印一个空格
if(i > 0) printf(" ");
}
printf("(%2d, %2d)", pts[i].x, pts[i].y);
}
//case结束后还需要输出一个空行！
printf("\n\n");
}
printf("End of program 4 by team X\n");
return 0;
}
（5）ZOJ 1244. Definite Values (0.2)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1244
最开始只有变量 a 有确定值，执行一系列赋值语句后，要求按字典顺序，输出所有有确定值的变量。如果任何变量都没有确定值，输出 none 。但这个题题目里没有明确的说清楚，就是所有变量名都是单字母，有了这个假设这个题目其实非常简单。但如果我们不考虑这一点，而是变量名任意，那显然还要建立符号表，又要变得更麻烦。
zoj1244
#include <stdio.h>
char variables[26];
int main(int argc, char* argv[])
{
char line[32];
int n, i, nCase = 0, charCount;
while(1)
{
scanf("%d", &n);
if(n == 0) break;
getchar(); /* 取走回车符号 */
++nCase;
/* Init: a is definite. */
variables[0] = 1;
for(i = 1; i < 26; i++)
variables[i] = 0;
for(i = 0; i < n; i++)
{
gets(line);
variables[line[0]-'a'] = variables[line[4]-'a'];
}
printf("Program #%d\n", nCase);
charCount = 0;
for(i = 0; i < 26; i++)
{
if(variables[i] > 0)
{
line[charCount] = 'a' + i;
charCount++;
}
}
if(charCount > 0)
{
for(i = 0; i < charCount; i++)
{
printf("%c ", line[i]);
}
printf("\n\n");
}
else printf("none\n\n");
}
return 0;
}
（6）ZOJ 1858. Soundex (0.2)
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1858
把单词按照发音归类，给出一个单词的拼写，按照规则求出这个单词的一个发音归类代码。
zoj1858_app
#include <stdio.h>
#include <string.h>
void GetSoundexCode(char* buf, const char* word)
{
int i;
char last_code = -1, cur_code;;
char* strs[6] = { "BFPV", "CGJKQSXZ", "DT", "L", "MN", "R" };
char* pDest = buf;
const char* pSrc = word;
while(*pSrc)
{
cur_code = -1;
for(i = 0; i < 6; i++)
{
if(strchr(strs[i], *pSrc) != NULL)
{
cur_code = '1' + i;
break;
}
}
if(last_code != cur_code && cur_code > 0)
{
*pDest = cur_code;
++pDest;
}
last_code = cur_code;
++pSrc;
}
//null-terminator!
*pDest = 0;
}
int main(int argc, char* argv[])
{
char line[24], code[24];
while(gets(line) != NULL)
{
GetSoundexCode(code, line);
printf("%s\n", code);
}
return 0;
}
备注：题目后面括号内的数字为我的主观认定难度值。
