复健 Day 1: AC 3/6
- D: 概率与期望
- E: 树形DP，线性基，DFS序
- F: 树形DP，记忆化搜索
传送门
A. Flip Flop Sum
输入一个长度为$n$的数组$a$，每个元素$a_i = 1 / -1$。你有且只有一次机会将$a_i$与$a_{i+1}$取相反数，求操作后的$max(\sum\limits_{i=1}^{n} a_i)$。
签到题，出现两个相邻负数直接取反和+4，否则若出现一正一负取反和不变，都没有仅可能全是整数，和-4。时间复杂度$O(n)$
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
| #include <cstdio>
#include <algorithm>
using namespace std;
int a[100010];
int main()
{
int T,n;
scanf("%d",&T);
while(T--)
{
bool flag1=false, flag2=false;
long long sum=0;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",a+i), sum+=a[i];
for(int i=2;i<=n;++i)
{
if(a[i]==-1&&a[i]==a[i-1]) flag1=true;
if(a[i]^a[i-1]) flag2=true;
}
if(flag1) printf("%lld\n", sum+4);
else if(flag2) printf("%lld\n", sum);
else printf("%lld\n",sum-4);
}
return 0;
}
|
B. The Forbidden Permutation
输入一个长度为$n$的排列$p_i$与一个长度为$m$，每个元素$\leq n$的数组$a$。如果对每个$a_i$都有$pos(a_i) \lt pos(a_{i+1}) \le pos(a_i)+d$，则称数组$a$被定义为坏数组。你需要执行操作，每次操作可以将$p_i$与$p_{i+1}$交换，问至少需要多少次操作才能使数组$a$变成好数组。
坏数组的性质非常特殊：输入的数组$a$是坏数组，则每个$a_i$在$p$中的顺序应当与在$a$中顺序一样，且两两之间差距不超过$d$。将$a_i$挂在$p_i$上，则每次对$p_i$操作都可以改变相邻$a_i$的间隔。只需要让一对相邻的$a_i$距离小于$0$（反序）或大于$d$即可。故$ans=min(min(d-(pos(a_{i+1})-pos(a_i))+1),min(pos(a_{i+1})-pos(a_i)))$.
如果排列长度$n \le d+1$，则不能操作让距离大于$d$，特判即可。时间复杂度$O(n+m)$
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
| #include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 100010
int p[MAXN],a[MAXN],ppos[MAXN],apos[MAXN];
int main()
{
int T,n,m,d;
scanf("%d",&T);
while(T--)
{
int ans=0x3f3f3f3f;
scanf("%d%d%d",&n,&m,&d);
for(int i=1;i<=n;++i) scanf("%d",p+i),ppos[p[i]]=i;
for(int i=1;i<=m;++i) scanf("%d",a+i),apos[i]=ppos[a[i]];
for(int i=2;i<=m;++i)
{
ans=min(ans,apos[i]-apos[i-1]);
if(d+1<n) ans=min(ans,d-(apos[i]-apos[i-1])+1);
}
printf("%d\n",max(ans,0));
}
return 0;
}
|
C. Flexible String
输入两个字符串$a$与$b$，其中$a$所含不同字符的个数$\le 10$。现可以将$a$中最高不超过$k$种字符任意转换成其他字符（决定转换后不同位置的同种字符可转换为不同字符），问转换后的$a$字符串可与$b$字符串最多有多少相同子串。（子串计算方法可重叠，即有多少$(l,r)$使得$a[l,r]=b[l,r]$）
假设我们已经确定转换的字符种类，那么每个可转换字符转换目标肯定是$b$字符串对应字符。转换后，求出所有不重叠的相同子串长度$l_i$，易知$ans=\sum \frac{l_i (l_i+1)}{2}$。
字符串$a$只包含$\le 10$种不同字符，则可能的转换方案有$C_m^k \le C_{10}^{5}$种，枚举的时间复杂度是正确的，搜索即可。时间复杂度$O(C_m^k n)$
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
53
54
55
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 100010
int n,k;
char c[11];
bool canmod[26];
char a[MAXN],b[MAXN];
long long ans;
void getans()
{
long long ret=0,tmp=0;
for(int i=1;i<=n;++i)
{
if(canmod[a[i]-'a']||a[i]==b[i]) ++tmp;
else ret+=tmp*(tmp+1)/2,tmp=0;
}
ret+=tmp*(tmp+1)/2;
ans=max(ans,ret);
}
void dfs(int id,int pos)
{
if(id>k)
{
getans();
return;
}
for(int i=pos;i+(k-id)<=c[0];++i)
{
canmod[c[i]-'a']=true;
dfs(id+1,i+1);
canmod[c[i]-'a']=false;
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
ans=0;
c[0]=0;
memset(canmod,0,sizeof canmod);
scanf("%d%d%s%s",&n,&k,a+1,b+1);
for(int i=1;i<=n;++i) if(!canmod[a[i]-'a']) canmod[a[i]-'a']=true,c[++c[0]]=a[i];
if(c[0]<=k) getans();
else
{
memset(canmod,0,sizeof canmod);
dfs(1,1);
}
printf("%lld\n",ans);
}
}
|
D. Flexible String Revisit
一个长度为$n$的01串，其中包含$k$个1，每次随机指定串中一个元素翻转，求整个01串第一次变为全0串的期望步数。
期望题。令$f_i$表示从$i$个1的状态经过随机过程第一次达到全0状态的期望步数。显然有$f_0=0$。试求$f_i$，在有$i$个1的状态下进行一次随机，有$\frac{i}{n}$的概率反转一个1，达到$f_{i-1}$的状态，还有$\frac{n-i}{n}$的概率反转一个1，达到$f_{i+1}$的状态，于是有$f_i = \frac{i}{n}f_{i-1}+\frac{n-i}{n}f_{i+1}+1$.
接下来就到了概率问题最难的环节了：试图解这个特殊的方程。我们已经找到了一个初始条件$f_0=0$，则有$f_1=\frac{1}{n}f_0+\frac{n-1}{n}f_2+1=1+\frac{n-1}{n}f_2$，这里只涉及$f_1$与$f_2$,如果带入$f_2=\frac{2}{n}f_1+\frac{n-2}{n}f_3+1$中，方程又会拆解为$f_2$与$f_3$之间的关系……这证明在$f_i$和$f_{i+1}$之间可以建立关系。令$f_i=a_i+b_if_{i+1}$，则有：
$$
\begin{align}
f_i &= \frac{i}{n} f_{i-1} + \frac{n-i}{n} f_{i+1} + 1 \\
&= \frac{i}{n} (a_{i-1}+b_{i-1}f_{i}) + \frac{n-i}{n} f_{i+1} + 1
\end{align}
$$
解得
$$
f_i = \frac{i a_{i-1}+n}{n-ib_{i-1}} + \frac{n-i}{n-ib_{i-1}} f_{i+1} \\
a_i = \frac{i a_{i-1}+n}{n-ib_{i-1}} \\
b_i = \frac{n-i}{n-ib_{i-1}} \\
(a_1 = 1, b_1 = \frac{n-1}{n})
$$
$a_i$与$b_i$均可递推得出确定值，于是我们就得到了$f_i$与$f_{i+1}$的递推关系。
我们再看另一侧，$f_n=f_{n-1}+1, f_{n-1}=\frac{n-1}{n}f_{n-2}+\frac{1}{n}f_{n}$，这里也可以用同样的方法进行计算：令$f_i=c_i+d_if_{i-1}$，则有：
$$
\begin{align}
f_i &= \frac{i}{n} f_{i-1} + \frac{n-i}{n} f_{i+1} + 1 \\
&= \frac{i}{n} f_{i-1} + \frac{n-i}{n} (c_{i+1} + d_{i+1}f_i) + 1
\end{align}
$$
解得：
$$
f_i = \frac{(n-i)c_{i+1}+n}{n-(n-i)d_{i+1}} + \frac{i}{n-(n-i)d_{i+1}} f_{i-1} \\
c_i = \frac{(n-i)c_{i+1}+n}{n-(n-i)d_{i+1}} \\
d_i = \frac{i}{n-(n-i)d_{i+1}} \\
(c_n = 1, d_n = 1)
$$
这样，我们得到了另一个$f_i$的递推式，其中$c_i$与$d_i$均可递推得出确定值。
联立两个$d_i$递推式可得：
$$
\begin{cases}
f_i = c_i + d_i f_{i-1} \\
f_{i-1} = a_{i-1} + b_{i-1} f_{i}
\end{cases} \\
\begin{align}
\Rightarrow f_i &= c_i + d_i a_{i-1} + b_{i-1} f_i \\
f_i &= \frac{c_i+d_ia_{i-1}}{1-d_ib_{i-1}}
\end{align}
$$
递推得到$a_i,b_i,c_i,d_i$，令$i=k$即可得到答案。
有两点需要注意：
- 需要特判$k=0$的情况。
- 分数的表达题目要求使用乘法逆元。$p$为素数，直接用快速幂法即可。
时间复杂度$O(n \log M)$
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
53
54
55
| #include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 1000010
#define MO 998244353ll
int n,k;
long long a[MAXN],b[MAXN],c[MAXN],d[MAXN];
char sa[MAXN],sb[MAXN];
long long inv(int x)
{
long long y=MO-2,tmp=x,ret=1;
while(y)
{
if(y&1) ret=(ret*tmp)%MO;
tmp=(tmp*tmp)%MO,y>>=1;
}
return ret;
}
long long sdiv(long long x,long long y)
{
x%=MO,y%=MO;
if(x<0) x+=MO;
if(y<0) y+=MO;
return (x*inv(y))%MO;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%s%s",&n,sa+1,sb+1);
k=0;
for(int i=1;i<=n;++i) k+=sa[i]!=sb[i];
if(!k)
{
printf("0\n");
continue;
}
a[1]=1,b[1]=sdiv(n-1,n);
for(int i=2;i<=n;++i)
{
a[i]=sdiv(i*a[i-1]+n,n-i*b[i-1]);
b[i]=sdiv(n-i,n-i*b[i-1]);
}
c[n]=1,d[n]=1;
for(int i=n-1;i;--i)
{
c[i]=sdiv((n-i)*c[i+1]+n,n-(n-i)*d[i+1]);
d[i]=sdiv(i,n-(n-i)*d[i+1]);
}
printf("%lld\n",sdiv(c[k]+a[k-1]*d[k],1-b[k-1]*d[k]));
}
return 0;
}
|
E. The Tree Has Fallen!
给你一颗$N$个点的树及其点权，$Q$次询问以某个点$r$为根的情况下，$v$的子树中子集最大异或和是多少。
$\sum n,q \le 2 \cdot 10^5$
树形 DP + 线性基 + DFS序 + 倍增算法 = 大融合怪。
首先考虑子集最大异或和问题。存储线性基，只需对每个数进行二进制拆分并实时高斯消元，$W$个数即可表达$0 \sim 2^W$范围内的整数的异或和情况。欲求子集最大异或和，对线性基中存储的元素进行异或即可。插入元素复杂度$O(W)$，两组线性基合并时间复杂度$O(W^2)$。以此为转移，使用树形 DP 即可获取全树所有子树的子集最大异或和。
按任意点为根定义有根树。当$r=v$时，输出根节点的结果；当$r$不在$v$子树内时，原定义子树结构与欲定义子树结构相同，输出以该点为根的子树的结果；当$r$在$v$子树内时，应输出除$v$往$r$方向向下第一个节点为根的子树之外所有节点为集合的结果：考虑 DFS 序，发现子树的 DFS 序是连续的，只需维护前缀和与后缀和线性基，合并即可。
这里线性基是子集最大异或和的标准做法，但 DFS 序比较难想。还有一个有趣的点，获取$v$往$r$方向向下第一个节点时，如果遍历儿子找点的话最坏时间复杂度$O(q n^2)$会 TLE（CF 数据你出的好啊），使用倍增算法维护祖先，跳着找即可。
时间复杂度$O(q \log^2 d)$，其中$d \le 10^9$为$a_i$取值范围。
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
| #include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 200010
class hamel
{
private:
int v[30];
public:
hamel()
{
for(int i=0;i<30;++i) this->v[i]=0;
}
void clear()
{
for(int i=0;i<30;++i) this->v[i]=0;
}
void merge(hamel &b)
{
for(int i=0;i<30;++i)
if(b.v[i])
this->insert(b.v[i]);
}
void insert(int x)
{
int to=-1;
for(int i=29;~i;--i)
if(x&(1<<i))
{
if(v[i]) x^=v[i];
else if(to==-1) to=i;
}
if(to!=-1)
{
v[to]=x;
for(int i=to+1;i<30;++i)
if(v[i]&(1<<to))
v[i]^=x;
}
}
int value()
{
int ret=0;
for(int i=29;~i;--i) ret^=v[i];
return ret;
}
};
int n,a[MAXN];
hamel f[MAXN],g[MAXN],h[MAXN];
int to[MAXN<<1],nxt[MAXN<<1],head[MAXN],tot;
int dfsi[MAXN],dfso[MAXN],dfsu[MAXN],cnt;
int fa[MAXN][20],dep[MAXN];
void ae(int x,int y)
{
to[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
void dfs1(int pos,int pre)
{
dep[pos]=dep[pre]+1;
fa[pos][0]=pre;
dfsu[++cnt]=pos;
dfsi[pos]=cnt;
f[pos].insert(a[pos]);
for(int i=head[pos];i;i=nxt[i])
if(to[i]!=pre)
{
dfs1(to[i],pos);
f[pos].merge(f[to[i]]);
}
dfso[pos]=cnt;
}
int getson(int r,int v)
{
int i=0;
while((1<<i)<=n) ++i;
for(--i;~i;--i) if(dep[fa[r][i]]>dep[v]) r=fa[r][i];
return r;
}
int main()
{
int T,Q,x,y,r,v;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",a+i);
for(int i=1;i<n;++i) scanf("%d%d",&x,&y),ae(x,y),ae(y,x);
dfs1(1,0);
for(int j=1;(1<<j)<=n;++j)
for(int i=1;i<=n;++i)
fa[i][j]=fa[fa[i][j-1]][j-1];
for(int i=1;i<=n;++i)
{
if(i>1) g[i].merge(g[i-1]);
g[i].insert(a[dfsu[i]]);
}
for(int i=n;i;--i)
{
if(i<n) h[i].merge(h[i+1]);
h[i].insert(a[dfsu[i]]);
}
scanf("%d",&Q);
while(Q--)
{
scanf("%d%d",&r,&v);
if(r==v)
{
printf("%d\n",f[1].value());
}
else if(dfsi[v]<=dfsi[r]&&dfsi[r]<=dfso[v])
{
int c=getson(r,v);
hamel tmp;
if(dfsi[c]-1>=1) tmp.merge(g[dfsi[c]-1]);
if(dfso[c]+1<=n) tmp.merge(h[dfso[c]+1]);
printf("%d\n",tmp.value());
}
else printf("%d\n",f[v].value());
}
for(int i=1;i<=n;++i) head[i]=0,f[i].clear(),g[i].clear(),h[i].clear();
cnt=tot=0;
}
return 0;
}
|
F. Maximizing Root
输入一棵点数为$n$的有根树及其点权（点权$a_i \le 1000$）。你可以最多执行$k$次操作，每次操作你可以选择一个之前未选择过的点，并将其子树中所有点点权都乘以一个数$x$，其中$x$需为该子树中所有点权的公因子。求操作后根节点最大可能点权。
树形 DP 好题。令$f_{x,y}$为节点$x$及其子树令其包含公因子$y$（在该节点使用操作或不使用均可）的最少步数。思考如何递推：若已知所有儿子的所有情况，仅需枚举在该点进行操作的乘法因子$z$，其中$z$需满足：$z$是$a_x$的因子；$z \cdot a_x$是$y$的倍数。此时对所有儿子对应的子树，为了能够一起乘以$z$，需要都包含公因子$z$；为了乘以$z$之后都包含公因子$y$，需要都包含公因子$y/\gcd (y,z)$，取交集，其共需包含$\operatorname{lcm}(y,z)$，取$f_{u,y} = \max\limits_z(\sum f_{v,\operatorname{lcm}(y,z)}+1)$即可；当$z=1$，即最后操作乘以 1 时，实际上意味着在子树根节点不需要进行操作，此时特判最后不 +1 即可。初始情况，当$\gcd_x$（$x$子树点权的最大公约数）是$y$的倍数时，$f_{x,y}=0$；当$\gcd_x \cdot \gcd_x$不是$y$的倍数时，$f_{x,y}$不合法。
使用记忆化搜索的方法进行递推。需要注意的是，我们求得的结果仅仅是可以乘$y$的最少步数，并不知道最后的乘数，而在最终求解时，根节点乘以多少是我们需要知道的答案，故将最后一层拆开，并不求$f_{1,y}$,而是求 1 号节点最后的乘数可以是多少。
时间复杂度$O(nm^2)$，其中$m \le \sqrt{max(a_i)} = \sqrt{1000}$为$a_1$因子个数。
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #include <cstdio>
#include <algorithm>
#include <vector>
#include <unordered_set>
using namespace std;
#define MAXN 100010
int n,k,a[MAXN],fa[MAXN],gcd[MAXN];
int f[MAXN][1001];
vector<int> to[MAXN];
vector<int> m[1010];
int lcm(int x,int y)
{
return x*y/__gcd(x,y);
}
void dfs(int pos,int pre)
{
fa[pos]=pre;
gcd[pos]=a[pos];
for(auto i:to[pos])
if(i!=pre)
{
dfs(i,pos);
gcd[pos]=__gcd(gcd[i],gcd[pos]);
}
}
int solve(int x,int y)
{
if(f[x][y]!=-1) return f[x][y];
if(gcd[x]%y==0) return f[x][y]=0;
if((a[x]*a[x])%y!=0) return f[x][y]=0x3f3f3f3f;
f[x][y]=0x3f3f3f3f;
for(int z:m[a[x]])
{
if((a[x]*z)%y!=0) continue;
int res=0,tmp;
for(int i:to[x]) if(i!=fa[x])
{
tmp=solve(i,lcm((y/__gcd(y,z)),z));
if(tmp==0x3f3f3f3f)
{
res=0x3f3f3f3f;
break;
}
res+=tmp;
}
if(z==1) f[x][y]=min(f[x][y], res);
else f[x][y]=min(f[x][y], res+1);
}
return f[x][y];
}
int main()
{
for(int i=1;i<=1000;++i)
{
for(int j=1;j*j<=i;++j)
if(i%j==0)
{
m[i].push_back(j);
if(j!=i/j) m[i].push_back(i/j);
}
}
int T,x,y;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
for(int j=1;j<=1000;++j)
f[i][j]=-1;
for(int i=1;i<=n;++i) to[i].clear();
for(int i=1;i<=n;++i) scanf("%d",a+i);
for(int i=1;i<n;++i) scanf("%d%d",&x,&y),to[x].push_back(y), to[y].push_back(x);
dfs(1,0);
int ans=a[1];
for(auto i:m[a[1]])
{
int res=0;
for(auto j:to[1])
{
solve(j,i);
if(f[j][i]==0x3f3f3f3f)
{
res=-1;
break;
}
res+=f[j][i];
}
if(res!=-1&&(i==1&&res<=k||i!=1&&res<k)) ans=max(ans, i*a[1]);
}
printf("%d\n",ans);
}
return 0;
}
|