codeforces 496B. Secret Combination 解题报告

题目链接：http://codeforces.com/problemset/problem/496/B

题目意思：给出 n 位数你，有两种操作：1、将每一位数字加一（当某一位 > 9 时只保存个位数） 2、循环右移（最右边那个数字去到第一位上）。问经过若个两种操作的组合后，得到的最小数值为多少。

我一开始用了vector来做= =，没有考虑到循环右移的情况。以为每一位从1加到9之后，找出最小的那个就可以.....

　　留个纪念（错误代码，别学，如果没有循环右移的限制，这个是对的）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <vector>
 6 using namespace std;
 7 
 8 const int maxn = 1e3 + 5;
 9 vector<int> v[maxn];
10 int a[maxn];
11 
12 int main()
13 {
14     #ifndef ONLINE_JUDGE
15         freopen("in.txt", "r", stdin);
16     #endif // ONLINE_JUDGE
17 
18     int n;
19     char ch;
20     while (scanf("%d", &n) != EOF)
21     {
22         getchar();
23         v[10].clear();
24         for (int i = 0; i < n; i++)
25         {
26             scanf("%c", &ch);
27             a[i] = ch - '0';
28         }
29         for (int i = 0; i < 9; i++)
30         {
31             for (int j = 0; j < n; j++)
32             {
33                 int add = a[j] + (i+1);
34                 v[i].push_back(add % 10);
35             }
36             sort(v[i].begin(), v[i].end());
37         }
38         sort(v, v+10);
39         for (int i = 0; i < n; i++)
40             printf("%d", v[0][i], i == n-1 ? ' ' : '
');
41     }
42     return 0;
43 }

View Code

　　按照步骤一步一步模拟即可。但是需要用到 b 数组来还原原始的数字。还有就是循环右移其实等价于循环左移！最后就是strcmp() 放到 get_reverse() 后面，这样需要两个strcmp 判断（循环外的add后面），这样放置只需要用到一次 strcmp() 就行了。放置位置也是值得注意的，不要颠倒了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int maxn = 1e3 + 5;
 8 char a[maxn];
 9 int n;
10 
11 void add(char a[], int added)
12 {
13     for (int i = 0; i < n; i++)
14     {
15         int tmp = (a[i]-'0' + added) % 10;
16         a[i] = tmp + '0';
17     }
18 }
19 
20 void get_reverse(char a[])
21 {
22     char tmp = a[0];
23     for (int i = 1; i < n; i++)
24         a[i-1] = a[i];
25     a[n-1] = tmp;
26 }
27 
28 int main()
29 {
30     #ifndef ONLINE_JUDGE
31         freopen("in.txt", "r", stdin);
32     #endif // ONLINE_JUDGE
33 
34     while (scanf("%d", &n) != EOF)
35     {
36         getchar();
37         char b[maxn] = {'0'};
38         char ans[maxn] = {'9'};
39         for (int i = 0; i < n; i++)
40             scanf("%c", &a[i]);
41         for (int i = 0; i <= 9; i++)
42         {
43             strcpy(b, a);
44             add(a, i);
45             for (int j = 0; j < n; j++)
46             {
47                 if (strcmp(ans, a) > 0)
48                     strcpy(ans, a);
49                 get_reverse(a);
50             }
51             strcpy(a, b);
52         }
53         puts(ans);
54     }
55     return 0;
56 }