例题7-1 除法（Division, UVa 725）
一定要注意数组初始化的位置
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define INF 10000 #define MAXN 5010 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue char buf[6]; int used[10]; bool check(char* a) { mem(used,0); for(int i =0;i<10;i++) { used[a[i]-'0']=1; } for(int i = 0;i<10;i++) { if(!used[i]) return false; } return true; } int main() { int n,i,j,kase=0; while(sf("%d",&n)==1 && n) { int ok=0; if(kase++) blank; for(i=1;i<=98765;i++) { spf(buf,"%05d%05d",i*n,i); int len = strlen(buf); if(len>10) break; if(check(buf)) { pf("%05d / %05d = %d ",i*n,i,n); ok = 1; } } if(!ok) pf("There are no solutions for %d. ",n); } }
例题7-2 最大乘积（Maximum Product, UVa 11059）
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define INF 10000 #define MAXN 5010 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue int buf[20]; int main() { int n,i,j,kase=0,cnt=1; while(sf("%d",&n)==1) { for(i=0;i<n;i++) { sf("%d",&buf[i]); } if(kase++) blank; long long ma = 0; for(i=0;i<n;i++) { long long res = 1; for(j=i;j<n;j++) { res*=buf[j]; if(res>ma) ma = res; } } pf("Case #%d: The maximum product is %I64d. ",cnt++,ma); } }
例题7-3 分数拆分（Fractions Again?!, UVa 10976）
尽量用余数%判断一个double是否是整数
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define INF 10000 #define MAXN 5010 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue int x[10011],y[10011]; int main() { int n,i,j,kase=0; while(sf("%d",&n)==1) { int v=0,cnt=0; mem(x,0); mem(y,0); for(i=n+1;i<=2*n;i++) { if(i*n % (i-n)==0) { x[v]=i*n/(i-n); y[v++]=i; } } pf("%d ",v); for(i = 0;i<v;i++) pf("1/%d = 1/%d + 1/%d ",n,x[i],y[i]); } }
生成1～n的排列
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define INF 10000 #define MAXN 5010 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue int a[10011],b[10011]; void NP(int n,int* a,int cur) { if(cur==n) { for(int i = 0;i<n;i++) pf("%d ",a[i]); blank; } else { for(int i =1;i<=n;i++) { int ok = 1; for(int j = 0;j<cur;j++) { if(a[j]==i) ok = 0; } if(ok) { a[cur] = i; NP(n,a,cur+1); } } } } int main() { int n,i,j,kase=0; while(sf("%d",&n)==1) { NP(n,a,0); } }
7.2.2 生成可重集的排列
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define INF 10000 #define MAXN 5010 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue void NP(int n,int* p,int* a,int cur) { if(cur==n) { for(int i = 0;i<n;i++) pf("%d ",a[i]); blank; } else { for(int i =0;i<n;i++) { if(!i || p[i-1]!=p[i]) { int c1=0,c2=0; for(int j = 0;j<cur;j++) { if(a[j]==p[i]) c1++; } for(int j = 0;j<n;j++) { if(p[j]==p[i]) c2++; } if(c1<c2) { a[cur] = p[i]; NP(n,p,a,cur+1); } } } } } int main() { int n,i,j,kase=0; int A[1000],P[1000]; while(sf("%d",&n)==1) { for(i = 0;i<n;i++) sf("%d",&P[i]); sort(P,P+n); NP(n,P,A,0); } } /* 5 6 5 8 7 2 5 6 5 8 5 2 */
库函数next_permutation
解决了重复问题，需要排序
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define INF 10000 #define MAXN 5010 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue int main() { int n,i,j,kase=0; int A[1000],P[1000]; while(sf("%d",&n)==1) { for(i = 0;i<n;i++) sf("%d",&P[i]); sort(P,P+n); do { for(i=0;i<n;i++) pf("%d ",P[i]); blank; } while(next_permutation(P,P+n)); } } /* 5 6 5 8 7 2 5 6 5 8 5 2 */
7.3 子集生成
7.3.1 增量构造法
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define INF 10000 #define MAXN 5010 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue void subset(int n,int* A,int cur) { int i; for(i=0;i<cur;i++) pf("%d ",A[i]); blank; int s = cur?A[cur-1]+1:0; for(i=s;i<n;i++) { A[cur] = i; subset(n,A,cur+1); } } int main() { int n,i,j,kase=0; int A[1000],P[1000]; while(sf("%d",&n)==1) { subset(n,A,0); } } /* 5 6 5 8 7 2 5 6 5 8 5 2 */
7.3.2 位向量法
void subset(int n,int* B,int cur) { int i; if(cur==n) { for(i=0;i<cur;i++) { if(B[i]) pf("%d ",i); } blank; return; } B[cur] = 1; subset(n,B,cur+1); B[cur] = 0; subset(n,B,cur+1); } int main() { int n,i,j,kase=0; int B[1000],P[1000]; while(sf("%d",&n)==1) { subset(n,B,0); } } /* 5 6 5 8 7 2 5 6 5 8 5 2 */
7.3.3 二进制法
void subset(int n,int s) { for(int i =0;i<n;i++) { if(s&(1<<i)) pf("%d ",i); } blank; } int main() { int n,i,j,kase=0; int B[1000],P[1000]; while(sf("%d",&n)==1) { for(int i = 0;i<(1<<n);i++) subset(n,i); } } /* 5 6 5 8 7 2 5 6 5 8 5 2 */
7.4.1 八皇后问题
void sh(int cur,int n) { if(cur==n) tot++; for(int i = 0;i<n;i++) { int ok = 1; C[cur] = i; for(j=0;j<cur;j++) { if(C[j] == C[cur] || cur-C[cur]==j-C[j] || cur+C[cur]==j+C[j]) { ok = 0; break; } } if(ok) sh(cur+1,n); } }
例题7-4 素数环（Prime Ring Problem, UVa 524）
很简单的问题，回溯法，注意细节
int n; int isp[50],A[20],vis[20]; int is_prime(int a) { int i; for(i=2;i<=a/2;i++) { if(a%i==0) return 0; } return 1; } void init() { for(int i =3;i<32;i++) { isp[i] = is_prime(i); } } void dfs(int cur) { int i; if(cur==n && isp[A[0]+A[n-1]]) { for(i=0;i<n;i++) pf("%d ",A[i]); blank; } for(i=2;i<=n;i++) { if(!vis[i] && isp[A[cur-1]+i]) { vis[i] = 1; A[cur] = i; dfs(cur+1); vis[i] = 0; } } } int main() { int kase = 0; init(); A[0]=1; while(sf("%d",&n)==1) { if(kase++) blank; pf("Case %d: ",kase+1); mem(vis,0); dfs(1); } }
例题7-5 困难的串（Krypton Factor, UVa 129）
枚举连续不重复子串只需要判断当前串的后缀
int n,L,cnt; int S[100]; int dfs(int cur)//返回0表示已经得到解，无须继续搜索 { int i,j,k; if(cnt++==n) { for(i=0;i<cur;i++) { if(i%64==0 && i) blank; else if(i%4==0 && i) pf(" "); pf("%c",S[i]+'A'); } blank; pf("%d ",cur); return 0; } for(i=0;i<L;i++) { S[cur] = i; int ok = 1; for(j=1;j*2<=cur+1;j++) //尝试长度为j*2的后缀 { int eq = 1; for(k=0;k<j;k++)//检查后一半是否等于前一半 { if(S[cur-k]!=S[cur-k-j]) { eq = 0;break; } } if(eq) { ok=0;break; } } if(ok) { if(!dfs(cur+1)) return 0; } } return 1; } int main() { int kase = 0; while(sf("%d%d",&n,&L)==2 && n) { cnt=0; mem(S,0); dfs(0); } }
例题7-6 带宽（Bandwidth, UVa 140）
简单回溯，主要是输入麻烦，弄清题意
有一个方法值得借鉴，想得到输入的字母的排序，可以先记录出现的字母，再导入到一个数组，以空间换时间
int ahl[27],node[9],save[9],mp[27][27]; char a[500]; int main() { while(gets(a)) { int i,j,c,cnt=0,mx=10,flag=0; if(!strcmp(a,"#")) break; int len = strlen(a); mem(mp,0); mem(ahl,0); mem(save,0); for(i=0;i<len;i++) { if(isalpha(a[i])) { ahl[a[i]-'A']=1; } if(a[i]==':') { c=a[i-1]-'A'; flag = 1; } else if(flag&&isalpha(a[i])) { mp[c][a[i]-'A']=mp[a[i]-'A'][c]=1; } else flag = 0; } for(i=0;i<26;i++) { if(ahl[i]) node[cnt++]=i; } do { int num = 0; for(i=0;i<cnt;i++) { for(j=i+1;j<cnt;j++) { if(mp[node[i]][node[j]] && abs(i-j)>num) num=abs(i-j); } if(num>mx)//剪枝 break; } if(mx>num) { mx=num; memcpy(save,node,sizeof(node)); } } while(next_permutation(node,node+cnt)); for(i=0;i<cnt;i++) pf("%c ",save[i]+'A'); pf("-> %d ",mx); } }
例题7-7 天平难题（Mobile Computing, ACM/ICPC Tokyo 2005, UVa1354）
7.5 路径寻找问题
八数码问题
const int maxstate = 1000000; typedef int state[9]; state st[maxstate],goal; int dist[maxstate];
//如果需要打印方案，可以在这里加一个"父亲编号"数组 int fa[maxstate] const int dx[] = {1,-1,0,0}; const int dy[] = {0,0,1,-1};int bfs() { int i; int ft = 1,rr=2;//0为无解 init_lookup_table(); while(ft<rr) { state& s = st[ft]; if(!memcmp(s,goal,sizeof(goal))) return ft; int z,newx,newy,newz; for(z=0;z<9;z++) if(!s[z]) break; int x = z%3,y=z/3; for(i=0;i<4;i++) { newx = x+dx[i]; newy = y+dy[i]; newz = newy*3+newx; if(newx<3 && newx>=0 && newy<3 && newy>=0) { state& t = st[rr]; memcpy(&t,&s,sizeof(s)); t[z]=s[newz]; t[newz]=s[z]; dist[rr]=dist[ft]+1; if(try_to_insert(rr)) rr++; } } ft++; } return 0; } int main() { int i; for(i=0;i<9;i++) sf("%d",&st[1][i]); for(i=0;i<9;i++) sf("%d",&goal[i]); int ans = bfs(); if(ans) pf("%d ",dist[ans]); else pf("-1 "); }
bfs需要判重，如果开9维数组太大，一般有三种解决方法：
一：set
最方便，时间效率最低，一般做跳板
set<int> vis; void init_lookup_table() { vis.clear(); } int try_to_insert(int a) { int v= 0; for(int i =0;i<9;i++) v=v*10+st[a][i]; if(vis.count(v)) return 0; vis.insert(v); return 1; }
二：把排列“变成”整数，然后只开一个一维数组
int vis[362880],fact[9];//362880=9! void init_lookup_table() { fact[0] = 1; for(int i =1;i<9;i++) fact[i] = fact[i-1]*i; } int try_to_insert(int a) { int code = 0; for(int i =0;i<9;i++) { int cnt = 0; for(int j = i+1;j<9;j++) { if(st[a][i]>st[a][j]) cnt++; } code+=fact[8-i]*cnt; } if(vis[code]) return 0; return vis[code] = 1; }
尽管原理巧妙，时间效率也非常高，但编码解码法的适用范围并不大：如果隐式图的总
结点数非常大，编码也将会很大，数组还是开不下。
三：使用哈希（hash）技术
const int hashsize = 1000003; int head[hashsize], next[maxstate]; void init_lookup_table( ) { memset(head, 0, sizeof(head)); } int hash(State& s){ int v = 0; for(int i = 0; i < 9; i++) v = v * 10 + s[i];//把9个数字组合成9位数 return v % hashsize; //确保hash函数值是不超过hash表的大小的非负整数 } int try_to_insert(int s){ int h = hash(st[s]); int u = head[h]; //从表头开始查找链表 while(u){ if(memcmp(st[u],st[s], sizeof(st[s]))==0)return 0; //找到了，插入失败 u = next[u]; //顺着链表继续找 } next[s] = head[h]; //插入到链表中 head[h] = s; return 1; }
哈希表的执行效率高，适用范围也很广。除了BFS中的结点判重外，还可以用到其他需
要快速查找的地方。不过需要注意的是：在哈希表中，对效率起到关键作用的是哈希函数。
如果哈希函数选取得当，几乎不会有结点的哈希值相同，且此时链表查找的速度也较快；但
如果冲突严重，整个哈希表会退化成少数几条长长的链表，查找速度将非常缓慢。有趣的
是，前面的编码函数可以看作是一个完美的哈希函数，不需要解决冲突。不过，如果事
先并不知道它是完美的，也就不敢像前面一样只开一个vis数组。哈希技术还有很多值得探
讨的地方，建议读者在网上查找相关资料。
例题7-8 倒水问题（Fill, UVa 10603）
struct node { int v[3],dist; bool operator <(const node& rhs) { return dist>rhs.dist; } }; int cap[3],vis[205][205],ans[205]; void update(const node& u) { for(int i =0;i<3;i++) { int d = u.v[i]; if(ans[d]<0 || u.dist<ans[d]) ans[d]=u.dist; } } void bfs(int a,int b,int c,int d) { pqueue<node> q; cap[0]=a;cap[1]=b;cap[2]=c; node start; start.v[0]=0;start.v[1]=0;start.v[2]=c; q.push(start); mem(vis,0); mem(ans,-1); vis[0][0]=1; while(!q.empty()) { node t = q.top();q.pop(); update(t); for(int i =0;i<3;i++) { for(int j = 0;j<3;j++) if(i!=j) { if(t.v[i]==0 || t.v[j]==cap[j]) continue; int amount = min(cap[j],t.v[i]+t.v[j])-t.v[j]; node t2; memcpy(&t2,&t,sizeof(t)); t2.v[i]-=amount; t2.v[j]+=amount; t2.dist=t.dist+amount; if(!vis[t2.v[0]][t2.v[1]]) { vis[t2.v[0]][t2.v[1]]=1; q.push(t2); } } } } while(d>=0) { if(ans[d]>=0) { pf("%d %d ",ans[d],d); return; } d--; } } int main() { int a,b,c,d; int t; sf("%d",&t); while(t--) { sf("%d%d%d%d",&a,&b,&c,&d); bfs(a,b,c,d); } }