526互联

2023冲刺国赛模拟 5.0

发布时间 2023-05-17 16:26:34作者: KafuuChinocpp

T1 今晚九点

考虑建立最短路模型，设点 \((x,y)\) 在方向 \(v\) 上可以走到的最远的点为 \((p_1,q_1)\) ，可以走到最近的点为 \((p_2,q_2)\) ，只需要建立从 \((x,y)\to (p_1,q_1)\) 的长度为 \(1\) 的边和从 \((x,y)\to (p_2,q_2)\) 的长度为 \(2\) 的边即可。

证明只需要考虑一个原先停留过的点不会被当做障碍即可。

code 
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <utility>
#include <cstring>
using namespace std;
const int max1 = 1000;
const int inf = 0x3f3f3f3f;

int n, m;
char mp[max1 + 5][max1 + 5];
vector < pair <int, int> > vec[max1 * max1 + 5];
pair <int, int> S, T, pos[max1 + 5][max1 + 5][4];
int dis[max1 + 5][max1 + 5];
bool vis[max1 + 5][max1 + 5];

int main ()
{
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for ( int i = 1; i <= n; i ++ )
        scanf("%s", mp[i] + 1);
    scanf("%d%d%d%d", &S.first, &S.second, &T.first, &T.second);

    for ( int i = 1; i <= n; i ++ )
        for ( int j = 1; j <= m; j ++ )
            if ( mp[i][j] == '#' )
                pos[i][j][0] = pos[i][j][1] = pos[i][j][2] = pos[i][j][3] = make_pair(i, j);
    
    for ( int i = 1; i <= n; i ++ )
        for ( int j = 1; j <= m; j ++ )
            if ( mp[i][j] == '.' )
                pos[i][j][0] = pos[i - 1][j][0];
    
    for ( int i = n; i >= 1; i -- )
        for ( int j = m; j >= 1; j -- )
            if ( mp[i][j] == '.' )
                pos[i][j][1] = pos[i + 1][j][1];
    
    for ( int i = 1; i <= n; i ++ )
        for ( int j = 1; j <= m; j ++ )
            if ( mp[i][j] == '.' )
                pos[i][j][2] = pos[i][j - 1][2];
    
    for ( int i = n; i >= 1; i -- )
        for ( int j = m; j >= 1; j -- )
            if ( mp[i][j] == '.' )
                pos[i][j][3] = pos[i][j + 1][3];

    for ( int i = 1; i <= n; i ++ )
    {
        memset(dis[i] + 1, 0x3f, sizeof(int) * m);
        memset(vis[i] + 1, 0, sizeof(bool) * m);
    }

    for ( int i = 0; i <= n * m; i ++ )
        vec[i].clear();

    dis[S.first][S.second] = 0; vec[0].push_back(S);
    for ( int i = 0; i <= n * m; i ++ )
    {
        for ( auto now : vec[i] )
        {
            if ( vis[now.first][now.second] )
                continue;
            
            vis[now.first][now.second] = true;
            
            if ( mp[now.first - 1][now.second] == '.' )
            {
                if ( dis[now.first - 1][now.second] > i + 2 )
                {
                    dis[now.first - 1][now.second] = i + 2;
                    vec[i + 2].push_back(make_pair(now.first - 1, now.second));
                }
            }

            if ( mp[now.first + 1][now.second] == '.' )
            {
                if ( dis[now.first + 1][now.second] > i + 2 )
                {
                    dis[now.first + 1][now.second] = i + 2;
                    vec[i + 2].push_back(make_pair(now.first + 1, now.second));
                }
            }

            if ( mp[now.first][now.second - 1] == '.' )
            {
                if ( dis[now.first][now.second - 1] > i + 2 )
                {
                    dis[now.first][now.second - 1] = i + 2;
                    vec[i + 2].push_back(make_pair(now.first, now.second - 1));
                }
            }

            if ( mp[now.first][now.second + 1] == '.' )
            {
                if ( dis[now.first][now.second + 1] > i + 2 )
                {
                    dis[now.first][now.second + 1] = i + 2;
                    vec[i + 2].push_back(make_pair(now.first, now.second + 1));
                }
            }

            pair <int, int> v;
            v = pos[now.first][now.second][0];
            ++v.first;
            if ( dis[v.first][v.second] > i + 1 )
            {
                dis[v.first][v.second] = i + 1;
                vec[i + 1].push_back(v);
            }

            v = pos[now.first][now.second][1];
            --v.first;
            if ( dis[v.first][v.second] > i + 1 )
            {
                dis[v.first][v.second] = i + 1;
                vec[i + 1].push_back(v);
            }

            v = pos[now.first][now.second][2];
            ++v.second;
            if ( dis[v.first][v.second] > i + 1 )
            {
                dis[v.first][v.second] = i + 1;
                vec[i + 1].push_back(v);
            }

            v = pos[now.first][now.second][3];
            --v.second;
            if ( dis[v.first][v.second] > i + 1 )
            {
                dis[v.first][v.second] = i + 1;
                vec[i + 1].push_back(v);
            }
        }
    }

    if ( dis[T.first][T.second] == inf )
        printf("-1\n");
    else
        printf("%d\n", dis[T.first][T.second]);

    return 0;
}

T2 嘉然唱歌

比较显然的一种思路是容斥，考虑枚举边集 \(S\) 表示钦定这些边连接两端点数值相同，其他边任意时的方案数，显然答案为 \(\sum_S(-1)^{|S|}f(S)\) ，容易发现 \(f(S)=\prod_T\min_{i\in T}(b_i)\) ，其中 \(T\) 表示 \(S\) 方案下的每个连通块。

考虑使用 dp 优化上述计算，设 \(f_{u,i}\) 表示当前以 \(u\) 为根的子树， \(u\) 节点所在连通块内最小值为 \(i\) 时的贡献和，由于 \(u\) 所在连通块最小值尚未确定，因此 \(u\) 所在连通块的贡献不被统计到 \(f_{u,i}\) 中。

考虑转移，假设当前合并上来的儿子为 \(v\) ，我们将 \(f_u\) 复制存储到 \(tmp\) 中，考虑 \(u\to v\) 的边是否位于 \(u\) 所在连通块内：

如果 \(u\to v\) 的边不在 \(u\) 所在连通块内，设 \(s=\sum f_{v,i}\times i\) ，显然有转移

\[tmp_i\times s\to f_{u,i} \]

否则有转移

\[(-1)\times tmp_i\times f_{v,j}\to f_{u,\min(i,j)} \]

考虑用启发式合并优化上述 dp ，简单推式子可以发现重儿子的信息很容易继承，考虑合并轻儿子的信息，为了方便使用数据结构，我们将 dp 转移式写成如下形式：

\[f_{u,i}=tmp_i\times s-tmp_i\times\sum_{j\ge i}f_{v,j}-f_{v,i}\times\sum_{j>i}tmp_j \]

由于我们在做启发式合并，因此 \(f_v\) 中的每一个元素都可以枚举，容易发现上述式子就是简单的区间乘和单调修改，直接使用动态开点线段树维护即可。

code 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int max1 = 500000;
const int mod = 998244353;

int n, lim[max1 + 5], save[max1 + 5], len;
vector <int> edge[max1 + 5];
int siz[max1 + 5], son[max1 + 5];
int num[max1 + 5], f[max1 + 5], g[max1 + 5], cnt;

struct Segment_Tree
{
    #define lson(now) tree[now].son[0]
    #define rson(now) tree[now].son[1]

    struct Struct_Segment_Tree
    {
        int son[2], sum1, sum2, tag;
    }tree[max1 * 40 + 5];
    int root[max1 + 5], total;

    void Clear ()
    {
        lson(0) = rson(0) = tree[0].sum1 = tree[0].sum2 = tree[0].tag = total = 0;
        return;
    }

    void Push_Up ( int now )
    {
        tree[now].sum1 = tree[lson(now)].sum1 + tree[rson(now)].sum1;
        tree[now].sum2 = tree[lson(now)].sum2 + tree[rson(now)].sum2;
        if ( tree[now].sum1 >= mod )
            tree[now].sum1 -= mod;
        if ( tree[now].sum2 >= mod )
            tree[now].sum2 -= mod;
        return;
    }

    void Update ( int now, int x )
    {
        tree[now].sum1 = 1LL * tree[now].sum1 * x % mod;
        tree[now].sum2 = 1LL * tree[now].sum2 * x % mod;
        tree[now].tag = 1LL * tree[now].tag * x % mod;
        return;
    }

    void Push_Down ( int now )
    {
        if ( tree[now].tag != 1 )
        {
            if ( lson(now) )
                Update(lson(now), tree[now].tag);
            if ( rson(now) )
                Update(rson(now), tree[now].tag);
            tree[now].tag = 1;
        }
        return;
    }

    void Insert ( int &now, int L, int R, int pos, int x )
    {
        if ( !now )
        {
            now = ++total;
            lson(now) = rson(now) = tree[now].sum1 = tree[now].sum2 = 0;
            tree[now].tag = 1;
        }
        if ( L == R )
        {
            tree[now].sum1 = ( tree[now].sum1 + x ) % mod;
            tree[now].sum2 = ( tree[now].sum2 + 1LL * x * save[L] ) % mod;
            return;
        }

        Push_Down(now);
        int mid = L + R >> 1;
        if ( pos <= mid )
            Insert(lson(now), L, mid, pos, x);
        else
            Insert(rson(now), mid + 1, R, pos, x);
        Push_Up(now);
        return;
    }

    void Insert ( int id, int pos, int x )
    {
        return Insert(root[id], 1, len, pos, x);
    }

    void Delete ( int &now, int L, int R, int ql, int qr )
    {
        if ( !now )
            return;

        if ( L >= ql && R <= qr )
            { now = 0; return; }
        Push_Down(now);

        int mid = L + R >> 1;
        if ( ql <= mid )
            Delete(lson(now), L, mid, ql, qr);
        if ( qr > mid )
            Delete(rson(now), mid + 1, R, ql, qr);
        Push_Up(now);
        return;
    }

    void Delete ( int id, int ql, int qr )
    {
        return Delete(root[id], 1, len, ql, qr);
    }

    void Update ( int now, int L, int R, int ql, int qr, int x )
    {
        if ( !now )
            return;
        
        if ( L >= ql && R <= qr )
            return Update(now, x);

        Push_Down(now);
        int mid = L + R >> 1;
        if ( ql <= mid )
            Update(lson(now), L, mid, ql, qr, x);
        if ( qr > mid )
            Update(rson(now), mid + 1, R, ql, qr, x);
        Push_Up(now);
        return;
    }

    void Update ( int id, int ql, int qr, int x )
    {
        return Update(root[id], 1, len, ql, qr, x);
    }

    int Query_Sum1 ( int now, int L, int R, int ql, int qr )
    {
        if ( !now )
            return 0;
        
        if ( L >= ql && R <= qr )
            return tree[now].sum1;
        
        Push_Down(now);
        int mid = L + R >> 1, res = 0;
        if ( ql <= mid )
            res += Query_Sum1(lson(now), L, mid, ql, qr);
        if ( qr > mid )
            res += Query_Sum1(rson(now), mid + 1, R, ql, qr);
        
        if ( res >= mod )
            res -= mod;
        
        return res;
    }

    int Query_Sum1 ( int id, int ql, int qr )
    {
        return Query_Sum1(root[id], 1, len, ql, qr);
    }

    int Query_Sum2 ( int now, int L, int R, int ql, int qr )
    {
        if ( !now )
            return 0;
        
        if ( L >= ql && R <= qr )
            return tree[now].sum2;
        
        Push_Down(now);
        int mid = L + R >> 1, res = 0;
        
        if ( ql <= mid )
            res += Query_Sum2(lson(now), L, mid, ql, qr);
        if ( qr > mid )
            res += Query_Sum2(rson(now), mid + 1, R, ql, qr);
        
        if ( res >= mod )
            res -= mod;
        
        return res;
    }

    int Query_Sum2 ( int id, int ql, int qr )
    {
        return Query_Sum2(root[id], 1, len, ql, qr);
    }

    void Dfs ( int now, int L, int R )
    {
        if ( !now )
            return;
        
        if ( L == R )
        {
            num[++cnt] = L;
            f[cnt] = tree[now].sum1;
            return;
        }

        Push_Down(now);
        int mid = L + R >> 1;
        Dfs(lson(now), L, mid);
        Dfs(rson(now), mid + 1, R);
        return;
    }

    void Dfs ( int id )
    {
        cnt = 0;
        return Dfs(root[id], 1, len);
    }

    int Merge ( int x, int y, int L, int R )
    {
        if ( !x || !y )
            return x | y;
        if ( L == R )
        {
            tree[x].sum1 += tree[y].sum1;
            tree[x].sum2 += tree[y].sum2;
            if ( tree[x].sum1 >= mod )
                tree[x].sum1 -= mod;
            if ( tree[x].sum2 >= mod )
                tree[x].sum2 -= mod;
            return x;
        }

        Push_Down(x), Push_Down(y);
        int mid = L + R >> 1;

        lson(x) = Merge(lson(x), lson(y), L, mid);
        rson(x) = Merge(rson(x), rson(y), mid + 1, R);

        Push_Up(x);
        return x;
    }
    
    void Merge ( int x, int y )
    {
        root[x] = Merge(root[x], root[y], 1, len);
        return;
    }
}Tree;

void Dfs ( int now, int fa )
{
    siz[now] = 1, son[now] = 0;
    int max_siz = 0;
    for ( auto v : edge[now] )
    {
        if ( v == fa )
            continue;
        
        Dfs(v, now);
        if ( siz[v] > max_siz )
            son[now] = v;
        siz[now] += siz[v];
    }

    if ( son[now] )
    {
        Tree.root[now] = Tree.root[son[now]];

        int new_val = ( Tree.Query_Sum2(son[now], 1, len) - Tree.Query_Sum1(son[now], lim[now], len) + mod ) % mod;
        Tree.Delete(now, lim[now], len);
        if ( lim[now] > 1 )
            Tree.Update(now, 1, lim[now] - 1, mod - 1);
        Tree.Insert(now, lim[now], new_val);
    }
    else
    {
        Tree.root[now] = 0;
        Tree.Insert(now, lim[now], 1);
    }

    for ( auto v : edge[now] )
    {
        if ( v == fa || v == son[now] )
            continue;
        
        Tree.Dfs(v);

        for ( int i = 1; i <= cnt; i ++ )
        {
            if ( num[i] < len )
                g[i] = ( f[i] + 1LL * f[i] * Tree.Query_Sum1(now, num[i] + 1, len) ) % mod;
            else
                g[i] = f[i];
        }

        int pos = len, k = Tree.Query_Sum2(v, 1, len);
        for ( int i = cnt; i >= 1; i -- )
        {
            if ( num[i] < pos )
                Tree.Update(now, num[i] + 1, pos, k);
            pos = num[i];
            k -= f[i];
            if ( k < 0 )
                k += mod;
        }
        Tree.Update(now, 1, pos, k);

        for ( int i = 1; i <= cnt; i ++ )
            Tree.Insert(v, num[i], mod - g[i]);
        Tree.Merge(now, v);
    }
    return;
}

int main ()
{
    freopen("b.in", "r", stdin);
    freopen("b.out", "w", stdout);

    scanf("%d", &n);
    for ( int i = 1; i <= n; i ++ )
        scanf("%d", &lim[i]), save[i] = lim[i];
    sort(save + 1, save + 1 + n);
    len = unique(save + 1, save + 1 + n) - ( save + 1 );
    for ( int i = 1; i <= n; i ++ )
        lim[i] = lower_bound(save + 1, save + 1 + len, lim[i]) - save;
    
    for ( int i = 2, u, v; i <= n; i ++ )
    {
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }

    Tree.Clear();
    
    Dfs(1, 0);

    printf("%d\n", Tree.Query_Sum2(1, 1, len));

    return 0;
}

T3 不见不散

很容易将原问题转化为通过 \(\tfrac{n(n-1)}{2}\) 次两两不同的交换使得原序列有序。

由于存在经典结论，交换序列中任意两个数会使得逆序对个数奇偶性发生变化，因此当原序列逆序对个数与 \(\tfrac{n(n-1)}{2}\) 的奇偶性不同时一定不存在合法方案。

找到序列中任意一个满足 \(A_i\ne i\) 的位置，将 \(i\) 与其他位置按照任意顺序交换并使得最终交换结果为 \(A_i=i\) ，容易发现这转化为一个 \(n-1\) 的子问题。

那么最终序列一定满足 \(A_i=i\) ，由于奇偶性的限制，可以发现序列大小 \(\operatorname{mod}4=0,1\) ，因此考虑 \(4\) 个一组进行消除。

设取出的 \(4\) 个位置为 \(x,y,z,w\) ，剩余位置组成集合 \(S\) ，将 \(x\) 与 \(S\) 内元素一一交换，之后交换 \(x,y\) ，将 \(S\) 集合翻转，将 \(y\) 与 \(S\) 内元素一一交换，容易发现此时 \(x,y\) 均与 \(S\) 集合内元素发生交换，并且 \(S\) 集合内 \(A_i\) 不受影响，最终只造成 \(x,y\) 发生交换，同理 \(z,w\) 做上述交换过程，最后按照顺序交换 \((x,z),(y,w),(x,w),(y,z)\) 就可以转化为规模为 \(n-4\) 的子问题。

code 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int max1 = 1000;

int n, p[max1 + 5], A[max1 + 5], cnt;
bool vis[max1 + 5];
vector <int> S;
vector < pair <int, int> > ans;

void Solve ( int x, int y )
{
    for ( auto i : S )
        swap(A[x], A[i]), ans.push_back(make_pair(x, i));
    swap(A[x], A[y]), ans.push_back(make_pair(x, y));
    reverse(S.begin(), S.end());
    for ( auto i : S )
        swap(A[y], A[i]), ans.push_back(make_pair(y, i));
    return;
}

int main ()
{
    freopen("c.in", "r", stdin);
    freopen("c.out", "w", stdout);

    scanf("%d", &n);
    for ( int i = 1; i <= n; i ++ )
        scanf("%d", &p[i]);
    for ( int i = 1; i <= n; i ++ )
        A[p[i]] = i;
    for ( int i = 1; i <= n; i ++ )
        for ( int j = i + 1; j <= n; j ++ )
            if ( A[i] > A[j] )
                ++cnt;
    
    memset(vis + 1, 0, sizeof(bool) * n);

    if ( ( cnt & 1 ) != ( ( n * ( n - 1 ) >> 1 ) & 1 ) )
        printf("NO\n");
    else
    {
        printf("YES\n");
        ans.clear();
        while ( true )
        {
            int pos = 0;
            for ( int i = 1; i <= n; i ++ )
                if ( !vis[i] && A[i] != i )
                    { pos = i; break; }
            
            if ( !pos )
                break;
            vis[pos] = true;
            
            for ( int i = 1; i <= n; i ++ )
                if ( !vis[i] && A[i] != pos )
                    swap(A[i], A[pos]), ans.push_back(make_pair(i, pos));
            for ( int i = 1; i <= n; i ++ )
            {
                if ( !vis[i] && A[i] == pos )
                {
                    swap(A[i], A[pos]);
                    ans.push_back(make_pair(i, pos));
                    break;
                }
            }
        }

        for ( int i = 1; i <= n; i ++ )
            if ( !vis[i] )
                S.push_back(i);
        
        while ( S.size() > 1 )
        {
            int x, y, z, w;
            x = S.back(), S.pop_back();
            y = S.back(), S.pop_back();
            z = S.back(), S.pop_back();
            w = S.back(), S.pop_back();
            
            Solve(x, y);
            Solve(z, w);
            swap(x, z), ans.push_back(make_pair(x, z));
            swap(y, w), ans.push_back(make_pair(y, w));
            swap(x, w), ans.push_back(make_pair(x, w));
            swap(y, z), ans.push_back(make_pair(y, z));
        }

        for ( auto v : ans )
            printf("%d %d\n", v.first, v.second);
    }

    return 0;
}