1622人阅读
ACM其它（17）
DFS（Depth First Search ）
一般是不用hash的,所以很多时候称之为”暴力”,也就是穷举所有情况,一般看几个我们OJ的dfs的版本的题目就可以模仿着做了,因为牵涉到递归,初学者学的时候最好能举一反三,理解其中真谛.
DFS --- EASY(15)
一般的DFS有时候可能会加入一些DP的思想,从而就变成了记忆化搜索,原理是将以前算过的状态记录下来,接下来的访问就不用继续递归计算,以后直接用就好了.
DFS + DP --- EASY(7)
DFS + DP --- NORMAL(1)
DFS --- NORMAL(16)
BFS（Breadth First Search ）
BFS --- EASY(17)
BFS --- NORMAL(27)
BFS+DFS --- EASY(4)
DoubleDirectionBFS(3)
BS( Binary Search )(5)
这类题目一般不会单一只有一个算法，一般都是二分+?（最大流，二分匹配，贪心，DP）等等，这里仅列出二分枚举的题目，即二分枚举答案，然后判断可行与否。
IDA Star (4)
迭代加深本身不难，但是好的剪枝比较难想
看起来像搜索但是搜索会TLE的题一览(1)
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：344169次
积分：7289
积分：7289
排名：第1582名
原创：390篇
转载：29篇
评论：166条
(1)(2)(6)(25)(17)(6)(23)(26)(7)(12)(17)(39)(33)(22)(19)(91)(14)(35)(24)BestCoder（31）
用贪心怎么做都是有反例的。。。。用搜索做不加剪枝会TLE的。。。用set打出所有可能的数就行了。。。
#include &iostream&
#include &queue&
#include &stack&
#include &map&
#include &set&
#include &bitset&
#include &cstdio&
#include &algorithm&
#include &cstring&
#include &climits&
#include &cstdlib&
#include &cmath&
#include &time.h&
#define maxn 200005
#define maxm 200005
#define eps 1e-10
#define mod
#define INF 0x3f3f3f3f
#define PI (acos(-1.0))
#define lowbit(x) (x&(-x))
#define mp make_pair
#define ls o&&1
#define rs o&&1 | 1
#define lson o&&1, L, mid
#define rson o&&1 | 1, mid+1, R
#define pii pair&int, int&
#pragma comment(linker, &/STACK:&)
typedef long long LL;
typedef unsigned long long ULL;
//typedef int LL;
LL qpow(LL a, LL b){LL res=1,base=a;while(b){if(b%2)res=res*base=base*b/=2;}}
LL powmod(LL a, LL b){LL res=1,base=a;while(b){if(b%2)res=res*base%base=base*base%b/=2;}}
int a[maxn];
void init()
for(int i = 2; i &= 50; i++) {
a[i] = a[i-1] + a[i-2];
if(a[i] & ) {
s.insert(1);
for(set&int&::iterator it = s.begin(); it != s.end(); it++) {
int t = (*it);
for(int i = 3; i & i++) {
if((LL)t * a[i] & )
else s.insert(t * a[i]);
void work()
scanf(&%d&, &x);
if(x == 0 || s.find(x) != s.end()) printf(&Yes\n&);
else printf(&No\n&);
int main()
while(scanf(&%d&, &_)!=EOF) {
while(_--) {
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：73273次
积分：6159
积分：6159
排名：第2159名
原创：581篇
评论：17条
(4)(14)(24)(24)(30)(11)(26)(7)(47)(28)(12)(18)(60)(31)(91)(63)(52)(48)下次自动登录
现在的位置:
& 综合 & 正文
HDOJ HDU 2069 Coin Change ACM 2069 IN HDU ..WA 真的成为习惯了……………….
//MiYu原创, 转帖请注明 : 转载自
题目地址 :
目前每日平均WA次数 20次以上...................................晚上做一道水题 HDOJ 2069 ACM IN HDU, 又跟上次的 TLE 的 -1 一样, 题目的最后一段是文件结束的说明,都没怎么自习去看, 结果直接就WA了.............最后在 元帅的提醒下, 原来这题真的很水,就跟刚学编程时做的100钱买小鸡,公鸡,母鸡 100只一样, 是可以直接暴力的, 因为数据不大.
当然,也可以用 母函数来做, 不过需要增开辅助空间 :
表示i分钱由j个硬币组成的方案数 , 然后在循环中增加一个循环 :用于保存在当前硬币数量k上增加
1 - n 个硬币时 ( k + n & =100
方案数暴力:
//MiYu原创, 转帖请注明 : 转载自
1 #include &iostream& 2 int main() 3 { 4
int n, d[251] = { 0 }; 5
int c1, c5, c10, c25, c50; 6
for ( n = 0; n != 251; n ++ ) 7
for ( c50 = 0; c50 * 50 &= c50 ++ ) 9
for ( c25 = 0; c50 * 50 + c25 * 25 &= c25++ )11
for ( c10 = 0; c50 * 50 + c25 * 25 + c10 * 10 &= c10++ )13
for ( c5 = 0; c50 * 50 + c25 * 25 + c10 * 10 + c5 * 5 &= c5++ )15
c1 = n - ( c50 * 50 + c25 * 25 + c10 * 10 + c5 * 5 );17
if ( c1 + c5 + c10 + c25 + c50 &= 100 ) 18
while ( ~scanf("%d", &n) )27
printf ( "%d\n", d[n] );29
return 0;31 }32
母函数代码 :
1 #include &iostream& 2 3 int c1[251][101]; 4 int c2[251][101]; 5 int mon[6] = { 0, 1, 5, 10, 25, 50 }; 6 int sum[251]; 7 int main () 8 { 9
c1[0][0] = 1;10
for ( int i = 1; i &= 5; ++ i )11
for ( int j = 0; j &= 250; ++ j ) 13
for ( int k = 0; k * mon[i] + j &= 250; ++ k )15
for ( int p = 0; p + k &= 100; ++ p )17
c2[ j + k * mon[i] ][p + k] += c1[j][p];19
for ( int j = 0; j != 251; ++ j )23
for ( int k = 0; k != 101; ++ k )25
c1[j][k] = c2[j][k]; 27
c2[j][k] = 0;28
for ( int j = 0; j != 251; ++ j )32
for ( int i = 0; i != 101; ++ i )34
sum[j] += c1[j][i] ;36
while ( cin && N )40
cout && sum[N] &&43
return 0; 45 } 46
&&&&推荐文章:
【上篇】【下篇】图论（56）
水题，直接套用KM模板就可以过掉了。
我的代码：
#include&stdio.h&
#include&algorithm&
#include&string.h&
#define inf
int map[305][305];
int lx[305],ly[305];
bool x[305],y[305];
int link[305];
bool dfs(int u)
for(i=1;i&=n;i++)
if(lx[u]+ly[i]==map[u][i]&&!y[i])
if(link[i]==-1||dfs(link[i]))
link[i]=u;
int main()
int i,j,k;
while(scanf(&%d&,&n)!=EOF)
for(i=1;i&=n;i++)
for(j=1;j&=n;j++)
scanf(&%d&,&map[i][j]);
memset(x,0,sizeof(y));
memset(y,0,sizeof(y));
memset(link,-1,sizeof(link));
for(i=1;i&=n;i++)
memset(ly,0,sizeof(ly));
for(k=1;k&=n;k++)
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
if(dfs(k))
for(i=1;i&=n;i++)
for(j=1;j&=n;j++)
if(!y[j]&&lx[i]+ly[j]-map[i][j]&d)
d=lx[i]+ly[j]-map[i][j];
for(i=1;i&=n;i++)
lx[i]=lx[i]-d;
for(i=1;i&=n;i++)
ly[i]=ly[i]+d;
int ans=0;
for(i=1;i&=n;i++)
ans=ans+map[link[i]][i];
printf(&%d\n&,ans);
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：251224次
积分：4970
积分：4970
排名：第3095名
原创：234篇
评论：89条
(1)(2)(2)(1)(1)(4)(2)(3)(27)(43)(43)(27)(4)(12)(10)(10)(14)(14)(6)(8)文章标签 ‘TLE’
Arithmetic Progressions题目大概意思：一个等差数列是一个能表示成a, a+b, a+2b,…, a+nb (n=0,1,2,3,…)的数列。在这个问题中a是一个非负的整数，b是正整数。写一个程序来找出在双平方数集合(双平方数集合是所有能表示成p^2＋q^2的数的集合)S中长度为n的等差数列。
这个题目拿到手感觉只能暴力搜索，事实便是如此。而且题目给了5秒钟的时限，于是我就开始写搜索了。提交之后在中间某一组数据果断超时了。实在想不到该怎么优化。后来看了[......]
The Clocks一题看完之后第一个想到的就是BFS（其实很有多方法可以解决，有兴趣可以去参考参考NOCOW的解题代码）。对于这样的BFS，我都是定义结构体来作为节点，像本题中使用一个state字符串来记录当前的状态，然后最开始用了一个vector来记录已经出现过的状态，结果在提交的时候悲剧的TLE了。
于是各种加优化，想了想，中间产生大量状态，然后每次都从头到尾的搜索vector效率是低了点（对于vector来说，全局的find函数是O(N)的复杂度），于是改用map，map排序了，复杂度O[......]
（推荐使用深蓝阅读订阅）
（关于作者 Wins0n/代码疯子）
免责声明：本站所有内容仅代表个人观点，无法保证100%准确，如有错误请联系指正，谢谢！
2016年一月 &(1)
2015年十月 &(1)
2015年六月 &(2)
2015年四月 &(1)
2015年一月 &(1)
2014年十一月 &(5)
2014年十月 &(1)
2014年九月 &(1)
2014年八月 &(2)
2014年七月 &(3)
2014年六月 &(4)
2014年四月 &(1)
2014年三月 &(2)
2014年二月 &(1)
2014年一月 &(1)
2013年十二月 &(1)
2013年十一月 &(2)
2013年十月 &(2)
2013年九月 &(3)
2013年八月 &(2)
2013年七月 &(3)
2013年六月 &(2)
2013年五月 &(1)
2013年四月 &(4)
2013年三月 &(2)
2013年二月 &(1)
2013年一月 &(2)
2012年十二月 &(5)
2012年十一月 &(3)
2012年十月 &(3)
2012年九月 &(4)
2012年八月 &(4)
2012年七月 &(3)
2012年六月 &(3)
2012年五月 &(6)
2012年四月 &(4)
2012年三月 &(6)
2012年二月 &(4)
2012年一月 &(7)
2011年十二月 &(9)
2011年十一月 &(9)
2011年十月 &(13)
2011年九月 &(18)
2011年八月 &(8)
2011年七月 &(7)
2011年六月 &(16)
2011年五月 &(13)
2011年四月 &(21)
2011年三月 &(22)
2011年二月 &(15)
2011年一月 &(7)
2010年十二月 &(23)
2010年十一月 &(33)
2010年十月 &(35)
2010年九月 &(42)