POI2010 Antisymmetry

对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如00001111和010101就是反对称的，1001就不是。

现在给出一个长度为N的01字符串，求它有多少个子串是反对称的。

manacher板子，写就完了

#include <bits/stdc++.h>
#define ull long long
const int maxn = 1e7;
char SS1[maxn], S[maxn], to[500];
int n, len[maxn], tot = 1;
signed main() {
    scanf("%d%s", &n, SS1 + 1);
    S[0] = '$', S[1] = '#';
    for (register int i = 1; i <= n; ++i) S[++tot] = SS1[i], S[++tot] = '#';
    to['1'] = '0', to['0'] = '1', to['#'] = '#', to['$'] = '$';
    int pos = 1, mx = 1;
    ull ans = 0;
    for (register int i = 1; i <= tot; i += 2) {
        len[i] = (i < mx ? std::min(mx - i, len[(pos << 1) - i]) : 1);
        while (S[i + len[i]] == to[S[i - len[i]]]) len[i]++;
        if (len[i] + i > mx) {
            mx = len[i] + i;
            pos = i;
        }
        ans += len[i] >> 1;
    }
    printf("%llu\n", ans);
    return 0;
}

Bovine Genomics

FJ拥有有斑点的牛和没有斑点的牛。他刚刚完成了牛基因的一门课程，他相信牛身上的斑点是由牛的基因突变引起的。FJ花费了巨大的代价，将他的牛的基因组排序。每个基因组都是长度为的字符串。当他把牛的基因组排列起来的时候，他得到了一个像下面这样的表格（，）:

位置: 1 2 3 4 5 6 7 8
斑点牛1: A A T C C C A T
斑点牛2: A C T T G C A A
斑点牛3: G G T C G C A A
普通牛1: A C T C C C A G
普通牛2: A C T C G C A T
普通牛3: A C T T C C A T
如果在某一段区间内，斑点牛和普通牛没有相同的基因段（即两组集合没有交集），那么FJ就能通过这段区间分辨两种牛。

请你帮FJ找出最短的满足条件的区间。

对每个字符串求哈希值。
\(n^2\)枚举整体的每个子串集合，然后由于求出哈希了，要判断两个字串的哈希集合是否有重复的。可以用set或者排序之后跑一遍双指针，复杂度nlogn。\(n^3 log n\)显然会T。考虑把枚举字串集合改为二分答案，二分答案的长度，然后每二分一次都check一遍。复杂度\(n^2 log_2 n\)

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int base = 29;
const int LEN = 514;
int n, m, N;
struct node {
    char str[LEN];
    ull f[LEN];
} s[LEN << 1];
ull p[LEN];
inline bool check(int st, int ed, int len) {
    set<ull> s1;
    set<ull> s2;
    for (int i = 1; i <= N; ++i) {
        if (i <= n)
            s1.insert(s[i].f[ed] - s[i].f[st - 1] * p[len]);
        else
            s2.insert(s[i].f[ed] - s[i].f[st - 1] * p[len]);
    }
    int len1 = s1.size(), len2 = s2.size(), len3;
    s1.insert(s2.begin(), s2.end());
    len3 = s1.size();
    if (len1 + len2 > len3)
        return false;
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    p[0] = 1;
    for (int i = 1; i <= 500; ++i) p[i] = (ull)(p[i - 1] * base);
    N = (n << 1);
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> s[i].str[j];
            s[i].f[j] = s[i].f[j - 1] * base + s[i].str[j] - 'A' + 1;
        }
    }
    int l = 1, r = m, mid;
    while (l < r) {
        bool flag = false;
        mid = (l + r) >> 1;
        for (int st = 1; st + mid - 1 <= m; ++st) {
            int ed = st + mid - 1;
            if (check(st, ed, mid)) {
                flag = true;
                break;
            }
        }
        if (flag)
            r = mid;
        else
            l = mid + 1;
    }
    printf("%d", l);
    return 0;
}

反例 贴一下卢的厌氧代码，不开O0过不去

#include <iostream>
#include <algorithm>
#pragma GCC optimize("O0")
using namespace std;
typedef long long ll;
const int N = 1010;
const ll ba = 131, p = 1e9 + 7;

int n, m;
ll h[N], ha[N][N], hb[N][N];
ll A[N], B[N];
char a[N][N], b[N][N];

bool check(int l, int r) {
    for (int i = 1; i <= n; ++i) A[i] = (p + ha[i][r] - (ha[i][l - 1] * h[r - l + 1])) % p;
    for (int i = 1; i <= n; ++i) B[i] = (p + hb[i][r] - (hb[i][l - 1] * h[r - l + 1])) % p;
    sort(A + 1, A + n + 1), sort(B + 1, B + n + 1);
    int len = 1;
    bool flag = 1;
    for (int i = 1; i <= n; ++i) {
        while (A[i] > B[len]) ++len;
        if (A[i] == B[len]) {
            flag = 0;
            break;
        }
    }
    return flag;
}

int main() {
    cin >> n >> m;
    h[0] = 1;
    for (int i = 1; i <= m; ++i) h[i] = h[i - 1] * ba % p;
    for (int i = 1; i <= n; ++i) {
        cin >> (a[i] + 1);
        for (int j = 1; j <= m; ++j) ha[i][j] = (ha[i][j - 1] * ba + (a[i][j] - 'A')) % p;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> (b[i] + 1);
        for (int j = 1; j <= m; ++j) hb[i][j] = (hb[i][j - 1] * ba + (b[i][j] - 'A')) % p;
    }
    int l = 1, r = m, mid;
    bool flag = 0;
    while (l < r) {
        mid = (l + r) >> 1;
        flag = 0;
        for (int i = 1; i + mid - 1 <= m; ++i)
            if (check(i, i + mid - 1)) {
                flag = 1;
                break;
            }
        if (flag)
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

friends

有三个好朋友喜欢在一起玩游戏,A君写下一个字符串S,B君将其复制一遍得到T,C君在T的任意位置(包括首尾)插入一个字符得到U.现在你得到了U,请你找出S.

求出哈希。
枚举插入字符的点，判断前面s和后面的s是否一样。
技巧：字符串\(S _{1...n}\) 现在有\(hash1_{1...a}, hash2_{a+2...n}\)
那么\(hash1,hash2\)拼一起的哈希值就是$hash1 * base^{hash2.length()+1} + hash2 $

似乎在梦中见过的样子

一个长度为 n 的字符串，所有形似于 A+B+A 的子串都是它的替身 , 且len(A)>=k,len(B)>=1 （位置不同其他性质相同的子串算不同子串,位置相同但拆分不同的子串算同一子串）,求它的替身的数量.

枚举A串，kmp，n^2复杂度。来不及写了，先走了