20191030测试总结

今天貌似没那么自闭了 调正解还是很自闭

T1:WOJ4780

求个前缀和之后就是个二位偏序的板子,送分题。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n, len, ans, a[5000005], b[5000005], c[5000005];
long long cc[5000005];
struct node
{
    long long a;
    int b;
    long long bb;
    int w;
} s[5000005];
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
int read()
{
    int x = 0, f = 1;
    char c = gc();
    while (!isdigit(c))
    {
        if (c == '-')
            f = -1;
        c = gc();
    }
    while (isdigit(c))
    {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = gc();
    }
    return x * f;
}
bool cmp(node aa, node bb)
{
    if (aa.a != bb.a)
        return aa.a < bb.a;
    if (aa.b != bb.b)
        return aa.b < bb.b;
    return aa.w < bb.w;
}
int lowbit(int x)
{
    return x & -x;
}
void add(int x, int val)
{
    while (x <= len)
    {
        c[x] = min(c[x], val);
        x += lowbit(x);
    }
    return;
}
int query(int x)
{
    int num = 0x7f7f7f7f;
    while (x >= 1)
    {
        num = min(c[x], num);
        x -= lowbit(x);
    }
    return num;
}
int main()
{
    n = read();
    for (int i = 1; i <= n; ++i)
    {
        s[i].w = i;
        a[i] = read();
        s[i].a = s[i - 1].a + a[i];
    }
    for (int i = 1; i <= n; ++i)
    {
        b[i] = read();
        s[i].bb = s[i - 1].bb + b[i];
        cc[i] = s[i].bb;
    }
    sort(cc + 1, cc + n + 1);
    len = unique(cc + 1, cc + n + 1) - cc - 1;
    for (int i = 1; i <= n; ++i)
        s[i].b = lower_bound(cc + 1, cc + len + 1, s[i].bb) - cc;
    sort(s + 1, s + n + 1, cmp);
    memset(c, 0x7f, sizeof(c));
    for (int i = 1; i <= n; ++i)
    {
        ans = max(ans, s[i].w - query(s[i].b));
        add(s[i].b, s[i].w);
        if (s[i].a >= 0 && s[i].bb >= 0)
            ans = max(ans, s[i].w);
    }
    printf("%d", ans);
    return 0;
}

T2:WOJ4781

求出DP方程之后发现是n^3方的,然后就不会推了。结果发现题解上说决策点具有单调递增的性质,又看了看发现是个四边形不等式优化。不说了滚去学了。

#include <iostream>
#include <cstdio>
using namespace std;
int n, g[5005][5005];
long long sum[5005], f[5005][5005];
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read()
{
    int x = 0, f = 1;
    char c = gc();
    while (!isdigit(c))
    {
        if (c == '-')
            f = -1;
        c = gc();
    }
    while (isdigit(c))
    {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = gc();
    }
    return x * f;
}
int main()
{
    n = read();
    for (register int i = 1; i <= n; ++i)
    {
        sum[i] = read();
        sum[i] += sum[i - 1];
    }
    for (register int i = 1; i <= n; ++i)
    {
        f[i][i] = sum[i] - sum[i - 1];
        g[i][i] = i;
    }
    for (register int i = 1; i < n; ++i)
        for (register int j = 1; j + i <= n; ++j)
        {
            int k = j + i;
            f[j][k] = 0x7f7f7f7f7f7f7f7f;
            for (register int l = g[j][k - 1]; l <= g[j + 1][k]; ++l)
                if (f[j][l - 1] + f[l + 1][k] < f[j][k])
                    f[j][k] = f[j][l - 1] + f[l + 1][k], g[j][k] = l;
            f[j][k] += sum[k] - sum[j - 1];
        }
    printf("%lld\n", f[1][n]);
    return 0;
}

T3:WOJ4782

极其自闭的一道题

首先推出期望方程,然后高斯消元求解,但是这里要求多次,显然会达到n^4复杂度而t掉,因此需要分治消元。

分治消元的具体做法是:先用前一半的方程进行消元,然后递归后一半;(恢复原矩阵后)再用后一半的方程进行消元,然后递归前一半。这样当区间缩小到单点时,这个方程并没有拿来消其它的方程,我们可以直接修改它并求出所有f_i。复杂度就优化到n^3了(虽然这个复杂度看起来很假但确实是对的)。

#include <iostream>
#include <cstdio>
#define mod 998244353
using namespace std;
int n, m, f[305][305], ans[305][305], p[305][305], g[10][305][305];
int ksm(int a, int k)
{
    int b = 1;
    while (k)
    {
        if (k & 1)
            b = (long long)b * a % mod;
        a = (long long)a * a % mod;
        k >>= 1;
    }
    return b;
}
void dfs(int l, int k)
{
    ans[l][k] = f[k][0];
    for (int i = 1; i <= n; ++i)
        if (i != k && f[k][i])
        {
            if (!p[l][i])
                dfs(l, i);
            ans[l][k] = (ans[l][k] - (long long)f[k][i] * ans[l][i]) % mod;
        }
    p[l][k] = 1;
    return;
}
void solve(int l, int r, int num)
{
    if (l == r)
    {
        p[l][r] = 1;
        for (int i = 1; i <= n; ++i)
            if (!p[l][i])
                dfs(l, i);
        return;
    }
    int mid = (l + r) >> 1;
    for (int i = l; i <= r; ++i)
    {
        g[num][i][0] = f[i][0];
        for (int j = l; j <= r; ++j)
            g[num][i][j] = f[i][j];
    }
    for (int i = l; i <= mid; ++i)
    {
        int k = ksm(f[i][i], mod - 2);
        f[i][0] = (long long)f[i][0] * k % mod;
        for (int j = i; j <= r; ++j)
            f[i][j] = (long long)f[i][j] * k % mod;
        for (int j = i + 1; j <= r; ++j)
            if (f[j][i])
            {
                f[j][0] = (f[j][0] - (long long)f[i][0] * f[j][i]) % mod;
                for (int k = r; k >= i; --k)
                    f[j][k] = (f[j][k] - (long long)f[i][k] * f[j][i]) % mod;
            }
    }
    solve(mid + 1, r, num + 1);
    for (int i = l; i <= r; ++i)
    {
        f[i][0] = g[num][i][0];
        for (int j = l; j <= r; ++j)
            f[i][j] = g[num][i][j];
    }
    for (int i = r; i > mid; --i)
    {
        int k = ksm(f[i][i], mod - 2);
        f[i][0] = (long long)f[i][0] * k % mod;
        for (int j = l; j <= i; ++j)
            f[i][j] = (long long)f[i][j] * k % mod;
        for (int j = i - 1; j >= l; --j)
            if (f[j][i])
            {
                f[j][0] = (f[j][0] - (long long)f[i][0] * f[j][i]) % mod;
                for (int k = l; k <= i; ++k)
                    f[j][k] = (f[j][k] - (long long)f[i][k] * f[j][i]) % mod;
            }
    }
    solve(l, mid, num + 1);
    for (int i = l; i <= r; ++i)
    {
        f[i][0] = g[num][i][0];
        for (int j = l; j <= r; ++j)
            f[i][j] = g[num][i][j];
    }
    return;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        ++f[u][u];
        ++f[u][0];
        --f[u][v];
    }
    solve(1, n, 0);
    for (int i = 2; i <= n; ++i)
        printf("%d\n", (ans[i][1] + mod) % mod);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注