# ZOJ 简单题集合（三）

（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;}

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1061

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

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）

依次给出一个三角形按逆时针方向排列的三个顶点的坐标（所有坐标范围在 -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

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;}

+ 订阅