codeforces 486C. Palindrome Transformation 解题报告

题目链接：http://codeforces.com/problemset/problem/486/C

题目意思：给出一个含有 n 个小写字母的字符串 s 和指针初始化的位置（指向s的某个字符）。可以对s进行四种操作：up，down，left，right。up/down是令到对称位置的字符相同所进行的操作次数。假设s[i] != s[j]（i, j是对称的，假设分别是a, k），up: a（位置1）根据字母表顺序变成 k（位置11）需要 10 次（直接a->k）。down：a 根据字母表逆向顺序变成 k 需要 16 次（a->z->k）。 left/right 主要是操作移动的指针。假如当前指向pos，left: i: 1～pos-1 中找到s[i] != s[n-i+1]， right： j: pos+1 ～ n 找到 s[j] != s[n-j+1]。

问使得s最终成为回文串需要使用这四种操作的最少次数是多少。

如果按题目要求直接一步一步模拟做，会发现好复杂。做了我两个多小时，无果！不仅指针会随时变动，而且当指向第一个元素的时候，又可以移动到最后一个元素（可以循环），还要比较左右两边的距离再判断移动的方向.......

看了题解，真是太厉害了。其实没有必要考虑这么多，前提是要知道需要变动的位置，这个不难。进行 up/down 操作。然后以 p 为中点向左右两边探测，选择离 p 较近的位置的方向，代表这个方向要走两次，另外那个自然就是一次了。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 using namespace std;

 const int maxn = 1e5 + ;

 bool ok[maxn];

 string s;

 int main()

 {

     #ifndef ONLINE_JUDGE

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

     #endif

     int n, p;

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

     {

         cin >> s;

         s = "Y" + s;  // 下标往右移了一位，刚好对应题目给出的下标

         memset(ok, false, sizeof(ok));

         int ans = ;

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

         {

             if (s[i] != s[n-i+])                // 要变动的位置

             {

                 if (abs(p-i) > abs(p-(n-i+)))   // p位置离哪边近

                     ok[n-i+] = true;

                 else

                     ok[i] = true;

                 int tmp = abs(s[i]-s[n-i+]);

                 ans += min(-tmp, tmp);   // 求down/up 操作次数

             }

         }

         // 找出指针移动的最大距离

         int l = p, r = p;

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

         {

             if (ok[i])

             {

                 l = i;

                 break;

             }

         }

         for (int i = n; i >= p; i--)

         {

             if (ok[i])

             {

                 r = i;

                 break;

             }

         }

         // 求left/right 操作次数

         ans += abs(p-l) + abs(p-r);

         ans += min(abs(p-l), abs(p-r));   // 距离短的那边要走两次: lrr, rll(以p为界)

         printf("%d\n", ans);

     }

     return ;

 }

以下这个是我的，写得比较痛苦，没有做出来，纪念下（读者请忽略）

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn = 1e5 + ;

 char s[maxn];

 int n, p, ans;

 inline int change_num(int cur)

 {

     int x = s[cur] - 'a';

     int y = s[n-cur-] - 'a';

     int change1 = y - x;

     int change2 = x +  - y;

     s[cur] = s[n-cur-];

     return min(change1, change2);

 }

 inline int get_moves(int cur)  // 这里存在大问题，比较难修改

 {

     printf("cur = %d\n", cur);

     int l = cur - , r = cur + ;

     l = (l <  ? n -  : l);

     r = (r >= n ?  : r);

     int cntl = ;

     int cntr = ;

     printf("before: l = %d, cntl = %d\n", l, cntl);

     printf("        r = %d, cntr = %d\n", r, cntr);

     while (s[l] == s[n-l-] && l != cur && l != n-l-)

     {

         cntl++;

         l = (l <  ? n -  : l-);

     }

     while (s[r] == s[n-r-] && r != cur && r != n-r-)

     {

         cntr++;

         r = (r >= n ?  : r);

         printf("in: r = %d\n", r);

     }

     printf("after:  l = %d, cntl = %d\n", l, cntl);

     printf("        r = %d, cntr = %d\n", r, cntr);

     if (cntl < cntr)

         return -cntl;

     return cntr;

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

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

     #endif

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

     {

         scanf("%s", s);

         int cnt = ;

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

         {

             if (s[i] != s[n-i-])

                 cnt++;

         }

         int ans = ;

         p--;

         if (s[p] != s[n-p-])

         {

             ans += change_num(p);

             cnt--;

         }

   //      printf("cnt = %d\n", cnt);

     //    printf("before:  ans = %d\n", ans);

         int after, now = p;

         while (cnt)

         {

             int after = get_moves(now);

             printf("after = %d\n", after);

             now += after;

             ans += abs(after);

             ans += change_num(now);

             printf("s = %s\n", s);

             printf("ans = %d\n\n", ans);

             cnt--;

             if (now == p)

                 break;

         }

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

codeforces 486C. Palindrome Transformation 解题报告

最新文章

热门文章