acm常用算法
⑴ acm总是超时，有简单算法吗
当然有，首先求整除9的个数不需要一个个试，求含有9的也可以按位数递归。
//求某个正整数中，小于自身，且含有数字9或能被9整除的正整数的个数。
/*思路分析：
求含有数字9的总数 + 能被9整除的总数 - 既含有数字9又能被9整除的个数
具体思路：从高位到低位求含有数字9的范围 - 此范围内能被9整除的个数
还要 + 此范围外的低位范围内的结果（进行递归调用），
最后加上所有能被9整除的正整数个数。
如此可将大整数n划分
*/
如下图我先写求整除9的函数，为保证字函数正确性，写了一个暴力算法进行比对。如下图
#include<iostream>
usingnamespacestd;
#include<stdlib.h>
#include<time.h>
//求某个正整数中，小于自身，且含有数字9或能被9整除的正整数的个数。
/*思路分析：
求含有数字9的总数+能被9整除的总数-既含有数字9又能被9整除的个数
具体思路：从高位到低位求含有数字9的范围-此范围内能被9整除的个数
还要+此范围外的低位范围内的结果（进行递归调用），
最后加上所有能被9整除的正整数个数。
如此可将大整数n划分
*/
//暴力验证算法
intsumOfDivided9_B(inta,intb){ //求介于a到b(不含b)之间的能被9整除的个数
intsum=0;
for(;a<b;a++){ //暴力算法做验证
if(0==a%9)sum++;
}returnsum;
}
//求介于a到b(不含b)之间的能被9整除的个数，（用户需保证a<b）
intsumOfDivided9(constint&a,constint&b){
return(b-1)/9-(a-1)/9; //即1~b-1减去1~a-1
}
intmain(){
srand(time(0)); //随机数种子
intcount=0; //错误的个数
for(inti=0;i<100;i++){
inta=rand(),b=a+1+rand()%10000; //随机生成范围，最多10000个数
intsum_B=sumOfDivided9_B(a,b); //暴力算法
intsum_Q=sumOfDivided9(a,b); //快速算法
if(sum_B!=sum_B){
cout<<"WRONG! ";
count++;
}elsecout<<"RIGHT√ ";
cout<<"(a="<<a<<")%9="<<a%9<<" (b="<<b<<")%9="<<b%9<<
" 暴力="<<sum_B<<" 快速="<<sum_Q<<endl;
}
cout<<"WRONGtotal="<<count<<endl;
system("pause");
}
未完待续！
⑵ 参加ACM大赛应该准备哪些课程
课程：
（1）基本算法: 二分,分治，贪心
（2） 离散数学离散数学动态规划
（3） 搜索算法：深度优先 搜索，广度优先搜A*算法 ，阿尔法贝塔剪枝
（4）数据结构:线段树, 树状数组，并查集,Trie图
（5）图论问题：最小生成树 最短路 强连通分量、桥和割点
（6）网络流算法：基本的网络流算法，Dinic算法，带上下界的网络流，最小费用流
（7）计算几何：线与线求交，线与面求交，求凸包，半平面求交等
（8） 离散数学，高等数学，线性代数，初等数论，计算几何
（9）计算机专业英语
（10）C++；基础的递归、枚举算法
(2)acm常用算法扩展阅读：
1.参赛队伍最多由三名参赛队员组成。
2.竞赛中命题10题左右，试题描述为英文，比赛时间为5个小时，前四个小时可以实时看到排名，最后一小时封榜，无法看到排名。
3.竞赛可以使用的语言：java, C, C++, Kotlin 和 Python。
4.重点考察选手的算法和程序设计能力，不考察实际工程中常用的系统编程，多线程编程等等；
5.选手可携带任何非电子类资料，包括书籍和打印出来的程序等，部分赛区会对选手携带的纸质资料做限制。
6.评委负责将结果（正确或出错的类型）通过网络尽快返回给选手，除此之外不提供任何额外帮助；
7.每个题目对应一种颜色的气球，通过该题目的队伍会得到对应颜色气球。每道题目第一支解决掉它的队还会额外获得一个“FIRST PROBLEM SOLVED”的气球。
⑶ acm中基本算法有哪些
回溯算法，贪心法，蛮力法，动态规划，分支限界，图算法
⑷ 我是用的是C语言，想在黑龙江省ACM大赛中拿三等奖,应该掌握那些算法……
当中有几百种计算机常用的算法的框架和模板，如果你还在为算法问题而困扰时，这资料会让你廓然开朗，我也在学，很有用所以极力推荐给你.
框架部分目录如下：
图论
路径问题
0/1边权最短路径
BFS
非负边权最短路径（Dijkstra）
可以用Dijkstra解决问题的特征
负边权最短路径
Bellman-Ford
Bellman-Ford的Yen-氏优化
差分约束系统
Floyd
广义路径问题
传递闭包
极小极大距离/极大极小距离
EulerPath/Tour
圈套圈算法
混合图的EulerPath/Tour
HamiltonPath/Tour
特殊图的HamiltonPath/Tour构造
生成树问题
最小生成树
第k小生成树
最优比率生成树
0/1分数规划
度限制生成树
连通性问题
强大的DFS算法
无向图连通性
割点
割边
二连通分支
有向图连通性
强连通分支
2-SAT
最小点基
有向无环图
拓扑排序
有向无环图与动态规划的关系
二分图匹配问题
一般图问题与二分图问题的转换思路
最大匹配（OK）
有向图的最小路径覆盖
0/1矩阵的最小覆盖
完备匹配（OK）
最优匹配（OK）
稳定婚姻
网络流问题
网络流模型的简单特征和与线性规划的关系
最大流最小割定理
最大流问题（OK）
有上下界的最大流问题
循环流
最小费用最大流/最大费用最大流
弦图的性质和判定
组合数学
解决组合数学问题时常用的思想
逼近
递推/动态规划
概率问题
Polya定理
计算几何/解析几何
计算几何的核心：叉积/面积
解析几何的主力：复数
基本形
点
直线，线段
多边形
凸多边形/凸包
凸包算法的引进，卷包裹法
Graham扫描法
水平序的引进，共线凸包的补丁
完美凸包算法
相关判定
两直线相交
两线段相交
点在任意多边形内的判定
点在凸多边形内的判定
经典问题
最小外接圆
近似O(n)的最小外接圆算法
点集直径
旋转卡壳，对踵点
多边形的三角剖分
数学/数论
高精度计算
高数度加减法、乘除法
最大公约数
Euclid算法
扩展的Euclid算法
同余方程/二元一次不定方程
同余方程组
线性方程组
高斯消元法
解mod2域上的线性方程组
整系数方程组的精确解法
矩阵
行列式的计算
利用矩阵乘法快速计算递推关系
分数
分数树
连分数逼近
数论计算
求N的约数个数
求phi(N)
求约数和
快速数论变换
……
素数问题
概率判素算法
概率因子分解
数据结构
组织结构
二叉堆
左偏树
二项树
胜者树
跳跃表
样式图标
斜堆
reap
统计结构
树状数组
虚二叉树
线段树
矩形面积并
圆形面积并
关系结构
Hash表
并查集
路径压缩思想的应用
STL中的数据结构
vector
deque
set/map
动态规划/记忆化搜索
动态规划和记忆化搜索在思考方式上的区别
最长子序列系列问题
最长不下降子序列
最长公共子序列
一类NP问题的动态规划解法
树型动态规划
背包问题
动态规划的优化
四边形不等式
函数的凸凹性
状态设计
规划方向
线性规划
常用思想
二分
最小表示法
串
KMP
Trie结构
后缀树/后缀数组
LCA/RMQ
有限状态自动机理论
排序
选择/冒泡
快速排序
堆排序
归并排序（OK）
基数排序
拓扑排序
排序网络
⑸ 怎样求大组合数（取模）（ACM算法）
这种题目然做过的，
意思比较简单，就由 m 个共 0 和 n 个 1 组成一个串，但从左到右要1出现的次数不少于0出现的次数。
由大牛的算法： 结果就是 C(m+n, n) - C(m+n, m-1) 再取模，我们可以对式子化简一下就是：
(n+m)！*
(n-m+1) / ((m)！* (n+1)！)
再取模，但由于组合数很大，直接用大数乘除就会超时了，看了别人的报告才知道原来可以用素数化简快速求模的， n! = 2^p[i] *
3^p[i] * 5^p[i]*...... 再求模就可以很快了~(^ = ^)~。。。
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define M 2000005
#define mm 20100501
bool sig[M];
int prime[150000], p[150000], len; // prime 记录素数， p 记录素数的幂 len 记录长度
void getprime() // 筛法找素数
{
int i,j,k=0;
prime[k++] = 2;
for(i=3; i<=M; i+=2)
{
if( !sig[i] )
{
prime[k++] = i;
for(j=i; j<=M; j+=i)
sig[j] = 1;
}
}
}
void get(int k, int s) // K! 的素数分解, S为指数的加减(分母，分子)
{
int i, mid;
for(i=0; prime[i]<=k && prime[i]; i++)
{
mid = k;
while(mid)
{
if(s)
p[i] += mid/prime[i];
else
p[i] -= mid/prime[i];
mid /= prime[i];
}
}
if(len < i)
len = i;
}
__int64 cal() // 计算结果 (prime[i...]^p[i...]) % mm
{
__int64 i,ans = 1;
for(i=0; i<=len; i++)
{
if( p[i] )
{
__int64 t = prime[i], b = p[i], ret = 1;
while(b) //计算 (t^b) % mm
{
if(b%2) ret *= t %mm;
t = t*t%mm;
b /= 2;
}
ans = ( ans*ret ) % mm;
}
}
return ans;
}
int main()
{
int t,m,n,i,mid;
__int64 ans;
getprime();
cin>>t;
while(t--)
{
cin>>n>>m;
len = 0;
memset(p, 0, sizeof(p));
mid = n-m+1; //先前要把 n-m+1 的因子加进 P 中去才能使 (m+n)! / ((m)!*(n+1)!) 整除
for(i=0; mid>1; i++)
{
if( mid%prime[i] == 0)
{
while(mid%prime[i]==0)
{
p[i] += 1;
mid /= prime[i];
}
}
}
get(m+n, 1);
get(m, 0);
get(n+1, 0);
ans = cal();
printf("%I64d\n", ans);
}
return 0;
}
可以用素数分解法，
先求出上面和下面的素数表示，然后约分后，再用求幂公式
⑹ ACM初学者要学习的内容
ACM国际大学生程序设计竞赛：知识与入门.pdf
链接: https://pan..com/s/19OY2FJUkk4RhW5WTsPkwfQ
《ACM国际大学生程序设计竞赛:知识与入门》适用于参加ACM国际大学生程序设计竞赛的本科生和研究生，对参加青少年信息学奥林匹克竞赛的中学生也很有指导价值。
⑺ ACM 凸包 算法
先解释下凸包 顾名思义 就是多边形是凸的 没有某个点是凹进多边形内部的 哈 文字我也描述不清楚 在高等数学里就有凸的定义 二次导数恒不小于0
再者 就是凸包算法的定义了 凸包算法一般就是计算能包裹住一个点集的最小的凸多边形
至于具体的算法 有很多 也不贴过来了 请看这篇帖子 伪代码比较容易看懂算法的原理
http://www.blogjava.net/sishuiweilan/archive/2007/10/10/151671.html
不懂的地方请追问
⑻ acm求个不超时的算法思路
第一步：将输入的数组进行排序，规则是由绝对值的大小由大到小排序 a[n] //用于存放输入的数字 for(int i=0; i<n; i++) { for(int j=i; j<n; j++) if((a[i]>a[j] && a[i]>-a[j]) || (-a[i]>a[j] && -a[i]>-a[j]) ) { swap(a[i], a[j]); //数值互换函数 } } 排列好以后取出前m个数进行乘法运算，结果为result 然后判断result是否大于零 如果大于零 你可以直接输出了 如果小于零 找出数组前m个中最小的正数 min1 以及绝对值最小的负数 min2 以及后面的数中的最大的正数 max1 以及后面的数种绝对值最大的负数 max2 我们之前已经排列过了 应该很好找 进行判断 if(min1*max1 > min2*max2) result = result/min2 *max1; else result = result/min1 *max2; 然后输出结果result就成了 如果你还想输出排列后的数组的话，就把前面判断里的直接计算 改成剔除数字里的min2和max1 互换位置 或将 min1和max2 互换位置，再进行计算输出就成了
⑼ 关于ACM竞赛
ACM考的是算法设计,编程,理解能力.
基本上ACM的题目都是英文的,所以你的英文要到火候,这个lz
应该没问题吧.
还有最主要的就是算法了,你可以去肯"算法导论"这本牛书.
第三就是编程能力,ACM竞赛中,时间也是一项衡量指标,怎样在最快的时间内解决问题,编译通过,并且运行正确.
最后,我觉得考虑问题的全面性也是很重要的,ACM的题目,很多都会有临界情况,如何让你的程序能够通过这些临界值的检验,很考察一个人思考问题的全面性的.