例7-1 UVa725 Division
直接枚举除数即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, cnt[20];
void solve(){
int flag = 0;
for(int i = 1234; ; ++i){
int j = i * n;
if(j < 10000 && i < 10000)
continue;
int tot = 0;
while(j)
cnt[tot++] = j % 10, j /= 10;
j = i;
while(j)
cnt[tot++] = j % 10, j /= 10;
if(i < 10000)cnt[tot++] = 0;
if(tot > 10)break;
sort(cnt, cnt + 10);
for(j = 0; j < 10; ++j)
if(cnt[j] != j)
break;
if(j == 10)
printf("%d / %05d = %d\n", i * n, i, n),
flag = 1;
}
if(!flag)
printf("There are no solutions for %d.\n", n);
}
int main(){
for(int T = 1; ; ++T){
n = read();
if(!n)break;
if(T > 1)printf("\n");
solve();
}
return 0;
}
例7-2 UVa11059 Maximum Product
枚举两端即可。
数据比较小，直接用long long。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n;
ll seq[50];
void init(){
for(int i = 0; i < n; ++i)
seq[i] = read();
}
void solve(){
ll ans = 0;
for(int i = 0; i < n; ++i)
for(int j = i; j < n; ++j){
ll st = 1;
for(int k = i; k <= j; ++k)
st *= seq[k];
ans = max(ans, st);
}
printf("%lld.\n\n", ans);
}
int main(){
int T = 0;
while(scanf("%d", &n) == 1){
T++;
printf("Case #%d: The maximum product is ", T);
init();
solve();
}
return 0;
}
例7-3 UVa10976 Fractions Again?!
由于$x \ge y$可以发现$\frac{1}{x} \le \frac{1}{y}$。
故$y$的下限为$k+1$，上限为$2k$。
将$y$从$k+1$开始枚举到$2k$即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, ans[10005][2], cnt;
void solve(){
cnt = 0;
for(int i = n + 1; i <= n + n; ++i){
int fz = i - n, fm = n * i;
if(fm % fz == 0)
ans[cnt][0] = fm / fz,
ans[cnt++][1] = i;
}
printf("%d\n", cnt);
for(int i = 0; i < cnt; ++i)
printf("1/%d = 1/%d + 1/%d\n", n, ans[i][0], ans[i][1]);
}
int main(){
while(scanf("%d", &n) == 1){
solve();
}
return 0;
}
例7-4 UVa524 Prime Ring Problem
直接DFS即可。
回溯法的入门型题目。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, ring[20];
bool isnt[50] = {0}, vis[20] = {0};
void init(){
isnt[1] = 1;
for(int i = 2; i <= 32; ++i)
if(!isnt[i]){
for(int j = i << 1; j <= 32; j += i)
isnt[j] = 1;
}
}
void dfs(int index, int cur){
ring[cur] = index;
if(cur == n){
if(!isnt[ring[1] + index]){
for(int i = 1; i < n; ++i)
printf("%d ", ring[i]);
printf("%d\n", ring[n]);
}
return ;
}
vis[index] = 1;
for(int i = 2; i <= n; ++i)
if(!vis[i] && !isnt[i + ring[cur]])
dfs(i, cur + 1);
vis[index] = 0;
}
void solve(){
dfs(1, 1);
}
int main(){
init();
int T = 1;
while(scanf("%d", &n) == 1){
if(T > 1)printf("\n");
printf("Case %d:\n", T);
solve();
T++;
}
return 0;
}
例7-6 UVa140 Bandwidth
枚举全排列，然后模拟即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
char s[1005];
bool mat[50][50], vis[50];
int p[10], n, b[10], ansp[10];
void init(){
memset(mat, 0, sizeof(mat));
memset(vis, 0, sizeof(vis));
for(int i = 0; isalpha(s[i]); ++i){
int cur = s[i++] - 'A';
vis[cur] = 1;
for(i++; isalpha(s[i]); ++i){
int to = s[i] - 'A';
mat[cur][to] = mat[to][cur] = 1;
vis[to] = 1;
}
}
}
void solve(){
n = 0;
for(int i = 0; i < 26; ++i)
if(vis[i])
p[n++] = i;
int ans = INF;
do{
int cur = 0;
memset(b, 0, sizeof(b));
for(int i = 0; i < n; ++i){
for(int j = i - 1; j >= 0; --j)
if(mat[p[i]][p[j]])
b[i] = max(b[i], i - j);
for(int j = i + 1; j < n; ++j)
if(mat[p[i]][p[j]])
b[i] = max(b[i], j - i);
cur = max(cur, b[i]);
if(cur >= ans)
break;
}
if(cur < ans){
memcpy(ansp, p, sizeof(p));
ans = cur;
}
}while(next_permutation(p, p + n));
for(int i = 0; i < n; ++i)
printf("%c ", ansp[i] + 'A');
printf("-> %d\n", ans);
}
int main(){
for(; ; ){
scanf("%s", s);
if(s[0] == '#')break;
init();
solve();
memset(s, 0, sizeof(s));
}
return 0;
}