终于到了第七章暴力求解法,上来三道小题热身。。
UVa #725 Division 例题 7-1
看到这题的数据吓尿了,太惨烈了。题目完全没有数据显示出来的难度,不过中间的小细节还是要像对待难题一样谨慎:
思路:枚举分母,从1234到98765。每次用分母乘以n得到分子的值。一旦得出的分子超过5位数就break
细节:
1、分子分母不能同时只有四位
2、分子为四位时,分母不能有0。反之同理
3、最后一个case的后面不要多出一个回车符
UVa #11059 Maximum Product 例题 7-2
这道题有点坑。想法很朴素,枚举子序列的开头结尾就可以了。
但它的输出格式要求和上一道题不同,虽然也说两个case之间要加空格,但是最后一个case后面是要有一个空行才行的。
另外子序列是应该包括单个元素的。
感觉这个题WA了也不要紧,因为确实有些没讲清楚。(这题数据里WA的比例也是非常吓人)
对于这类不太明确的题,更要充分利用UVa的uDebug
UVa #10976 Fractions Again?! 例题 7-3
从样例输出想到从小到大枚举y到2k。
关于如何找到x,我一开始脑残了用了个枚举判断1/x什么时候能取到1/k - 1/y。这种方法在k大了之后程序会爆掉。。
其实判断一下 是否(y*k)%(y-k) == 0即可,如果是的话x = (y*k) / (y-k)
Run Time: 0.249s
// UVa #LT7-1.725.cpp #include<fstream> #include<cstring> #include<cstdlib> #include<cstdio> #include<set> using namespace std; int length(int a) { int cnt = 0; while(a) { cnt ++; a /= 10; } return cnt; } int has_zero(int a) { while(a) { if(a%10 == 0) return 1; a /= 10; } return 0; } int distinct(int a, int b) { set<int> s; int tmp; while(a) { tmp = a%10; if(s.count(tmp)) return 0; s.insert(tmp); a /= 10; if(length(b) == 4) { if(tmp == 0) return 0; } } while(b) { tmp = b%10; if(s.count(tmp)) return 0; s.insert(tmp); b /= 10; } return 1; } int main() { int N, first = 1; while(scanf("%d", &N) && N) { if(first) first = 0; else printf("\n"); int a, b, flag = 0; for(b = 1234; b < 98765; b ++) { a = b * N; if(distinct(a, b)) { if((length(a) == 4 && has_zero(a)) || (length(b) == 4 && has_zero(b)) || (length(a) == 4 && length(b) == 4 )) continue; if(length(a) == 4) printf("0"); printf("%d / ", a); if(length(b) == 4) printf("0"); printf("%d = %d\n", b, N); flag = 1; } else if(length(a) > 5) break; } if(!flag) printf("There are no solutions for %d.\n", N); } return 0; }
Run Time: 0.015s
// UVa #LT7-2.11059.cpp #include<cstring> #include<cstdlib> #include<cstdio> #define maxn 500 using namespace std; int main() { int N, kase = 0; while(scanf("%d", &N) != EOF) { int a[20]; for(int i = 0; i < N; i ++) scanf("%d", &a[i]); long long maxP = 0; for(int i = 0; i < N; i ++) for(int j = i; j < N; j ++) { long long tmp = 1; for(int k = i; k <= j; k ++) tmp *= a[k]; if(tmp > maxP) maxP = tmp; } printf("Case #%d: The maximum product is %lld.\n\n", ++kase, maxP); } return 0; }
Run Time: 0.025s
// UVa #LT7-3.10976.cpp #include<cstring> #include<cstdlib> #include<cstdio> #include<vector> #define maxn 500 using namespace std; int main() { int k; while(scanf("%d", &k) != EOF) { double kvalue = 1.0/k; vector<pair<long long,long long> > result; for(long long y = k+1; y <= 2*k; y ++) { long long up = y - k; long long down = k*y; if(down%up == 0) result.push_back(pair<long long, long long>(down/up, y)); } printf("%d\n", result.size()); for(int i = 0; i < result.size(); i ++) printf("1/%d = 1/%lld + 1/%d\n", k, result[i].first, result[i].second); } return 0; }