暑假集训系列题解（五）
题目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$。
题解
矩阵快速幂，通过构造邻接矩阵做乘法幂运算的方式计算出最终的概率。
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);
}
}