@Chobi15
2015-07-18T12:02:58.000000Z
字数 5365
阅读 1591
ACM程序设计大赛是大学级别最高的脑力竞赛,素来被冠以"程序设计的奥林匹克"的尊称。大赛自1970年开始至今已有40年历史,是世界范围内历史最悠久、规模最大的程序设计竞赛。比赛形式是:经过校级和地区级选拔的参赛组,于指定的时间、地点参加世界级的决赛,由3个成员组成的小组应用一台计算机解决6到8个生活中的实际问题。竞赛结束后,参赛各队以解出问题的多少进行排名,若解出问题数相同,按照总用时的长短排名。
Online Judge系统(简称OJ)是一个在线的判题系统。用户可以在线提交程序多种程序(如C、C++、Pascal)源代码,系统对源代码进行编译和执行,并通过预先设计的测试数据来检验程序源代码的正确性。
今后我们做题都会在OJ上面进行,以下是几个推荐的OJ网址
1. 北京师范大学OJ(BNUOJ)集训的题目都会挂在这个OJ上
2. 北京大学OJ(POJ)
3. 杭州电子科技大学OJ(HDUOJ)
4. CODEFORCES(俄罗斯的一个OJ,基本每周都会举行个人赛)
国内外OJ还有很多,这里不进行一一列举
当你完成题目后,点击submit(提交),选择你使用编译语言(C++,C, Java等),在代码栏内粘贴上你的代码,点击submit按钮,就提交了你的代码了.
试着完成自己的第一道题吧:A + B Problem
一个用户提交的程序在Online Judge系统下执行时将受到比较严格的限制,包括运行时间限制,内存使用限制和安全限制等。用户程序执行的结果将被Online Judge系统捕捉并保存,然后再转交给一个裁判程序。该裁判程序或者比较用户程序的输出数据和标准输出样例的差别,或者检验用户程序的输出数据是否满足一定的逻辑条件。
最后系统返回给用户一个状态:
1. 通过(Accepted,AC)
2. 答案错误(Wrong Answer,WA)
3. 超时(Time Limit Exceed,TLE)
4. 超过输出限制(Output Limit Exceed,OLE)
5. 超内存(Memory Limit Exceed,MLE)
6. 运行时错误(Runtime Error,RE)
7. 格式错误(Presentation Error,PE)
8. 无法编译(Compile Error,CE )
注意: 比赛中每一次提交若未能AC,一般是要罚时20分钟的,所以提交请慎重
读入一个数n,并读入接下来的n个数据
5 1 2 3 4 5
scanf(“%d”, &n);
for (i = 0; i < n; ++i) {
scanf("%d", &arr[i]);
}
按行读入数据,需要能够确定行内数据的个数
1 2 3 4 5
6 7 8
char str[100];
while(gets(str)) {
int i = 0, l, p = 0;
sscanf(str+p, “%d%n”, &arr[i++], &l) != EOF) {
p += l;
}
}
读入文本中所有的以<>括起来的内容
< html>< body>kasjdflkja<1>sdas<2>s
char ans[]
int cnt = 0;
while (scanf("%c", &ch) != EOF) { //输入不为文件末尾
if (ch == '<') {
while (1) {
scanf("%c", &ch);
if (ch == '>') {break;}
else {ans[cnt++] = ch;}
}
}
} //边读边处理
char buf[10000];
while (scanf(”%*[^<]<%[^>]>", buf) != EOF) {
…
}
读入一个数字
scanf (“%d”, &num);
scanf (“%f”, &num);
scanf (“%lf”, &num);
scanf (“%s”, num);
读入时间
2014_01_02 12:30:45
int year, month, date, h, m, s;
scanf("%d-%d-%d %d:%d:%d", &year, &month, &date, &h, &m, &s);
依次读入多个字符,字符以空格隔开
a f d
scanf("%c%*c%c%*c%c", &a, &b, &c);
//%*c忽略一个字符
scanf(),用于读入以不可见字符分隔的数据结束
%d %I64d或%lld
%lf 或 %f
%s %n
%c 尽量少用
%[] 正则表达式
%*c
根据题目给出的数据组数判断
输入第一行为k,表示有k组测试数据
int k;
scanf("%d", &k);
while(k--){
scanf(XXX);
...
}
输入仅有一组数据
scanf(XXX);
读入直到文件结束
输入包含多组数据, 每数组据包含XXX内容
如 每组测试数据包括 两个数 m n. 0 0表示输入结束
while(scanf("%d%d", &x, &y) && !(x==0 && y == 0)){
...
}
输入以EOF结束
while(scanf(...)!=EOF);
输出时间,格式要求:yyyy-MM-dd hh:mm:ss
2013-01-01 01:01:01
printf(“%04d-%02d-%02d %02d:%02d:%02d\n”, …);
小数点后3位,四舍五入
printf(“%.3lf\n”, f);
小数点后3位,进一法
printf(“%.3lf\n”, f+0.0005);
结束标志
scanf()的结束标志为 回车'\n',Tab'\t' 和空格' '.
fgets(), gets()的结束标志为 回车'\n'.
//对于输入文本 "hello world!" 回车.
scanf("%s", string); // srting的内容为 "hello"
gets(string); // string的内容为 "hello world"
回车字符\n
scanf从stdin流,即终端输入,遇回车‘\n’停止,但‘\n’还在输入流中。
gets, fgets 输入时会连同回车'\n'一同读入,但不会存入数组中.
//对于输入文本 "hello" 回车 'c' 回车.
scanf("%s", str); ch = getchar(); //ch读入的字符为 '\n'.
gets(str); ch = getchar(); //ch读入的字符为 'c'.
安全
gets使用时要注意,gets函数格式gets(a);不检查内存空间,容易溢出。
fgets相对gets而言要安全点,格式fgets(*s,size,stdin),*s为地址,size为要读取的长度,stdin是从终端读取。
strlen(测量字符串长度)
strstr(一个字符串中搜索另一个字符串)
strcmp(字符串比较)
strcpy与strncpy(字符串的复制)
sscanf与sprintf(从字符串格式化读入,向字符串格式化写入)
memset 这是一个内存初始化函数,初始化字符串可用初始值只能为0 和 -1
memset(str,0, sizeof(str));
atoi, itoa, atof, atol,禁用!!!!!
计算下面这个结果:
32767+32767
计算下面这个结果:
327673276732767+327673276732767
计算下面这个结果:
327673276732767327673276732767 + 327673276732767327673276732767
整数(int)数据范围为-2^32~2^32-1,长整数(long long)数据范围为-2^64~2^64-1,如果十进数超过20位就不能胜任了。这时就要用到高精度数的运算了。
int w[100];一般为w[0]存储该数的位数,w[1]存个位,w[2]存十位,….
如整数“120”,按高精度数存储:w[0]=3;w[1]=0;w[2]=2;w[3]=1。
注意这里是倒着保存数的。这样做的目的在于进行运算时方便数位对齐。
但由于是高精度数的运算可以多次用到,所以我们定义成函数形式方便使用。为了让函数能直接返回值,所以可以定义成结构体。
struct hp
{
int w[10005];// w[0]用于存储这个数的位数
};
高精度数相加实际上就是模拟我们自己计算加法的过程。
步骤 1.对应位相加 2.进位.高精度加法类似
hp jia(hp a, hp b)
{
hp c;
memset(c.w, 0, sizeof(c.w)); //将c.w里所有数清0.
c.w[0] = a.w[0] > b.w[0] ? a.w[0] : b.w[0];//初步估算位数
for(int i = 1; i <= c.w[0]; i++){
c.w[i] = a.w[i]+b.w[i]; //对应位相加
}
for(int i = 1; i <= c.w[0]; i++){
if(c.w[i] >= 10){
c.w[i] %= 10;
c.w[i+1] += 1; //进位
}
}
if(c.w[c.w[0]+1] != 0)c.w[0]++;
return c;
}
高精度乘法也是模拟计算乘法
步骤 1.对应位相乘 2.进位
hp cheng(hp a, hp b)
{
hp c;
memset(c.w, 0, sizeof(c.w)); //将c.w里所有数清0.
c.w[0] = a.w[0] + b.w[0] - 1; //初步估算结果的位数
for(int i = 1; i <= a.w[0]; i++){
for(int j = 1; j <= b.w[0]; j++){
c.w[i+j-1] += a.w[i] * b.w[j]; //每一位相乘
}
}
for(int i = 1; i <= c.w[0]; i++){
if(c.w[i] >= 10){
c.w[i+1] += c.w[i] / 10;
c.w[i] %= 10;
}
}
if(c.w[c.w[0]+1] != 0)c.w[0]++; // 计算精确位数
return c;
}
高精度的输出方式为从最高位输出到最低位
void print(hp c)
{
for(int i = c.w[0]; i >= 1; i--){ //输出
printf("%d", c.w[i]);
}
printf("\n");
}
因为高精度的数已经不能用int 和 long long来储存.所以自然也不能用scanf("%d%lld")来输入.
输入方法为:
1. 将高精度数储存到字符串中
2. 把字符串转化为 struct hp 变量,用于之后的计算
输入数据 123456789123456789
hp input()
{
hp a;
memset(a.w, 0, sizeof(a.w))
char str[100];
scanf("%s", str); //将数字用数组保存
int len = strlen(str);
a.w[0] = len;
for(int i = len-1; i >= 0; i--){
a.w[len- i] = str[i] - '0'; //通过位置关系构建高精度数.
}
return a;
}
第一章的内容就讲完啦.来,完成我们的第一题!!
Bull Math
Input
输入包括两行 每一行是一个不超过40位的数字
Output
输出这两个数的乘积
代码:
#include <cstdio>
#include <cstring>
struct hp
{
int w[100];
};
hp cheng(hp a, hp b)
{
hp c;
memset(c.w, 0, sizeof(c.w)); //将c.w里所有数清0.
c.w[0] = a.w[0] + b.w[0] - 1; //初步估算结果的位数
for(int i = 1; i <= a.w[0]; i++){
for(int j = 1; j <= b.w[0]; j++){
c.w[i+j-1] += a.w[i] * b.w[j]; //每一位相乘
}
}
for(int i = 1; i <= c.w[0]; i++){
if(c.w[i] >= 10){
c.w[i+1] += c.w[i] / 10;
c.w[i] %= 10;
}
}
if(c.w[c.w[0]+1] != 0)c.w[0]++; // 计算精确位数
return c;
}
void print(hp c)
{
for(int i = c.w[0]; i >= 1; i--){ //输出
printf("%d", c.w[i]);
}
printf("\n");
}
hp input()
{
hp a;
memset(a.w, 0 ,sizeof(a.w));
char str[100];
scanf("%s", str);
int len = strlen(str);
a.w[0] = len;
for(int i = len-1; i >= 0; i--){
a.w[len- i] = str[i] - '0';
}
return a;
}
int main()
{
hp a, b;
a = input(); // 输入a
b = input(); // 输入b
hp c = cheng(a, b); // 计算 a * b
print(c); //输出结果c
return 0;
}