鱼C论坛

 找回密码
 立即注册
查看: 6453|回复: 31

[技术交流] ACM基础算法(一)

  [复制链接]
发表于 2012-4-20 20:33:30 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
和大家分享探讨下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. int deal(int temp)
  5. {
  6. char bit[10];
  7. char *head;
  8. int loop;
  9. int sum = 0;
  10. for( loop=1; loop<=temp; loop++)
  11. {
  12. itoa(loop,bit,10);

  13. head = bit;
  14. while( *head )
  15. {
  16. if( *head == '1' )
  17. {
  18. sum++;
  19. }
  20. head++;
  21. }
  22. }
  23. return sum;
  24. }

  25. int main()
  26. {
  27. int a,b;
  28. int sum_1,sum_2;
  29. while( scanf("%d%d",&a,&b) != EOF )
  30. {

  31. if ( (a == 0) && (b == 0))
  32. break;
  33. if ( a > b)
  34. {
  35. sum_1 = deal(a);
  36. sum_2 = deal(b-1);
  37. printf("%d\n",sum_1 - sum_2);
  38. }
  39. else
  40. {
  41. sum_1 = deal(b);
  42. sum_2 = deal(a-1);
  43. printf("%d\n",sum_1 - sum_2);
  44. }
  45. }

  46. }
复制代码

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



评分

参与人数 3荣誉 +10 鱼币 +27 贡献 +10 收起 理由
小甲鱼 + 10 + 20 + 5 感谢楼主无私奉献!
格式天下 + 5 + 5 sorry , 我给点成反对了,手抖了下………….
番茄 + 2 赞一个!

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-4-24 23:53:03 | 显示全部楼层
居然没人顶,这么好的贴,楼主加油!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-4-26 14:12:51 | 显示全部楼层
顶楼主 我也很想研究下ACM的东西
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-4-29 20:39:05 | 显示全部楼层
ACM看不懂 果断路过
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-4-29 21:31:26 | 显示全部楼层
楼主加油额。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-4-29 21:37:32 | 显示全部楼层
XX
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-4-29 21:46:17 | 显示全部楼层
顶起   不错   受教了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-4-29 21:47:45 | 显示全部楼层
lz能给推荐一些书籍神马的吗
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-5-8 18:30:19 | 显示全部楼层
挺好····························
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-1-14 17:19:39 | 显示全部楼层
楼主经验贴不错
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-1-14 17:29:45 | 显示全部楼层
悲剧啊,居然没能看懂提议。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-1-14 18:13:43 | 显示全部楼层
好人啊( ⊙o⊙ )哇
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-1-16 02:25:19 | 显示全部楼层
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. int deal(int low, int high)
  5. {
  6. int i, j;
  7. char bit[10];
  8. char sum = 0;
  9. for (i = low; i <= high; i++)
  10. {
  11. itoa(i, &bit[0], 10); // itoa并不是标准C函数
  12. for (j = 0; j < strlen(&bit[0]); j++)
  13. {
  14. if ('1' == bit[j])
  15. sum++;
  16. }
  17. }
  18. return sum;
  19. }

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

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-1-16 17:35:43 | 显示全部楼层
好好好学习 ~~~~~~~~~~~~~~~~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-1-20 20:13:31 | 显示全部楼层
都大三了,ACM已经失去激情了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-1-22 08:41:41 | 显示全部楼层
写的不错  能否继续深入
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-1-22 10:44:29 | 显示全部楼层
ACM是什么.....
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-7-2 12:05:47 | 显示全部楼层
看看老帖,支持下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-7-2 12:36:43 | 显示全部楼层
楼主你好,我现在大一刚刚开始接触ACM,非常想在这方面有所突破。
能不能加个QQ好友,还希望您能指点一二,谢谢。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-6-3 19:13:43 | 显示全部楼层
需要LOOKLOOK。。。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 21:59

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表