HDOJ刷题笔记(一)

发表于 更新于 阅读次数： Valine：
本文字数： 1.3k 阅读时长 ≈ 1 分钟

坐而论道，不如起而行之。要学数据结构与算法，还是得多刷题。

HDOJ 是“杭州电子科技大学程序在线评测系统”（Hangzhou Dianzi University Online Judge）的缩写，是一个提供编程题目以及在线测评的网站，其兼容Pascal、C、C++、Java、GCC、G++等多种语言，并拥有良好的运行速度和很高的测评正确率。HDOJ是目前相对较为优秀的一个ACM在线测评系统，因而打算以此开始。

Pro.ID 1000

第一题具体内容不表，因为与内容不相关，主要是在代码逻辑完全正确的情况下，我的代码总是会报出Wrong Answer的错，在经过查阅才了解，需要不断读入数据，而非一次读入，用C++表示即为while(cin>>n)类似于这样的代码。

在查阅资料的过程中，我发现了一种更为高效的写法：for(int n;~scanf("%d",&n);<Your Code>)。

Pro.ID 1001

题目描述：In this problem, your task is to calculate SUM(n) = 1 + 2 + 3 + … + n.

要求输入：The input will consist of a series of integers n, one integer per line.

要求输出：For each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit signed integer.

解题思路：看到要求和，立刻就想到了使用求和公式S=(1+n)*n/2一套带走，不曾想就遇到了两个坑。

1
2
3
4
5
6
7
8
9
10
#include<iostream>
using namespace std;
int main()
{
	int a;
	while(cin>>a) {
		cout<<(a+1)*a/2<<endl;
	}
	return 0;
 }

一开始，我想当然的就这么写，发现报了错误：

其一，按题目要求，需要多空一个空行，我这里面只有一个回车，题目需要两个回车。

其二，需要注意的是，虽然在声明中保证了其在32位整数范围内，但是由于在计算过程中使用了乘法，n*(n+1)直接相乘可能会导致溢出，所以要把n和(n+1)分开，理所当然地想到要(1+n)*(n/2)，但是这里又有一个坑了，C++中整型计算是向零舍入的，如果n为奇数的话，结果会出错，因而需要对奇偶进行判断，所以可以考虑如下写法：

1
2
3
4
5
#include<stdio.h>
int main(){
    for(int n;~scanf("%d",&n);printf("%d\n\n",n%2==0?(1+n)*(n/2):(1+n)*(n/2)+n/2+1));
    return 0;
}