暑假集训系列题解（五）

暑假集训系列题解（五）

题目1

题目链接

鸽子

题目描述

你的机房共有 n 台电脑，但是第 k 台电脑坏了。

你的老师给你 m 次要求，每次要求你将第 ui 和 vi 台电脑交换，这样坏的电脑就可能会被交换到一个新的位置。

但由于你希望进行暗箱操作，你可以拒绝执行其中的若干条要求，使得坏的电脑最终交换到 j 号位置。

由于骗过老师很累，请对于 j=1...n 求出最少可能的不执行要求条数，使得坏的电脑在第 j 个位置。

输入

本题有多组测试数据。

第一行一个数 T 表示一共有 T 组数据。对于每一组数据：

第一行三个整数 n,m,k ，表示电脑个数，总操作次数和坏电脑的初始位置。

下面 m 行，每行两个正整数 ui , vi ，表示这次操作选择的两个位置。

满足 1≤T≤5，1≤n≤10^{5，0≤m≤10}5，1≤k≤n。

输出

对每组数据，输出共一行 n 个整数，第 i 个整数表示使坏电脑最终停留在该位置所需的最少暗箱操作次数。

若最终坏电脑不可能停留在该位置，则输出 −1。

样例输入

1
5 5 1
3 5
2 1
4 1
3 1
3 1

样例输出

2 0 3 1 -1

题解

动态规划，当要求转移u和v时：

dp[i][u]=min(dp[i-1][u]+1,dp[i-1][v]);
dp[i][v]=min(dp[i-1][v]+1,dp[i-1][u]);

代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f
using namespace std;
typedef long long ll;
ll dp[200500] = {0};
int main()
{
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    ll t;
    scanf("%lld", &t);
    while (t--)
    {
        ll n, m, k;
        scanf("%lld%lld%lld", &n, &m, &k);
        for (ll i = 1; i <= n; i++)
            dp[i] = inf;
        dp[k] = 0;
        ll u, v;
        for (ll i = 1; i <= m; i++)
        {
            scanf("%lld%lld", &u, &v);
            ll tmpv = min(dp[v] + 1, dp[u]);
            ll tmpu = min(dp[u] + 1, dp[v]);
            dp[v] = tmpv;
            dp[u] = tmpu;
        }
        for (ll i = 1; i <= n; i++)
        {
            if (dp[i] == inf)
            {
                if (i != n)
                    printf("-1 ");
                else
                    printf("-1");
            }
            else
            {
                if (i != n)
                    printf("%lld ", dp[i]);
                else
                    printf("%lld", dp[i]);
            }
        }
        printf("\n");
    }
}

题目2

题目链接

迷失

题目描述

小 T 迷失在了一个有 n 个点的群岛上。

初始时他在 1 号岛，他要通过架在岛间的 m 座双向桥，在正好过 k 座桥时达到 n 号岛的大门。

这些桥中有若干座附魔桥。当小 T 经过一座附魔桥时，如果他身上没有附魔标记则被标记，如果他身上已有附魔标记则标记消失。

大门只会在他身上有附魔标记时才会开启，只有这样他才能逃离。

小 T 迷失在了群岛之间，他每次会等概率随机挑选一座与他所在岛屿相连的桥走。小 T 向你询问他能逃离的概率。

保证图无自环无重边。

输入

第一行一个数 T 表示一共有 T 组数据。对于每一组数据：

第一行三个正整数 n，m，k。

此后 m 行，每行三个数 ui，vi，wi ，表示一座从 ui 到 vi 的桥。若 wi=1 则该桥是附魔桥，否则（wi=0）是普通桥。

保证无自环无重边，T≤10，1≤ui,vi≤n，wi 为 0 到 1 的整数，满足 2≤n≤100，1≤m≤n×(n−1)/2，1≤k≤10^6。

输出

输出一共 T 行。对于每一组数据，输出一行一个正整数：他能逃离的概率对 998244353 的模。

样例输入

2
4 4 2
1 2 1
2 4 0
1 3 0
3 4 0
6 7 2
1 2 0
1 3 1
1 4 1
2 5 0
3 5 0
3 6 0
4 6 0

样例输出

748683265
610038216

提示

第一组数据 从 $1$ 走到 $n$ 并且经过一条附魔边的概率为 $1/4$ ，对 $998244353$ 取模后为 $748683265$。 第二组数据 概率为 $5/18$ ，对 $998244353$ 取模后为 $610038216$​。

题解

矩阵快速幂，通过构造邻接矩阵做乘法幂运算的方式计算出最终的概率。

代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll ksm(ll a, ll b)
{
    ll ans1 = 1, ans2 = a;
    while (b != 0)
    {
        if (b % 2)
            ans1 = (ans2 * ans1) % mod;
        ans2 = (ans2 * ans2) % mod;
        b /= 2;
    }
    return ans1;
}
ll a[400][400] = {0};
ll ans1[400][400] = {0};
ll ans2[400][400] = {0};
vector<pair<int, int>> v[400];
int n, m, k;
void cf(ll a[400][400], ll b[400][400])
{
    ll c[400][400] = {0};
    for (ll i = 1; i <= 2 * n; i++)
    {
        for (ll j = 1; j <= 2 * n; j++)
        {
            for (ll k = 1; k <= 2 * n; k++)
            {
                c[i][j] += a[i][k] * b[k][j];
                c[i][j] %= mod;
            }
        }
    }
    for (ll i = 1; i <= 2 * n; i++)
    {
        for (ll j = 1; j <= 2 * n; j++)
        {
            a[i][j] = c[i][j];
            a[i][j] %= mod;
        }
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d %d %d", &n, &m, &k);
        memset(a, 0, sizeof(a));
        for (int i = 1; i <= n; i++)
            v[i].clear();
        int from, to, val;
        for (int i = 1; i <= m; i++)
        {
            scanf("%d %d %d", &from, &to, &val);
            v[from].push_back({to, val});
            v[to].push_back({from, val});
        }
        for (int i = 1; i <= n; i++)
        {
            ll tmp = ksm((ll)v[i].size(), mod - 2);
            for (int k = 0; k < v[i].size(); k++)
            {
                pair<int, int> j = v[i][k];
                if (j.second == 0)
                {
                    a[i * 2 - 1][j.first * 2 - 1] = tmp;
                    a[i * 2][j.first * 2] = tmp;
                }
                else
                {
                    a[i * 2 - 1][j.first * 2] = tmp;
                    a[i * 2][j.first * 2 - 1] = tmp;
                }
            }
        }

        for (ll i = 1; i <= 2 * n; i++)
        {
            for (ll j = 1; j <= 2 * n; j++)
            {
                ans1[i][j] = a[i][j];
                if (i == j)
                    ans2[i][j] = 1;
                else
                    ans2[i][j] = 0;
            }
        }

        while (k != 0)
        {
            if (k % 2)
                cf(ans2, ans1);
            cf(ans1, ans1);
            k /= 2;
        }
        printf("%lld\n", ans2[1][2 * n]);
    }
}

题目3

题目链接

https://ac.nowcoder.com/acm/contest/11256/K

题目

题解

维护单调子序列，找到符合条件的区间。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[100500] = {0};
int main()
{
    ll n, m;
    scanf("%lld%lld", &n, &m);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    while (m--)
    {
        ll k;
        scanf("%lld", &k);
        deque<ll> que1, que2; ///维护递增序列和递减序列
        ll ans = 0, last = 0;
        for (ll i = 1; i <= n; i++)
        {
            while (!que1.empty() && a[que1.back()] < a[i]) ///递减
                que1.pop_back();
            que1.push_back(i);

            while (!que2.empty() && a[que2.back()] > a[i]) ///递增
                que2.pop_back();
            que2.push_back(i);

            while (!que1.empty() && !que2.empty() && a[que1.front()] - a[que2.front()] > k)
            {
                if (que1.front() < que2.front())
                    ans += (n - que2.front() + 1) * (que1.front() - last), last = que1.front(), que1.pop_front();
                else
                    ans += (n - que1.front() + 1) * (que2.front() - last), last = que2.front(), que2.pop_front();
            }
        }
        printf("%lld\n", ans);
    }
}