题目链接：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 ;
}