简单的线性动态规划题。

我们设状态 $$$dp_{i,j}$$$ 为：考虑到第 $$$i$$$ 个字符，已经匹配了 $$$j$$$ 个字符的方案数。初始状态下仅有 $$$dp_{0,0}=1$$$ ，其余均为 $$$0$$$ 。状态转移的过程如下：记给定的待匹配串为 $$$s$$$ ，目标序列"helloworld"为 $$$t$$$ ，则如果 $$$s_i=t_j$$$ ，有 $$$dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}$$$ ，否则 $$$dp_{i,j}=dp_{i-1,j}$$$ 。

由于目标序列很短，对变量 $$$j$$$ 的迭代只需要 $$$10$$$ 次，因此该做法的时间复杂度是 $$$O(10n)$$$ ，空间复杂度是 $$$O(10n)$$$ 。

由于每个状态我们仅在一次转移中用到，我们可以对数组进行压缩，其空间复杂度可以被优化到 $$$O(10)$$$ ，同时我们可以枚举可能的情形以减少循环，这将使得时间复杂度略有降低（依然是 $$$O(n)$$$ 级别），但这不是必要的，不优化同样可以通过本题。

动态规划，字符串

#include <bits/stdc++.h>

using namespace std;
const int mod = 998244353;
char s[100005];
long long dp[15];

void solve() {
	scanf("%s", s);
	int n = strlen(s);
	memset(dp, 0, sizeof dp);
	dp[0] = 1;
	for (int i = 0; i < n; ++i) {
		switch (s[i]) {
			case 'h':
				dp[1] += dp[0];
				dp[1] %= mod;
				break;
			case 'e':
				dp[2] += dp[1];
				dp[2] %= mod;
				break;
			case 'l':
				dp[9] += dp[8];
				dp[9] %= mod;
				dp[4] += dp[3];
				dp[4] %= mod;
				dp[3] += dp[2];
				dp[3] %= mod;
				break;
			case 'o':
				dp[7] += dp[6];
				dp[7] %= mod;
				dp[5] += dp[4];
				dp[5] %= mod;
				break;
			case 'w':
				dp[6] += dp[5];
				dp[6] %= mod;
				break;
			case 'r':
				dp[8] += dp[7];
				dp[8] %= mod;
				break;
			case 'd':
				dp[10] += dp[9];
				dp[10] %= mod;
				break;
		}
	}
	printf("%lld\n", dp[10] % mod);
}

int main() {
//	freopen("in.txt", "r", stdin);
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}

简单的期望动态规划题。

题目其实已经提示了解法。在仅考虑“再来1瓶”的时候，转移方程是 $$$E(X)=1+pE(X)$$$ ，那么推广到“再来1瓶”和“再来2瓶”独立发生时，转移方程变成 $$$E(X)=1+p_1E(X)+2p_2E(X)$$$ 。

本题解仅对“再来1瓶”时的转移方程加以解释，其推广请读者类比推出。

在打开这一瓶矿泉水之前，最终的期望值就已经确定，喝掉这一瓶时一定能得到期望为1的矿泉水，而对于兑奖，有 $$$p$$$ 的概率得到新的一瓶，又能得到期望为 $$$E$$$ 的矿泉水，这两者的和就等于期望值，解方程就能算出期望。

需要注意的一点是，当 $$$p_1+2p_2\ge1$$$ 时，期望会趋向无穷大。（因为你喝掉1瓶后得到超过1瓶，矿泉水只会越喝越多）

单个测试数据的时间复杂度是 $$$O(log_{mod})$$$ ，因为要用到快速幂。

动态规划，期望，逆元

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
inline ll qpow(ll a,ll b){
	ll s=1;a%=mod;
	for(;b;b>>=1){
		if(b&1)s=s*a%mod;
		a=a*a%mod;
	}
	return s;
}
ll n,a1,b1,a2,b2,p,q;
inline void work(){
	cin>>n>>a1>>b1>>a2>>b2;
	ll num=a1*b2+2*a2*b1;
	ll den=b1*b2;
	if(n>=2&&num>=den){
		cout<<"Another hundred million bottles!"<<endl;
		return;
	}
	p=a1*qpow(b1,mod-2)%mod;
	q=a2*qpow(b2,mod-2)%mod;	
	ll t=1-p-2*q;
	t=(t%mod+mod)%mod;
	ll ans=n/2%mod*qpow(t,mod-2)%mod;
	cout<<ans<<endl;
}
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int T;cin>>T;
	while(T--)work();
	return 0;
}

较简单的状态压缩动态规划题。

题目以0和1表示点的颜色是黑还是白，我们进行沿用。对于9个点的图，我们只需知道颜色序列变为 $$$000000000$$$ 或 $$$111111111$$$ ，且当前位置位于 $$$en$$$ 点，最少需要多少步，然后对这两者取较小者即可（如果做不到，其步数为无穷大）。

由于点数很少，我们用一个32位整数来压缩状态，以整数的二进制位来表示某个点的颜色状态。例如 $$$000000000$$$ 压缩为整数 $$$0$$$ ， $$$111111111$$$ 压缩为整数 $$$511$$$ ，等等。

然后我们就能写出状态： $$$dp_{i,j}$$$ 表示压缩后的颜色状态为 $$$i$$$ ，当前位于编号为 $$$j$$$ 的点。初始状态下，假定数据给出的初始颜色信息是 $$$s$$$ ，那么只有 $$$dp_{s,st}=0$$$ ，其余状态都是无穷大。再使用BFS进行搜索（用DFS也可以），搜索完成后，若能够达到上述的末状态（最短距离不为无穷大），则说明有解，输出即可，否则说明无解，输出 $$$-1$$$ 。

这一解法的时空复杂度均是 $$$O(n\cdot2^n)$$$ 。

状态压缩，二进制，动态规划，BFS，DFS

#include <bits/stdc++.h>

using namespace std;

int n, m, st, en;

int dis[1 << 18][18];
vector<int> g[18];

int bfs(int k, int p) {
	queue<pair<int, int>> q;
	q.emplace(k, p);
	dis[k][p] = 1;
	while (!q.empty()) {
		auto cur = q.front();
		q.pop();
		if ((cur.first == 0 || cur.first == (1 << n) - 1) && cur.second == en) return dis[cur.first][cur.second];
		for (int i: g[cur.second]) {
			if (!dis[cur.first ^ 1 << i][i]) {
				dis[cur.first ^ 1 << i][i] = dis[cur.first][cur.second] + 1;
				q.emplace(cur.first ^ 1 << i, i);
			}
		}
	}
	return -1;
}

void solve() {
	scanf("%d%d", &n, &m);
	scanf("%d%d", &st, &en);
	--st, --en;
	while (m--) {
		int x, y;
		scanf("%d%d", &x, &y);
		--x, --y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	int k = 0;
	for (int i = 0; i < n; ++i) {
		int p;
		scanf("%1d", &p);
		k |= p << i;
	}
	memset(dis, 0, sizeof dis);
	printf("%d\n", bfs(k ^ 1 << st, st));
	for (int i = 0; i < n; ++i) g[i].clear();
}

int main() {
//	freopen("in.txt", "r", stdin);
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}

中等难度的构造题。

首先，我们需要判断什么情形是无解的：

• 点的度数大于等于点的个数（ $$$r\ge n$$$ ，即便某个点向除了自己以外的所有点都连了边，仍然不能满足度数限制）
• 点的度数乘点的个数是奇数，即整个图上度数是奇数（ $$$r\cdot n\ mod\ 2=1$$$ ，任何图的度数之和一定是偶数）

有了度数之和，我们就能算出边的数量是度数的一半。

接下来说怎么构造连边方式。

有经验的选手一定见过这样一个问题：给定若干个点，已知每个点的度数，要求构造任何一个简单图满足上述条件。我们只要维护一个堆（在C++中体现为优先队列），每次取度最大的点，并与剩余各点中度数最大的若干个点相连，重复操作直到所有点剩余度数为0。

本题中也可以运用这种方法，首先构造出一个 $$$n$$$ 个点，每个点的度为 $$$r$$$ 的无向简单图。至此，我们得到的答案与正确答案仅有连通性上的差距：现在得到的图不一定连通！

那么，我们只需完善这个图的连通性就好了。在连边的过程中，我们可以使用并查集来维护连通块。完成连边之后，我们得到了若干个独立的 $$$r$$$ 度正则图，如果对于连通块 $$$A$$$ 和连通块 $$$B$$$ ，有边 $$$x_1x_2\in A$$$ ，边 $$$y_1y_2\in B$$$ ，我们拆除原有边 $$$x_1x_2$$$和$$$y_1y_2$$$ ，然后新增边 $$$x_1y_1$$$ 和 $$$x_2y_2$$$ ，各点的度数不发生改变（先减1再加1）。这样就完成了两个连通块的合并。

不断合并连通块直到所有点都相互连通，就是正确答案了。

这样做的时间复杂度是 $$$O(elog_2e)$$$ ，其中 $$$e$$$ 表示图上边的数量。

构造，图论，贪心，并查集

#include <bits/stdc++.h>

using namespace std;

int fa[2005];
int me[2005];

int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int mp[2005][2005];

int main() {
//	freopen("in.txt", "r", stdin);
	int n, r;
	scanf("%d%d", &n, &r);
	if (n <= r || n * r & 1) {
		printf("-1\n");
		return 0;
	}
	for (int i = 1; i <= n; ++i) fa[i] = i;
	priority_queue<pair<int, int>> q;
	for (int i = 1; i <= n; ++i) q.emplace(r, i);
	while (!q.empty()) {
		auto p = q.top();
		q.pop();
		int x = p.first, y = p.second;
		for (int i = 0; i < x; ++i) {
			p = q.top();
			q.pop();
			fa[find(p.second)] = find(y);
			me[y] = p.second;
			me[p.second] = y;
			mp[y][p.second] = mp[p.second][y] = 1;
			--p.first;
			if (p.first > 0) q.push(p);
		}
	}
	if (find(1) != 1) {
		int tmp = find(1);
		fa[1] = fa[tmp] = 1;
	}
	for (int i = 2; i <= n; ++i) {
		if (find(i) != 1) {
			int x = find(i);
			int y = me[1], z = me[x];
			fa[x] = 1;
			mp[1][y] = mp[y][1] = mp[x][z] = mp[z][x] = 0;
			mp[1][x] = mp[x][1] = mp[y][z] = mp[z][y] = 1;
			me[1] = x;
		}
	}
	printf("%d\n", n * r / 2);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j < i; ++j) {
			if (mp[i][j]) printf("%d %d\n", i, j);
		}
	}
	return 0;
}

较难的构造题。

对于无解情形以及边数的计算，上一题中已经讲解，这里不再赘述。

我们首先有一个 $$$n$$$ 个点的空图。

第一步，我们按照 $$$1-2-3-...-(n-1)-n-1$$$ 的顺序连边。这一操作之后，所有点的度数都增加了 $$$2$$$ 。

第二步，我们按照 $$$1-3-5-7-...$$$ 的顺序连边。现在有两种情况：如果点数 $$$n$$$ 是奇数，那么 $$$n$$$ 号点将与 $$$2$$$ 号点连边（ $$$n+2-n=2$$$ ，也就是说，如果我们把点按顺时针排列， $$$n$$$ 号点沿顺时针往后数 $$$2$$$ 个点恰好是 $$$2$$$ 号点），然后按照 $$$2-4-6-8-...$$$ 的顺序连边，直到 $$$n-1$$$ 号点与 $$$1$$$ 号点相连；如果点数 $$$n$$$ 是偶数，那么 $$$n-1$$$ 号点向后数 $$$2$$$ 个点恰好是 $$$1$$$ 号点，将它们相连，再按照 $$$2-4-6-8-...$$$ 的顺序连边。这一操作之后，所有点的度数都又增加了 $$$2$$$ 。

第三步，我们按照 $$$1-4-7-10-...$$$ 的顺序连边。依然有两种情况： $$$n$$$ 被 $$$3$$$ 整除或不被 $$$3$$$ 整除。与上一步相似， $$$n$$$ 被 $$$3$$$ 整除时会形成 $$$1$$$ 个由 $$$n$$$ 个点组成的环，否则会形成 $$$3$$$ 个由 $$$\frac{n}{3}$$$ 个点组成的环。这一操作也能使所有点的度数增加 $$$2$$$ 。

重复类似的操作，我们可以不断增加所有点的度数。若 $$$r$$$ 是偶数，我们一定可以通过这个方法完成连边；若 $$$r$$$ 是奇数，则通过若干次操作后所有点的度数都剩下 $$$1$$$ 度，根据 $$$n$$$ 和 $$$r$$$ 不会同时为奇数，我们可以确定 $$$n$$$ 一定是偶数，我们只需将 $$$i$$$ 号点与 $$$i+\frac{n}{2}$$$ 号点相连即可。

对于连通性，在第一步中形成了一个 $$$n$$$ 个点的环，整个图一定连通。

对于自环，显然这个连边方式不会与自身连边。

对于重边，由于不同的操作中形成的边的两个顶点编号之差都不相同，因此不同操作直接不可能形成相同的边。而同一操作中边的出发顶点是唯一的，故这些边是不重复的。

这一做法的时间复杂度是 $$$O(e)$$$ ，其中 $$$e$$$ 是边的数量。

构造，图论

#include <bits/stdc++.h>

using namespace std;

int main() {
//	freopen("in.txt", "r", stdin);
	int n, r;
	scanf("%d%d", &n, &r);
	if (n <= r || n * r & 1) {
		printf("-1\n");
		return 0;
	}
	printf("%d\n", n * r / 2);
	for (int i = 1; i <= r / 2; ++i) {
		int g = __gcd(i, n);
		for (int j = 0; j < g; ++j) {
			int p = j;
			do {
				int q = (p + i) % n;
				printf("%d %d\n", p + 1, q + 1);
				p = q;
			} while (p != j);
		}
	}
	if (r & 1) {
		for (int i = 1; i <= n / 2; ++i) {
			printf("%d %d\n", i, i + n / 2);
		}
	}
	return 0;
}

比较偏向模板的快速沃尔什变换（或快速莫比乌斯变换）问题。

观察到 $$$q$$$ 的数据范围只有 $$$20$$$ ，我们考虑将性格信息进行数位压缩。

设 $$$A(x)$$$ 和 $$$B(x)$$$ 分别是性格为 $$$x$$$ 的男生和女生的活跃程度，对于数位压缩后的集合 $$$x$$$ 和集合 $$$y$$$ ， $$$x$$$ & $$$y$$$ 恰好就是集合的交集，其中 & 表示按位与运算。设 $$$f(x)$$$ 为性格需求为 $$$x$$$ 的活动，那么我们会有： $$$f(x)=\sum_{i\ and\ j=x}A(i)B(j)$$$ 。

然后使用快速沃尔什变换（FWT）或者快速莫比乌斯变换（FMT）即可解决。

整体时间复杂度是 $$$O(nlog_2n)$$$ 。

快速沃尔什变换（FWT），快速莫比乌斯变换（FMT），二进制，数位压缩

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int N = 1 << 20;
const int mod = 998244353;
int a[N], b[N], c[N];

void fwt_and(int *arr, int n, int flag) {
	for (int i = 1; i << 1 <= n; i <<= 1)
		for (int j = 0; j < n; j += i << 1)
			for (int k = 0; k < i; ++k)
				arr[j + k] = (arr[j + k] + (ll) arr[i + j + k] * flag) % mod;
}

ll quickpow(ll x, ll y) {
	ll res = 1;
	x %= mod;
	while (y) {
		if (y & 1)
			res = res * x % mod;
		y >>= 1;
		x = x * x % mod;
	}
	return res;
}

ll inv(ll n) {
	return quickpow(n, mod - 2);
}

int main() {
//	freopen("in.txt", "r", stdin);
	const int neg1 = mod - 1;
	int n, m, p, q;
	scanf("%d%d%d%d", &n, &m, &p, &q);
	const ll inm = inv((ll) n * m % mod);
	while (n--) {
		int x, k, d = 0, t;
		scanf("%d%d", &x, &k);
		while (k--) {
			scanf("%d", &t);
			d |= 1 << t;
		}
		d >>= 1;
		a[d] = x;
	}
	while (m--) {
		int x, k, d = 0, t;
		scanf("%d%d", &x, &k);
		while (k--) {
			scanf("%d", &t);
			d |= 1 << t;
		}
		d >>= 1;
		b[d] = x;
	}
	fwt_and(a, 1 << q, 1);
	fwt_and(b, 1 << q, 1);
	for (int i = 0; i < 1 << q; ++i) c[i] = (ll) a[i] * b[i] % mod;
	fwt_and(c, 1 << q, neg1);
	while (p--) {
		int k, d = 0, t;
		scanf("%d", &k);
		while (k--) {
			scanf("%d", &t);
			d |= 1 << t;
		}
		d >>= 1;
		printf("%lld\n", c[d] * inm % mod);
	}
	return 0;
}