首页 > 代码库 > CodeForces 486C Palindrome Transformation
CodeForces 486C Palindrome Transformation
题意:
n(10^5)个字符 光标停在第pos个字符上 光标可以左右任意移动 而且可以从最左移到最右也可以从最右移到最左 在光标处的字符可以按字母顺序或倒序更改 更改也可以a->z或者z->a 光标移动和字符更改都需要1s 问最短几s能把串变成回文的
思路:
最后的状态是一定的 因此更改的次数和策略无关 扫一遍就可以知道更改最少需要几s
光标移动需要一定的策略 容易想到最优的方法一定是在字符串的一半移动 因此记录在字符串左一半和右一半最远的不回文的位置 让光标移动就好了
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<map> #include<set> #include<vector> #include<queue> #include<cstdlib> #include<ctime> #include<cmath> using namespace std; typedef long long LL; #define N 100010 int len, now, ans, res = N; char s[N]; int wa[N]; int main() { scanf("%d%d%s", &len, &now, s); now--; int L = len, R = -1; for (int l = 0, r = len - 1; l < r; l++, r--) { if (s[l] != s[r]) { int f = abs(s[l] - s[r]); ans += min(f, 26 - f); wa[l] = wa[r] = 1; L = min(L, l); R = max(R, l); } } if (ans) { res = min(res, min(abs(now - L) + R - L, abs(now - R) + R - L)); swap(L, R); L = len - 1 - L; R = len - 1 - R; res = min(res, min(abs(now - L) + R - L, abs(now - R) + R - L)); ans += res; } printf("%d\n", ans); return 0; }
CodeForces 486C Palindrome Transformation
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。