A – Darker and Darker
一眼题，直接 BFS 找最长最短路即可。
Continue reading →思博题。考虑最后的路径肯定是多个黑白子路径的拼接，那么路径的代价就是进入黑色子路径的次数，那么我们只需要建图的时候给白色入黑色的边赋 \(1\) 的权即可。
Continue reading →这场代码都好短啊。
傻逼题，随便搞就行了。
// ARC091A.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
int main()
{
scanf("%d%d", &n, &m);
if (n > m)
swap(n, m);
if (n == 1)
{
if (m == 1)
puts("1");
else
printf("%d\n", max(0, m - 2));
return 0;
}
printf("%lld\n", max(0LL, 1LL * (n - 2) * (m - 2)));
return 0;
}
Continue reading → 如果本身就不是回文串，那么答案就是 \(1\)；如果本身是的话，考虑找一个分割点使得左右都不是，那么答案就是 \(2\)；如果还是没找到，那么就是无解了，因为最后串要么就是个单纯串或者是个删完一次之后变成单纯串的东西。
sb 题，不讲。（为什么 B 组会有这么水的题？）
这道题翻译过来就是独立集计数，也是一道 sb 题。
首先，这种计数题肯定都是基于树形 DP 的，所以我们来设状态。起初，我设的状态是：该节点所在的子树的独立集个数为 \(dp[u]\)。后面发现不太对劲：状态转移时，大体可以分为两种进行计数，一种是儿子子树内的乘积（包括空集在内，这样就可以算所有的并集个数），还有一种是孙子子树和本节点的独立集。所以，这些信息要分开储存：设\(dp[u][1]\)为独立集个数，\(dp[u][0]\)孙子节点的独立集个数。所以，可以得到下列方程：