codeforces 496B. Secret Combination 解题报告

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

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

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

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

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <vector>

 using namespace std;

 const int maxn = 1e3 + ;

 vector<int> v[maxn];

 int a[maxn];

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("in.txt", "r", stdin);

     #endif // ONLINE_JUDGE

     int n;

     char ch;

     while (scanf("%d", &n) != EOF)

     {

         getchar();

         v[].clear();

         for (int i = ; i < n; i++)

         {

             scanf("%c", &ch);

             a[i] = ch - '';

         }

         for (int i = ; i < ; i++)

         {

             for (int j = ; j < n; j++)

             {

                 int add = a[j] + (i+);

                 v[i].push_back(add % );

             }

             sort(v[i].begin(), v[i].end());

         }

         sort(v, v+);

         for (int i = ; i < n; i++)

             printf("%d", v[][i], i == n- ? ' ' : '\n');

     }

     return ;

 }

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

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 const int maxn = 1e3 + ;

 char a[maxn];

 int n;

 void add(char a[], int added)

 {

     for (int i = ; i < n; i++)

     {

         int tmp = (a[i]-'' + added) % ;

         a[i] = tmp + '';

     }

 }

 void get_reverse(char a[])

 {

     char tmp = a[];

     for (int i = ; i < n; i++)

         a[i-] = a[i];

     a[n-] = tmp;

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("in.txt", "r", stdin);

     #endif // ONLINE_JUDGE

     while (scanf("%d", &n) != EOF)

     {

         getchar();

         char b[maxn] = {''};

         char ans[maxn] = {''};

         for (int i = ; i < n; i++)

             scanf("%c", &a[i]);

         for (int i = ; i <= ; i++)

         {

             strcpy(b, a);

             add(a, i);

             for (int j = ; j < n; j++)

             {

                 if (strcmp(ans, a) > )

                     strcpy(ans, a);

                 get_reverse(a);

             }

             strcpy(a, b);

         }

         puts(ans);

     }

     return ;

 }