ACM基础算法(一)
和大家分享探讨下ACM的一些基础算法，让大家有所了解。我即将毕业，参加ACM两届了，基本都是省赛程度吧。不厉害，有些个人经验，在此和大家分享。希望有兴趣的同学，能从中受益。首先说说队伍，最好队伍固定：3个人，需要有一个人数学功底较好(是相对其他两个人来说的)----用于建模；
一个人专业英语需要过关，能理解题目的含义；
一个人，编程过硬.
以上我说的三个人，是每个人都应该有，并且具有相应突出的表现的。也就是说，大家各有所长。
说说比赛题目类型：数据结构类
基础算法类
数学计算类
几何类
数论
动态规划
图论
还有关于函数的调用：我需用的是C语言答题，这里面切记，非标准库函数 是不允许使用的，即使编译器提供了，但OJ是一定通过不了的，所以大家需要，将一些常用的函数，自己写一下。以便使用。我会做一个专题来分享自己的代码的。
我标注红字的，是最应该掌握的，同时也是最容易做出来的。
今天先说基础算法里面：分治、递归、贪心、枚举 这四种是最常见的，也是最应该掌握的。
第一个分治的思想。分治的思想，就是将一个大的问题，细化，用局部来替换整体。其中实行的前提是，
局部具有和整体一样的性质。
而这其中，简单的来说，就是 利用集合中的关系，做差集、补集、交集、并集的运算。
这里给大家一个简单的例子，是哈工大的OJ上的一道例题
给定两个数a和b,计算出 1 在 a 和 b 之间出现的次数
例如：如果 a = 1024, b = 1032 那么 1出现的次数就是 10
这里我解题的思想是用 的闭区间与 (0,a)的开区间做减法，进而求得1在 a b 之间出现的次数，大家可以画一个数轴就很好的理解了..
代码如下:
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
int deal(int temp)
{
char bit;
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);
}
}
}
好了，今天的就说到这里，有问题的可以留言，大家交流，我会尽量保证每日一更的。希望对大家有帮助
居然没人顶，这么好的贴，楼主加油！ 顶楼主 我也很想研究下ACM的东西 ACM看不懂 果断路过 楼主加油额。。。 XX 顶起 不错 受教了 lz能给推荐一些书籍神马的吗 挺好···························· 楼主经验贴不错 悲剧啊，居然没能看懂提议。。。 好人啊( ⊙o⊙ )哇 #include <stdio.h>
#include <stdlib.h>
#include <string.h>
int deal(int low, int high)
{
int i, j;
char bit;
char sum = 0;
for (i = low; i <= high; i++)
{
itoa(i, &bit, 10); // itoa并不是标准C函数
for (j = 0; j < strlen(&bit); j++)
{
if ('1' == bit)
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);
}
好好好学习 ~~~~~~~~~~~~~~~~ 都大三了，ACM已经失去激情了 写的不错能否继续深入 ACM是什么..... 看看老帖，支持下 楼主你好，我现在大一刚刚开始接触ACM，非常想在这方面有所突破。
能不能加个QQ好友，还希望您能指点一二，谢谢。 需要LOOKLOOK。。。。。
页:
[1]
2