AtCoder Beginner Contest 244 D~F 题解_f - shortest good path

D - Swap Hats

题目大意

有$3$个Takahashi，他们帽子的颜色分别为$S_1,S_2,S_3$。
我们现在想通过正好$10^{18}$次操作，使得$S_i=T_i$。
每次操作如下：

• 选择$(i,j)$，交换$S_i$和$S_j$。

试问能否达成目标？

输入格式

$S_1{S}_2{S}_3$
$T_1{T}_2{T}_3$

输出格式

如果能达成目标，输出Yes；否则，输出No。

样例

样例输入

R G B
R G B
1
2

样例输出

Yes
1

分析

本题情况不多，可以手动枚举所有可能的情况，最终发现所有$S_i=T_i$或者所有$S_i\ne T_i$时输出Yes，否则输出No。

代码

#include <cstdio>
using namespace std;

int main()
{
	char a, b, c, d, e, f;
	scanf("%c %c %c %c %c %c", &a, &b, &c, &d, &e, &f);
	puts(((a == d) + (b == e) + (c == f)) == 1? "No": "Yes");
	return 0;
}
1
2
3
4
5
6
7
8
9
10

---

E - King Bombee

题目大意

给定由$N$个点、$M$条边组成的简单无向图。第$i$条边连接顶点$U_i$和$V_i$。
求图中从$S$到$T$、长度为$K$且经过顶点$X$偶数次的路径的数量，对$998244353$取模。

$2\le N\le 2000$
$1\le M\le 2000$
$1\le K\le 2000$
$1\le S,T,X\le N$
$X\ne S,X\ne T$
$1\le U_i<V_i\le N$
$(U_i,V_i)\ne (U_j,V_j)$（$i\ne j$）

输入格式

$NMKSTX$
$U_1{V}_1$
$⋮$
$U_N{V}_N$

输出格式

输出图中从$S$到$T$、长度为$K$且经过顶点$X$偶数次的路径的数量，对$998244353$取模。

样例

样例输入1

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

样例输出1

4
1

有$4$条符合条件的路径：

• $1\to 2\to 1\to 2\to 3$
• $1\to 2\to 3\to 2\to 3$
• $1\to 4\to 1\to 4\to 3$
• $1\to 4\to 3\to 4\to 3$

注意$X=2$必须出现偶数次。

样例输入2

6 5 10 1 2 3
2 3
2 4
4 6
3 6
1 5
1
2
3
4
5
6

样例输出2

0
1

这张图没有连通。

样例输入3

10 15 20 4 4 6
2 6
2 7
5 7
4 5
2 4
3 7
1 7
1 4
2 9
5 10
1 3
7 8
7 9
1 6
1 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

样例输出3

952504739
1

注意对$998244353$取模。

分析

我们先不考虑$X$的限制条件，则可以令$\mathrm{dp}(i,j)=$第$i$步走到$j$的可能数，则因为点$j$可以从$G_j$中的任意一点走过来（$G$为邻接表存储），所以我们得到
$$\mathrm{dp}(i,j)=\sum _{k=1}^{|G_j|}\mathrm{dp}(i-1,{G_j}_k)$$
再考虑$X$必须是偶数的情况，令$\mathrm{dp}(i,j,k)=$第$i$步走到$j$且$X$的出现次数除以$2$的余数为$k$的情况，则每次额外判断${G_j}_k$是否等于$X$即可。
$\mathrm{DP}$状态转移方程详见代码。

代码

注意：代码中运用了滚动表的优化，可以节省空间，当然也可以使用普通写法。

#include <cstdio>
#include <vector>
#define maxn 2005
#define MOD 998244353
using namespace std;

inline void mod(int& x)
{
	if(x >= MOD) x -= MOD;
}

vector<int> G[maxn];
int dp[2][maxn][2];

int main()
{
	int n, m, k, s, t, x;
	scanf("%d%d%d%d%d%d", &n, &m, &k, &s, &t, &x);
	x --;
	while(m--)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		G[--u].push_back(--v);
		G[v].push_back(u);
	}
	dp[0][--s][0] = 1;
	for(int i=1; i<=k; i++)
	{
		bool c = i & 1, p = i & 1 ^ 1;
		for(int v=0; v<n; v++)
		{
			dp[c][v][0] = dp[c][v][1] = 0;
			for(int u: G[v])
				mod(dp[c][v][0] += dp[p][u][u == x]),
				mod(dp[c][v][1] += dp[p][u][u != x]);
		}
	}
	printf("%d\n", dp[k & 1][--t][0]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

---

F - Shortest Good Path

分析

令$\mathrm{dis}[S][j]=$于点$j$结束的good path with respest to S的最短长度，跑一遍$\text{BFS}$即可。具体实现时可将$S$按位压缩为二进制，加快运算速度。

代码

#include <cstdio>
#include <queue>
#define INF 2147483647
#define maxn 17
using namespace std;

using ULL = unsigned long long;

int dis[1 << maxn][maxn];
vector<int> G[maxn];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	while(m--)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		G[--u].push_back(--v);
		G[v].push_back(u);
	}
	queue<ULL> q;
	for(int i=0; i<n; i++)
		dis[1 << i][i] = 1, q.push(1ULL<<i+32^i);
	while(!q.empty())
	{
		ULL pkg = q.front(); q.pop();
		int st = pkg >> 32ULL, v = pkg & 0x7fffffff;
		int nd = dis[st][v] + 1;
		for(int u: G[v])
		{
			int nst = st ^ (1 << u);
			if(dis[nst][u] == 0)
			{
				dis[nst][u] = nd;
				q.push(ULL(nst) << 32ULL ^ u);
			}
		}
	}
	long long ans = 0LL;
	for(int i=1, lim=1<<n; i<lim; i++)
	{
		int cur = INF;
		for(int j=0; j<n; j++)
			if(dis[i][j] > 0 && dis[i][j] < cur)
				cur = dis[i][j];
		ans += cur;
	}
	printf("%lld\n", ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52