快速排序是最快的排序算法，多用来将长度为10000~200000的数组排序。
var n,i:longint; a:array[1..100000] of longint; procedure qsort(l,r:longint); var i,j,temp,mid:longint; begin i:=l; j:=r; mid:=a[(l+r) div 2]; repeat while a[i]<mid do inc(i); while a[j]>mid do dec(j); if i<=j then begin temp:=a[i];a[i]:=a[j];a[j]:=temp; inc(i);dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; begin readln(n); for i:=1 to n do read(a[i]); qsort(1,n); for i:=1 to n do write(a[i],' '); end.选择排序是最容易写的排序，最高可以使长度在千级的数组有序。注意如果元素很少，采用选择排序可能会优于快速排序。
var a:array[1..1000]of longint; i,j,t,n:longint; begin read(n); for i:=1 to n do read(a[i]); for i:=1 to n-1 do for j:=i+1 to n do if a[i]>a[j] then begin t:=a[i];a[i]:=a[j];a[j]:=t; end; for i:= 1 to n do write(a[i],' '); end.这是一种稍微高级一些的算法，和快速排序一样采用了分治思想，不过这种方法是稳定的排序。归并排序还可以顺便求一下逆序对个数。
var i,n,ans:longint; a,b:array[0..1000001]of longint; procedure msort(l,r:longint); var i,j,k,mid:longint; begin if l>=r then exit; mid:=(l+r) div 2; msort(l,mid); msort(mid+1,r); i:=l; j:=mid+1; k:=l; while (i<=mid)or(j<=r) do begin if (i<=mid) and ((j>r)or(a[i]<=a[j])) then begin b[k]:=a[i]; inc(i); //ans:=ans+j-mid-1;这一步就是求逆序对，最后输出ans即可 end else begin b[k]:=a[j]; inc(j); end; inc(k); end; for i:=l to r do a[i]:=b[i]; end; begin read(n); for i:=1 to n do read(a[i]); msort(1,n); for i:=1 to n do write(a[i],' '); end.这种排序听上去很难，平时也很少用，但某些情况它可以起大用处（见NOIP2004提高组合并果子）。实际上它的代码并不长。
var i,n:longint; a:array[0..1000001] of longint; procedure swap(var a,b:longint); var t:longint; begin t:=a; a:=b; b:=t; end; procedure heapsort(i,m:longint); var t:longint; begin t:=i*2; while t<=m do begin if (t<m) and (a[t]>a[t+1]) then inc(t); if a[i]>a[t] then begin swap(a[i],a[t]);i:=t;t:=2*i; end else break; end; end; begin read(n); for i:=1 to n do read(a[i]); for i:=n div 2 downto 1 do heapsort(i,n); for i:=n downto 2 do begin write(a[1],' '); a[1]:=a[i]; heapsort(1,i-1); end; write(a[1]); end.搜索，骗分神器也。绝大多数的题目深搜都可以得到一些分（顺便卡卡评测机），想不出来高分解法时就靠它了。下面的程序以N皇后问题来作为模板。
var s,n:longint; b,c,d:array[-26..26]of boolean; a:array[1..13]of longint; procedure search(k:longint); var i:longint; begin if k=n+1 then begin inc(s); for i:=1 to n-1 do write(a[i],' '); writeln(a[n]); exit; end; for i:=1 to n do if (not b[i])and(not c[i-k])and(not d[k+i]) then begin b[i]:=true;c[i-k]:=true;d[k+i]:=true; a[k]:=i; search(k+1); b[i]:=false;c[i-k]:=false;d[k+i]:=false; end; end; begin s:=0; read(n); search(1); write(s); end.宽搜是对深搜的优化，采用了队列的方式，思维复杂度较深搜有一些提高。下面的程序以细胞问题来作为模板。
type rec=record x,y:longint; end; var m,n,i,j,k,sum,r,h:longint; q:array[0..10001]of rec; a:array[0..100,0..100]of boolean; u:array[1..4]of integer=(1,-1,0,0); v:array[1..4]of integer=(0,0,-1,1); x:char; procedure bfs(i,j:longint); begin h:=0;r:=1; q[1].x:=i;q[1].y:=j; a[i,j]:=false; while h<r do begin inc(h); for k:=1 to 4 do if a[q[h].x+u[k],q[h].y+v[k]] then begin inc(r); q[r].x:=q[h].x+u[k];q[r].y:=q[h].y+v[k]; a[q[r].x,q[r].y]:=false; end; end; end; begin readln(m,n); for i:=1 to m do begin for j:=1 to n do begin read(x); if ord(x)>ord('0') then a[i,j]:=true else a[i,j]:=false; end; readln; end; sum:=0; for i:=1 to m do for j:=1 to n do if a[i,j] then begin inc(sum); bfs(i,j); end; write(sum); end.哈希适用于状态不多但是很大的情况，最重要的就是找到一个高效的哈希函数，然后就不难了。下面的程序以暗杀问题（这真的是一道Hash题而不是什么Novel或Teleplay）来作为模板。
const inf=10007; type arr=array[0..31]of longint; rec=record data,no:longint; end; var sum,count:array[0..100001,0..30]of longint; h:array[0..inf,0..55]of rec; i,j,n,m,max,t:longint; function check(x,y:longint):boolean; var i:longint; begin for i:=1 to m do if count[x,i]<>count[y,i] then exit(false); exit(true); end; procedure insert(t:longint); var i,p:longint; begin p:=0; for i:=1 to m do p:=p+count[t,i]*i; p:=abs(p) mod inf; i:=0; while h[p,i].no=1 do begin if check(h[p,i].data,t)=true then begin if t-h[p,i].data>max then max:=t-h[p,i].data; exit; end; inc(i); end; h[p,i].no:=1; h[p,i].data:=t; end; begin max:=0; fillchar(h,sizeof(h),0); h[0,0].no:=1; readln(n,m); for i:=1 to n do begin read(t); for j:=1 to m do begin sum[i,j]:=sum[i-1,j]+t mod 2; count[i,j]:=sum[i,j]-sum[i,1]; t:=t shr 1; end; insert(i); end; write(max); end.可以多次求出某个个静态区间里的最大值（或最小值等等）。下面的程序以天才的记忆来作为模板。
var st:array[0..200001,0..21]of longint; a:array[0..200001]of longint; i,j,n,q,l,r,len:longint; function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; begin readln(n); for i:=1 to n do begin read(a[i]); st[i,0]:=a[i]; end; readln(q); for j:=1 to trunc(ln(n)/ln(2)) do for i:=1 to n-(1 shl j)+1 do st[i,j]:=max(st[i,j-1],st[i+(1 shl (j-1)),j-1]); for i:=1 to q do begin readln(l,r); len:=trunc(ln(r-l+1)/ln(2)); writeln(max(st[l,len],st[r-(1 shl len)+1,len])); end; end.如果把上一种算法的“静态”改成“动态”（就是这个序列不断变化），RMQ算法就不再适用，线段树会更好用。下面的程序以动态区间求和来作为模板。
#include<iostream> using namespace std; #define int long long struct node { int l,r,sum; } tree[300001]; int a[100001],f[100001]; int lazy[300001]; void buildTree(int x,int l,int r) { tree[x].l=l;tree[x].r=r; if (l==r) { tree[x].sum=a[l]; return; } buildTree(x*2,l,(l+r)>>1); buildTree(x*2+1,1+((l+r)>>1),r); tree[x].sum=tree[x*2].sum+tree[x*2+1].sum; } void pushdown(int x) { int mid=(tree[x].l+tree[x].r)/2; tree[x*2].sum+=(mid-tree[x].l+1)*lazy[x]; tree[x*2+1].sum+=(tree[x].r-mid)*lazy[x]; lazy[x*2]+=lazy[x]; lazy[x*2+1]+=lazy[x]; lazy[x]=0; } void update(int x,int l,int r,int k) { if(tree[x].l>=l&&tree[x].r<=r) { tree[x].sum+=(tree[x].r-tree[x].l+1)*k; lazy[x]+=k; return; } if(tree[x].l>r||tree[x].r<l) return; int mid=(tree[x].r+tree[x].l)/2; if(lazy[x])pushdown(x); update(x*2,l,r,k); update(x*2+1,l,r,k); tree[x].sum=tree[x*2].sum+tree[x*2+1].sum; } int query(int x,int l,int r) { if(tree[x].l>=l&&tree[x].r<=r) return tree[x].sum; if(tree[x].l>r||tree[x].r<l) return 0; if(lazy[x])pushdown(x); return query(x*2,l,r)+query(x*2+1,l,r); } signed main() { int n,m,t,x,y,z; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; buildTree(1,1,n); for(int i=1;i<=m;i++) { cin>>t>>x>>y; if(t==1){cin>>z;update(1,x,y,z);} else cout<<query(1,x,y)<<endl; } return 0; }和线段树差不多，下面的程序仍以动态区间求和来作为模板，不过这题和上面的不一样。
#include<cstdio> #include<cstring> long long a[500010],c[500010]; int n,m,x,y,k,t; long long lowbit(long long x) { return x&-x; } long long sum(long long x) { long long ret=0; while (x>0) { ret+=c[x]; x-=lowbit(x); } return ret; } void add(long long x,long long d) { while (x<=n) { c[x]+=d; x+=lowbit(x); } } int main() { scanf("%d%d",&n,&m); memset(a,0,sizeof(a)); for (int i=1;i<=n;i++) { scanf("%d",&x);add(i,x); } for (int i=1;i<=m;i++) { scanf("%d%d%d",&k,&x,&y); if (k==1) add(x,y); else printf("%d\n",sum(y)-sum(x-1)); } return 0; }将边按照权值排序后贪心一遍即可。
var i,n,m,ans,root1,root2:longint; elen,eu,ev,father:array[0..200001]of longint; procedure qsort(l,r:longint); var i,j,temp,mid:longint; begin i:=l; j:=r; mid:=elen[(l+r) div 2]; repeat while elen[i]<mid do inc(i); while elen[j]>mid do dec(j); if i<=j then begin temp:=elen[i];elen[i]:=elen[j];elen[j]:=temp; temp:=eu[i];eu[i]:=eu[j];eu[j]:=temp; temp:=ev[i];ev[i]:=ev[j];ev[j]:=temp; inc(i);dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; function getfather(x:longint):longint; begin if father[x]=x then exit(x); father[x]:=getfather(father[x]); exit(father[x]); end; begin readln(n,m); for i:=1 to m do readln(eu[i],ev[i],elen[i]); qsort(1,m); ans:=0; for i:=1 to m do ans:=ans+elen[i]; for i:=1 to n do father[i]:=i; for i:=1 to m do begin root1:=getfather(eu[i]); root2:=getfather(ev[i]); if root1=root2 then ans:=ans-elen[i] else father[root1]:=root2; end; write(ans); end.双重循环枚举点，替换最优值。不过还是克鲁斯卡尔算法用的多些。
const maxn=1001; var cost:array[1..maxn,1..maxn] of longint; lowcost,closet:array[1..maxn] of longint; i,j,k,n,min,mincost:longint; begin readln(n); for i:=1 to n do for j:=1 to n do read(cost[i,j]); for i:=1 to n do begin lowcost[i]:=cost[1,i]; closet[i]:=1; end; mincost:=0; for i:=1 to n-1 do begin min:=maxlongint div 3; for j:=1 to n do if (lowcost[j]<>0) and (lowcost[j]<min) then begin min:=lowcost[j]; k:=j; end; mincost:=mincost+cost[closet[k],k]; writeln('(',closet[k],',',k,')'); lowcost[k]:=0; for j:=1 to n do if cost[k,j]<lowcost[j] then begin lowcost[j]:=cost[k,j];closet[j]:=k end; end; write(mincost); end.和普利姆算法的程序非常相似。
var a:array[1..1000,1..2]of longint; c:array[1..1000]of real; b:array[1..1000]of boolean; f:array[1..1000,1..1000]of real; n,i,j,k,x,y,m,s,t:longint; min:real; begin readln(n); for i:=1 to n do readln(a[i,1],a[i,2]); readln(m); fillchar(f,sizeof(f),$5f); for i:=1 to m do begin readln(x,y); f[x,y]:=sqrt(sqr(a[x,1]-a[y,1])+sqr(a[x,2]-a[y,2])); f[y,x]:=f[x,y]; end; readln(s,t); for i:=1 to n do c[i]:=f[s,i]; for i:=1 to n-1 do begin min:=maxlongint; k:=0; for j:=1 to n do if (not b[j])and(c[j]<min) then begin min:=c[j]; k:=j; end; if k=0 then break; b[k]:=true; for j:=1 to n do if c[k]+f[k,j]<c[j] then c[j]:=c[k]+f[k,j]; end; writeln(c[t]:0:2); end.最经典的方法，三重循环枚举即可。
var map,dis:array[0..101,0..101]of extended; x,y:array[0..101]of longint; a,b,i,j,k,n,m,s,t:longint; function min(x,y:real):real; begin if x<y then exit(x) else exit(y); end; begin readln(n); for i:=1 to n do readln(x[i],y[i]); readln(m); for i:=1 to n do for j:=1 to n do map[i,j]:=1e30/3; for i:=1 to m do begin readln(a,b); map[a,b]:=sqrt(sqr(x[a]-x[b])+sqr(y[a]-y[b])); map[b,a]:=map[a,b]; end; readln(s,t); dis:=map; for k:=1 to n do for i:=1 to n do for j:=1 to n do dis[i,j]:=min(dis[i,j],dis[i,k]+dis[k,j]); write(dis[s,t]:0:2); end.将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。
var map:array[0..101,0..101]of longint; c,d:array[0..101]of longint; flag:array[0..101]of boolean; i,j,k,n,x,y:longint; check:boolean; begin fillchar(map,sizeof(map),false); fillchar(c,sizeof(c),0); fillchar(d,sizeof(d),0); readln(n); while not eof do begin readln(x,y); inc(c[x]); inc(d[y]); map[x,c[x]]:=y; end; fillchar(flag,sizeof(flag),false); for k:=1 to n do begin for i:=1 to n do if (flag[i]=false)and(d[i]=0) then begin write(i,' '); flag[i]:=true; for j:=1 to c[i] do dec(d[map[i,j]]); break; end; end; end.给出一个背包，让你往里面放入一些物品，物品有价值和重量，每个物品只能放一次，求最大价值。
var i,j,n,m:longint; f:array[0..100000]of longint; c,w:array[0..5000]of longint; begin fillchar(f,sizeof(f),0); readln(n,m); for i:=1 to n do readln(w[i],c[i]); for i:=1 to n do for j:=m downto w[i] do if f[j-w[i]]+c[i]>f[j] then f[j]:=f[j-w[i]]+c[i]; write(f[m]); end.与01背包唯一的区别就是每件物品都用无数件。
uses math; const maxn=1000; var i,j,n,m:longint; w,u:array[1..maxn]of longint; f:array[0..maxn,0..maxn]of longint; begin read(m,n); for i:=1 to n do read(w[i],u[i]); for i:=1 to n do for j:=1 to m do if j<w[i] then f[i,j]:=f[i-1,j] else f[i,j]:=max(f[i-1,j],f[i,j-w[i]]+u[i]); write(f[n,m]); end.与01背包唯一的区别就是每件物品都有Num[i]件。
var n,m,i,j:longint; w,p,s:int64; a,b,c,f:array[0..1000000] of int64; begin read(n,m); for i:=1 to n do read(c[i],a[i],b[i]); for i:=1 to n do begin s:=1; while s shl 1-1<=b[i] do begin w:=a[i]*s; p:=c[i]*s; for j:=m downto w do if f[j-w]+p>f[j] then f[j]:=f[j-w]+p; s:=s shl 1; end; s:=b[i]-s+1; if s=0 then continue; w:=a[i]*s; p:=c[i]*s; for j:=m downto w do if f[j-w]+p>f[j] then f[j]:=f[j-w]+p; end; write(f[m]); end.举个通(wei)俗(suo)的例子，有一些男生和女生，他们中的一些人喜欢某些异性，那么最多可以创造多少对情侣（雾）呢？这个问题可以用匈牙利算法解决。下面的程序以棋盘覆盖来作为模板。
var map:array[1..10000,1..4] of longint; link,v:array[1..10000] of longint; cover:array[1..10000] of boolean; n,m,x,y,i,j,ans:longint; visit:array[0..101,0..101] of boolean; function find(i:longint):boolean; var k,q,m:longint; begin find:=true; for m:=1 to v[i] do begin k:=map[i,m]; if not cover[k] then begin q:=link[k];link[k]:=i; cover[k]:=true; if (q=0)or(find(q)) then exit; link[k]:=q; end; end; exit(false); end; begin readln(n,m); fillchar(visit,sizeof(visit),false); fillchar(v,sizeof(v),0); for i:=1 to n do for j:=1 to n do visit[i,j]:=true; for i:=1 to m do begin readln(x,y); visit[x,y]:=false; end; for i:=1 to n*n do begin x:=(i-1) div n+1; y:=i-(x-1)*n; if not visit[x,y] then continue; if visit[x+1,y] then begin inc(v[i]);map[i,v[i]]:=i+n; end; if visit[x-1,y] then begin inc(v[i]);map[i,v[i]]:=i-n; end; if visit[x,y+1] then begin inc(v[i]);map[i,v[i]]:=i+1; end; if visit[x,y-1] then begin inc(v[i]);map[i,v[i]]:=i-1; end; end; for i:=1 to n*n do begin x:=(i-1) div n+1; y:=i-(x-1)*n; if not visit[x,y] then continue; fillchar(cover,sizeof(cover),0); find(i); end; ans:=0; for i:=1 to n*n do if link[i]<>0 then inc(ans); write(ans div 2); end.位运算本身并不是一种算法，只是比普通的乘和除速度快。有时候，位运算可以起到神奇的作用（比如逻辑电路）。 常用位运算列表： And运算：都1取1，否则取0 Or运算：有1取1，否则取0 Xor运算：不同取1，相同取0 Not运算：全部取反 Shl运算：相当于乘以2 Shr运算：相当于除以2
给出两个字符串，快速求出第一个字符串在第二个字符串中出现的位置。
#include<cstdio> #include<cstring> char t[1000010],p[1000010]; int f[1000010]; void getfail(char* p,int* f) { int m=strlen(p); f[0]=0;f[1]=0; for (int i=1;i<m;i++) { int j=f[i]; while (j && p[i]!=p[j]) j=f[j]; f[i+1]=p[i]==p[j]? j+1 : 0; } } void find(char* t,char* p,int* f) { int n=strlen(t),m=strlen(p); getfail(p,f); int j=0; for (int i=0;i<n;i++) { while (j && p[j]!=t[i]) j=f[j]; if (p[j]==t[i]) j++; if (j==m) printf("%d\n",i-m+2); } } int main() { scanf("%s",&t); scanf("%s",&p); find(t,p,f); for (int i=1;i<=strlen(p);i++) printf("%d ",f[i]); }处理集合的合并和查询问题，有时与其他算法混合。下面的程序以家族来作为模板。
var father:array[1..6000] of longint; n,m,p,i,x,y:longint; function getfather(x:longint):longint; begin if father[x]=x then exit(x) else begin father[x]:=getfather(father[x]); exit(father[x]); end; end; procedure merge(x,y:longint); var fa1,fa2:longint; begin fa1:=getfather(x);fa2:=getfather(y); father[fa1]:=fa2; end; function judge(x,y:longint):boolean; var fa1,fa2:longint; begin fa1:=getfather(x);fa2:=getfather(y); if fa1=fa2 then exit(true) else exit(false); end; begin readln(n,m,p); for i:=1 to n do father[i]:=i; for i:=1 to m do begin readln(x,y); merge(x,y); end; for i:=1 to p do begin readln(x,y); if judge(x,y) then writeln('Yes') else writeln('No'); end; end.这个东西没有什么好解释的，多记些公式定理，万一用上就赚大了。比如排列和组合的公式、斜率和截距的公式、点和线距离的公式等等。
每一题都有把握AC的神犇还是很少的，所以对于我们这些蒟蒻来说，能得分就已经很高兴了，所以我们要学会骗分。当然，会做的题目还是没有必要骗的。现在的试题输出样例几乎得不到分，我们可以分析样例，输出一个式子（或者随机数），这样得分的几率比输出样例大一些。不过再次强调骗分导论不能喧宾夺主，学好算法才是根本。更详细的骗分导论点击这里。
快速幂，顾名思义就是快速计算a^b mod n的值，且复杂度为log级。
var a,b,n:int64; function f(a,b,n:int64):int64; var t,y:int64; begin t:=1; y:=a; while b<>0 do begin if(b and 1)=1 then t:=t*y mod n; y:=y*y mod n; b:=b shr 1; end; exit(t); end; begin read(a,b,n); write(f(a,b,n)); end.解线性方程组的一种方法。下面的程序以高斯消元法来作为模板。
#include<iostream> #include<cstdio> #define N 101 using namespace std; int n,Max; double a[N][N],ans[N],t; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=n+1;j++) scanf("%lf",&a[i][j]); for(int k=1;k<=n;k++){ Max=k; for(int i=k+1;i<=n;i++) if(a[i][k]>a[Max][k]) Max=i; for(int i=k;i<=n+1;i++) swap(a[Max][i],a[k][i]); for(int i=k+1;i<=n;i++){ t=a[i][k]/a[k][k]; for(int j=k;j<=n+1;j++) a[i][j]-=a[k][j]*t; } } for(int i=n;i;i--){ if(a[i][i]) ans[i]=a[i][n+1]/a[i][i]; else {puts("No Solution");return 0;} for(int j=1;j<i;j++) a[j][n+1]-=a[j][i]*ans[i]; } for(int i=1;i<=n;i++) printf("%.2lf\n",ans[i]); }转载于:https://www.cnblogs.com/JRX2015U43/p/6533494.html
相关资源：JAVA上百实例源码以及开源项目