uva 725 Division(暴力模拟)

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 不是1e5
if (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;
}
上一篇:[RxJS] Subject basic


下一篇:ASP.NET MVC+Vue.js实现联系人管理