ACM模板.pdf内容包括搜索回溯分治、计算几何、动态规划、背包问题求解、线段树典型求解问题、字典树

文件名称: ACM模板.pdf

所属分类: C++

开发工具:

文件大小: 1mb

下载次数: 0

上传时间: 2019-07-01

提供者: fhav****

下载 (1mb)

不能下载？报告错误

详细说明：内容包括搜索回溯分治、计算几何、动态规划、背包问题求解、线段树典型求解问题、字典树、图论、差分约束系统、贪心等，适用于大学生ACM竞赛赛前准备训练for第i个旱后的位置=1to8do ∥在本行的8列中去试 f本行本列允许放置皇后then begin 放置第i个皇后对放置呈后的位置进行标记 ifi8then输出 |经放完个皇后 else Search(i+l) ∥放置第计1个呈后对放置皇后的位冒释放标记,尝试下一个位置是否可行 end #inc ludesiostream'> #inc lude using namespace std ta9]; bool hang9」 ∥行标记 bool lie[91 ∥列标记 bool xiel[l7I \标记 bool xie2[17];∥/标记 oid printo al printf("<%od>. " total int Fo for(Fl; iy printf("%d", a[j]); printf(n") void scarch(int t) int io for(Fl; 1<9; t+1) ∥搜索所有的可能性 if (hanglt] &&lic[i&&xicI[(t-1)+8]&&xic2[t+i) a[t]=i hang[]=ic[i]=xiel[t)+8]=xi2tij- false;∥改变标记得到种答案 printo; Else /没有得到,则继续搜索 hang[t-ie[i-xiel[(ti+8]xie2t+i]-true;/把标记改回来,继续搜 mcmsct(hang, truc, sizeof(hang) memset(lie, true, sizeof(lie)) memset(xiel, true, sizeof(xiel)) memset(xie, true, sizeof(xie2) total printf("total: %od\n, total) (例2)素数环素数环:从1到20这20个数摆成一个环,要求相邻的两个数的和是一个素数算法分析】非常明显,这是一道回溯的题目。从1开始,每个空位有20种可能,只要填进去的数合法:与前面的数不相同;与左边相邻的数的和是一个素数。第20个数还要判断和第 1个数的和是否素数。【算法流稈】 l、数据初始化;2、递归填数:判断第J种可能是否合汯 A、如果合法:填数:判断是否到达日标(20个己填完):是,打印结果;不是,递归填下一个 B、如果不合法:选择下一种可能 #inc lude #includec-cmath using namespace std int a[21]; bool b[21] int total oid printo int i0 for(i=1;i<21;+-i printf("od "a]) printf("in); har ch ch=cin. get g bool pd(int a, int b) int c=a+b double sqrt=sqrt(c*1.0); int 10 f(c%=0) false return true: id search(int t) int i0 for(i=1i<=20;-+i) 搜索所有的可能性 if(pd(alt-1l, i)&&bi) [=i; bi]=false; ∥变标记 i(t20) fpd(a20],a[1])∥搜到一种答案 Else 没有搜到,继续搜索 earch(t+1) b[i]=true; /把标记改回来 mcmsct(b, truc, sizeof(b)) Lotal( scarch(1); cout<<"total: < #includes algorithm> using namespace std int stic knumber bian bool fla int sticklength[25] bool used[25] void check(int s, int bs, int next) ∥从next根棍的位置开始拼凑长度,s:当前长度bs:已经拼凑的木棍数 Int ns, nbs, 1 if(flag==true) return or(i=ncxt;i< sticknumbcr;计+)从ncxt开始搜索 if (used[==tr continue if(ns+stic klength[i]>bian) continue ns+=sticklength[i [ if(ns==bian) =0; nos 找到了三边,另一边也就不用找了 g if(flag==true) break i(ns==0)∥/如果要重雜凑边要从新开始搜索即从最大的没用的木棍开始 if(nsb: int maino //freopen("inLxt","I", Stdin) int tcstnumber cin>>testnumber int 1 while( testnumber-- cin>>sticknumbcr bian=( memset(used, 0, stic knumber*sizeof(bool)) for (i=0; i>sticklength[i bian+=sticklength 1 sort(stic klength, stic klength+sticknumber, cmp) g if(bian%4)!=0)不是4的倍数(剪枝2) flag=false bian=bian /4 i( sticklength[0]}>bian)第一根木棍的长度大于边长(剪枝1) flagfals if( nlag==false) cout continue; ag check(0,0,0); if(flag-true cout< using namespace std int a[ 1100] Int ans void merge(ints, int mid int)从大到小排序 int b[1100] Int 1 cout<< merge"aliD) b[k++]=a1 cout<"a"<<"J;"≤a[<”a["j<":""< a (t-j+1)<=0) as+k]=b[k--I /* for(is; K<=t; i++) cout<]< t) return int mid=(s+t)/2 mergesort(s, mid) mergesort(mid+1, t) erge(s, mid, t);

(系统自动生成,下载前可以参看下载内容)