2017-5-30

題目描述

給你兩個(gè)三位數(shù)的排列，求出滿足條件的排列總數(shù)

解答

暴力枚舉法

代碼

/* ID: 18795871 PROG: combo LANG: C++ */ #include<iostream> #include<fstream> #include<cmath> using namespace std;ifstream fin("combo.in"); ofstream fout("combo.out");int a,b,c,d,e,f,N;bool res(int m,int n){//求差值if (abs(m-n)<=2||abs(m-n)>=N-2) return true;return false; }int main() {fin>>N;fin>>a>>b>>c>>d>>e>>f;int i,j,k,f1,f2,f3,f4,r=0;for (i=1;i<=N;i++){f1=0;f2=0;if (!res(i,a)&&!res(i,d)) continue;if (res(i,a)) f1=1;if (res(i,d)) f2=1;for (j=1;j<=N;j++){f3=0;f4=0;if (!res(j,b)&&!res(j,e)) continue;if (res(j,b)) f3=1;if (res(j,e)) f4=1;for (k=1;k<=N;k++){if (f1&&f3&&res(k,c)) r++;else if (f2&&f4&&res(k,f)) r++;//避免重復(fù) }}}fout<<r<<endl;return 0; }

感覺自己之前寫的邏輯不是很好，說一下我現(xiàn)在的邏輯吧！
我理解的枚舉分兩種：
第一種是不管三七二十一把所有的情況都列出來，然后在判斷是否滿足給定的條件，
第二種是找到可能的解的區(qū)間。
像這一道題目我們還可以將上下兩個(gè)列出來，但是發(fā)現(xiàn)還要去重，所以我果斷選擇了第一種。

枚舉每一位可能出現(xiàn)的情況，如果它不和任意一個(gè)距離 ” 小于 ” 2的話就不可能了，需要我們注意的是，我們最后還需要判斷一下是否三位同時(shí)滿足兩個(gè)中的某一個(gè)，因?yàn)槲覀冎灰骋晃粷M足兩個(gè)中的某一個(gè)就可以了，但是我們最后要求的是三位同時(shí)滿足。

/* ID: 18795871 PROG: combo LANG: C++ */ #include<iostream> #include<fstream> #include<cstring> using namespace std;ifstream fin("combo.in"); ofstream fout("combo.out");int n,cnt; int x1[3],x2[3];bool isOK1(int p,int w){if (p==x1[w]) return true;if (x1[w]==2){if (p==1||p==n||p==3||p==4) return true;return false;}if (x1[w]==1){if (p==n-1||p==n||p==2||p==3) return true;return false;}if (x1[w]==n){if (p==n-2||p==n-1||p==1||p==2) return true;return false;}if (x1[w]==n-1){if (p==n-2||p==n-3||p==n||p==1) return true;return false;}if (p<=x1[w]+2&&p>=x1[w]-2) return true;return false; }bool isOK2(int p,int w){if (p==x2[w]) return true;if (x2[w]==2){if (p==1||p==n||p==3||p==4) return true;return false;}if (x2[w]==1){if (p==n-1||p==n||p==2||p==3) return true;return false;}if (x2[w]==n){if (p==n-2||p==n-1||p==1||p==2) return true;return false;}if (x2[w]==n-1){if (p==n-2||p==n-3||p==n||p==1) return true;return false;}if (p<=x2[w]+2&&p>=x2[w]-2) return true;return false; }int main(){while (fin>>n){cnt=0;int i,j,k;fin>>x1[0]>>x1[1]>>x1[2]>>x2[0]>>x2[1]>>x2[2];for (i=1;i<=n;i++){if ((!isOK1(i,0))&&(!isOK2(i,0))) continue;for (j=1;j<=n;j++){if ((!isOK1(j,1))&&(!isOK2(j,1))) continue;for (k=1;k<=n;k++){if ((!isOK1(k,2))&&(!isOK2(k,2))) continue;if ((isOK1(i,0)&&isOK1(j,1)&&isOK1(k,2))||(isOK2(i,0)&&isOK2(j,1)&&isOK2(k,2))){cnt++; }}}}fout<<cnt<<endl;}return 0; }

但是我的邏輯函數(shù)寫的太不優(yōu)美了！于是乎，出現(xiàn)了最后的代碼：

/* ID: 18795871 PROG: combo LANG: C++ */ #include<iostream> #include<fstream> #include<cmath> using namespace std;ifstream fin("combo.in"); ofstream fout("combo.out");int n,cnt; int x1[3],x2[3];bool isOK1(int p,int w){if (abs(p-x1[w])<=2||abs(p-x1[w])>=n-2) return true;return false; }bool isOK2(int p,int w){if (abs(p-x2[w])<=2||abs(p-x2[w])>=n-2) return true;return false; }int main(){while (fin>>n){cnt=0;int i,j,k;fin>>x1[0]>>x1[1]>>x1[2]>>x2[0]>>x2[1]>>x2[2];for (i=1;i<=n;i++){if ((!isOK1(i,0))&&(!isOK2(i,0))) continue;for (j=1;j<=n;j++){if ((!isOK1(j,1))&&(!isOK2(j,1))) continue;for (k=1;k<=n;k++){if ((!isOK1(k,2))&&(!isOK2(k,2))) continue;if ((isOK1(i,0)&&isOK1(j,1)&&isOK1(k,2))||(isOK2(i,0)&&isOK2(j,1)&&isOK2(k,2))){cnt++; }}}}fout<<cnt<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的USACO-Section1.4 Combination Lock （枚举）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。