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$是回文的。

题目分析

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

代码

#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$的非零数位相乘结果。

$$g(n)=\begin{cases}n & if\,\,n\lt10 \\ g(f(n)) & otherwise \end{cases}$$

给出$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][]$中。
询问时通过两次二分即可得到答案。

代码

#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$为：

$$f(i,j)=\begin{cases}P[i] & if\,\,j=1 \\ f(P[i],j-1) & otherwise \end{cases}$$

令$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$，即置换：

$$\begin{pmatrix}l & l+1 & l+2 & \cdots & r \\ l+1 & l+2 & l+3 & \cdots & l \end{pmatrix}$$

因此只需要找到一个分界点$i$使得$i\bmod a=0,(n-i)\bmod b=0$，即可构造出解。
如果找不到，输出$-1$。

代码

#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$的序列长度。

代码

#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

题目大意

计算：

$$\sum_{i=0}^n\binom nii^k$$ $$1\le n\le10^9,1\le k\le5000$$

题目分析

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

• 标解
• 解法二
• 解法三
• 解法四
• 解法五
• 解法六

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

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

$$x^k=\sum_{i=0}^k{k \brace i}x^{\underline{i}}$$

故：

$$\begin{aligned} \sum_{i=0}^n\binom nii^k&=\sum_{i=0}^n\binom ni\sum_{j=0}^k{k \brace j}i^{\underline j} \\ &=\sum_{j=0}^k{k \brace j}\sum_{i=0}^n\binom nii^{\underline{j}} \\ &=\sum_{j=0}^k{k \brace j}\sum_{i=0}^n\frac{n!}{i!(n-i)!}\frac{i!}{(i-j)!} \\ &=n!\sum_{j=0}^k{k \brace j}\sum_{i=0}^n\frac{1}{(n-i)!(i-j)!} \\ &=n!\sum_{j=0}^k{k \brace j}\sum_{i=0}^n\binom{n-j}{n-i}\frac{1}{(n-j)!} \\ &=n!\sum_{j=0}^k{k \brace j}\frac{1}{(n-j)!}\sum_{i=0}^n\binom{n-j}{n-i} \\ &=\sum_{j=0}^k{k \brace j}n^{\underline j}\cdot 2^{n-j} \end{aligned}$$

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

代码

#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$跳跃到任意一个叶子结点所需的最小代价。

题目分析

不难列出状态转移方程。

$$f(i)=\min\limits_{j\in t(i),j\neq i}\lbrace f(j)+a_i\times b_j\rbrace$$

转移顺序从下往上。
当然，这样的转移是$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错因：在启发式合并后，需要清空原来儿子的凸包，否则会持续占用内存池，导致空间爆炸。

代码

#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类似问题，使用回文自动机优化动规解决。

代码

#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;
}