Codeforces Round 463 题解(全解锁) | Bill Yang's Blog

Codeforces Round 463 题解(全解锁)

Round 462,疯狂被hack,疯狂fst,掉了106的rating(terrible pretest),没脸见人了。
Round 463,把昨天掉的rating都攒回来了,喵喵喵?

先丢几个链接
比赛地址
官方题解

Problem A. Palindromic Supersequence

题目大意

给一个串$A$,长度$\le10^3$,找出一个串$B$,长度$\le10^4$,使得$A$是$B$的子序列,且$B$是回文的。

题目分析

直接正着输一遍,倒着输一遍即可。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
char s[10005];
int main() {
scanf("%s",s);
printf("%s",s);
int len=strlen(s);
reverse(s,s+len);
printf("%s",s);
return 0;
}

Problem B. Recursive Queries

题目大意

设$f(n)$为数字$n$的非零数位相乘结果。

给出$Q(1\le Q\le2\times10^5)$组$l,r,k(1\le l\le r\le10^6,1\le k\le9)$,找到$l\le x\le r$,使得$g(x)=k$。

题目分析

先把所有的$g(n)$算出来,将$g(n)=k$的所有$n$从小到大储存在数组$a[k][]$中。
询问时通过两次二分即可得到答案。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=1000005;
vector<int> S[maxn];
int g[maxn];
int Solve(int x) {
int sum=1;
while(x) {
int tmp=x%10;
if(tmp==0)tmp=1;
sum=sum*tmp;
x/=10;
}
return sum;
}
int main() {
for(int i=1; i<=1000000; i++) {
if(i<10)g[i]=i;
else g[i]=g[Solve(i)];
S[g[i]].push_back(i);
}
int q=Get_Int();
for(int i=1; i<=q; i++) {
int l=Get_Int(),r=Get_Int(),k=Get_Int();
auto it1=lower_bound(S[k].begin(),S[k].end(),l),it2=upper_bound(S[k].begin(),S[k].end(),r);
if(it1==it2)puts("0");
else printf("%d\n",(int)distance(it1,it2)+(*it2==r));
}
return 0;
}

Problem C. Permutation Cycle

题目大意

令$P[1\ldots n]$是一个$1$到$n$的排列,定义函数$f$为:

令$g(i)$为最小的$j$使得$f(i,j)=i$,现在给出$n,a,b$,找到一个排列$P$对于$1\le i\le n$,使得$g(i)=a$或$g(i)=b$。

题目分析

我们可以直接构造一个简单的循环使得在循环内部的$i$均满足$g(i)=x$,即置换:

因此只需要找到一个分界点$i$使得$i\bmod a=0,(n-i)\bmod b=0$,即可构造出解。
如果找不到,输出$-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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=1000005;
int n,a,b,sum1,sum2,ans[maxn];
int main() {
n=Get_Int();
a=Get_Int();
b=Get_Int();
sum1=sum2=-1;
for(int i=0; i<=n; i+=a)
if((n-i)%b==0) {
sum1=i/a;
sum2=(n-i)/b;
break;
}
if(sum1==-1) {puts("-1");return 0;}
int tmp=0;
for(; sum1; sum1--,tmp+=a) {
int l=tmp+1,r=tmp+a;
for(int i=l; i<r; i++)ans[i]=i+1;
ans[r]=l;
}
for(; sum2; sum2--,tmp+=b) {
int l=tmp+1,r=tmp+b;
for(int i=l; i<r; i++)ans[i]=i+1;
ans[r]=l;
}
for(int i=1; i<=n; i++)printf("%d ",ans[i]);
return 0;
}

Problem D. Tree

题目大意

有一棵树,一开始只有$1$号点,其权重为$0$,令$cnt$为任意时刻树中结点个数,现在给出$Q$个询问。

  • $1\,\, x\,\, w$:增加一个编号为$cnt+1$的结点,其权重为$w$,其父亲为$x$。
  • $2\,\, x\,\, lim$:输出一个序列$a$,使其满足:
    1. 第一个元素是$x$。
    2. 序列中的每个元素均为其前一个元素的祖先。
    3. 序列中元素权重和不超过$lim$。
    4. 对于序列中相邻的两个数$i,i+1$,满足$w[a_i]\le w[a_{i+1}]$,在树$(a_i,a_{i+1})$的路径上不存在点$k$,使得$w[k]\ge w[a_i]$。

题目分析

我们发现第$4$个条件等价于,如果$a_i=x$的某个最近祖先$y$满足$w[y]\ge w[x]$,则$y$必须是$a_{i+1}$。
因此我们可以采用倍增的思想,预处理出每个父亲权重都$\ge$儿子权重的树,预处理出ST表,在这棵新树上倍增,即可得到最长的权重和不超过$lim$的序列长度。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=400005,K=20;
LL sum[maxn][K],val[maxn];
int n,p[maxn][K],lastans;
void Sparse_Table(int Now,int fa) {
int pos=fa;
for(int i=K-1; i>=0; i--)if(~p[pos][i]&&val[p[pos][i]]<val[Now])pos=p[pos][i];
if(val[fa]>=val[Now]) {
p[Now][0]=fa;
sum[Now][0]=val[fa];
} else {
p[Now][0]=p[pos][0];
sum[Now][0]=val[p[pos][0]];
}
for(int i=1; i<K; i++)
if(~p[Now][i-1]) {
p[Now][i]=p[p[Now][i-1]][i-1];
sum[Now][i]=sum[Now][i-1]+sum[p[Now][i-1]][i-1];
} else break;
}
int main() {
int t=Get_Int();
memset(p,-1,sizeof(p));
p[n=1][0]=-1;
while(t--) {
int opt=Get_Int();
if(opt==1) {
LL x=Get_Int()^lastans;
val[++n]=Get_Int()^lastans;
Sparse_Table(n,x);
} else {
LL x=Get_Int()^lastans,lim=Get_Int()^lastans,now=val[x];
if(val[x]>lim) {
printf("%d\n",lastans=0);
continue;
}
lastans=1;
for(int j=K-1; j>=0; j--)
if(~p[x][j]&&now+sum[x][j]<=lim) {
lastans+=1<<j;
now+=sum[x][j];
x=p[x][j];
}
printf("%d\n",lastans);
}
}
return 0;
}

Problem E. Team Work

题目大意

计算:

题目分析

截止于目前,这道题共发现了$6$种解法,并没有深入研究哪些做法是等价的,直接丢链接。

什么,你问我最喜欢哪一个?当然是第四种啦。
考试的时候,hyc想的是标解,我想的就是第四种方法。
however没有想出来,差一步配凑,不然就可以稳稳地$200+$rating了。

标解利用了对多项式求导,然后转化为与原式类似的形式进行Dp。
而解法四就很简单了,直接利用了常见套路,对$i^k$进行斯特林展开。
关于斯特林展开

故:

预处理斯特林数时间复杂度$O(k^2)$,回答时间复杂度$O(k)$。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=5005,mod=1e9+7;
int n,k;
LL S[maxn][maxn],ans=0;
LL Quick_Pow(LL a,LL b) {
LL sum=1;
for(; b; b>>=1,a=a*a%mod)if(b&1)sum=sum*a%mod;
return sum;
}
int main() {
n=Get_Int();
k=Get_Int();
S[0][0]=1;
for(int i=1; i<=k; i++)
for(int j=1; j<=i; j++)S[i][j]=(S[i-1][j]*j%mod+S[i-1][j-1])%mod;
LL nowf=1;
for(int j=0; j<=min(n,k); j++) {
ans=(ans+S[k][j]*nowf%mod*Quick_Pow(2,n-j)%mod)%mod;
nowf=nowf*(n-j)%mod;
}
printf("%I64d\n",ans);
return 0;
}

Problem F. Escape Through Leaf

题目大意

给出一棵以$1$为根的树,每个结点$i$有两个属性$a_i,b_i$。
每次可以从$x$跳跃到其子树中任意一个点$y$(不包含$x$),代价为$a_x\times b_y$,跳跃的总代价为每次跳跃代价的和。
询问从每一个点$i$跳跃到任意一个叶子结点所需的最小代价。

题目分析

不难列出状态转移方程。

转移顺序从下往上。
当然,这样的转移是$O(n^2)$的。

显然,对于该转移方程,我们可以使用斜率优化,几何意义如下:
令$x=b_j,y=f(j)$,构成平面上的一个点$(b_j,f(j))$,利用直线$k=-a_i$去逼近平面上的点,使得截距$f(i)$尽量小。
显然,可以维护子树中的一个下凸包来优化转移。

但是,因为从下往上转移,因此涉及到凸包的合并问题。
凸包是可以$O(n+m)$合并的,但是本题显然不能这样合并,会被卡成$O(n^2)$。
因此我们只能使用动态凸包进行启发式合并。

将原树进行重链剖分,对于重儿子,父亲直接继承其凸包,否则将轻儿子凸包中所有点全部取出,依次插入父亲的凸包。
不难证明,这样的时间复杂度是$O(n\log nT(n))$的,其中$T(n)$是一次插入的代价。

动态凸包应该会写吧,就用平衡树来维护凸包,每次按照水平序插入到其应该在的位置,然后更新凸包(删除不优的前驱与后继),最后重新计算所在凸包位置前后的斜率。
查询的时候提供了斜率$k$,只需要使用二分,找到凸包上最逼近$k$的切点,利用切点更新答案。

这样均摊下来,时间复杂度是$O(n\log^2 n)$的。

题目分析

可能错因:

  • 可能CE错因:凸包上的点维护三个信息$(x,y,k)$,其中$k$可能需要开mutable,因为set默认迭代器为const_iterator
  • 可能WA 6错因:在判断优劣的时候,避免精度问题,将除法转为乘法$\Delta x\times \Delta y$,过程可能爆long long,需要用long double
  • 可能MLE错因:在启发式合并后,需要清空原来儿子的凸包,否则会持续占用内存池,导致空间爆炸。

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
struct Point {
LL x,y;
mutable double k;
Point(LL x=0,LL y=0,LL k=0):x(x),y(y),k(k) {}
bool operator < (const Point& b) const {
if(b.y==1e15)return k<b.k;
return x<b.x||(x==b.x&&y<b.y);
}
};
struct Convex_Hull: set<Point> {
bool bad(iterator it) {
if(next(it)==end()||it==begin())return false;
return (double)(it->y-prev(it)->y)*(next(it)->x-prev(it)->x)>=(double)(next(it)->y-prev(it)->y)*(it->x-prev(it)->x);
}
void compute(iterator it) {
if(next(it)==end())it->k=1e15;
else it->k=(double)(next(it)->y-it->y)/(next(it)->x-it->x);
}
void add(Point x) {
if(find(x)!=end())return;
auto it=insert(x).first;
if(bad(it)) {
erase(it);
return;
}
while(it!=begin()&&bad(prev(it)))erase(prev(it));
while(next(it)!=end()&&bad(next(it)))erase(next(it));
compute(it);
if(it!=begin())compute(prev(it));
}
LL query(double k) {
if(empty())return 1e15;
auto it=lower_bound(Point(0,1e15,-k));
return k*it->x+it->y;
}
} S[maxn];
LL a[maxn],b[maxn],f[maxn];
int n,Size[maxn],Belong[maxn],cnt=0;
vector<int> edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Dfs(int Now,int fa) {
Size[Now]=1;
if(edges[Now].size()==1&&fa) {
f[Now]=0;
Belong[Now]=++cnt;
S[cnt].add(Point(b[Now],0));
return;
}
int son=0;
for(int Next:edges[Now]) {
if(Next==fa)continue;
Dfs(Next,Now);
Size[Now]+=Size[Next];
if(Size[Next]>Size[son])son=Next;
}
Belong[Now]=Belong[son];
for(int Next:edges[Now]) {
if(Next==son||Next==fa)continue;
for(auto it:S[Belong[Next]])S[Belong[Now]].add(it);
S[Belong[Next]].clear();
}
f[Now]=S[Belong[Now]].query(a[Now]);
S[Belong[Now]].add(Point(b[Now],f[Now]));
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=1; i<=n; i++)b[i]=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
Dfs(1,0);
for(int i=1; i<=n; i++)printf("%I64d ",f[i]);
return 0;
}

Problem G. Palindrome Partition

题目大意

给出一个字符串$s(2\le\left| s\right|\le10^6)$,将其分割成$k$段$(p_1,p_2,p_3,\ldots,p_k)$,使得$p_i=p_{k-i+1}\quad (1\le i\le k)$,输出不同划分数,模$10^9+7$。

题目分析

标解是在回文自动机上动规。
不会做,不打算填坑。
update 2017.2.18:我竟然来填坑了。

记$s=s_1s_2s_3\cdots s_{\left|s\right|}$。
令$t=s_1s_{\left|s\right|}s_2s_{\left|s\right|-1}\cdots s_\frac{\left|s\right|}{2}s_{\frac{\left|s\right|}{2}+1}$。
则“将$t$划分为$k$段$(p_1,p_2,p_3,\ldots,p_k)$,使得每段$p_i$均为回文” 的方案可以一一对应到 “将$s$划分成$k$段$(p_1,p_2,p_3,\ldots,p_k)$,使得$p_i=p_{k-i+1}\quad (1\le i\le k)$”的方案。
因此,构造出$t$,问题转化为TOJ2044类似问题,使用回文自动机优化动规解决

代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=1000005,mod=1e9+7;
struct Palindsome_Automaton {
int child[maxn][26];
int n,size,last,s[maxn],len[maxn],next[maxn],diff[maxn],snext[maxn];
Palindsome_Automaton() {
size=-1;
newnode(0); //even
newnode(-1); //odd
last=n=0;
s[0]=-1;
next[0]=next[1]=1;
}
int newnode(int v) {
int now=++size;
len[now]=v;
return now;
}
void insert(int data) {
s[++n]=data;
int p=last;
while(s[n-len[p]-1]!=s[n])p=next[p];
if(!child[p][data]) {
int now=newnode(len[p]+2),q=next[p];
while(s[n-len[q]-1]!=s[n])q=next[q];
next[now]=child[q][data];
child[p][data]=now;
diff[now]=len[now]-len[next[now]];
snext[now]=diff[now]==diff[next[now]]?snext[next[now]]:next[now];
}
last=child[p][data];
}
} pam;
char s[maxn],tmp[maxn];
int n;
int f[maxn],series[maxn];
void add(int &x,int v) {
x+=v;
if(x>=mod)x-=mod;
}
int main() {
scanf("%s",tmp+1);
n=strlen(tmp+1);
for(int i=1; i<=(n>>1); i++)s[(i<<1)-1]=tmp[i];
for(int i=1; i<=(n>>1); i++)s[i<<1]=tmp[n-i+1];
f[0]=1;
for(int i=1; i<=n; i++) {
pam.insert(s[i]-'a');
for(int v=pam.last; pam.len[v]>0; v=pam.snext[v]) {
series[v]=f[i-(pam.len[pam.snext[v]]+pam.diff[v])];
if(pam.diff[v]==pam.diff[pam.next[v]])add(series[v],series[pam.next[v]]);
add(f[i],series[v]);
}
if(i&1)f[i]=0;
}
printf("%d\n",f[n]);
return 0;
}
0%