20191105测试总结

什么毒瘤题啊。。。爆零了

T1：WOJ4793

显然如果打了御牌就必须要打完，然后就可以贪心了：若打了御牌，那么兵牌就只用打小于0的，否则直接打；若没有打御牌，那么就拿大的兵牌打对方小的兵牌，知道不能打为止。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
int n, m, mm, ans1, ans2;
struct node
{
    int val;
    int num;
} a[1000005], b[1000005], c[1000005], aa[1000005], bb[1000005], cc[1000005];
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
bool cmp(node aa, node bb)
{
    return aa.val < bb.val;
}
signed main()
{
    n = read(), m = read(), mm = read();
    for (int i = 1; i <= n; ++i)
    {
        a[i].val = read();
        a[i].num = read();
    }
    for (int i = 1; i <= m; ++i)
    {
        b[i].val = read();
        b[i].num = read();
    }
    for (int i = 1; i <= mm; ++i)
    {
        c[i].val = read();
        c[i].num = read();
    }
    sort(a + 1, a + n + 1, cmp);
    sort(b + 1, b + m + 1, cmp);
    sort(c + 1, c + mm + 1, cmp);
    for (int i = 1; i <= n; ++i)
        aa[i] = a[i];
    for (int i = 1; i <= m; ++i)
        bb[i] = b[i];
    for (int i = 1; i <= mm; ++i)
        cc[i] = c[i];
    int j = n;
    for (int i = 1; i <= mm; ++i)
    {
        while (j && a[j].val >= c[i].val && a[j].num < c[i].num)
        {
            ans1 += a[j].num * (a[j].val - c[i].val);
            c[i].num -= a[j].num;
            a[j].num = 0;
            --j;
        }
        if (!j || a[j].val < c[i].val)
            break;
        ans1 += c[i].num * (a[j].val - c[i].val);
        a[j].num -= c[i].num;
        c[i].num = 0;
    }
    swap(a, aa);
    swap(b, bb);
    swap(c, cc);
    int pan = 0;
    j = 1;
    for (int i = 1; i <= m; ++i)
    {
        while (j < n && a[j].val < b[i].val)
            ++j;
        while (j < n && a[j].val >= b[i].val && a[j].num < b[i].num)
        {
            b[i].num -= a[j].num;
            a[j].num = 0;
            ++j;
        }
        if (a[j].num < b[i].num)
        {
            pan = 1;
            break;
        }
        a[j].num -= b[i].num;
        b[i].num = 0;
        if (j == n && !a[j].num)
        {
            pan = 1;
            break;
        }
    }
    j = n;
    for (int i = 1; i <= mm; ++i)
    {
        if (c[i].val >= 0)
            break;
        while (j && a[j].val >= c[i].val && a[j].num < c[i].num)
        {
            ans2 += a[j].num * (a[j].val - c[i].val);
            c[i].num -= a[j].num;
            a[j].num = 0;
            --j;
        }
        if (!j || a[j].val < c[i].val)
            break;
        ans2 += c[i].num * (a[j].val - c[i].val);
        a[j].num -= c[i].num;
        c[i].num = 0;
    }
    if (!pan)
        for (int i = 1; i <= n; ++i)
            if (a[i].val > 0)
                ans2 += a[i].val * a[i].num;
    printf("%lld", max(ans1, ans2));
    return 0;
}

T2：WOJ4794

按照最小生成树的思路乱搞，细节参考题解。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define mod 1000000007
#define int long long
using namespace std;
int t, n, m, xx, tot, sum, cnt, les, equ;
int fa[100005][25], maxn[100005][25];
int head[100005], nxt[200005], to[200005], w[200005], mo[100005], dep[100005];
int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        ch = getchar();
        if (ch == '-')
            f = -1;
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int find(int x)
{
    if (x == mo[x])
        return x;
    return mo[x] = find(mo[x]);
}
void add(int a, int b, int c)
{
    nxt[++tot] = head[a];
    head[a] = tot;
    to[tot] = b;
    w[tot] = c;
    nxt[++tot] = head[b];
    head[b] = tot;
    to[tot] = a;
    w[tot] = c;
}
void dfs(int u, int faa)
{
    dep[u] = dep[faa] + 1;
    fa[u][0] = faa;
    for (int i = 1; i <= 20; ++i)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int i = 1; i <= 20; ++i)
        maxn[u][i] = max(maxn[u][i - 1], maxn[fa[u][i - 1]][i - 1]);
    for (int i = head[u]; i; i = nxt[i])
    {
        int v = to[i];
        if (v == faa)
            continue;
        maxn[v][0] = w[i];
        dfs(v, u);
    }
}
int query(int a, int b)
{
    if (dep[a] < dep[b])
        swap(a, b);
    int tmp = 0;
    for (int i = 20; i >= 0; --i)
    {
        if (dep[fa[a][i]] >= dep[b])
        {
            tmp = max(tmp, maxn[a][i]);
            a = fa[a][i];
        }
    }
    if (a == b)
        return tmp;
    for (int i = 20; i >= 0; --i)
    {
        if (fa[a][i] != fa[b][i])
        {
            tmp = max(tmp, max(maxn[a][i], maxn[b][i]));
            a = fa[a][i], b = fa[b][i];
        }
    }
    return max(tmp, max(maxn[a][0], maxn[b][0]));
}
struct node
{
    int u, v, w, lazy;
    void init()
    {
        lazy = 0;
    }
} e[200005];
bool cmp(node a, node b)
{
    return a.w < b.w;
}
int ksm(int a, int k)
{
    int b = 1;
    while (k)
    {
        if (k & 1)
            b = b * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return b;
}
int solve()
{
    sum = 0;
    cnt = 0;
    les = 0;
    equ = 0;
    for (int i = 1; i <= m; ++i)
    {
        int x = find(e[i].u), y = find(e[i].v);
        if (x != y)
        {
            ++cnt;
            sum += e[i].w;
            mo[x] = y;
            e[i].lazy = 1;
            add(e[i].u, e[i].v, e[i].w);
            if (cnt == n - 1)
                break;
        }
    }
    if (sum > xx)
        return 0;
    dfs(1, 0);
    int now = sum;
    for (int i = 1; i <= m; ++i)
    {
        if (!e[i].lazy)
        {
            now = sum + e[i].w - query(e[i].u, e[i].v);
            if (now == xx)
                equ++;
            if (now < xx)
                les++;
        }
    }
    int ans = 0;
    if (sum == xx)
        ans = (ans + (ksm(2, m) - 2 * ksm(2, m - n + 1 - equ) % mod + mod) % mod) % mod;
    else
        ans = (ans + 2 * (ksm(2, m - n + 1 - les) - ksm(2, m - n + 1 - les - equ) + mod) % mod) % mod;
    return ans;
}
signed main()
{
    t = read();
    for (int tt = 1; tt <= t; ++tt)
    {
        tot = 0;
        memset(head, 0, sizeof(head));
        n = read();
        m = read();
        xx = read();
        for (int i = 1; i <= n; ++i)
            mo[i] = i;
        for (int i = 1; i <= m; ++i)
        {
            e[i].lazy = 0;
            e[i].u = read();
            e[i].v = read();
            e[i].w = read();
        }
        sort(e + 1, e + m + 1, cmp);
        printf("%lld\n", solve());
    }
    return 0;
}

T3：WOJ4795

非常毒瘤的数位DP，借助KMP，然后按位确定S的每一位的值，当然这样的复杂度暂时是不正确的。

考虑优化：将每个点的的重儿子提取出来，然后进行一次倍增，思路类似于20191026测试总结中的T3。

太毒瘤了。。。代码直接改了一下std。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
long long read()
{
    long long x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
namespace io
{
const int MaxBuff = 1 << 15;
const int Output = 1 << 23;
char B[MaxBuff], *S = B, *T = B;
#define getc() ((S == T) && (T = (S = B) + fread(B, 1, MaxBuff, stdin), S == T) ? 0 : *S++)
char Out[Output], *it = Out;
void flush()
{
    fwrite(Out, 1, it - Out, stdout);
    it = Out;
}
} // namespace io
template <class Type>
void Print(register Type x, register char ch = '\n')
{
    using namespace io;
    if (!x)
        *it++ = '0';
    else
    {
        if (x < 0)
            *it++ = '-', x = -x;
        static int s[100];
        register int t = 0;
        while (x)
            s[++t] = x % 10, x /= 10;
        while (t)
            *it++ = '0' + s[t--];
    }
    *it++ = ch;
}
const int N = 5e4 + 5;
const int M = 21;
const int L = 17;
const int mod = 1e9 + 7;
const long long inf = (long long)1e18 + 1;
int T, n, m, q;
bool p[N][10];
int fail[M], val[L][N][M], trans[M][10], pw[L] = {10};
long long f[N][M], rkl[L][N][M], rkr[L][N][M];
char str[M], s[N], ed[L][N][M];
long long fix(long long x)
{
    return x < inf ? x : inf;
}
void kmp()
{
    fail[0] = fail[1] = 0;
    for (int i = 2; i <= m; ++i)
    {
        int now = fail[i - 1];
        while (now && str[now + 1] != str[i])
            now = fail[now];
        if (str[now + 1] == str[i])
            fail[i] = now + 1;
        else
            fail[i] = 0;
    }
}
void init()
{
    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j <= 9; ++j)
        {
            int now = i;
            while (now && str[now + 1] != j + '0')
                now = fail[now];
            if (str[now + 1] != j + '0')
                trans[i][j] = 0;
            else
                trans[i][j] = now + 1;
        }
    }
    for (int j = 0; j <= 9; ++j)
        trans[m][j] = m;
}
void input()
{
    n = read(), q = read();
    scanf("%s%s", str + 1, s + 1);
    m = strlen(str + 1);
    for (int i = 1; i <= n; ++i)
    {
        if (s[i] == '?')
            memset(p[i], 1, sizeof(p[i]));
        else
            memset(p[i], 0, sizeof(p[i])), p[i][s[i] - '0'] = 1;
    }
    kmp(), init();
}
int query(long long k)
{
    if (k > f[1][0])
        return -1;
    int x = 1, y = 0, res = 0;
    while (x <= n)
    {
        for (int i = L - 1; ~i; --i)
        {
            if (x + (1 << i) <= n + 1 && rkl[i][x][y] < k && k <= rkr[i][x][y])
            {
                res = ((long long)res * pw[i] + val[i][x][y]) % mod;
                k -= rkl[i][x][y], y = ed[i][x][y], x += (1 << i);
            }
        }
        if (x > n)
            break;
        for (int i = 0; i <= 9; ++i)
        {
            if (k > f[x + 1][trans[y][i]])
                k -= f[x + 1][trans[y][i]];
            else
            {
                res = (10LL * res + i) % mod;
                ++x, y = trans[y][i];
                break;
            }
        }
    }
    return res;
}
int main()
{
    for (int i = 1; i < L; ++i)
        pw[i] = (long long)pw[i - 1] * pw[i - 1] % mod;
    T = read();
    while (T--)
    {
        input();
        for (int i = 0; i <= m; ++i)
            f[n + 1][i] = (i == m);
        for (int i = n; i >= 0; --i)
        {
            for (int j = 0; j <= m; ++j)
            {
                f[i][j] = 0;
                long long mx = -1;
                int nxt = -1;
                for (int k = 0; k <= 9; ++k)
                {
                    if (p[i][k])
                    {
                        f[i][j] = fix(f[i][j] + f[i + 1][trans[j][k]]);
                        if (f[i + 1][trans[j][k]] > mx)
                            nxt = k, mx = f[i + 1][trans[j][k]];
                    }
                }
                ed[0][i][j] = trans[j][nxt];
                val[0][i][j] = nxt, rkl[0][i][j] = 0;
                for (int k = 0; k < nxt; ++k)
                    if (p[i][k])
                        rkl[0][i][j] = fix(rkl[0][i][j] + f[i + 1][trans[j][k]]);
                rkr[0][i][j] = fix(rkl[0][i][j] + f[i + 1][trans[j][nxt]]);
            }
        }
        for (int k = 1; k < L; ++k)
        {
            int len = (1 << (k - 1));
            for (int i = 1; i + (1 << k) <= n + 1; ++i)
            {
                for (int j = 0; j <= m; ++j)
                {
                    int x = ed[k - 1][i][j];
                    ed[k][i][j] = ed[k - 1][i + len][x];
                    val[k][i][j] = (1LL * val[k - 1][i][j] * pw[k - 1] + val[k - 1][i + len][x]) % mod;
                    rkl[k][i][j] = fix(rkl[k - 1][i][j] + rkl[k - 1][i + len][x]);
                    rkr[k][i][j] = fix(rkl[k - 1][i][j] + rkr[k - 1][i + len][x]);
                }
            }
        }
        while (q--)
        {
            long long k = read();
            Print(query(k));
        }
        io::flush();
    }
    return 0;
}