标题:C论坛算法团队 首战 西安电子科技大学OJ
取消只看楼主
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
得分:0 
Problem 1010 - 素数环问题
Problem 1010 - 素数环问题

Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 473  Accepted: 93  Special Judge: No


Description


  有一个由n个数字相连组成的圆环(n<20),组成圆环的数字分别为1,2,3...n-1,n.要求每两个相邻元素的和为素数。(注意:第一个元素始终为1)。


 

Input

n (0<n<20)

Output

要求输出所有符合条件的组成圆环的元素,每个符合条件的圆环按顺时针或者逆时针将元素依次输出,输出格式见样例。要求按字典序输出。
每例以空行分开。

Sample Input

6
8

Sample Output

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

Hint


Source

Wang Miao
分析
素数环,将1到N的整数排成一圈,使相邻两个数之和为素数。

根据定义对由1到N的整数序列进行深度优先遍历即可。

当遍历到某一个值已经不满足要求可以直接回溯,所以不需要遍历所有状态空间,速度还是很不错的。

根据题目的意思,它给的N值都是可以构成素数环的。但并不是任意的N都可以构成素数环。

比如当N是大于1的奇数时就构不成素数环。为什么?

根据抽屉原理,如果N为奇数(大于1)那么围成一圈后必然有两个不相等的奇数相邻,而两个不相等的奇数的和绝不会是素数。

另外,由于在搜索过程中需要进行大量的素数判断,且题目中N的取值范围不大,所以先准备一张素数表可以减少重复计算提高效率。素数筛在这里应用很合适。
程序代码:
#include<stdio.h>
char np[40];
   
void ring(int n, int d)
{
    static int r[20], f[21];
    int i, t;
    if(d == n)
    {
        if(np[r[n - 1] + 1]) return;
        for(putchar('1'), i = 1; i < n; printf(" %d", r[i++]));
        puts("");
        return;
    }
    if(!d)
    {
        for(i = 0; i < n; f[i] = 0, r[i++] = i + 1);
        ring(n, d + 1);
    }
    else for(i = 2; i <= n; i++)
    {
        if(f[i] || np[i + r[d - 1]]) continue;
        r[d] = i; f[i] = 1;
        ring(n, d + 1);
        f[i] = 0;
    }
}

int main()
{
    int i, j;
    for(i = 2; i < 40; i++)
    if(!np[i]) for(j = i + i; j < 40; j += i) np[j] = 1;
    for(i = 1; scanf("%d", &j) != EOF; i++)
    {
        if(i - 1) puts("");
        printf("Case %d:\n", i);
        ring(j, 0);
    }
    return 0;
}


重剑无锋,大巧不工
2012-10-06 20:54
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
得分:0 
Problem 1011 - 金子上的友情
Problem 1011 - 金子上的友情

Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 235  Accepted: 76  Special Judge: No


Description


  Wm 和Qinz 是一对好朋友,他俩有着一段伟大的友谊,然而这段友谊是建立在一场残酷的竞争之后的英熊惺惺相惜,那场战斗是这样的
----------------------我------是------华------丽--------的-------分--------割----------线------------------
  地上有三堆金子,第i堆里面a[i]颗金子,每个人轮流从任意一堆金子中取出来任意多颗,当然取出来的颗数不能超过这堆金子的剩余量,现在告诉你这三堆金子每堆的颗数,如果场上三堆金子都剩余0颗的话,没金子可取的那个人要把手中取到的金子全部交给对方,并且对方获胜。
  Wm先取金子,输出最后获胜的人的名字

Input

每行三个数,分别为第一,第二,第三堆金子的颗数(0<=颗数<2^16),题目可能包含多组数据。

Output

输出获胜者的名字

Sample Input

1 1 1
1 2 3


Sample Output

Wm
Qinz

Hint


Source

Wudired
分析
经典博弈问题——尼姆博弈(Nimm Game)。

结论非常简单,如果三堆东西数值的二进制表示的异或结果为0则先拿者输,否则赢。

但结论的推导过程很复杂。如果哪位在不知尼姆博弈为何物的情况下自行得出上面的结论,请一定留下名字。我非常愿意与这样的天才交流。

最后说点题外话。我建议大家,不管将来从事哪个行业,尽力拓宽自己的知识面对你都是有好处的。

不是学会写字就能写好文章,不是学会语言就能编好程序。
程序代码:
#include<stdio.h>
int main()
{
    int a, b, c;
    while(scanf("%d%d%d", &a, &b, &c) != EOF)
    puts(a ^ b ^ c ? "Wm" : "Qinz");
    return 0;
}

重剑无锋,大巧不工
2012-10-07 16:54
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
得分:0 
Problem 1012 - 奇妙的旅行
Problem 1012 - 奇妙的旅行

Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 279  Accepted: 63  Special Judge: No


Description


  炸鸡儿非常喜欢旅行,而且喜欢在坐标轴上旅行,从起点A到终点B(0<=A,B<=100000)。他旅行的方法很特殊,喜欢用跳的,每次跳一个地方只有三种方法:
从点C跳到点C+1。
从点C跳到点C-1。
从点C跳到点2*C。
请问他从A跳到B至少需要多少步?

Input

每组数据两个整数A,B(0<=A,B<=100000)。

Output

每例输出一行,表示至少需要的步数。

Sample Input

1 100000
0 100000

Sample Output

21
22

Hint


Source

Wang Miao
分析
又是一道搜索题,广搜吧。不过有两个结论可以提高效率减少无效搜索。

1、当a > b时,从a到b需要 a - b 步。

2、当a > (2/3)b时,进行2a这样的步骤无意义,不会比a+1更快接近b。

应该还有更强的结论,甚至怀疑a,b之间存在一个优美的函数关系。留给各位思考吧。
程序代码:
#include<stdio.h>
int cal(int a, int b)
{
    int r[160000] = {}, s[160000], n, mb, i, t, p, q;
    if(a >= b) return a - b;
    mb = b * 2 / 3;
    for(s[0] = a, n = 1, i = 0; i < n && (t = s[i]) - b; i++)
    {
        q = r[t] + 1;
        if(t < b && !r[p = t + 1]) r[s[n++] = p] = q;
        if(t <= mb && !r[p = t << 1]) r[s[n++] = p] = q;
        if(t && !r[p = t - 1]) r[s[n++] = p] = q;
    }
    return r[b];
}
int main()
{
    int a, b;
    while(scanf("%d%d", &a, &b) != EOF) printf("%d\n", cal(a, b));
    return 0;
}


重剑无锋,大巧不工
2012-10-07 19:22
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
得分:0 
Problem 1017 - Duan's problem
Problem 1017 - Duan's problem

Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 179  Accepted: 42  Special Judge: No

Duan was a naulty boy. One day, he made a mistake again. His teacher was very angry, and want to punish him. The teacher wanted him to solve a problem. If he successfully solved it, he could go home.

Here is the problem. Duan is given two number a and b. As everybody knows, a number is made of 0-9. The teacher wanted him to count how many 0-9 in a*b, and calculate which one appears more than others.

For example, if a is 100, b is 4, then a*b is 400.
Number 0 1 2 3 4 5 6 7 8 9
Frequency 2 0 0 0 1 0 0 0 0 0
so duan should answer 0.
If a is 110,b is 10,then a*b is 1100
Number 0 1 2 3 4 5 6 7 8 9
Frequency 2 2 0 0 0 0 0 0 0 0
so duan should answer 0 and 1.

Can you help him?

Input

There are multiple test cases.Each case contains two integers a and b (0 <= a < 10^10000, 0<=b<10^9). Input file ends of EOF.

Output

On a single line, print the numbers of largest frequency in incremental order separated by one space.

Sample Input

100 4
110 10

Sample Output

0
0 1

Hint


Source

5th Xidian University Collegiate Programming Contest(2007.9)
分析
题目的要求就是计算a * b中各数字的数量,输出出现次数最多的数字(如果不止一个,则按升序输出所有出现次数最多的)

其中a的取值范围为10^10000,所以算是大数运算吧。但b的取值范围只有10^9,所以难度不大。

想想我们小学时怎么列竖式计算乘法就知道怎么计算了。

简单解释一下我的代码中内层循环中6个for循环的作用,每个for循环完成一组计算

第一个,对c数组清零。c[i]表示数字i出现的次数

第二个,进行大数运算,将运算后的每一位结果累加到c中

第三个,将进位中剩余的量累加到c中

第四个,寻找c中的最大值,这里重用了变量n,之前它用来表示a的长度,现在它表示c中的最大值

第五个,检索到第一个出现次数最多的数字

第六个,按要求输出所有出现次数最多的数字
程序代码:
#include<stdio.h>
#include<string.h>
int main()
{
    char a[10001];
    int b, c[10], n, i;
    long long f;
    for(f = 0; scanf("%s%d", a, &b) != EOF; puts(""))
    {
        for(i = 0; i < 10; c[i++] = 0);
        for(n = strlen(a); n--; c[(f += (long long)b * (a[n] - '0')) % 10]++, f /= 10);
        for(; f; c[f % 10]++, f /= 10);
        for(n = i = 0; i < 10; n < c[i] && (n = c[i]), i++);
        for(i = 0; i < 10 && c[i] < n; i++);
        for(printf("%d", i++); i < 10; c[i] == n && printf(" %d", i), i++);
    }
    return 0;
}

重剑无锋,大巧不工
2012-10-10 15:37
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
得分:0 
Problem 1018 - Tour Guide
Problem 1018 - Tour Guide

Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 3  Accepted: 2  Special Judge: No


Description


You are working as a guide on a tour bus for retired people, and today you have taken your regular Nordic seniors to The Gate of Heavenly Peace. You let them have a lunch break where they could do whatever they like. Now you have to get them back to the bus, but they are all walking in random directions. You try to intersect them, and send them straight back to the bus. Minimize the time before the last person is in the bus. You will always be able to run faster than any of the tour guests, and they walk with constant speed, no matter what you tell them. The seniors walk in straight lines, and the only way of changing their direction is to give them promises of camphor candy. A senior will neither stop at nor enter the bus before given such a promise.

Input

A number of test cases consisting of: A line with an integer 1 ≤ n ≤ 8, the number of people on the tour. A line with an floating point number 1 < v ≤ 100, your maximum speed (you start in the bus at the origin). Then follow n lines, each containing four floating point numbers xi yi vi ai, the starting coordinates (−10^6 ≤ xi, yi ≤ 10^6), speed (1 ≤ vi < 100) and direction (0 ≤ ai < 2π) of each of the tour guests.
The input is terminated by a case with n = 0, which should not be processed. All floating point numbers in the input will be written in standard decimal notation, and have no more than 10 digits.

Output

For each test case, print a line with the time it takes before everybody is back in the bus (the origin). Round the answer to the nearest integer. The answer will never be larger than 10^6.

Sample Input

1
50.0
125.0 175.0 25.0 1.96
3
100.0
40.0 25.0 20.0 5.95
-185.0 195.0 6.0 2.35
30.0 -80.0 23.0 2.76
0

Sample Output

20
51

Hint


Source

5th Xidian University Collegiate Programming Contest(2007.9)
分析
先简单翻译一下这一题目。一个导游带着一群北欧来的老人逛天安门。到了天安门后老人们自由活动到处跑,时间到了,导游要把他们全找回到旅游车上。设旅游车及导游、老人在一个平面坐标系内,旅游车所处的位置为坐标原点,老人们处在坐标系的某个点上,并以一个恒定的速度在一个恒定的方向上移动。导游从导游车上出发挨个以一个恒定的速度去寻找这些老人,当他遇到一个老人后给他一块糖(噱头)他便开始以他的速度走回旅游车。现在问直到最后一个老人上车最短需要多少时间。

解这个问题首先要解决的是,当导游处于某一点时,他想找到某一个老人需要的最短时间是多少,以及在哪儿早到这个老人。

解决了这个问题后,我们只需要遍历所有的找法,找出时间最短的即可。



老人的初始坐标、移动速度、移动方向为 x1, y1, v1, d

导游当前的坐标、移动速度和到他从车上出发到现在已经用去的时间为 x0, y0, v0, t0

导游遇到老人时的坐标及他从车上出发到现在所用去的时间为 x, y, t

为了在最短时间内遇到老人,导游应该沿直线移动到相遇点,由此可以建立如下方程组

x = x1 + t * v1 * cos(d)

y = y1 + t * v2 * sin(d)

(x - x0)^2 + (y - y0)^2 = (v0 * (t - t0))^2

解这个方程组即可得到x, y, t。

代码说明

PERSON结构中的d元素,在作为导游时表示当前他已用去的时间,在作为老人时表示老人的移动方向。

intersect函数计算导游g与老人s相遇的时间、地点及老人返回旅游车的时间。

参数mg将返回相遇后g的相应参数,函数返回值为这个老人返回旅游车的时间。

函数sub_cal既是遍历每一种找回老人的方式所用的最少时间,遍历方式即是按照全排列的产生方式确定一个寻找老人的序列,计算在这一序列下所用的最少时间。

函数cal是对sub_cal做了下接口封装。
程序代码:
#include<stdio.h>
#include<math.h>

#define COUNT_MAX    8
#define TIME_MAX    1E7

typedef struct
{
    double x;
    double y;
    double v;
    double d;
}PERSON;

PERSON Senior[COUNT_MAX];
int List[COUNT_MAX];
int N;

double intersect(PERSON g, PERSON s, PERSON * mg)
{
    double c0, c1, c2, vsd, vcd, a, b, c;
    double x, y, t;

    vsd = s.v * sin(s.d);
    vcd = s.v * cos(s.d);
    c0 = g.v * g.v * g.d;
    c1 = s.x - g.x;
    c2 = s.y - g.y;

    a = s.v * s.v - g.v * g.v;
    b = 2 * (c0 + c1 * vcd + c2 * vsd);
    c = c1 * c1 + c2 * c2 - c0 * g.d;

    t = -(b + sqrt(b * b - 4 * a * c)) / (2 * a);
    x = s.x + vcd * t;
    y = s.y + vsd * t;

    mg->x = x;
    mg->y = y;
    mg->v = g.v;
    mg->d = t;

    return t + sqrt(x * x + y * y) / s.v;
}

double sub_cal(PERSON g, double use_t, int deep)
{
    static double min_t;
    double t;
    PERSON mg;
    int i, j, tmp;

    if(deep == 0) min_t = TIME_MAX;
    if(deep == N && min_t > use_t) min_t = use_t;

    for(i = deep; i < N; i++)
    {
        tmp = List[i]; List[i] = List[deep]; List[deep] = tmp;
        t = intersect(g, Senior[List[deep]], &mg);
        if(t < min_t) sub_cal(mg, t > use_t ? t : use_t, deep + 1);
        tmp = List[i]; List[i] = List[deep]; List[deep] = tmp;
    }
    return min_t;
}

double cal(double v)
{
    PERSON g = {0, 0, v, 0};
    return sub_cal(g, 0, 0);
}

int main()
{
    double v;
    int i;
   
    for(i = 0; i < COUNT_MAX; List[i] = i++);
    for(; scanf("%d", &N), N; printf("%.0f\n", cal(v)))
    for(scanf("%lf", &v), i = 0; i < N; i++)
        scanf("%lf%lf%lf%lf", &Senior[i].x, &Senior[i].y, &Senior[i].v, &Senior[i].d);
    return 0;
}
收到的鲜花
  • czz52421992012-10-15 19:37 送鲜花  10朵   附言:这题我一看只有2个人ac,被吓到了,完全没考 ...

重剑无锋,大巧不工
2012-10-12 19:42
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-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
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
得分: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
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
得分: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
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
得分: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
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
得分:0 
回复 95楼 C_戴忠意
呵呵,拿你的帐号测试了你的代码,搞定了。

开始我怀疑是pow函数的截断误差造成的,修改后还是不对。突然想到了我的代码RT的原因,发现你没有处理0的输出。

附上我的AC代码给你对比参考。
程序代码:
#include<stdio.h>
#include<ctype.h>
#include<math.h>
char * trans(int a, char * n, int b)
{
    int d, i, t;
    for(d = i = 0; t = toupper(n[i++]); d = d * a + (t <= '9' ? t - '0' : t - 'A' + 10));
    for(n[i = (d ? log(d) : 0) / log(b) + 1] = 0; i--; d /= b) n[i] = (t = d % b) <= 9 ? t + '0' : t - 10 + 'A';
    return n;
}
int main()
{
    int a, b;
    char n[128];
    scanf("%d%s%d", &a, n, &b);
    printf("%s\n", trans(a, n, b));
    return 0;
}

重剑无锋,大巧不工
2012-11-14 17:45



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-382411-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.829192 second(s), 9 queries.
Copyright©2004-2025, BCCN.NET, All Rights Reserved