本文共 2069 字，大约阅读时间需要 6 分钟。
manacher+dp.其实理解manacher就可以解了，大水题，dp就是dp[i]=dp[i>>1]+1如何满足k-palindrome条件。
1 /* 7D */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 using namespace std; 22 //#pragma comment(linker,"/STACK:102400000,1024000") 23 24 #define sti set 25 #define stpii set > 26 #define mpii map 27 #define vi vector 28 #define pii pair 29 #define vpii vector > 30 #define rep(i, a, n) for (int i=a;i =a;--i) 32 #define clr clear 33 #define pb push_back 34 #define mp make_pair 35 #define fir first 36 #define sec second 37 #define all(x) (x).begin(),(x).end() 38 #define SZ(x) ((int)(x).size()) 39 #define lson l, mid, rt<<1 40 #define rson mid+1, r, rt<<1|1 41 42 const int maxn = 5e6+5; 43 int dp[maxn]; 44 int Len[maxn*2]; 45 char s[maxn]; 46 char d[maxn*2]; 47 48 void init() { 49 int slen = strlen(s); 50 int j = 0; 51 52 d[j++] = '$'; 53 d[j++] = '#'; 54 rep(i, 0, slen) { 55 d[j++] = s[i]; 56 d[j++] = '#'; 57 } 58 } 59 60 void manacher() { 61 int dlen = strlen(d); 62 int p = 0, p0 = 0; 63 64 rep(i, 1, dlen) { 65 if (p > i) 66 Len[i] = min(p-i, Len[2*p0-i]); 67 else 68 Len[i] = 1; 69 while (d[i+Len[i]] == d[i-Len[i]]) 70 ++Len[i]; 71 if (i + Len[i] > p) { 72 p = i + Len[i]; 73 p0 = i; 74 } 75 } 76 } 77 78 void solve() { 79 init(); 80 manacher(); 81 82 int slen = strlen(s); 83 int ans = 1; 84 85 dp[1] = 1; 86 rep(i, 2, slen+1) { 87 if (Len[i+1] >= i+1) { 88 dp[i] = dp[i>>1] + 1; 89 } 90 ans += dp[i]; 91 } 92 93 printf("%d\n", ans); 94 } 95 96 int main() { 97 ios::sync_with_stdio(false); 98 #ifndef ONLINE_JUDGE 99 freopen("data.in", "r", stdin);100 freopen("data.out", "w", stdout);101 #endif102 103 scanf("%s", s);104 solve();105 106 #ifndef ONLINE_JUDGE107 printf("time = %d.\n", (int)clock());108 #endif109 110 return 0;111 }
转载于:https://www.cnblogs.com/bombe1013/p/4852322.html