USACO题目解析Prime Cryptarithm.docxVIP

下面是一个乘法竖式，如果用我们给定的那n个数字来取代*，可以使式子成立的话，我们就叫这个式子牛式。 * * *x * * ---------- * * * * * * ---------- * * * *数字只能取代*，当然第一位不能为0,况且给定的数字里不包括0。注意一下在美国的学校中教的“部分乘积”，第一部分乘积是第二个数的个位和第一个数的积，第二部分乘积是第二个数的十位和第一个数的乘积.写一个程序找出所有的牛式。[编辑]格式PROGRAM NAME: crypt1INPUT FORMAT:(file crypt1.in) Line 1:数字的个数n。 Line 2:N个用空格分开的数字（每个数字都属于{1,2,3,4,5,6,7,8,9}）。OUTPUT FORMAT:(file crypt1.out)共一行，一个数字。表示牛式的总数。[编辑]SAMPLE INPUT52 3 4 6 8//在digit[2、3、4、6、8]上标志1即可[编辑]SAMPLE OUTPUT1[编辑]样例分析 2 22x 2 2 ---------- 4 44 4 44 ---------- 4 8 8 4注意：结果只能为4位暴力：#include cstdio#include cstdlib#include cstring#include string#include map#include listusing namespace std;?FILE *in, *out;?voidopenfile() { in = fopen(crypt1.in, r); out = fopen(crypt1.out, w+); }voidclosefile() { fclose(in); fclose(out); }?/** TODO VAR. */intarr[10], n;bool ex[10];?int main(){openfile();fscanf(in, %d, n);memset(ex, 0, sizeof(ex));for(inti = 0; i n; i++) {fscanf(in, %d, arr + i);ex[arr[i]] = true; }?int r = 0;for(inti = 0; i n; i++)for(int j = 0; j n; j++)for(int k = 0; k n; k++)for(int l = 0; l n; l++)for(int m = 0; m n; m++) {int a = arr[i] * 100 + arr[j] * 10 + arr[k];int b = a * arr[l], c = a * arr[m], d = b + c * 10;if(b 1000 || c 1000 || d 10000) continue;if(!ex[b % 10] || !ex[c % 10] || !ex[d % 10]) continue;b /= 10, c /= 10, d /= 10;if(!ex[b % 10] || !ex[c % 10] || !ex[d % 10]) continue;d /= 10;if(!ex[b / 10] || !ex[c / 10] || !ex[d % 10] || !ex[d / 10]) continue;?r++; }?fprintf(out, %d\n, r);?closefile();return 0;}好些：#include iostream#include stdio.husing namespace std;bool mark[10];int n, a, b, num[10];bool check(int m, int k){if (m / k 0) return false;do {if (mark[m % 10] != true)return false;m /= 10; } while (m 0);return true;}int main(void){freopen (crypt1.in, r, stdin);freopen (crypt1.out, w, stdout); scanf (%d, n);for (inti = 1; i = n; i++) {scanf (%d, num[i]);mark[num[i]] = true; }int tot(0);for (