acm总是超时，有简单算法吗？_百度知道
acm总是超时，有简单算法吗？
求某个数中，小于自身，且含有数字9或能被9整除的数的个数。
我有更好的答案
当然有，首先求整除9的个数不需要一个个试，求含有9的也可以按位数递归。//求某个正整数中，小于自身，且含有数字9或能被9整除的正整数的个数。/*思路分析：求含有数字9的总数 + 能被9整除的总数 - 既含有数字9又能被9整除的个数具体思路：从高位到低位求含有数字9的范围 - 此范围内能被9整除的个数还要 + 此范围外的低位范围内的结果（进行递归调用），最后加上所有能被9整除的正整数个数。如此可将大整数n划分*/如下图我先写求整除9的函数，为保证字函数正确性，写了一个暴力算法进行比对。如下图结果完全正确！参考代码在网页端可见！#include&iostream&using&namespace&#include&stdlib.h&#include&time.h&//求某个正整数中，小于自身，且含有数字9或能被9整除的正整数的个数。/*思路分析：求含有数字9的总数&+&能被9整除的总数&-&既含有数字9又能被9整除的个数具体思路：从高位到低位求含有数字9的范围&-&此范围内能被9整除的个数 还要&+&此范围外的低位范围内的结果（进行递归调用）， 最后加上所有能被9整除的正整数个数。如此可将大整数n划分*///暴力验证算法int&sumOfDivided9_B(int&a,&int&b)&{ //求介于a到b(不含b)之间的能被9整除的个数 int&sum&=&0; for&(;&a&&&b;a++)&{ //暴力算法做验证
if&(0&==&a&%&9)sum++; }return&}//求介于a到b(不含b)之间的能被9整除的个数，（用户需保证a&b）int&sumOfDivided9(const&int&&a,&const&int&&b)&{ return&(b&-&1)&/&9&-&(a&-&1)&/&9; //即&1&~b-1&减去&1~a-1}int&main()&{ srand(time(0)); //随机数种子 int&count&=&0; //错误的个数 for&(int&i&=&0;&i&&&100;i++){
int&a&=&rand(),b&=&a&+&1&+&rand()&%&10000; //随机生成范围，最多10000个数
int&sum_B&=&sumOfDivided9_B(a,&b); //暴力算法
int&sum_Q&=&sumOfDivided9(a,&b); //快速算法
if&(sum_B&!=&sum_B)&{
cout&&&&&WRONG!\t&;
}else&cout&&&&&RIGHT√\t&;
cout&&&&&&(a=&&&&&a&&&&&)%9=&&&&&a&%&9&&&&&\t(b=&&&&&b&&&&&)%9=&&&&&b&%&9&&&&
&\t暴力=&&&&&sum_B&&&&&\t快速=&&&&&sum_Q&&&& } cout&&&&&WRONG&total=&&&&&count&& system(&pause&);}未完待续！
不好意思还没答完最优解法是O(logN)时间复杂度，空间可以O(1)正在写
没事，知道怎么改了
软件工程师、工学学士
#include&iostream&
#include&stdio.h&
#include&string.h&
#define M 2000005
#define mm
bool sig[M];
int prime[150000], p[150000], // 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++] =
for(j=i; j&=M; j+=i)
sig[j] = 1;
void get(int k, int s) // K! 的素数分解, S为指数的加减(分母，分子)
for(i=0; prime[i]&=k && prime[i]; i++)
while(mid)
p[i] += mid/prime[i];
p[i] -= mid/prime[i];
mid /= prime[i];
if(len & i)
__int64 cal() // 计算结果 (prime[i...]^p[i...]) % mm
__int64 i,ans = 1;
for(i=0; i&= i++)
if( p[i] )
__int64 t = prime[i], b = p[i], ret = 1;
while(b) //计算 (t^b) % mm
if(b%2) ret *= t %
ans = ( ans*ret ) %
int main()
int t,m,n,i,
getprime();
为您推荐：
其他类似问题
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。算法总结(3)--k-Sum求和，找到和为定值的多个数
2Sum,3Sum,4Sum,…,nSum这类问题
主要用到了hashmap结构，二分法思路，前后指针等
需要将2Sum问题的几种方法，算法时间和空间复杂度深刻理解，并能手写出代码来
1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
求解思路一，采用map结构，时间复杂度O(n)
ac代码如下
class Solution {
vector&int& twoSum(vector&int&& nums, int target) {
vector&int&
int len = nums.size();
if ( len & 2)
map&int, int&
for (int i = 0; i & i++){
if (mp[target - nums[i]] != 0){
res.push_back(mp[target - nums[i]] - 1);
res.push_back(i);
mp[nums[i]] = i + 1;
求解思路二，排序+二分搜索 O(nlogn)
class Solution {
int bsearch(vector&int& nums, int left, int right, int key)
while (left &= right)
int mid = right + (left - right) / 2;
if (nums[mid] == key)
else if (nums[mid] & key)
left = mid + 1;
right = mid - 1;
return -1;
vector&int& twoSum(vector&int&& nums, int target) {
int len = nums.size();
vector&int& nums2 =
if (len & 2)
vector&int&
sort(nums2.begin(), nums2.end());
for (int i = 0; i & len - 1; i++)
int findpos = bsearch(nums2, i + 1, len - 1, target - nums2[i]);
if (findpos != -1)
int val1 = nums2[i];
int val2 = nums2[findpos];
vector&int&
int vlen = 0;
for (int j = 0; j & j++)
if (nums[j] == val1 || nums[j] == val2)
v.push_back(j);
if (vlen == 2)
vector&int&
求解思路三，排序+前后指针法 O(nlogn)
class Solution {
vector&int& twoSum(vector&int&& nums, int target) {
vector&int&
int len = nums.size();
if (len & 2)
vector&int& numsTmp =
sort(nums.begin(), nums.end());
int sta = 0;
int end = len - 1;
while (sta & end)
if (nums[sta] + nums[end] == target)
bool f1 = false;
bool f2 = false;
for (int i = 0; i & i++)
if (f1 && f2)
if (!f1 && numsTmp[i] == nums[sta])
res.push_back(i);
f1 = true;
else if (!f2 && numsTmp[i] == nums[end])
res.push_back(i);
f2 = true;
else if (nums[sta] + nums[end] & target)
16. 3Sum Closest
找到和为定值的多个数
类似 背包问题
主要是递归，动态规划等方法
416. Partition Equal Subset Sum（leetcode）
这题采用dfs查找会超时，采用动态规划来做
对比零钱问题(每种数值的钱可以使用多次)
class Solution {
bool canPartition(vector&int&& nums) {
int len = nums.size();
int sums = 0;
int maxVal = -1;
for (int i = 0; i & i++)
sums += nums[i];
if (nums[i] & maxVal){
maxVal = nums[i];
if (sums % 2 == 1)
return false;
int m = sums / 2;
if (maxVal & m)
return false;
if (maxVal == m)
return true;
vector&bool& dp(m + 1, false);
dp[0] = true;
for (int i = 0; i & ++i)
for (int j = j &= nums[i]; --j)
dp[j] = dp[j] || dp[j - nums[i]];
return dp[m];
超时代码（dfs）
class Solution {
void dfs(int m, int index,vector&int&& nums,int len)
if (m & 0)
if (m == 0 && index &= len)
flag = true;
if (index &= len)
dfs(m - nums[index], index + 1,nums,len);
dfs(m, index + 1,nums,len);
bool canPartition(vector&int&& nums) {
int len = nums.size();
int sums = 0;
int maxVal = -1;
for (int i = 0; i & i++)
sums += nums[i];
if (nums[i] & maxVal){
maxVal = nums[i];
if (sums % 2 == 1)
return false;
int m = sums / 2;
if (maxVal & m)
return false;
if (maxVal == m)
return true;
flag = false;
dfs(m, 0, nums, len);
没有更多推荐了，
不良信息举报
举报内容：
算法总结(3)--k-Sum求和，找到和为定值的多个数
举报原因：
原文地址：
原因补充：
最多只允许输入30个字
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！没有更多推荐了，
不良信息举报
举报内容：
ACM入门算法之---递归专场
举报原因：
原文地址：
原因补充：
最多只允许输入30个字
加入CSDN，享受更精准的内容推荐，与500万程序员共同成长！扫一扫体验手机阅读
ACM中常用的算法有哪些？
有算法的题都是秒杀题，
难题都是YY一个方法，或是做一个畸形的变化转成一个有固定解的模型
一位高手对我的建议：
一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.acm主要是考算法的
，主要时间是花在思考算法上，不是花在写程序与debug上。
下面给个计划你练练：
第一阶段：
练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，
因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打
1.最短路(Floyd、Dijstra,BellmanFord)
2.最小生成树(先写个prim,kruscal要用并查集，不好写)
3.大数（高精度）加减乘除
4.二分查找.&
(代码可在五行以内)
5.叉乘、判线段相交、然后写个凸包.
6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)
7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.
调用系统的qsort, 技巧很多，慢慢掌握.
9. 任意进制间的转换
第二阶段：
练习复杂一点，但也较常用的算法。
1. 二分图匹配（匈牙利），最小路径覆盖
网络流，最小费用流。
3. 线段树.
4. 并查集。
熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp
6.博弈类算法。博弈树，二进制法等。
7.最大团，最大独立集。
8.判断点在多边形内。
差分约束系统.
10. 双向广度搜索、A*算法，最小耗散优先.
第三阶段：
前两个阶段是打基础，第三阶段是锻炼在比赛中可以快速建立模型、想新算法
。这就要平时多做做综合的题型了。
把oibh上的论文看看（大概几百篇的，我只看了一点点，呵呵）。
平时扫扫zoj上的难题啦，别老做那些不用想的题.(中大acm的版主经常说我挑简单的来
多参加网上的比赛，感受一下比赛的气氛，评估自己的实力.
4. 一道题不要过了就算，问一下人，有更好的算法也打一下。
5. 做过的题要记好&
逻辑类：枚举、贪心、动态规划、深搜广搜
结构类：栈、并查集、堆、树、拓扑图、图论
几何类：凸包
公式类：Fibonacci，排列组合，概率
几何类的小算法很多，比如求点线关系；还有线性方程组、最大最小流；还有一些特定的算法：最短路劲、排序等。
我感觉最其中重要的是 搜索， 搜索可以对大部分问题提供通解，但会有效率问题，于是有双向广搜、A星搜索等等。在现实应用中，我觉得相对其他一些来讲，搜索也是比较有用的。
<span type="1" blog_id="619220" userid='
分享到朋友圈
关注作者，不错过每一篇精彩一道简单的acm题目,可是老是超时!!!
[问题点数：15分，结帖人eks_222]
一道简单的acm题目,可是老是超时!!!
[问题点数：15分，结帖人eks_222]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
2009年4月 专题开发/技术/项目大版内专家分月排行榜第二2009年3月 专题开发/技术/项目大版内专家分月排行榜第二2009年2月 专题开发/技术/项目大版内专家分月排行榜第二2008年12月 专题开发/技术/项目大版内专家分月排行榜第二2008年10月 专题开发/技术/项目大版内专家分月排行榜第二2008年3月 专题开发/技术/项目大版内专家分月排行榜第二
2008年5月 专题开发/技术/项目大版内专家分月排行榜第三
匿名用户不能发表回复！|