20191012测试总结

原地爆炸。。。

T1：WOJ4749

点双连通分量，挺裸的

#include <iostream>
#include <cstdio>
using namespace std;
int n, m, x, y, sum = 1, cnt, col, top, ttop, ans;
int s[1000005], dfn[1000005], low[1000005];
int head[1000005], use[1000005], co[1000005];
int num[1000005], tot[1000005], ss[1000005];
struct node
{
    int v;
    int next;
} a[2000005];
int read()
{
    int x = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
    {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
void ins(int u, int v)
{
    ++sum;
    a[sum].v = v;
    a[sum].next = head[u];
    head[u] = sum;
    return;
}
void tarjan(int k)
{
    ++cnt;
    dfn[k] = cnt;
    low[k] = cnt;
    ss[++ttop] = k;
    int d = head[k];
    while (d)
    {
        if (!use[d >> 1])
        {
            use[d >> 1] = 1;
            s[++top] = (d >> 1);
            if (!dfn[a[d].v])
            {
                tarjan(a[d].v);
                low[k] = min(low[k], low[a[d].v]);
                if (low[a[d].v] >= dfn[k])
                {
                    ++col;
                    while (s[top] != (d >> 1))
                    {
                        co[s[top]] = col;
                        --top;
                        ++num[col];
                    }
                    co[s[top]] = col;
                    --top;
                    ++num[col];
                    while (ss[ttop] != a[d].v)
                    {
                        --ttop;
                        ++tot[col];
                    }
                    --ttop;
                    tot[col] += 2;
                }
            }
            else
                low[k] = min(low[k], dfn[a[d].v]);
        }
        d = a[d].next;
    }
    return;
}
int main()
{
    n = read();
    m = read();
    for (int i = 1; i <= m; ++i)
    {
        x = read();
        y = read();
        ins(x, y);
        ins(y, x);
    }
    tarjan(1);
    for (int i = 1; i <= m; ++i)
        if (co[i] && tot[co[i]] == num[co[i]])
            ans ^= i;
    printf("%d", ans);
    return 0;
}

T2：WOJ4750

很套路的AC自动机DP，注意需要用矩阵快速幂优化

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int m, sum = 1, a[105], bo[205], tr[205][26], nxt[205];
char s[205];
long long n, ans;
void insert(int k)
{
    int root = 1, len = strlen(s);
    for (int i = 0; i < len; ++i)
    {
        int k = s[i] - 'a';
        if (!tr[root][k])
            tr[root][k] = ++sum;
        root = tr[root][k];
    }
    bo[root] += a[k];
    return;
}
struct matrix
{
    long long a[205][205];
    matrix()
    {
        memset(a, 0, sizeof(a));
    }
    matrix(long long x)
    {
        for (int i = 1; i <= sum; ++i)
            for (int j = 1; j <= sum; ++j)
                a[i][j] = x;
    }
    matrix operator*(const matrix &bb) const
    {
        matrix cc(-1);
        for (int i = 1; i <= sum; ++i)
            for (int j = 1; j <= sum; ++j)
                for (int k = 1; k <= sum; ++k)
                    if (a[i][k] != -1 && bb.a[k][j] != -1)
                        cc.a[i][j] = max(cc.a[i][j], a[i][k] + bb.a[k][j]);
        return cc;
    }
};
void build()
{
    for (int i = 0; i < 26; ++i)
        tr[0][i] = 1;
    int h = 0, t = 1, q[205];
    q[1] = 1;
    while (h < t)
    {
        ++h;
        int k = q[h];
        for (int i = 0; i < 26; ++i)
            if (tr[k][i])
            {
                nxt[tr[k][i]] = tr[nxt[k]][i];
                bo[tr[k][i]] += bo[tr[nxt[k]][i]];
                q[++t] = tr[k][i];
            }
            else
                tr[k][i] = tr[nxt[k]][i];
    }
    return;
}
matrix ksm(matrix aa, long long k)
{
    matrix x(-1);
    x.a[1][1] = 0;
    while (k)
    {
        if (k & 1)
            x = x * aa;
        aa = aa * aa;
        k >>= 1;
    }
    return x;
}
int main()
{
    scanf("%lld%d", &n, &m);
    for (int i = 1; i <= m; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= m; ++i)
    {
        scanf("%s", s);
        insert(i);
    }
    build();
    matrix aa(-1);
    for (int i = 1; i <= sum; ++i)
        for (int j = 0; j < 26; ++j)
            aa.a[i][tr[i][j]] = bo[tr[i][j]];
    aa = ksm(aa, n);
    for (int i = 1; i <= sum; ++i)
        ans = max(ans, aa.a[1][i]);
    printf("%lld", ans);
    return 0;
}

T3：WOJ4751

显然的差分约束

不过由于边数太多，需要线段树优化建图。。。

由于这道题鸽的有点久，改的时候已经记不大清一些具体内容了，又半天调不对，因此直接代码是std。

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 400010, E = 2000000;
int n, s, m, i, x, y, z, tot, l[N << 1], r[N << 1], pos[N];
int a[M], d[M], g[M], v[E], nxt[E], ed;
char w[E];
int h, t, q[M], f[M];
inline void read(int &a)
{
    char c;
    while (!(((c = getchar()) >= '0') && (c <= '9')))
        ;
    a = c - '0';
    while (((c = getchar()) >= '0') && (c <= '9'))
        (a *= 10) += c - '0';
}
inline void add(int x, int y, char z)
{
    d[y]++;
    v[++ed] = y;
    w[ed] = z;
    nxt[ed] = g[x];
    g[x] = ed;
}
inline int build(int a, int b)
{
    int x = ++tot;
    if (a == b)
        return pos[a] = x;
    int mid = (a + b) >> 1;
    add(l[x] = build(a, mid), x, 0);
    add(r[x] = build(mid + 1, b), x, 0);
    return x;
}
void ask(int x, int a, int b, int c, int d)
{
    if (c > d)
        return;
    if (c <= a && b <= d)
    {
        add(x, tot, 1);
        return;
    }
    int mid = (a + b) >> 1;
    if (c <= mid)
        ask(l[x], a, mid, c, d);
    if (d > mid)
        ask(r[x], mid + 1, b, c, d);
}
int main()
{
    read(n), read(s), read(m);
    build(1, n);
    while (s--)
        read(x), read(y), a[pos[x]] = y;
    while (m--)
    {
        read(x), read(y), read(z);
        tot++;
        for (i = 1; i <= z; i++)
            read(q[i]), add(tot, pos[q[i]], 0);
        ask(1, 1, n, x, q[1] - 1);
        ask(1, 1, n, q[z] + 1, y);
        for (i = 1; i < z; i++)
            ask(1, 1, n, q[i] + 1, q[i + 1] - 1);
    }
    for (h = i = 1; i <= tot; i++)
        if (!d[i])
            f[q[++t] = i] = 1;
    while (h <= t)
    {
        x = q[h++];
        if (f[x] > 1000000000)
            return puts("Impossible"), 0;
        if (a[x])
        {
            if (a[x] < f[x])
                return puts("Impossible"), 0;
            if (a[x] > f[x])
                f[x] = a[x];
        }
        for (i = g[x]; i; i = nxt[i])
        {
            if (f[v[i]] < f[x] + w[i])
                f[v[i]] = f[x] + w[i];
            if (!(--d[v[i]]))
                q[++t] = v[i];
        }
    }
    if (t < tot)
        return puts("Impossible"), 0;
    for (puts("Possible"), i = 1; i <= n; i++)
        printf("%d ", f[pos[i]]);
    return 0;
}