Now the contest is open for everyone!
Link: [contest:353762]
Invitation link: https://codeforces.me/contestInvitation/07d1578a0b03430fd518eba26675362015235557
[problem:353762A]
简单的线性动态规划题。
我们设状态 $$$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;
}
[problem:353762B]
简单的期望动态规划题。
题目其实已经提示了解法。在仅考虑“再来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;
}
[problem:353762C]
较简单的状态压缩动态规划题。
题目以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;
}
[problem:353762D1]
注意:本解法只能通过简单版本,不能通过困难版本!
中等难度的构造题。
首先,我们需要判断什么情形是无解的:
- 点的度数大于等于点的个数( $$$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;
}
[problem:353762D2]
注意:此解法是本题较优秀的解法,可以同时通过简单和困难两个版本。
较难的构造题。
对于无解情形以及边数的计算,上一题中已经讲解,这里不再赘述。
我们首先有一个 $$$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;
}
[problem:353762E]
比较偏向模板的快速沃尔什变换(或快速莫比乌斯变换)问题。
观察到 $$$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;
}