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 之间出现的次数，大家可以画一个数轴就很好的理解了..

代码如下:

1. #include "stdio.h"
   
2. #include "stdlib.h"
   
3. #include "string.h"
   
4. 
   
5. 
   
6. int deal(int temp)
   
7. {
   
8. char bit[10];
   
9. char *head;
   
10. int loop;
    
11. int sum = 0;
    
12. for( loop=1; loop<=temp; loop++)
    
13. {
    
14. itoa(loop,bit,10);
    
15. 
    
16. head = bit;
    
17. while( *head )
    
18. {
    
19. if( *head == '1' )
    
20. {
    
21. sum++;
    
22. }
    
23. head++;
    
24. }
    
25. }
    
26. return sum;
    
27. }
    
28. 
    
29. int main()
    
30. {
    
31. int a,b;
    
32. int sum_1,sum_2;
    
33. while( scanf("%d%d",&a,&b) != EOF )
    
34. {
    
35. 
    
36. if ( (a == 0) && (b == 0))
    
37. break;
    
38. if ( a > b)
    
39. {
    
40. sum_1 = deal(a);
    
41. sum_2 = deal(b-1);
    
42. printf("%d\n",sum_1 - sum_2);
    
43. }
    
44. else
    
45. {
    
46. sum_1 = deal(b);
    
47. sum_2 = deal(a-1);
    
48. printf("%d\n",sum_1 - sum_2);
    
49. }
    
50. }
    
51. 
    
52. }

复制代码

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

乘风追日

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

chengmin_prime

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

服气

ACM看不懂 果断路过

╰☆落叶秋风

楼主加油额。。。

HACKER

XX

唯舆之缌

顶起   不错   受教了

唯舆之缌

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

shaolee

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

Hate.RT

楼主经验贴不错

fishs

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

风之翼

好人啊( ⊙o⊙ )哇

z____

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. int deal(int low, int high)
   
6. {
   
7. int i, j;
   
8. char bit[10];
   
9. char sum = 0;
   
10. for (i = low; i <= high; i++)
    
11. {
    
12. itoa(i, &bit[0], 10); // itoa并不是标准C函数
    
13. for (j = 0; j < strlen(&bit[0]); j++)
    
14. {
    
15. if ('1' == bit[j])
    
16. sum++;
    
17. }
    
18. }
    
19. return sum;
    
20. }
    
21. 
    
22. int main()
    
23. {
    
24. int a, b;
    
25. int sum;
    
26. scanf("%d %d", &a, &b);
    
27. /*在这里判断输入是不是0完全是多余
    
28. 另外,EOF是文件结束标志(其值为-1),你的主程序是死循环
    
29. 你的意思应该是从文件输入吧-_-!
    
30. 那就是fscanf了(键误???????)
    
31. */
    
32. sum = deal(a, b);
    
33. printf("%d\n", sum);
    
34. }

复制代码

行知工学谢斌

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

pro_xk

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

Gw_love_VC.

写的不错  能否继续深入

生命树

ACM是什么.....

Cocol

看看老帖，支持下

Geeker.s

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

x517302248

需要LOOKLOOK。。。。。