ACM基础算法(一)

风啦啦吹

和大家分享探讨下ACM的一些基础算法，让大家有所了解。我即将毕业，参加ACM两届了，基本都是省赛程度吧。不厉害，有些个人经验，在此和大家分享。希望有兴趣的同学，能从中受益。

首先说说队伍，最好队伍固定：3个人，需要有一个人数学功底较好(是相对其他两个人来说的)----用于建模；
                                                              一个人专业英语需要过关，能理解题目的含义；
                                                              一个人，编程过硬.
以上我说的三个人，是每个人都应该有，并且具有相应突出的表现的。也就是说，大家各有所长。

说说比赛题目类型：数据结构类
                               基础算法类
                               数学计算类
                               几何类
                               数论
                               动态规划
                               图论

还有关于函数的调用：我需用的是C语言答题，这里面切记，非标准库函数 是不允许使用的，即使编译器提供了，但OJ是一定通过不了的，所以大家需要，将一些常用的函数，自己写一下。以便使用。我会做一个专题来分享自己的代码的。

我标注红字的，是最应该掌握的，同时也是最容易做出来的。

今天先说基础算法里面：分治、递归、贪心、枚举 这四种是最常见的，也是最应该掌握的。

第一个分治的思想。分治的思想，就是将一个大的问题，细化，用局部来替换整体。其中实行的前提是，
                                局部具有和整体一样的性质。
而这其中，简单的来说，就是 利用集合中的关系，做差集、补集、交集、并集的运算。
这里给大家一个简单的例子，是哈工大的OJ上的一道例题

给定两个数a和b,计算出 1 在 a 和 b 之间出现的次数

例如：如果 a = 1024, b = 1032 那么 1出现的次数就是 10

这里我解题的思想是  用 [0,b]的闭区间  与 (0,a)的开区间做减法，进而求得1在 a b 之间出现的次数，大家可以画一个数轴就很好的理解了..

代码如下:

#include "stdio.h"
#include "stdlib.h"
#include "string.h"


int deal(int temp)
{
char bit[10];
char *head;
int loop;
int sum = 0;
for( loop=1; loop<=temp; loop++)
{
itoa(loop,bit,10);

head = bit;
while( *head )
{
if( *head == '1' )
{
sum++;
}
head++;
}
}
return sum;
}

int main()
{
int a,b;
int sum_1,sum_2;
while( scanf("%d%d",&a,&b) != EOF )
{

if ( (a == 0) && (b == 0))
break;
if ( a > b)
{
sum_1 = deal(a);
sum_2 = deal(b-1);
printf("%d\n",sum_1 - sum_2);
}
else
{
sum_1 = deal(b);
sum_2 = deal(a-1);
printf("%d\n",sum_1 - sum_2);
}
}

}

好了，今天的就说到这里，有问题的可以留言，大家交流，我会尽量保证每日一更的。希望对大家有帮助

乘风追日

居然没人顶，这么好的贴，楼主加油！

chengmin_prime

顶楼主 我也很想研究下ACM的东西

服气

ACM看不懂 果断路过

╰☆落叶秋风

楼主加油额。。。

HACKER

XX

唯舆之缌

顶起   不错   受教了

唯舆之缌

lz能给推荐一些书籍神马的吗

shaolee

挺好····························

Hate.RT

楼主经验贴不错

fishs

悲剧啊，居然没能看懂提议。。。

风之翼

好人啊( ⊙o⊙ )哇

z____

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

int deal(int low, int high)
{
int i, j;
char bit[10];
char sum = 0;
for (i = low; i <= high; i++)
{
itoa(i, &bit[0], 10); // itoa并不是标准C函数
for (j = 0; j < strlen(&bit[0]); j++)
{
if ('1' == bit[j])
sum++;
}
}
return sum;
}

int main()
{
int a, b;
int sum;
scanf("%d %d", &a, &b);
/*在这里判断输入是不是0完全是多余
另外,EOF是文件结束标志(其值为-1),你的主程序是死循环
你的意思应该是从文件输入吧-_-!
那就是fscanf了(键误???????)
*/
sum = deal(a, b);
printf("%d\n", sum);
}

行知工学谢斌

好好好学习 ~~~~~~~~~~~~~~~~

pro_xk

都大三了，ACM已经失去激情了

Gw_love_VC.

写的不错  能否继续深入

生命树

ACM是什么.....

Cocol

看看老帖，支持下

Geeker.s

楼主你好，我现在大一刚刚开始接触ACM，非常想在这方面有所突破。
能不能加个QQ好友，还希望您能指点一二，谢谢。

x517302248

需要LOOKLOOK。。。。。