那些严重拖慢做题进度的题以及遇到的坑2

杭电205X && 206X

A == B ?

Give you two numbers A and B, if A is equal to B, you should print “YES”, or print “NO”.

这一题是最坑的，AC率只有15.9%，主要原因就是题目条件说得太简略了，后面也有一些题是这样的，有一些时要注意的。

这里A和B并不是简单的数，可能是很长的数，长到没有变量类型可以表示，也可以是000000000000000000.00000000001这种形式很坑的数，所以并不是那么简单

不过Java里面有相应的模块，于是就很容易过了，而用C++就很难搞了

import java.util.Scanner;
import java.math.BigDecimal;  // 大的十进制数

public class Main {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            BigDecimal A = in.nextBigDecimal;
            BigDecimal B = in.nextBigDecimal;
            if (A.compareTo(B) == 0) {
                System.out.println("YES");
            }
            else {
                System.out.println("NO");
            }
        }
    }
}

总结一下，这种涉及到位数很多的数用Java可以比较方便的解决。（得知道有相应的模块233）

Rectangles

Given two rectangles and the coordinates of two points on the diagonals of each rectangle,you have to calculate the area of the intersected part of two rectangles. its sides are parallel to OX and OY

分析：

这一题知道算法就很简单，如果没想清楚就很坑了…比如说我…

方法一：

重叠部分长度等于两者长度相加减去最大最小坐标之差，对于x，是下面这种，y也类似

rela_x = fabs(x1 - x2) + fabs(x3 - x4) - (x[3] + x[0]) // x[3], x[0]是最大和最小的坐标

如果这个值小于零，说明不相交，大于零就是相应的长度

于是当相交的时候，面积就是rela_x * rela_y

方法二：

重叠部分的长度总是四个坐标中中间两个的差值，于是面积有

(x[2] - x[1]) * (y[3] - y[1])

关键就是要相处算法，死讨论情况是很难做出来的…

A + B Again

There must be many A + B problems in our HDOJ , now a new one is coming.
Give you two hexadecimal integers , your task is to calculate the sum of them,and print it in hexadecimal too.
Easy ? AC it !

分析：

说白了就是十六进制的输入和输出，我不知道有相应的内容，于是手动转换…果不其然WA…

直接上代码吧…

#include<stdio.h>
int main()
{
    // 15位16进制相当于60位二进制，所以要开大一点
    long long a, b;
    // x占位符表示16进制
    while(scanf("%llx %llx", &a, &b) != EOF)
    {
        // 不能输出负的十六进制，所以这里要处理一下
        if (a + b < 0)
            printf("-%llx\n", -(a + b));
        else
            printf("%llx\n", (a + b));
    }
}

你看吧，基础不牢，地动山摇…

The sum problem

Given a sequence 1,2,3,……N, your job is to calculate all the possible sub-sequences that the sum of the sub-sequence is M.

分析：

题目本身是很简单的，是连续的数列，都不涉及到动态规划
但是隐藏了一个坑，那就是输入的数字范围很大，因此如果不控制复杂度就机器容易超时

在这里用解方程的思想来做：

首项为f，末项为e，项数为n

m = (f + e) * n / 2;
e - f + 1 = n;

因此可以用项数和m来表示f解出f，当f为1的时候，n可能取到的值最大，约为sqrt(2m)，也就是说子序列的长度不可能超多这个值，因此循环从1到sqrt(2m)就可以了，当解出来的f是正整数而且不超过范围说明就是所求

int len = floor(sqrt(2 * m));
        double x = 0;
        for (int i = len; i >= 1; --i)
        {
            x = (2.0 * m / i + 1 - i) * 0.5;
            int a = floor(x);
            x -= a;
            if (x == 0 && (a + i - 1) <= n)
                printf("[%d,%d]\n", a, a + i - 1);
        }

补充：

floor()是数学函数，是求一个浮点数的不大于它的最大整数，返回值也是一个double型的浮点数
类似的还有:
ceil()：求一个浮点数的不小于它的最小整数,返回值也是一个double型的浮点数
round():求一个浮点数的四舍五入值，返回也是一个整数，也就是说看小数点第二位四舍五入

例如：round(1.499999) is 1.000000

感觉自己是一个木头脑袋…

龟兔赛跑

据说在很久很久以前，可怜的兔子经历了人生中最大的打击——赛跑输给乌龟后，心中郁闷，发誓要报仇雪恨，于是躲进了杭州下沙某农业园卧薪尝胆潜心修炼，终于练成了绝技，能够毫不休息得以恒定的速度(VR m/s)一直跑。兔子一直想找机会好好得教训一下乌龟，以雪前耻。
最近正值HDU举办50周年校庆，社会各大名流齐聚下沙，兔子也趁此机会向乌龟发起挑战。虽然乌龟深知获胜希望不大，不过迫于舆论压力，只能接受挑战。
比赛是设在一条笔直的道路上，长度为L米，规则很简单，谁先到达终点谁就算获胜。
无奈乌龟自从上次获胜以后，成了名龟，被一些八卦杂志称为“动物界的刘翔”，广告不断，手头也有了不少积蓄。为了能够再赢兔子，乌龟不惜花下血本买了最先进的武器——“”小飞鸽”牌电动车。这辆车在有电的情况下能够以VT1 m/s的速度“飞驰”，可惜电池容量有限，每次充满电最多只能行驶C米的距离，以后就只能用脚来蹬了，乌龟用脚蹬时的速度为VT2 m/s。更过分的是，乌龟竟然在跑道上修建了很多很多（N个)的供电站，供自己给电动车充电。其中，每次充电需要花费T秒钟的时间。当然，乌龟经过一个充电站的时候可以选择去或不去充电。
比赛马上开始了，兔子和带着充满电的电动车的乌龟并列站在起跑线上。你的任务就是写个程序，判断乌龟用最佳的方案进军时，能不能赢了一直以恒定速度奔跑的兔子。

分析：

这个题目条件十分逗逼，也是一个涉及到动态规划的，在这里先留个坑等看了动态规划的相关内容再回来补充

Treasure the new start, freshmen!

background:
A new semester comes , and the HDU also meets its 50th birthday. No matter what’s your major, the only thing I want to tell you is:”Treasure the college life and seize the time.” Most people thought that the college life should be colorful, less presure.But in actual, the college life is also busy and rough. If you want to master the knowledge learned from the book, a great deal of leisure time should be spend on individual study and practise, especially on the latter one. I think the every one of you should take the learning attitude just as you have in senior school.
“No pain, No Gain”, HDU also has scholarship, who can win it? That’s mainly rely on the GPA(grade-point average) of the student had got. Now, I gonna tell you the rule, and your task is to program to caculate the GPA.
If there are K(K > 0) courses, the i-th course has the credit Ci, your score Si, then the result GPA is
GPA = (C1 S1 + C2 S2 +……+Ci * Si……) / (C1 + C2 + ……+ Ci……) (1 <= i <= K, Ci != 0)
If there is a 0 <= Si < 60, The GPA is always not existed.

这题其实是水题，但是一直WA

有几个坑：

学分和成绩都可以是小数，所以要用double类型的，这里题目中没有说出来，以后要长一点心！
break使用的时候要慎重！特别是在输入数据的时候，提前break了后面输入的数据就都是错的！