跳转至

暑假集训系列题解(五)

暑假集训系列题解(五)

题目1

题目链接

鸽子

题目描述

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

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

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

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

输入

本题有多组测试数据。

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

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

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

满足 1≤T≤5,1≤n≤105,0≤m≤105,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​。

题解

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

image-20210801095133305

代码
#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

题目

image-20210801101820987

题解

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

代码
#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);
    }
}