ZOJ 简单题集合(三)-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

ZOJ 简单题集合(三)

简介: (1)ZOJ 1045. HangOver (0.1) http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1045 在桌子边码扑克牌,给出表示扑克牌延伸出桌子的距离的浮点数,问需要多少张牌。

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

 

备注:题目后面括号内的数字为我的主观认定难度值。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: