ABC193 题解

[toc]

AC代码

A – Discount

B – Play Snuke

C – Unexpressed

询问 $N$ 以内的自然数中有多少个数字不可以被表示为 $a^b$ 的形式？

$N\leq 10^{10}$ 。

在 $O(\sqrt{N})$ 范围内暴力枚举 $a$ ，然后埃氏筛即可，用set去重。

D – Poker

一副牌 $9K$ 张（有 $K$ 个 $1,2,\ldots,9$），随机打乱后，Takahashi和Aoki每个人抽 $5$ 张，其中 $4$ 张已经翻开，最后一张未翻开。牌型的权值计算公式为：$\sum_{i=1}^9 i \times 10^{c_i}$ ，$c_i$ 指的是同一数字的卡牌数量，求Takahashi获胜的概率（牌型权值更高者获胜）。

$2\leq K\leq 10^5$ 。

由于牌的类型只有 $9$ 种，因此总共最多 $9\times 9$ 种情况，直接暴力计算每种情况下Takahashi获胜的概率并累加即可。

E – Oversleeping

求满足下列方程组的最小解 $t$ ：
$\begin{cases} t\equiv i\pmod{(2X+2Y)} &(i\in[X,X+Y)) \\ t\equiv j\pmod{(P+Q)} & (j\in[P,P+Q)) \end{cases}$
$1\leq X,P\leq 10^9, 1\leq Y,Q\leq 500$ 。

由于 $Y,Q$ 范围很小直接暴力枚举 $i,j$ 然后EXCRT解同余方程组。

F – Zebraness

给定一个 $N\times N$ 的网格图，每个单元中含有 B, W, ? 三种字符之一，其中 ? 既可以是 B 也可以是 W ，询问该网格图中最多有几对相邻的（四联通）不同字符对？

$N\leq 100$ 。

看了官方题解涨姿势了，如果知道这是Project selection problem的一种变形说不定能想到这是一个网络流的题？

第一次做这类题，先在网上找了一道入门题练手，也对这类题型有了一定的理解。

先进行一个预处理：我们要求最大的相邻不同字符对数，不妨转化为求最小的相邻相同字符对数，这有利于我们使用最小割来解决问题。但是PSP(Project selection problem)的核心思路需要利用异色边的特性，因此我们将网格中的奇数点（$(i,j)$ 满足 $(i+j)\pmod{2}=1$ 时称为奇数点）翻转，即 B 翻转为 W ，W 翻转为 B ，? 不变。这一变换利用了二分图的特性，使得我们求解的目标重新被改写为求最小的相邻不同字符对数。接下来就是本题最关键的建图方式：

建立超级源点 $S$ 和超级汇点 $T$ ；
对于 $S$ 到每个黑色点（本题中字符为B的点）建立双向边，权值为 $INF$；
对于每个白色点（本题中字符为W的点）到 $T$ 建立双向边，权值为 $INF$；
任意两个相邻点都建立双向边，权值为 $1$；
建好的图中的最小割就是所求答案（最小的相邻不同字符对数）。

如果我们按照最小割将图切开并且去掉超级源点、汇点，那么所有连通块都只会剩下同色点和 ? 。这是因为如果存在 $B,W$ 之间的边，那就必定存在一条 $S\rightarrow B\rightarrow W\rightarrow T$ 或者 $T\rightarrow B\rightarrow W\rightarrow S$ 的通路（超级源点和汇点的连边因为边权为 $INF$ ，所以不会被切断），于是我们可以把 ? 直接染色为连通块的主体颜色。

好像第 $2,3$ 步的建边不需要建双向边就行了（官方题解），但是根据我的想法是需要的，可能两者等价。

~~说不定以后可以搞个PSP的最小割总结~~。