C论坛算法团队首战西安电子科技大学OJ - C语言论坛

| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛 |

编程论坛 → 开发语言 → 『 C语言论坛』 → C论坛算法团队首战西安电子科技大学OJ

我的收件箱(0)

欢迎加入我们，一同切磋技术

共有 42026 人关注过本帖， 47 人收藏

标题：C论坛算法团队首战西安电子科技大学OJ

只看楼主加入收藏

beyondyf

等　级：贵宾
威　望：103
帖　子：3282
专家分：12654
注　册：2008-1-21

第 21 楼

得分:0

Problem 1021 - Binary Tree

Problem 1021 - Binary Tree

Time Limit: 1000MS Memory Limit: 65536KB Difficulty:
Total Submit: 51 Accepted: 21 Special Judge: No

Description

Tiantian is studying “Data Structure” now, and the Binary Tree took her attention. It is a kind of data structure that has the property of tree and with its special structure and operation. For its property: every node(except the root) in the tree has only one parent and no more than two children, we may sometime construct algorithms with the complex of O(nlogn) or O(logn) with the help of it! How to construct a nice binary tree? Here comes the problem.

We have got an ” inorder traversal” sequence of a binary tree, each element in the sequence represents the power of the node. Your task is to build the tree with the maximum cost.
A leaf gets the cost of its own power, and an empty subtree gets the cost of 1.
How to calculate the power for building a binary tree? Take the left subtree and the right subtree with cost of t1, t2, the root power with k .
cost of the binary tree = t1 * t2 + k

Input

The input contains several test cases. Each test case starts with a line containing an integer N (1<=N<=30), which describes the number of the nodes in the binary tree. And then N integers follow in the next line, separated by a space, to describe the N nodes’ power. Each power is a positive integer no larger than 100. The total cost of building the binary tree is no larger than 4,000,000,000.

Output

For each test case, output only one line of one integer, to tell the maximum cost of building the binary tree.

Sample Input

5
5 7 1 2 10

Sample Output

145

Hint

Source

6th Xidian University Collegiate Programming Contest(2008.9)

分析

计算一个二叉树的最大cost。cost值的定义在题目描述中，这里不再赘述。

题目的输入数据给出的是一棵二叉树的中序遍历序列。具有相同中序遍历序列的N个结点的二叉树大概有N！棵。

所以如果打算穷举所有满足条件的二叉树来计算最大的cost值是不现实的，100的阶乘超过了宇宙中所有原子数目的总和。

还是先从二叉树中序遍历序列的结构分析开始。

对于有n个结点的二叉树的中序遍历序列，如果第i个结点为根结点，那么序列中1 至 (i - 1)结点都是i结点的左子树中的结点，(i + 1)至n结点都是i结点的右子树中的结点。

设f(i, j)表示由中序遍历序列中第i到第j结点构成的子树的cost值

那么f(i, j) = max{f(i, k - 1) * f(k + 1, j) + f(k, k) | i <= k <= j}

分析到这儿，解决这一问题的动态规划算法模型已经出来了。我们只需要选择一个合适的计算顺序计算出f(1,n)即得到最终我们需要的答案。（PS：在我的代码选择的下标是从0开始，即最终的结果为f(0,n-1)，因为计算过程很简单，就没有写单独的函数，直接写在main函数里了）

程序代码：

#include<stdio.h>
int main()
{
    unsigned f[100][100];
    int n, i, j, k, m, t;
    for(; scanf("%d", &n) != EOF; printf("%u\n", f[0][n - 1]))
    {
        for(i = 0; i < n; i++) scanf("%u", &f[i][i]);
        for(i = n - 2; i >= 0; i--)
        for(j = i + 1; j < n; f[i][j++] = m)
        for(m = 0, k = i; k <= j; k++)
        if(m < (t = (k <= i ? 1 : f[i][k - 1]) * (k >= j ? 1 : f[k + 1][j]) + f[k][k])) m = t;
    }
    return 0;
}

重剑无锋，大巧不工

2012-10-17 01:00

beyondyf

等　级：贵宾
威　望：103
帖　子：3282
专家分：12654
注　册：2008-1-21

第 22 楼

得分:0

Problem 1022 - Calculating Area

Problem 1022 - Calculating Area

Time Limit: 1000MS Memory Limit: 65536KB Difficulty:
Total Submit: 41 Accepted: 13 Special Judge: No

Description

Tiantian got a chance to get a house! To her surprise, the house has a shape of triangle! What Tiantian has to do is to select three points from the points given to her, without any other points inside the triangle constructed by the selected points. Of course, she’s sure to select the ones which to make the house the largest.

Input

The input contains several test cases. For each test case there are several lines of data. The first line is the number of points: at least 4, and at most 15. For each point, there is a data line that starts with a one character label for the point and is followed by its coordinates which are nonnegative integers less than 100. The first label is A, and the next is B, and so on.
The end of input is indicated by a 0 for the number of points. The sample input below corresponds to the diagram in the problem.

Output

For each test case there is one line of output. It contains the three labels of the vertices of the house, listed in increasing alphabetical order, with no blank spaces.

Sample Input

6
A 1 0
B 4 0
C 0 3
D 1 3
E 4 4
F 0 6
0

Sample Output

BEF

Hint

Source

6th Xidian University Collegiate Programming Contest(2008.9)

分析

这个问题其实也没什么可讲的，在点集内选择三点构成三角形，判断三角形内是否包含其它点并计算三角形的面积。

三角形的面积计算方法有很多（估计很多人最先想到的是海伦公式），由于题目中点的参数是笛卡尔坐标系下的参数，所以适合用延边积分的方式计算。

我的代码中area2函数计算的就是由p0,p1,p2三点构成的三角形的面积关系。准确的说是这个三角形面积的2倍。因为问题中需要的只是比较面积的大小，并不需要实际面积，而这种2倍的关系并不影响比较。这样在面积的计算中可以减少一次除法运算。

当然，由于点坐标参数都是整数，所以这个除法运算可以用移位运算代替，也消耗不了多少时间，但终归是没必要的步骤。

判断其它点是某在三角形内，传统的做法是用射线法。但对于三角形而言，使用这种方法没什么必要，有点小题大作，这里我使用了另一种方法，事实上这种方法适用于任意凸多边形，但当边数过多时它的效率会比射线法低。这里再多说一句。任何算法都有它适合的应用范围，学习算法不光是了解各种算法的实现方法，更重要的是能根据具体的问题选择适合的算法。

简单说一下这种判断某一点是否在三角形边的方法。

取这一点与原三角形的任意两个顶点构成一个新三角形。这样应对顶点的不同取法，一共可以构成三个新三角形。

如果该点位于原三角形之内或边上，那么这三个新三角形的面积之和将等于原三角形的面积。

如果该点位于原三角形之外，则这三个新三角形的面积之和将大于原三角形的面积。

这种判断方法证明过程很简单，也很适合在极坐标系下使用。

程序代码：

#include<stdio.h>

typedef struct { int x; int y; } Point;

int area2(Point p0, Point p1, Point p2)
{
    int a;
    a = (p1.x - p0.x) * (p1.y + p0.y);
    a += (p2.x - p1.x) * (p2.y + p1.y);
    a += (p0.x - p2.x) * (p0.y + p2.y);
    return abs(a);
}

int inside(Point p0, Point p1, Point p2, Point p3)
{
    int a, b;
    a = area2(p1, p2, p3);
    b = area2(p0, p1, p2);
    b += area2(p0, p2, p3);
    b += area2(p0, p3, p1);
    return a == b;
}

void max_triangle(Point * p, int n)
{
    int a = 0, ta, i, j, k, t;
    char s[4] = {};
    for(i = 0; i < n; i++)
    for(j = i + 1; j < n; j++)
    for(k = j + 1; k < n; k++)
    {
        ta = area2(p[i], p[j], p[k]);
        if(ta <= a) continue;
        for(t = 0; t < n; t++)
        {
            if(t == i || t == j || t == k) continue;
            if(inside(p[t], p[i], p[j], p[k])) break;
        }
        if(t == n)
        {
            a = ta;
            s[0] = 'A' + i;
            s[1] = 'A' + j;
            s[2] = 'A' + k;
        }
    }
    puts(s);
}       
   
int main()
{
    Point p[16];
    int n, i;
    char s[8];
    for(; scanf("%d", &n), n; max_triangle(p, n))
    for(i = 0; i < n; i++) scanf("%s%d%d", s, &p[i].x, &p[i].y);
    return 0;
}

重剑无锋，大巧不工

2012-10-18 11:48

beyondyf

等　级：贵宾
威　望：103
帖　子：3282
专家分：12654
注　册：2008-1-21

第 23 楼

得分:0

第23题我测试了很多数据，结果提交依旧WA。现在已经开始怀疑题目本身有问题了。

先不枉下论断，多数还是自己思虑不周。把自己的代码先贴上来供各位参考。

程序代码：

#include<stdio.h>
long long f(long long a, int b, int k)//a为题中数n，b为题中基数p，k为题中某数字k；我选了自己喜欢的命名含意
{
    long long c = 0, p, q, t; //c统计次数，p第i位的基权，q第i位前（高位）的值，t是个余数一两句话解释不清楚，看代码
    if(k >= b) return 0;
    for(p = 1, q = a; q /= b; p *= b)
    {
        c += k ? q * p : (q - 1) * p;
        t = (a - q * p * b) - k * p + 1; //这里没有使用取模运算是为了防止溢出
        c += t < 0 ? 0 : t < p ? t : p;
    }
    t = (k ? a - k * p : 0) + 1;
    return c + (t <= 0 ? 0 : t < p ? t : p);
}
int main()
{
    long long n;
    int p, k;
    char s[4];
    for(; scanf("%lld%d%s", &n, &p, s) != EOF; printf("%lld\n", f(n, p, k)))
        k = s[0] >= 'a' ? s[0] - 'a' + 36 : s[0] >= 'A' ? s[0] - 'A' + 10 : s[0] - '0';
    return 0;
}

重剑无锋，大巧不工

2012-10-22 09:25

C_戴忠意

等　级：蜘蛛侠
威　望：2
帖　子：575
专家分：1349
注　册：2011-10-21

第 24 楼

得分:0

Problem 1049 - 斐波那契数 Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 1383  Accepted: 289  Special Judge: No Description
Description
斐波那契数列是如下的一个数列，0,1，1，2，3，5……，其通项公式为F（n）=F（n-1）+F（n-2），（n>=2） ,其中F（0）=0，F（1）=1，你的任务很简单，判定斐波契数列的第K项是否为偶数，如果是输出YES，否则输出NO
Input第一行，T，表示有T个测试样例。
接下来T行，每行一个数据K（0<=K<=10^10000），表示要判定的是哪一项。Output如果第K项是偶数，输出YES，否则输出NO。
Sample Input
2
0
1
Sample Output
YES
NO

算法：
本题算法应该是大数的除法，初学者大家不要见笑我的代码。
题目意思判断第N项斐波那契数是否为偶数
推导方法：
偶数=奇数+奇数=偶数+偶数；
奇数=奇数+偶数；
fibonacci（n）= fibonacci（n-1）+ fibonacci（n-2）；
0 1 1 2 3 5 8 13 21 ...
每隔两项是偶数。
因此判断斐波那契数是否为偶数既是求斐波那契第N项是否为3的倍数
因为本题数据量在10^10000范围内，所以只有借助大数模拟的方法实现。
以下是代码：

程序代码：

#include <stdio.h>
#include <string.h>
#define N 100005

int main()
{
    char str[N];
    int i,nNum,divisor,remainder;
    scanf("%d",&nNum);
    while(nNum--)
    {
        scanf("%s",str);
        int len=strlen(str);
        if(!strcmp(str,"1") || !strcmp(str,"2") || !strcmp(str,"4") || !strcmp(str,"5") || !strcmp(str,"7") || !strcmp(str,"8"))
        {
            printf("NO\n");
            continue ;
        }
        for(i=0,divisor=0,remainder=0;i<len;i++)
        {
            //printf("%d\n",i);
            if(!strcmp(str,"0")) break ;
             divisor*=10;
            divisor+=str[i]-'0';
            if(divisor<3 && i!=len-1) divisor=divisor*10+(str[++i]-'0');
            divisor=divisor%3;
            remainder=divisor;
            //printf("%d %d\n",divisor,remainder);
        }
        if(remainder) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

[ 本帖最后由 C_戴忠意于 2012-10-24 11:23 编辑 ]

编程之路定要走完……

2012-10-24 11:21

beyondyf

等　级：贵宾
威　望：103
帖　子：3282
专家分：12654
注　册：2008-1-21

第 25 楼

得分:0

欢迎 C_戴忠意的加入，如果我没记错你是内科大的吧，和老杨是校友。还记得你改了个名字，怎么不用那个了？

小戴对1049题的分析很不错，原理部分阐述的很到位了，希望再接再厉！

鼓励完了提点优化意见，旨在帮助君更上一层楼。

1.关于N是否为3的倍数的判断方法，小戴写的没错，但效率不够好。

如果设N的倍数长度为m，则小戴在计算它是否为3的倍数时需要进行m次乘法、m次加法、还有m次取模运算。

这个过程与我们列竖式手工做除法的过程是一样的。

但还记不记得我们小学时就学过另一种判断一个数是不是3的倍数的方法？

如果一个数每位上数字的和是3的倍数，那么这个数也是3的倍数。

应用这一结论，可以将计算过程改进到只需进行m次加法和1次取模运算。

2.代码中有过多的冗余逻辑，除最后一个if语句外，其它的三个if都没有什么意义，完全可以删掉，对效率没什么影响（还会有些许提高）。

代码的结构逻辑反映的是作者的思维逻辑，小戴的思维逻辑还须历练。只要坚持，相信会有化境的一天。

最后送一段我的代码，希望对小戴及各位喜欢算法的朋友有所帮助。留给各位一个思考题，为什么我的代码中没有减'0'这步运算但结果也是正确的？

程序代码：

#include<stdio.h>
int main()
{
    char s[10001], * p;
    int t, r;
    for(scanf("%d", &t); t--; puts(r % 3 ? "NO" : "YES"))
    for(scanf("%s", p = s), r = 0; *p; r += *(p++));
    return 0;
}

重剑无锋，大巧不工

2012-10-24 21:16

C_戴忠意

等　级：蜘蛛侠
威　望：2
帖　子：575
专家分：1349
注　册：2011-10-21

第 26 楼

得分:0

Problem 1031 - 走楼梯 Time Limit: 1000MS Memory Limit: 65536KB Difficulty:

Total Submit: 590 Accepted: 296 Special Judge: No Description　　ZYF最喜欢的活动是走楼梯！所以他每次去实验室总会坐电梯随机到一个楼层，然后走楼梯到实验

室所在的楼层，并为此得意不已。现在的问题来了，已经知道每两层楼之间的楼梯级数、ZYF坐电梯要到达的楼层、实验室所在楼层，那么ZYF每次得走多少级楼梯才能到达实

验室？

Input输入数据的第一行是一个正整数T（0＜T≤100），表示有T组测试数据。

每组测试数据有两行：第一行为三个整数N, A, B（0＜N≤100, 0＜A, B≤N），表示有N层楼，ZYF坐电梯到的楼层A，实验室所在楼层为B；第二行包括N–1个整数，其中第i

个整数代表从第i层到第i + 1层之间的楼梯级数Si（0＜Si≤100）。Output对于每组测试数据，在一行上输出一个整数P，表示ZYF到实验室所在楼层需要走P级楼梯。

Sample Input
3
6 1 5
10 10 10 10 10
6 5 1
10 10 10 10 10
10 3 7
1 2 3 4 5 6 7 8 9

Sample Output
40
40
18

这道题貌似没什么算法可言，我就是发现挺好写，直接就过了，唯一注意的就是楼梯可能从高到低。

。

程序代码：


#include <stdio.h>

int main()
{
    int i,nNum,n,a,b,res,stair[100];
    scanf("%d",&nNum);
    while(nNum--)
    {
        scanf("%d %d %d",&n,&a,&b);
        if(a > b)
        {
            a += b;
            b = a - b;
            a -= b;
        }
        if(a == b)
        {
            printf("0\n");
            continue ;
        }
        for(i=1,res=0;i<n;i++)
        {
            scanf("%d",&stair[i]);
            if((i>a && i<b) || i==a) res+=stair[i];
        }
        printf("%d\n",res);
    }
    return 0;
}

[ 本帖最后由 C_戴忠意于 2012-10-25 22:22 编辑 ]

编程之路定要走完……

2012-10-25 22:18

C_戴忠意

等　级：蜘蛛侠
威　望：2
帖　子：575
专家分：1349
注　册：2011-10-21

第 27 楼

得分:0

Problem 1032 - 找模式串 Time Limit: 1000MS Memory Limit: 65536KB Difficulty:

Total Submit: 458 Accepted: 225 Special Judge: No Description　　在字符串中查找指定的模式串是一种常见的运算，称为模式匹配。请你编写实现模式匹配的程序。

Input输入数据的第一行是一个正整数T（0＜T≤100），表示有T组测试数据。

每组测试数据有两行：第一行为字符串S（长度不超过128，全部为大写英文字母），第二行为模式串P（长度不超过20）。Output对于每组测试数据，在一行上输出一个整数，表

示模式串P在字符串S中的位置序号（若出现多次，则输出第一次出现时的位置）。若在字符串S中找不到模式串P，则输出整数-1。

Sample Input3

ABCDEF
AB
EJBBMSWJPREAEYBM
MBWEJ
DCZRZYFGJVTPWKF
ZYFG

Sample Output
0
-1
4
算法：我还是习惯性的用模拟法，因为字符串匹配KMP我也写不好。

我是这样做的，从字符串1取和字符串2的长度相等的字符依次比较字符，如果中间有不同的就继续外层循环，否则输出当前外层循环的值。

如果外层循环顺序正常执行完，那么说明不匹配输出 -1；

好，把代码附上

程序代码：

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

int main()
{
    char str1[105],str2[25];
    int i,j,len,pos,nNum;
    scanf("%d",&nNum);
    while(nNum--)
    {
        scanf("%s %s",str1,str2);
        for(i=pos=0,len=strlen(str1);i<len;i++)
        {
            for(j=i;j<i+strlen(str2);j++)
                if(str1[j]!=str2[pos++]) break ;
            if(pos==strlen(str2))
            {
                printf("%d\n",i);
                break ;
            }
            pos=0;
        }
        if(i==len) printf("-1\n");
    }
    return 0;
}

编程之路定要走完……

2012-10-25 22:50

C_戴忠意

等　级：蜘蛛侠
威　望：2
帖　子：575
专家分：1349
注　册：2011-10-21

第 28 楼

得分:0

Problem 1103 - gl & hf Time Limit: 1000MS Memory Limit: 65536KB Difficulty:

Total Submit: 400 Accepted: 242 Special Judge: No Description欢迎参加西电第九届ACM校内赛！作为一名经历了四届校赛的ACM老队员以及本次校赛的出题人，每次

校赛都让我有一种全新的感受——有第一次参加校赛时提交代码时紧张到双手发抖，也有当裁判时看到有些不明真相的人提交编译后程序时的欢乐。不管你是第几次参赛，好

好享受这一刻带给你的各种感受，经历就是一种财富。为了让大家更好地记住这悲喜交加的日子，特意准备了这么一道题：

给你一个日期，你只要输出这个日期是在校赛前还是校赛后，或者刚好就是校赛那一天（2011年5月22号）。

题目是什么意思呢？Good luck and have fun，祝大家在本次校赛取得好成绩！

Input输入数据的第一行是一个正整数T（0<T<=100），表示有T组测试数据。

每组测试数据只有一行，为三个数字Y,M,D（0<Y<=10000, 0<M<=12, 0<D<=31），表示Y年M月D号。日期符合现实日期规范。Output对于每组测试数据，在一行上输出一个字符串

：如果在校赛日前之前，则输出"before"；如果在校赛日期之后，则输出"after"；如果刚好是校赛那天，则输出"nice day"。

Sample Input3

2000 2 29
2011 5 22
2011 11 11

Sample Output

before
nice day
after

算法：判断某年某月某日是固定年月日的前后，只要从年到月挨个比较即可。
代码比较简单不说了

程序代码：

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

struct Time
{
    int year;
    int month;
    int day;
};

int main()
{
    int nNum;
    struct Time time;
    scanf("%d",&nNum);
    while(nNum--)
    {
        scanf("%d %d %d",&time.year,&time.month,&time.day);
        if(time.year > 2011) puts("after");
        else if(time.year < 2011) puts("before");
        else
            if(time.month > 5) puts("after");
            else if(time.month < 5) puts("before");
            else
                if(time.day > 22) puts("after");
                else if(time.day < 22) puts("before");
                else puts("nice day");
           
    }
    return 0;
}

[ 本帖最后由 C_戴忠意于 2012-10-26 08:32 编辑 ]

编程之路定要走完……

2012-10-26 08:26

C_戴忠意

等　级：蜘蛛侠
威　望：2
帖　子：575
专家分：1349
注　册：2011-10-21

第 29 楼

得分:0

Problem 1026 - An Easy Problem

Time Limit: 1000MS Memory Limit: 65536KB

Difficulty:

Total Submit: 249 Accepted: 103 Special Judge: No DescriptionIn mathematics, a prime number (or a prime) is a natural number which has exactly two distinc

t natural number divisors: 1 and itself. In many cases, it is not enough to know whether a number is prime; sometimes, you need to know its factors.

Every positive integer greater than 1 can be expressed as a product of prime numbers. This factorization is unique and is called the prime factorization. Fo

r example, the number 60 can be decomposed into factors 2×2×3×5, each of which is prime. Note that the same prime can appear more than once in the factor

ization. Note that the same prime can appear more than once in the factorization.

Write a program to display the prime factorization of a number n.

InputThere are multiple test cases. Each case takes one line and contains exact one integer n(2≤n≤2^31-1).

n=0 indicates the end of the input and should not be processed by your program.OutputFor each case, output the prime factorization of a number n.

Sample Input

2
60
13
0

Sample Output

2
2*2*3*5
13
算法：本题其实就是整数拆分成素数的乘积。注：任何一个大于1的整数都能拆分成几个素数的乘积。

我这算法太费时间，就是从2->n逐一去掉一个较小的素数直到不能被这个素数整除为止，接着再逐一去掉第二小、第三小...，直到除为零。

程序代码：

#include <stdio.h>

int main()
{
    long long n,num;
    int i,first;
    while(scanf("%lld",&n) && n)
    {
        for(i=2,first=1,num=n;i<=n;i++)
        {
            while(num%i==0)
            {
                num/=i;
                printf(first ? "%d" : "*%d",i);
                first=0;
            }
        }
        printf("\n");
    }
    return 0;
}

[ 本帖最后由 C_戴忠意于 2012-10-26 21:23 编辑 ]

编程之路定要走完……

2012-10-26 19:12

C_戴忠意

等　级：蜘蛛侠
威　望：2
帖　子：575
专家分：1349
注　册：2011-10-21

第 30 楼

得分:0

Problem 1054 - Daybreak 的染色问题

Time Limit: 1000MS Memory Limit: 65536KB

Difficulty:
Total Submit: 192 Accepted: 78 Special Judge: No Description 有一段长为 n (1<=n<=1000)米的栏杆,初始为白色.Boss 要求 daybreak 去对这根栏杆进行染色,给了它三种颜色的涂料,分别是红色,蓝色,黄色(daybreak 的幸运色), Boss 每次要 daybreak 染色一个区间,比如 [a,b] 代表将第 a 米到第 b 米的栏杆染成某色, r 代表红色, b 代表蓝色, y 代表黄色.

某一段有可能被重复染色,也就会发生颜色的合成,相信每个能考进西电的同学在小学都进修并精通三原色合成法则,此处不再赘述.给出 Boss 要 daybreak 染色的各区间与颜色, 帮 daybreak 计算出进行完所有染色任务后,每段栏杆的颜色.

Input第一行是数据的组数 T (1<=T<=100), 对于每组数据,
第一行是 n,m(0<=m<=1000),l. n 代表栏杆长度, m 代表要求染色的区间数,l 代表最后要考察的位置数;
第二行到第 m+1 行,每行有三个数, a(1<=a<=n), b(1<=b<=n),c. a,b 分别表示区间的端点,c 代表颜色,有如下三种取值 r,b,y;
第 m+2 行到第 m+l+1 行每行有一个数字 x,表示要输出第 x 米的颜色.同一行数据之间均用一个空格隔开,行末无空格.Output每组数据输出 l 行,代表输入中要求的第 x 米的颜色.颜色表如下
w (白色) ,r (红色) ,b (蓝色) ,y (黄色) ,p (紫色) ,o (橙色) ,g (绿色) ,k (黑色).
每组最后输出一个空行.
注:对于已经形成的染色,再将原色染上去,不会影响目前的颜色,即绿色上再染黄色还是绿色.

Sample Input

2
5 3 3
1 2 r
2 3 y
4 3 b
1
2
3
1 0 1
1

Sample Output

r
o
g

w

算法：本题太绕了，写的好烦，不过还好情况都考虑到了一次过。

红 + 黄 = 橙；
蓝 + 红 = 紫；
蓝 + 黄 = 绿；
红 + 黄 + 蓝 =黑；
红 + 绿 +　蓝　= 白；

其实我就是根据这个原理做出来的，只要把情况考虑清楚应该没问题，还是不说了，看代码吧。

程序代码：

#include <stdio.h>

typedef struct Color
{
    int a,b;
    char c;
};

char palette(char col,char color)
{
    if(col=='w') return color;
    if((col=='r' && color=='y') || (col=='y' && color=='r')) return 'o';
    else if((col=='r' && color=='b') || (col=='b' && color=='r')) return 'p';
    else if((col=='b' && color=='y') || (col=='y' && color=='b')) return 'g';
    else if((col=='p' && color=='y') || (col=='o' && color=='b') || (col=='g' && color=='r')) return 'k';
    else if(col=='g' && color=='r') return 'w';
    else return col;
}

int main()
{
    int caseNum,n,m,l,i,j,idex;
    char col;
    struct Color color[1005];
    scanf("%d-",&caseNum);
    while(caseNum--)
    {
        scanf("%d %d %d",&n,&m,&l);
        for(i=0;i<m;i++) scanf("%d %d %c",&color[i].a,&color[i].b,&color[i].c);
        for(i=0;i<l;i++)
        {
            col='w';
            scanf("%d",&idex);
            for(j=0;j<m;j++)
            {
                if((idex>=color[j].a && idex<=color[j].b) || (idex<=color[j].a && idex >=color[j].b))
                    col=palette(col,color[j].c);
            }
            printf("%c\n",col);
        }
        if(caseNum) printf("\n");
    }
    return 0;
}

[ 本帖最后由 C_戴忠意于 2012-10-26 21:22 编辑 ]

编程之路定要走完……

2012-10-26 21:21

快速回复：C论坛算法团队首战西安电子科技大学OJ