CF-196 D.The Next Good String(hash)

題目鏈接

題意

給一個數字$d$和字符串$s$,求字符串$t$滿足:

$s$和$t$等長

$t$的字典序大于$s$且盡可能小

$t$中不包含長度$\ge d$的回文串

思路

不包括長度$\ge d$的回文串,只需檢查是否包含長度為$d$和$d+1$的回文串

回文串可以用hash來判斷

首先求出最小的字典序,然后從前往后檢查是否包含$d$和$d+1$的回文串,貪心修改每個字符串

#include <bits/stdc++.h> #define ull unsigned long long const int maxn = 4e5 + 5; using namespace std; int d, len; char s[maxn], t[maxn]; ull hash_l[maxn], hash_r[maxn], p[maxn], base = 131; ull get_l(int x, int y) {return hash_l[x] - hash_l[x-y] * p[y+1]; } ull get_r(int x, int y) {return hash_r[x] - hash_r[x-y]; } int check(int x) {if (x >= d && get_l(x, d)*p[x-d+1] == get_r(x, d)) {return 1;}if (x > d && get_l(x, d+1)*p[x-d] == get_r(x, d+1)) return 1; return 0; } int dfs(int x, int sta) {if (x > len) {return 1;}char c = sta ? s[x] : 'a';for (char i = c; i <= 'z'; ++i) {t[x] = i;hash_l[x] = hash_l[x-1] * base + (i-'a'+1);hash_r[x] = hash_r[x-1] + p[x] * (i-'a'+1);if (check(x)) continue;if (dfs(x+1, sta && t[x] == s[x])) return 1;}return 0; } int main() {cin >> d >> s+1;len = strlen(s+1);for (int i = len; i >= 1; --i) {if (s[i] == 'z') s[i] = 'a';else {s[i]++;break;}if (i == 1) {cout << "Impossible\n";return 0;}}p[1] = 1;for (int i = 2; i <= len; ++i) p[i] = p[i-1] * base;if (dfs(1, 1)) cout << t+1 << endl;else cout << "Impossible\n";return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的CF-196 D.The Next Good String(hash)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。