Division

紫書入門級別的暴力，可我還是寫了好長時間 = =

【題目鏈接】uva 725

【題目類型】化簡暴力

&題解：
首先要看懂題意，他的意思也就是0~9都只出現一遍，在這2個5位數中。
接著，你要知道：枚舉一個5位數就夠了，不用2個5位數都枚舉，因為你可以通過n知道第2個5位數。
最后set維護出現的次數，ok判斷是否可行，pri輸出。

【時間復雜度】O(1e5)

&代碼：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; #define cle(a,val) memset(a,(val),sizeof(a)) #define SI(N) scanf("%d",&(N)) #define SII(N,M) scanf("%d %d",&(N),&(M)) #define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K)) #define rep(i,b) for(int i=0;i<(b);i++) #define rez(i,a,b) for(int i=(a);i<=(b);i++) #define red(i,a,b) for(int i=(a);i>=(b);i--) const ll LINF = 0x3f3f3f3f3f3f3f3f; #define PU(x) puts(#x); int n; set<int> sei, se2; vector<pair<int, int> > vep; bool ok(int d) {se2 = sei;int t = d / n;if (t * n != d) {return false;}int u = 0;while (t) {u++;sei.insert(t % 10);t /= 10;}if (u > 5) {return false;}if (sei.size() == 9 && !sei.count(0) && u == 4) {return true;}if (sei.size() == 10) {return true;}return false; } void pri() {if (vep.empty()) {printf("There are no solutions for %d.\n", n);return;}int t = vep.size();rep(i, t)printf("%05d / %05d = %d\n", vep[i].first, vep[i].second, n); } void Solve() {int uu = 0;while (~SI(n), n) {if (uu) PU()uu = 1;sei.clear() ;vep.clear();rez(i1, 0, 9) {sei.insert(i1);rez(i2, 0, 9) {if (sei.count(i2)) continue;sei.insert(i2);rez(i3, 0, 9) {if (sei.count(i3)) continue;sei.insert(i3);rez(i4, 0, 9) {if (sei.count(i4)) continue;sei.insert(i4);rez(i5, 0, 9) {if (sei.count(i5)) continue;sei.insert(i5);int d = i1 * 1e4 + i2 * 1e3 + i3 * 1e2 + i4 * 1e1 + i5;if (ok(d)) {pair<int, int> p;p.first = d;p.second = d / n;vep.push_back(p);}sei = se2;sei.erase(i5);}sei.erase(i4);}sei.erase(i3);}sei.erase(i2);}sei.erase(i1);}pri();} } int main() {Solve();return 0; }

上面是按位搜索的暴力，代碼較長，下面是直接枚舉的暴力，枚舉枚舉范圍1234~98765，之后再判斷，這樣寫代碼就較短了。我枚舉的是第一個5位數，當然，也可以枚舉第二個，你自己可以試下。

&代碼2：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; #define cle(a,val) memset(a,(val),sizeof(a)) #define SI(N) scanf("%d",&(N)) #define SII(N,M) scanf("%d %d",&(N),&(M)) #define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K)) #define rep(i,b) for(ll i=0;i<(b);i++) #define rez(i,a,b) for(ll i=(a);i<=(b);i++) #define red(i,a,b) for(ll i=(a);i>=(b);i--) const ll LINF = 0x3f3f3f3f3f3f3f3f; #define PU(x) puts(#x); #define PI(A) cout<<(A)<<endl; #define DG(x) cout<<#x<<"="<<(x)<<endl; #define DGG(x,y) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl; #define DGGG(x,y,z) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<" "<<#z<<"="<<(z)<<endl; #define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl; #define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;} const double EPS = 1e-9 ; /* C o d i n g S p a c e */ const int MAXN = 1000 + 5 ; int n; bool used[10]; bool ok(int x, int y) {if (y*n!=x) return false;cle(used, 0);//這是1e4 不是1e5if (x < 10000) used[0] = 1;if (y < 10000) used[0] = 1;int u1 = 0, u2 = 0;while (x) {used[x % 10] = 1;x /= 10;u1++;}while (y) {used[y % 10] = 1;y /= 10;u2++;}int c = 0;if (u1 < 6 && u2 < 6)rep(i, 10) if (used[i]) c++;return (c == 10); } void Solve() {int kg = 0;while (~SI(n), n) {if (kg)puts("");kg = -1;for (int i = 1234; i <= 98765; i++)if (ok(i, i / n)) {printf("%05d / %05d = %d\n", i, i / n, n);kg = 1;}if (kg == -1) printf("There are no solutions for %d.\n", n);} } int main() {Solve();return 0; }

轉載于:https://www.cnblogs.com/s1124yy/p/5901425.html

總結

以上是生活随笔為你收集整理的uva 725 Division（暴力模拟）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。