题目链接&＃xff1a;http://codeforces.com/problemset/problem/352/A
题目意思&＃xff1a;给定一个只有0或5组成的序列&＃xff0c;你要重新编排这个序列&＃xff08;当然你可以不取尽这些数字&＃xff09;&＃xff0c;使得这个序列尽可能地大&＃xff0c;并且能被90除尽。
做这道题目&＃xff0c;是多次调试本场比赛的B&＃xff0c;完全不成功后回头再做的&＃xff0c;一开始什么思路都没有&＃xff0c;因为觉得是考纯数学&＃xff0c;直接看B......怎么说&＃xff0c;很大程度是靠直觉的。只知道&＃xff0c;这个序列肯定是这种形式&＃xff1a;5xx...0 或者像题目所说的特殊情况&＃xff1a;0&＃xff08;不过前提是0的个数不为0&＃xff09;。其他就不得而知了。然后在纸上比划了下&＃xff0c;发现能被90除尽的序列&＃xff0c;5的个数必须满足是9的倍数&＃xff1a;9&＃xff0c;18... 。至于如何证明&＃xff0c;就希望聪明的读者指导一下了。
1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6
7 int cnt[10]; // 统计0和5的个数
8
9 int main()
10 {
11 int i, n, tmp, flag;
12 while (scanf("%d", &n) !&＃61; EOF)
13 {
14 memset(cnt, 0, sizeof(cnt));
15 for (i &＃61; 0; i
16 {
17 scanf("%d", &tmp);
18 cnt[tmp]&＃43;&＃43;;
19 }
20 flag &＃61; 0;
21 int len &＃61; cnt[5] / 9;
22 // printf("len &＃61; %d\n", len);
23 if (len >&＃61; 1 && cnt[0] !&＃61; 0) // 必须两个条件同时满足&＃xff0c;这个序列5的个数是9的倍数&＃xff0c;且保证个位数必须为0
24 {
25 flag &＃61; 1;
26 for (i &＃61; 0; i
27 printf("5");
28 for (i &＃61; 0; i
29 printf("0");
30 printf("\n");
31 }
32 if (!flag && cnt[0] &＃61;&＃61; 0)
33 printf("-1\n");
34 else if (!flag && cnt[0] !&＃61; 0) // 题目认为0也能被90除尽
35 printf("0\n");
36 }
37 return 0;
38 }
京公网安备 11010802041100号