20191026测试总结

说好的大家一起考CSP-S模拟赛，然而事实是大家一起考NOI模拟赛）雾

T1：WOJ4771

非常水的一道题，直接输出输入即可，记得取模。下面是证明(数学公式不好打，偷个懒直接放题解吧)：

WOJ4771

#include <iostream>
#include <cstdio>
#define mod 998244353
using namespace std;
int n;
int main()
{
    scanf("%d", &n);
    printf("%d", n % mod);
    return 0;
}

T2：WOJ4772

大概是因为没睡醒，考场完全没思路。。。瞎打了个程序挂完了。

显然是两棵树的结构。因此，我们可以发现，对于一棵树中的一条路，它可以被它的两个端点在另一棵树上的简单路径上的点代替，因此我们设两颗树分别为tr1、tr2，然后将tr1上的所有边在tr2上差分，再计算tr2上的每条边可以被哪些可以代替这条边的tr1上的边代替即可。

我们在遍历tr2求答案的时候显然答案需要由一个节点的每一个子树相结合来算出答案，因此首先想到线段树合并。不过，由于数据过大，会MLE，因此这里我们还需要再进行一次差分。

细节的实现就看代码吧。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;
int n, tot, in[1000005], out[1000005], ans[1000005], c[2000005];
vector<int> vec[1000005];
struct point
{
    int sum;
    int fa[1000005];
    int dep[1000005];
    int siz[1000005];
    int top[1000005];
    int son[1000005];
    int head[1000005];
    struct node
    {
        int v;
        int next;
    } a[2000005];
    void ins(int u, int v)
    {
        ++sum;
        a[sum].v = v;
        a[sum].next = head[u];
        head[u] = sum;
        ++sum;
        a[sum].v = u;
        a[sum].next = head[v];
        head[v] = sum;
        return;
    }
    void dfs1(int k)
    {
        son[k] = -1;
        dep[k] = dep[fa[k]] + 1;
        siz[k] = 1;
        int d = head[k];
        while (d)
        {
            if (a[d].v != fa[k])
            {
                fa[a[d].v] = k;
                dfs1(a[d].v);
                if (son[k] == -1 || siz[son[k]] < siz[a[d].v])
                    son[k] = a[d].v;
                siz[k] += siz[a[d].v];
            }
            d = a[d].next;
        }
        return;
    }
    void dfs2(int k, int topf)
    {
        top[k] = topf;
        int d = head[k];
        if (son[k] != -1)
            dfs2(son[k], topf);
        d = head[k];
        while (d)
        {
            if (a[d].v != fa[k] && a[d].v != son[k])
                dfs2(a[d].v, a[d].v);
            d = a[d].next;
        }
        return;
    }
    void dfs3(int k)
    {
        in[k] = ++tot;
        if (son[k] != -1)
            dfs3(son[k]);
        int d = head[k];
        while (d)
        {
            if (a[d].v != fa[k] && a[d].v != son[k])
                dfs3(a[d].v);
            d = a[d].next;
        }
        out[k] = ++tot;
        return;
    }
    int lca(int x, int y)
    {
        while (top[x] != top[y])
        {
            if (dep[top[x]] < dep[top[y]])
                swap(x, y);
            x = fa[top[x]];
        }
        if (dep[x] < dep[y])
            return x;
        else
            return y;
    }
} tr1, tr2;
int lowbit(int x)
{
    return x & -x;
}
void modify(int x, int val)
{
    while (x <= tot)
    {
        c[x] += val;
        x += lowbit(x);
    }
    return;
}
int query(int x)
{
    int y = 0;
    while (x >= 1)
    {
        y += c[x];
        x -= lowbit(x);
    }
    return y;
}
void solve(int k)
{
    int lca = tr1.lca(k, tr2.fa[k]);
    int pre;
    if (k > 1)
        pre = query(in[k]) + query(in[tr2.fa[k]]) - 2 * query(in[lca]);
    int d = tr2.head[k];
    while (d)
    {
        if (tr2.a[d].v != tr2.fa[k])
            solve(tr2.a[d].v);
        d = tr2.a[d].next;
    }
    for (int i = 0; i < vec[k].size(); i++)
    {
        int x = vec[k][i];
        if (x > 0)
        {
            modify(in[x], 1);
            modify(out[x], -1);
        }
        else
        {
            modify(in[-x], -2);
            modify(out[-x], 2);
        }
    }
    if (k > 1)
        ans[k] = query(in[k]) + query(in[tr2.fa[k]]) - 2 * query(in[lca]) - pre;
    return;
}
int main()
{
    int size = 128 << 20;
    //__asm__("movl %0, %%esp\n" ::"r"((char *)malloc(size) + size)); //调试用这个
     __asm__("movq %0,%%rsp\n" ::"r"((char *)malloc(size) + size)); //提交用这个
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        tr2.ins(x, y);
    }
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        tr1.ins(x, y);
    }
    tr1.dfs1(1);
    tr1.dfs2(1, 1);
    tr1.dfs3(1);
    tr2.dfs1(1);
    tr2.dfs2(1, 1);
    for (int i = 1; i < 2 * n - 1; i += 2)
    {
        int x = tr1.a[i].v, y = tr1.a[i + 1].v, lca = tr2.lca(x, y);
        if (tr1.dep[x] < tr1.dep[y])
            swap(x, y);
        vec[x].push_back(x);
        vec[y].push_back(x);
        vec[lca].push_back(-x);
    }
    solve(1);
    for (int i = 1; i < n * 2 - 1; i += 2)
    {
        int x = tr2.a[i].v, y = tr2.a[i + 1].v;
        if (tr2.dep[x] < tr2.dep[y])
            swap(x, y);
        printf("%d ", ans[x]);
    }
    exit(0);
}

T3：WOJ4773

看一眼数据范围可以推算出复杂度大约为log，想了想又不太可能用数据结构，因此考场直接鸽了这道题。

考后一看题解：显然重儿子是个十分重要的条件。

首先把每个点到重儿子的边单独提出来，会形成一棵树。倍增预处理t[i,j],s[i,j]，分别表示从i出发沿着树边走2^j步到达t[i,j]，字典序在i的子图中为第s[i,j]大。同时也要预先处理儿子的siz的前缀和（方便后面二分）。

设当前位于i号点，要求第k大的边，如果任意s[i,j]不满足s[i,j]+siz[t[i,j]]≥k且s[i,j]≤k，则第k小路径的终点必然不从最大的儿子进入，我们此时二分找出k在哪个儿子之下，由于这个儿子的siz小等于重儿子的siz，因此跳入这个儿子后，i的siz至少小了一半。否则通过倍增数组跳入最大儿子中，此时k减小s[i,j]。

显然我们会轮流在树上和不在树上轮流跳，两种走法的复杂度都是logn的，因此可以看出算法的复杂度是O(nlog^2n) 的。

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define inf 0x3f3f3f3f3f3f3f3fLL
using namespace std;
int n, m, qq, out[100005], v[100005][32];
long long siz[100005], s[100005][32];
queue<int> q;
vector<long long> sum[100005];
vector<int> son[100005], fa[100005];
int query(int k, int d)
{
    if (!d)
        return k;
    for (int i = 31; i >= 0; --i)
        if (v[k][i] && s[k][i] <= d && siz[v[k][i]] + s[k][i] >= d)
            return query(v[k][i], d - s[k][i]);
    int p = (--lower_bound(sum[k].begin(), sum[k].end(), d)) - sum[k].begin();
    if (p != -1)
        d -= sum[k][p];
    return query(son[k][p + 1], d - 1);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        ++out[x];
        son[x].push_back(y);
        fa[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
        if (!out[i])
            q.push(i);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int d = 0; d < son[u].size(); ++d)
        {
            siz[u] += (siz[son[u][d]] + 1);
            siz[u] = min(siz[u], inf);
            sum[u].push_back(siz[u]);
        }
        if (son[u].size())
        {
            int p = 0;
            for (int d = 1; d < son[u].size(); ++d)
                if (siz[son[u][d]] > siz[son[u][p]])
                    p = d;
            s[u][0] = 1;
            v[u][0] = son[u][p];
            for (int d = 0; d < p; d++)
            {
                s[u][0] += siz[son[u][d]] + 1;
                s[u][0] = min(s[u][0], inf);
            }
            for (int i = 1; i < 31; i++)
            {
                v[u][i] = v[v[u][i - 1]][i - 1];
                if (!v[u][i])
                    break;
                s[u][i] = s[u][i - 1] + s[v[u][i - 1]][i - 1];
                s[u][i] = min(s[u][i], inf);
            }
        }
        for (int d = 0; d < fa[u].size(); ++d)
        {
            int v = fa[u][d];
            --out[v];
            if (!out[v])
                q.push(v);
        }
    }
    scanf("%d", &qq);
    for (int i = 1; i <= qq; i++)
    {
        int ss, k;
        scanf("%d%d", &ss, &k);
        if (siz[ss] < k)
            puts("-1");
        else
            printf("%d\n", query(ss, k));
    }
}

这套题简直毒瘤，照着std改都差点肝不动。

搜索此博客

EarringYYR

20191026测试总结

评论

发表评论

此博客中的热门博文

LOJ6070 【2017 山东一轮集训 Day4」基因】题解

二项式反演

五边形数定理