20191024测试总结

在T2费了太多时间了，时间安排策略还要注意啊

T1：WOJ4766

显然早餐和晚餐需要分开考虑，然后在纸上稍微推算一下我们就可以发现显然早餐或者晚餐需要在一颗完整的子树上，剩下的节点就是另外的肠子。如果找不到大小正确的子树，那么就输出-1，否则直接按照类拓扑排序的思想标号即可。

#include <iostream>
#include <cstdio>
using namespace std;
int n, aa, bb, sum, cnt, h, t, p, q[100005], num[100005], tot[100005], head[100005], vis[100005], siz[100005], fa[100005], ans[100005];
struct node
{
    int v;
    int next;
} a[200005];
void ins(int u, int v)
{
    ++sum;
    a[sum].v = v;
    a[sum].next = head[u];
    head[u] = sum;
    return;
}
void dfs1(int k, int f)
{
    fa[k] = f;
    siz[k] = 1;
    int d = head[k];
    while (d)
    {
        if (a[d].v != f)
        {
            dfs1(a[d].v, k);
            siz[k] += siz[a[d].v];
        }
        d = a[d].next;
    }
    return;
}
void dfs2(int k, int val)
{
    vis[k] = val;
    int d = head[k];
    while (d)
    {
        if (a[d].v != fa[k])
            dfs2(a[d].v, val);
        d = a[d].next;
    }
    return;
}
int main()
{
    scanf("%d%d%d", &n, &aa, &bb);
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        ++num[u];
        ++num[v];
        ++tot[u];
        ++tot[v];
        ins(u, v);
        ins(v, u);
    }
    dfs1(1, 0);
    for (int i = 1; i <= n; ++i)
    {
        if (siz[i] == aa)
        {
            p = 1;
            dfs2(i, 1);
            for (int j = 1; j <= n; ++j)
                if (!vis[j])
                    vis[j] = -1;
            break;
        }
        if (siz[i] == bb)
        {
            p = 1;
            dfs2(i, -1);
            for (int j = 1; j <= n; ++j)
                if (!vis[j])
                    vis[j] = 1;
            break;
        }
    }
    if (!p)
    {
        printf("-1");
        return 0;
    }
    for (int i = 1; i <= n; ++i)
        if (vis[i] == 1 && num[i] == 1)
            q[++t] = i;
    while (h < t)
    {
        ++cnt;
        int k = q[++h];
        ans[k] = cnt;
        int d = head[k];
        while (d)
        {
            if (vis[a[d].v] == 1 && !ans[a[d].v])
            {
                --num[a[d].v];
                if (num[a[d].v] == 1)
                    q[++t] = a[d].v;
            }
            d = a[d].next;
        }
    }
    h = 0;
    t = 0;
    cnt = 0;
    for (int i = 1; i <= n; ++i)
        if (vis[i] == -1 && tot[i] == 1)
            q[++t] = i;
    while (h < t)
    {
        --cnt;
        int k = q[++h];
        ans[k] = cnt;
        int d = head[k];
        while (d)
        {
            if (vis[a[d].v] == -1 && !ans[a[d].v])
            {
                --tot[a[d].v];
                if (tot[a[d].v] == 1)
                    q[++t] = a[d].v;
            }
            d = a[d].next;
        }
    }
    for (int i = 1; i <= n; ++i)
        printf("%d ", ans[i]);
    return 0;
}

T2：WOJ4767

显然，括号的作用是将一些符号的正负性改变且只有在-号后添加有用，因此我们首先会认为只需要0或1层括号就等同于多层括号了，不过这不完全正确。实际上，我们需要最多2层括号，因为-((a+b)-c)这种情况就是不能展开的。而对于2层以上的括号，我们可以证明都可以转化为0、1、2层括号的形式，因此我们只需要枚举到达每个位置的时左侧还有多少个括号没有匹配然后dp。

PS：在代码中我们对于-号后都强制添加一个(，因为显然添加括号后，括号后的第一个数的正负性不会改变，因此需要特殊处理。如果我们最后发现在这个-号后添加括号不是最优的情况，那么这种情况就相当于将-a转换成了-(a)，显然对结果的正确性没有影响。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int t, n;
long long a[200005], b[200005], f[200005][3];
char c[200005];
int main()
{
    scanf("%d", &t);
    for (int tt = 1; tt <= t; ++tt)
    {
        scanf("%d", &n);
        b[1] = 1;
        for (int i = 1; i < n; ++i)
        {
            scanf("%lld %c", &a[i], &c[i + 1]);
            if (c[i + 1] == '+')
                b[i + 1] = 1;
            else
                b[i + 1] = -1;
        }
        scanf("%lld", &a[n]);
        f[0][0] = 0;
        f[0][1] = -1000000000000000000;
        f[0][2] = -1000000000000000000;
        for (int i = 1; i <= n; ++i)
            if (b[i] == 1)
            {
                f[i][0] = max(max(f[i - 1][0] + a[i], f[i - 1][1] + a[i]), f[i - 1][2] + a[i]);
                f[i][1] = max(f[i - 1][1] - a[i], f[i - 1][2] - a[i]);
                f[i][2] = f[i - 1][2] + a[i];
            }
            else
            {
                f[i][0] = -1000000000000000000;
                f[i][1] = max(max(f[i - 1][0] - a[i], f[i - 1][1] - a[i]), f[i - 1][2] - a[i]);
                f[i][2] = max(f[i - 1][1] + a[i], f[i - 1][2] + a[i]);
            }
        printf("%lld\n", max(max(f[n][0], f[n][1]), f[n][2]));
    }
    return 0;
}

T3：WOJ4768

神奇的DP。

显然，我们遇到障碍物时候沿着边走是最优解并且不可能往回走。此外，我们沿着边走出一个障碍后就不用拐弯了。可以证明最优解一定满足以上条件。

对此，我们进行dp。对于每个障碍都进行一次dp，找它之前如果直走会被阻挡的路线，然后对其进行更新，最有将所有路径更新到终点就完事了。

然后我们就碰到了一个问题。显然空间爆炸了。不过我们发现障碍物的个数并不多，因此直接set保存一下就完事了。下面上代码：

#include <iostream>
#include <cstdio>
#include <set>
#include <cmath>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int n, tx;
struct point
{
    int l;
    int r;
    int d;
    int u;
} a[500005];
struct node
{
    int x;
    int y;
    int d;
    node(int aa, int bb, int cc)
    {
        x = aa;
        y = bb;
        d = cc;
    }
    inline bool operator<(const node &bb) const
    {
        return y < bb.y;
    }
};
set<node> s;
inline bool cmp(point aa, point bb)
{
    return aa.l < bb.l;
}
inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c))
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (isdigit(c))
    {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline int dis(int x, int y, int xx, int yy)
{
    return abs(x - xx) + abs(y - yy);
}
int main()
{
    n = read();
    tx = read();
    for (int i = 1; i <= n; ++i)
    {
        a[i].l = read();
        a[i].d = read();
        a[i].r = read();
        a[i].u = read();
        if (a[i].l > a[i].r)
            swap(a[i].l, a[i].r);
        if (a[i].d > a[i].u)
            swap(a[i].d, a[i].u);
    }
    sort(a + 1, a + n + 1, cmp);
    s.insert(node(0, 0, 0));
    for (int i = 1; i <= n; ++i)
    {
        set<node>::iterator h, t, gu;
        int p = inf, q = inf;
        h = s.lower_bound(node(a[i].l, a[i].d, 0));
        t = s.upper_bound(node(a[i].l, a[i].u, 0));
        while (h != t)
        {
            p = min(p, dis(h->x, h->y, a[i].l, a[i].d) + h->d);
            q = min(q, dis(h->x, h->y, a[i].l, a[i].u) + h->d);
            gu = h;
            ++h;
            s.erase(gu);
        }
        s.insert(node(a[i].l, a[i].d, p));
        s.insert(node(a[i].l, a[i].u, q));
    }
    int ans = inf;
    for (set<node>::iterator it = s.begin(); it != s.end(); ++it)
        ans = min(ans, dis(it->x, it->y, tx, 0) + it->d);
    printf("%d", ans);
    return 0;
}