E – Independence

这道题直接去想性质不好想，因为贪心的话、找到两个大小相近的团没什么性质。我们可以考虑建一张反图。如果这是个二分图，那么左右部恰好可以作为题中的两个 state。然而，意识到并不保证是一张连通的二分图，所以我们可以用一些连通块来拼成两个 state。那么，我们可以用个背包搞搞，再最后算算答案即可。（就不需要贪心的构造两个大小相近的团了，全部都算一遍即可）。

// ARC099E.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 770;

int n, m, color[MAX_N], cnt[2];
bool G[MAX_N][MAX_N], tmp[MAX_N << 1], pack[MAX_N << 1];

void dfs(int u, int col)
{
    color[u] = col, cnt[col == 1]++;
    for (int i = 1; i <= n; i++)
        if (G[u][i] == false && i != u)
            if (color[i] == col)
                puts("-1"), exit(0);
            else if (color[i] == 0)
                dfs(i, -col);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v; i <= m; i++)
        scanf("%d%d", &u, &v), G[u][v] = G[v][u] = true;
    pack[0] = true;
    for (int i = 1; i <= n; i++)
        if (!color[i])
        {
            cnt[0] = cnt[1] = 0, dfs(i, 1);
            memset(tmp, false, sizeof(tmp));
            for (int j = 0; j <= n; j++)
                tmp[j + cnt[0]] |= pack[j], tmp[j + cnt[1]] |= pack[j];
            memcpy(pack, tmp, sizeof(pack));
        }
    int ans = 0x7fffffff;
    for (int i = 0; i <= n; i++)
        if (pack[i])
            ans = min(ans, i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2);
    printf("%d\n", ans);
    return 0;
}

F – Eating Symbols Hard

这个题也好。

发现移动指针并不会对结果产生影响，而 \(+\) 和 \(-\) 会作出贡献。思考这个贡献，发现最终结果可以被表示为一个多项式，也就跟哈希很像。那么，如果我们要在一个区间哈希上批量移动指针，那么就相当于乘上单位、或者是单位逆元，最后我们用 \(map\) 存一存即可。

// ARC099F.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 501000, mod = 998244353;

int fpow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

const int base[4] = {133, 233, 911, 691}, base_inv[4] = {fpow(base[0], mod - 2), fpow(base[1], mod - 2), fpow(base[2], mod - 2), fpow(base[3], mod - 2)};

struct node
{
    int val[4];

    bool operator<(const node &rhs) const
    {
        for (int i = 0; i < 4; i++)
            if (val[i] != rhs.val[i])
                return (val[i] < rhs.val[i]);
        return false;
    }

    bool operator==(const node &rhs) const
    {
        for (int i = 0; i < 4; i++)
            if (val[i] != rhs.val[i])
                return false;
        return true;
    }
} prefix[MAX_N], base_pre;

map<node, int> cnt;
int n, base_pow[MAX_N][4], base_invs[MAX_N][4], pos[MAX_N];
char str[MAX_N];

int getPow(int idx, int j) { return idx >= 0 ? base_pow[idx][j] : base_invs[-idx][j]; }

node calc(node x, node y, int idx)
{
    for (int i = 0; i < 4; i++)
        x.val[i] = (0LL + x.val[i] + 1LL * y.val[i] * getPow(idx, i) % mod) % mod;
    return x;
}

int main()
{
    scanf("%d%s", &n, str + 1);
    for (int j = 0; j < 4; j++)
        for (int i = base_pow[0][j] = base_invs[0][j] = 1; i <= n; i++)
            base_pow[i][j] = 1LL * base_pow[i - 1][j] * base[j] % mod, base_invs[i][j] = 1LL * base_invs[i - 1][j] * base_inv[j] % mod;
    for (int j = 0; j < 4; j++)
        for (int i = 1, ptr = 0; i <= n; i++)
        {
            if (str[i] == '+')
                base_pre.val[j] = (0LL + base_pre.val[j] + getPow(ptr, j)) % mod;
            else if (str[i] == '-')
                base_pre.val[j] = (0LL + base_pre.val[j] + mod - getPow(ptr, j)) % mod;
            else if (str[i] == '<')
                ptr--;
            else
                ptr++;
            prefix[i].val[j] = base_pre.val[j], pos[i] = ptr;
        }
    cnt[base_pre]++;
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        ans += cnt[prefix[i]], cnt[calc(prefix[i], base_pre, pos[i])]++;
    printf("%lld\n", ans);
    return 0;
}