ZOJ 简单题集合（四）

（1）ZOJ 1016. Parencodings

题意：把一个括号表达式 S，从 P 编码转换为 W 编码。

P 编码：P = P1，P2, ... , Pn; 其中 Pi  是 S 的第 i 个右括号前面的左括号个数。

W 编码：W = W1, W2, ... , Wn; 对于 S 中的某一个右括号 a，Wi 是从与 a 匹配的左括号开始数起，数到 a 为止的右括号个数。

 

例如：S (((()()())))
P-编码： 4 5 6 6 6 6；
W-编码： 1 1 1 4 5 6；

 

分析：编码的元素个数就是右括号个数，也就是字符串S的一半长度。根据 P 编码建立起 S 字符串，然后根据 W 编码的定义进行转换。这里转换成 W 编码时，虽然是线性扫描，但是存在重复扫描的现象，但并没有利用已经扫描过的信息。潜意识里感觉有可能有优化的余地。不过这个题目规模很小，所以意义不大。

 

zoj_1016

#include <stdio.h>
#include <string.h>

char str[256];

/* 根据 P 编码建立括号表达式 */
void init_from_p(int* p, int length)
{
    int i, j;
    int index = 0;
    int left_count = 0;

    for(i = 0; i < length; i++)
    {
        for(j = 0; j < (p[i] - left_count); j++)
        {
            str[index] = '(';
            ++index;
        }
        left_count = p[i];
        str[index] = ')';
        ++index;
    }
    str[index] = '\0';
}

/* 根据建立的括号表达式转换到 W 编码 */
void convert_to_w(int* w)
{
    int index = 0, depth = 0;
    int right_count = 0;
    char *p = str, *p2;
    while(*p)
    {
        if(*p == ')')
        {
            right_count = 1;
            depth = 1;
            p2 = p - 1;
            while(depth > 0)
            {
                if(*p2 == ')')
                {
                    right_count++;
                    depth++;
                }
                else if(*p2 == '(')
                    depth--;
                --p2;
            }
            w[index] = right_count;
            ++index;
        }
        ++p;
    }
}

int main(int argc, char* argv[])
{
    int t, n, i, j;
    int p[24], w[24];

    scanf("%ld", &t);
    for(i = 0; i < t; i++)
    {
        scanf("%ld", &n);
        for(j = 0; j < n; j++)
            scanf("%ld", p + j);

        memset(str, 0, sizeof(str));
        init_from_p(p, n);
        convert_to_w(w);

        for(j = 0; j < (n - 1); j++)
            printf("%ld ", w[j]);

        printf("%ld\n", w[j]);
    }
    return 0;
}

 

（2）ZOJ 1434. Frogger's For Dinner

题意：一个比较有趣的模拟题目。一只青蛙要横穿过马路，马路中间有双向的 8 车道，上面分布着汽车，用 10 X 10 的网格表示。青蛙可以从选择任何一列向下穿越（之后青蛙只能位于这一列），汽车是“折回式”循环行驶的，即每一行（车道）上的汽车的速度相同（以免发生车祸）。青蛙前进的规则是，青蛙先前进一行，然后所有汽车沿着自己的方向前进 N 格，如果青蛙撞到汽车（重叠），或者汽车走过的轨迹覆盖到了青蛙的位置，则青蛙被杀死。题目要求的本质是判断青蛙是否能够成功穿过马路。

 

分析：如果有汽车的速度是 9，显然该汽车一次移动轨迹可以完整覆盖所有列，则青蛙必然无法穿过。如果一行上摆满 10 辆汽车，显然青蛙也无法穿过。这可以使我们提前确定答案。注意，事后发现下面的代码中直接对 map 做了实时改动，但是也 AC 了，深层原因我没有去想。实际上每尝试一列，都应该使用 map 的全新副本进行模拟，map 本身不要进行任何变动。 

 

zoj_1434

#include <stdio.h>
#include <string.h>

char map[10][10];

/* run one row down. return 1 if the frog is alive */
/* row, col: the position of the frog */
int run(int frogRow, int frogCol)
{
    char tmpRow[12];
    int row, col;
    int x2;
    int bAliving = 1;
    for(col = 0; col < 10; col++)
    {
        if(map[frogRow + 1][col] != 0)
        {
            if(frogRow + 1 <= 4)
                x2 = col - map[frogRow + 1][col];
            else
                x2 = col + map[frogRow + 1][col];

            /* the frog is killed ? */
            if(x2 < 0)
            {
                if(frogCol <= col || frogCol >= (x2 + 10))
                    return 0;
            }
            else if(x2 > 9)
            {
                if(frogCol >= col || frogCol <= (x2 - 10))
                    return 0;
            }
            else
            {
                if((frogCol - col) * (frogCol - x2) <= 0)
                    return 0;
            }
        }
    }

    /* make the vehicles run */
    for(row = 1; row <= 8; row++)
    {
        memset(tmpRow, 0, sizeof(tmpRow));
        for(col = 0; col < 10; col++)
        {
            if(map[row][col] != 0)
            {
                if(row <= 4)
                    x2 = col - map[row][col];
                else
                    x2 = col + map[row][col];

                if(x2 < 0) x2 += 10;
                else if(x2 > 9) x2 -= 10;

                tmpRow[x2] = map[row][col];
            }
        }
        memcpy(map[row], tmpRow, 10);
    }
    return 1;
}

int can_across()
{
    int frogRow, frogCol;
    for(frogCol = 0; frogCol < 10; frogCol++)
    {
        frogRow = 0;
        while(1)
        {
            if(run(frogRow, frogCol))
                frogRow++;
            else
                break;

            if(frogRow == 9)
                return 1;
        }
    }
    return 0;
}

int main(int argc, char* argv[])
{
    char line[48];
    int i, j, car_count;
    int bCanAcross;
    while(gets(line) != NULL) /* START */
    {
        bCanAcross = 1; /* resume the frog can across.*/
        memset(map, 0, sizeof(map));
        for(i = 1; i <= 8; i++)
        {
            gets(line);
            car_count = 0;
            for(j = 0; j < 10; j++)
            {
                map[i][j] = line[j * 2] - '0';
                if(map[i][j] == 9)
                    bCanAcross = 0; /* the car's speed is too fast! */
                if(map[i][j] != 0)
                    car_count++;
            }
            if(car_count == 10) /* there are too many cars */
                bCanAcross = 0;
        }
        gets(line); /* END */

        if(bCanAcross)
            bCanAcross = can_across(); /* test which col can across */

        if(bCanAcross) printf("LEFTOVER POSSUM\n");
        else printf("FROGGER\n");
    }
    return 0;
}

 

（3）ZOJ 1707. Automatic Editing

题意：给出一个字符串，和 n 条查找替换规则。依次应用这些规则，然后输出处理后的结果。注意，1）每次都从头开始搜索要替换的字符串；2）一旦使用完了某条规则（即要查找的单词不再出现），之后就不能再次使用这条规则。3）大小写重要。

 

zoj_1707

#include <stdio.h>
#include <string.h>

char find[10][96];
char replace[10][96];

void edit(int n, char* text, char* result)
{
    int i, len;
    char tmp[256];
    char* p = NULL;
    strcpy(tmp, text);
    for(i = 0; i < n; i++)
    {
        len = strlen(find[i]);
        while((p = strstr(tmp, find[i])) != NULL)
        {
            *p = 0;
            sprintf(result, "%s%s%s", tmp, replace[i], p + len);
            strcpy(tmp, result);
        }
    }
}

int main(int argc, char* argv[])
{
    char line[256], result[256];
    int n, i;
    while(1)
    {
        scanf("%ld", &n);
        if(n == 0) break;
        getchar(); /* discard the newline char */
        for(i = 0; i < n; i++)
        {
            gets(find[i]);
            gets(replace[i]);
        }
        gets(line);
        edit(n, line, result);
        printf("%s\n", result);
    }

    return 0;
}

 

（4）ZOJ 1879. Jolly Jumpers

题意：一个由 n 个整数组成的数列，如果相邻元素的差值的绝对值恰好为 1 到 n-1，则该数列被称称为 jolly jumper。

例如：[ 1 4 2 3 ] 是一个 jolly jumper，因为其相邻元素的差值的绝对值分别是 3，2，1。只包含一个元素的数列也定义为 jolly jumper。判断一个给定的数列是否是 jolly jumper。（n < 3000 ）

 

zoj_1879

#include <stdio.h>
#include <string.h>
#include <math.h>

char flags[3000];

int main(int argc, char* argv[])
{
    int n, i, lastNum, curNum, tmp;
    int bFindResult, bIsJolly;
    while(scanf("%ld", &n) != EOF)
    {
        memset(flags, 0, sizeof(flags));

        bFindResult = 0;
        bIsJolly = 1;

        scanf("%ld", &lastNum);
        for(i = 1; i < n; i++)
        {
            scanf("%ld", &curNum);

            if(bIsJolly)
            {
                tmp = (int)fabs(curNum - lastNum);
                lastNum = curNum;

                if(tmp == 0 || tmp > n-1 || flags[tmp])
                    bIsJolly = 0;
                else
                    flags[tmp] = 1;
            }
        }

        if(bIsJolly) printf("Jolly\n");
        else printf("Not jolly\n");
    }
    return 0;
}

 

（5）ZOJ 1889. Ones （本文重点）

题意：给出一个不能被 2 和 5 整除的整数 n （0 <= n <= 10000），它的某个倍数用 10 进制表示全部是 1 组成。问符合这个条件的倍数数字由多少个 1 组成。

例如：n = 7 时， 7 * 15873 = 111111；包含 6 个 1，因此结果为 6。

分析：可以很明显的看到，该体产生的数字已经远超过整型类型表达的范围。因此不能试图用整型去寻找该倍数。根据题目，我们只需要确定存在这样一个数字，由 m 个 1 组成，它能被 n 整除。因此只需要试验 m 的值，从 1 开始逐渐增加，直到找到第一个可以被 n 整除的数字为止。我们只需要考虑该数字除以 n 的余数即可（即 mod n）。假设 m 时余数为 remain，容易得出 m = m + 1 时，余数为 (remain * 10 + 1) mod n; 

 

zoj_1889

#include <stdio.h>
int main(int argc, char* argv[])
{
    int n, result, remain;
    while(scanf("%ld", &n) != EOF)
    {
        remain = 1 - 1 / n * n;
        result = 1;
        while(remain != 0)
        {
            result++;
            remain = remain * 10 + 1;
            remain = remain - remain / n * n;
        }
        printf("%ld\n", result);
    }
    return 0;
}

（6）ZOJ 2423. Fractal

题意：要求打印出一个分形图。分形图用X字符表示，定义如下表。要求绘制出度数为 n （n <= 7) 的分形图。

degree box fractal
1 X
2
X  X

  X

X  X
用 B(n-1) 表示 n-1 度  
B(n-1)            B(n-1)

          B(n-1)

B(n-1)            B(n-1)

 

注意：任何一行结尾不可以有多余的空格，否则将会导致“Presentation Error”。

分析：采用根据其递归定义，用递归函数初始化出一个模板，然后滤除每一行结尾的空格后输出即可。代码中使用了 5 个对 B（n-1）的调用，这里实际上 5 个子矩阵的内容是完全一样的，因此只需要调用一次左上角的 B（n-1），然后把它拷贝到其他四个位置即可，这样可以大大减少递归调用次数，提高代码效率。此题目度数很小，因此可以不做出优化。

 

zoj_2423

#include <stdio.h>
#include <string.h>

char map[732][732];

void fractal(int n, int row, int col, int length)
{
    if(n == 1)
    {
        map[row][col] = 'X';
        return;
    }
    else
    {
        int k = length / 3;
        fractal(n-1, row, col, k);
        fractal(n-1, row, col + k * 2, k);
        fractal(n-1, row + k, col + k, k);
        fractal(n-1, row + k * 2, col, k);
        fractal(n-1, row + k * 2, col + k * 2, k);
    }
}

void trim(int length)
{
    int row, col;
    for(row = 0; row < length; ++row)
    {
        for(col = length; col >= 0; --col)
            if(map[row][col] == 'X') break;

        map[row][col + 1] = '\0';
    }
}

void print_map(int length)
{
    int row;
    for(row = 0; row < length; ++row)
        printf("%s\n", map[row]);
    printf("-\n");
}

int main(int argc, char* argv[])
{
    int length[] = { 0, 1, 3, 9, 27, 81, 243, 729 };
    int n;
    while(scanf("%ld", &n) != EOF)
    {
        if(n < 0) break;
        memset(map, ' ', sizeof(map));
        fractal(n, 0, 0, length[n]);
        trim(length[n]);
        print_map(length[n]);
    }
    return 0;
}

 

（7）ZOJ 2886. Look and Say

题意：字符串处理题目。一个字符串 122344111 可以被描述为“1个1，2个2，1个3，2个4，3个1”。因此，其后继是“1122132431”。类似的，1111111111 后继是 101。通常一个字符串的前继不是唯一的，例如 112213243 个 1 组成的数字，后继也是 1122132431。给出一个字符串，输出它的后继。

 

zoj_2886

#include <stdio.h>
void look_say(char *text)
{
    char *p = text;
    int count = 0;
    while(*p)
    {
        count = 1;
        while(p[1] == p[0])
        {
            ++count;
            ++p;
        }
        printf("%ld%c", count, *p);
        ++p;
    }
}

int main(int argc, char* argv[])
{
    char line[1024];
    int n, i;
    scanf("%ld\n", &n);
    for(i = 0; i < n; i++)
    {
        gets(line);
        look_say(line);
        printf("\n");
    }
    return 0;
}

（8）ZOJ 3488. Conic Section

题意：给出方程 ax2+bxy+cy2+dx+ey+f=0 的系数，判断该曲线是圆，椭圆，双曲线还是抛物线。

分析：此题比较坑爹，反复提交失败后，我忍不住搜索了这个题目。原来方程的系数应该定义为浮点数，而不是整数！了解此题后，则此题毫无难度，尽管给了一个比较有趣的平面截双圆锥的图，但纯属科普作用。

 

zoj_3488

#define EQUAL(a, b) (fabs((a)-(b)) < 0.0000001)

#include <stdio.h>
#include <math.h>

int main(int argc, char* argv[])
{
    int T, i;
    double a, b, c, d, e, f;
    scanf("%ld", &T);
    for(i = 0; i < T; i++)
    {
        scanf("%lf %lf %lf %lf %lf %lf",
            &a, &b, &c, &d, &e, &f);

        if(EQUAL(a*c, 0))
            printf("parabola\n");
        else if(a*c > 0)
        {
            if(EQUAL(a, c))
                printf("circle\n");
            else
                printf("ellipse\n");
        }
        else if(a*c < 0)
            printf("hyperbola\n");
    }
    return 0;
}

 

时间： 2024-10-10 12:58:03

ZOJ 简单题集合（四）的相关文章

ZOJ 简单题集合

这部分题由于过于简单,属于白送题目,因此把所有特别简单题的合集于此. 1048:统计某人12个月的银行帐户余额的平均数.(简单的令人汗!) Code_1048/*ZOJ 1048: 统计小数的平均数!居然就是12个double求平均数..汗!*/ #include <stdio.h>double balance[12];int main() {  int i;  double sum=0,aver;  for(i=0;i<12;i++)  {   scanf("%lf"

ZOJ 简单题集合（二）

对以下简单题,我同时给出一个我主观认为的难度值(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 <stri

c语言编程-关于C语言字符串的简单题求助

问题描述 关于C语言字符串的简单题求助 进行对输入的字符串重新排列,要求字母在前,数字在后,并不改变字母和数字之间的字符排列顺序. 解决方案 #include void main() { char a[10] = {0}, b[10] = {0}, c[10]={0}; int n = 0, m = 0, k = 0,f = 0; printf("输入字符串:"); gets(a); for(int j = 0; j < 10; j++) { if((a[j] >= 'a'

源代码-求大神，ZOJ 1002题怎么老出错

问题描述 求大神,ZOJ 1002题怎么老出错 题目链接http://acm.zju.edu.cn/onlinejudge/showRuns.do?contestId=1 提交结果老是的回复是 wrong answer. 样本输入输出都正确. 我提交是用C++提交的,这个应该不成问题 求大神指点. C语言 以下是我提交的源代码 #include"stdio.h" #define N 6 char net[N][N];//最大存储数据容量 int MAX,max;//MAX为最终最大值,

多家地方电视台播猜谜节目简单题骗高话费

新京报制图/丁华勇吉林卫视播出的电视猜谜节目.青海卫视播出的电视猜谜节目. 一边是高额现金大奖,一边是简单得看一眼就能知道答案的猜谜题目.近来,此类有奖竞猜节目出现在不少电视台的清晨和午夜时段,丰厚的奖项,加上主持人"快拿起电话,5000元大奖就是你的."的诱惑,吸引不少观众参与.但真正打过电话的人,都大呼"上当". 6月29日凌晨1时30分许,几家地方卫视频道不约而同的播出电视猜谜节目."什么酒需要两个人一起喝?"节目中不断有语音提示"

c# GDI+简单绘图（四）

前几篇我已经向大家介绍了如何使用GDI+来绘图,并做了一个截图的实例,这篇我向大家介绍下如何来做一个类似windows画图的工具. 个人认为如果想做一个功能强大的绘图工具,那么单纯掌握GDI还远远不够,我的目前也只能做一个比较简单的绘图工具了．不足之处,欢迎大家讨论! 先来看一下最终效果吧: 主要实现功能:画直线,矩形,橡皮,圆形,切换颜色,打开图片,保存图片,清除图片,手动调节画布大小;软件刚启动时,为一张空白画布,我们可以直接在画布上绘画,也可以通过菜单中的"打开",导入一张图片,

HDOJ 1326 Box of Bricks(简单题)

Problem Description Little Bob likes playing with his box of bricks. He puts the bricks one upon another and builds stacks of different height. Look, I've built a wall!'', he tells his older sister Alice.Nah, you should make all stacks the same heigh

HDOJ 1323 Perfection（简单题）

Problem Description From the article Number Theory in the 1994 Microsoft Encarta: "If a, b, c are integers such that a = bc, a is called a multiple of b or of c, and b or c is called a divisor or factor of a. If c is not 1/-1, b is called a proper di

HDOJ/HDU 2568 前进(简单题)

Problem Description 轻松通过墓碑,进入古墓后,才发现里面别有洞天. 突然,Yifenfei发现自己周围是黑压压的一群蝙蝠,个个扇动翅膀正准备一起向他发起进攻! 形势十分危急! 好在此时的yifenfei已经不是以前那个经常被lemon抢走MM的菜鸟了!面对众多蝙蝠的嗜血狂攻,只见yifenfei使出轻灵的剑法,刷,刷,刷,瞬间搞定-- 现已知yifenfei使用了2招(剑招A和剑招B):剑招A,一招能杀死一半的蝙蝠.但是如果当前的蝙蝠数为奇数,那么就必须先出一招剑招B杀死其中