【Codeforces Round #336】

  感觉当题解翻译工挺不错的。

【A.Chain Reaction】

  一个很基础的DP，设f[i]表示不考虑右边光塔的情况下，坐标<=i的光塔最多保留多少个。i上有光塔则f[i]=f[i-1]，否则f[i]=f[i-b[i]-1]+1。答案为max{n-f[i]}

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000010;

int f[maxn],d[maxn];
int n,dis,ans;

int main()
{
	scanf("%d",&n);
	for (int i=1,a,b;i<=n;i++) scanf("%d%d",&a,&b),d[a+1]=b,dis=max(dis,a+1);
	for (int i=1;i<=dis;i++) if (!d[i]) f[i]=f[i-1];
	else f[i]=f[max(i-d[i]-1,0)]+1,ans=max(ans,f[i]);
	printf("%d\n",n-ans);
	return 0;
}

【B.Zuma】

  首先可以看出这是一个区间DP，设f[i][j]表示消除第i~j个珠子需要最少几次。边界情况：f[i][i]=1；f[i][j]=0(i>j)

  然后DP(i,j)时分三种情况：

    1.单独消去第i个珠子：f[i][j]=f[i+1][j]+1；

    2.消去第i个与第i+1个珠子（条件是c[i]==c[i+1）：f[i][j]=f[i+2][j]+1；

    3.消去第i~k个珠子（i+2<=k<=j，条件是c[i]==c[k]）：f[i][j]=f[i+1][k-1]+f[k+1][j]；（即消除区间i+1~k-1里的珠子时一起消去第i个与第k个珠子）

  DP一遍即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=510;

int f[maxn][maxn];
int c[maxn];
int n;

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&c[i]);
	for (int i=1;i<=n;i++) f[i][i]=1;
	for (int i=n-1;i>=1;i--)
	for (int j=i+1;j<=n;j++)
	{
		f[i][j]=1+f[i+1][j];
		if (c[i]==c[i+1]) f[i][j]=min(f[i][j],1+f[i+2][j]);
		for (int k=i+2;k<=j;k++) if (c[i]==c[k]) f[i][j]=min(f[i][j],f[i+1][k-1]+f[k+1][j]);
	}
	printf("%d\n",f[1][n]);
	return 0;
}

【C.Marbles】

  将其中一个字符串中所有的字符反向（即'W'->'E','N'->'S'这样），如果两个字符串有长度相等、翻转后完全相同的后缀，那么答案为"No"。

  具体证明：还在看← ←

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1000010;

char a[maxn],b[maxn];
int next[maxn];
int n,match;

char Change(char ch) {if (ch=='W') return 'E';else if (ch=='E') return 'W';else if (ch=='N') return 'S';else if (ch=='S') return 'N';}

int main()
{
	scanf("%d",&n);n--;
	scanf("%s%s",a+1,b+1);
	for (int i=1;i<=n;i++) b[i]=Change(b[i]);
	reverse(a+1,a+1+n);
	next[0]=-1;
	for (int i=2,j=0;i<=n;next[i++]=++j) while (j>=0 && a[j+1]!=a[i]) j=next[j];
	for (int i=1;i<=n;i++,match++) while (match>=0 && a[match+1]!=b[i]) match=next[match];
	if (match) puts("NO");else puts("YES");
	return 0;
}

【D.Power Tree】

  先不要管操作顺序，把整棵树事先建出来，初始值为0，用它的DFS序建线段树（这么做的目的是为了对整棵子树进行维护）。

  先考虑只询问根节点的情况。容易发现每个节点对答案的贡献的形式是v[x]*m[x]，我们要维护的就是这个m。

  每次将一个点y连接为x的子节点时，m[x]*=(d[x]+2)/(d[x]+1)，子树中所有节点的m都乘上这个值。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=200010,mod=1e9+7;

struct Querys {int type;int x;}Q[maxn];

struct Segment_Tree
{
	LL w[maxn<<2],m[maxn<<2];
	LL tagm[maxn<<2];
	LL sum[maxn<<2];
	int n;

	#define ls (o<<1)
	#define rs ((o<<1)|1)
	#define mid ((l+r)>>1)

	void Update(int o) {sum[o]=(sum[ls]+sum[rs])%mod;}
	
	void Mark_Mul(int o,LL mul) {(m[o]*=mul)%=mod;(sum[o]*=mul)%=mod;(tagm[o]*=mul)%=mod;}

	void Push_Down(int o)
	{
		if (tagm[o]>1)
		{
			Mark_Mul(ls,tagm[o]);
			Mark_Mul(rs,tagm[o]);
			tagm[o]=1;
		}
	}

	void Active(int o,int l,int r,int x,LL mx)
	{
		if (l==r) {m[o]=mx;sum[o]=w[o]*m[o]%mod;return;}
		Push_Down(o);
		if (x<=mid) Active(ls,l,mid,x,mx);
		else Active(rs,mid+1,r,x,mx);
		Update(o);
	}

	void Build(int o,int l,int r,LL *temp)
	{
		if (l==r) {w[o]=temp[l];m[o]=0;tagm[o]=1;sum[o]=0;return;}
		tagm[o]=1;
		Build(ls,l,mid,temp);
		Build(rs,mid+1,r,temp);
	}

	LL Getm(int o,int l,int r,int x)
	{
		if (l==r) return m[o];
		Push_Down(o);
		LL res=0;
		if (x<=mid) res=Getm(ls,l,mid,x);
		else res=Getm(rs,mid+1,r,x);
		Update(o);
		return res;
	}

	void Change(int o,int l,int r,int a,int b,LL mx)
	{
		if (a<=l && r<=b) {Mark_Mul(o,mx);return;}
		Push_Down(o);
		if (a<=mid) Change(ls,l,mid,a,b,mx);
		if (b> mid) Change(rs,mid+1,r,a,b,mx);
		Update(o);
	}

	LL Query(int o,int l,int r,int a,int b)
	{
		if (a<=l && r<=b) return sum[o];
		Push_Down(o);
		LL res=0;
		if (a<=mid) res+=Query(ls,l,mid,a,b);
		if (b> mid) res+=Query(rs,mid+1,r,a,b);
		return res%mod;
	}

	void Active(int x,LL mx) {Active(1,1,n,x,mx);}
	LL Getm(int x) {return Getm(1,1,n,x);}
	void Change(int a,int b,LL mx) {Change(1,1,n,a,b,mx);}
	LL Query(int a,int b) {return Query(1,1,n,a,b);}
}T;

int n,m;
int head[maxn],next[maxn<<1],E[maxn<<1],Ecnt;
int q[maxn],ql[maxn],qr[maxn],dfscnt;
int d[maxn];
LL inv[maxn];
LL temp[maxn],temp2[maxn];

LL getinv(LL x) {LL res=1,p=mod-2;while (p) {if (p&1) (res*=x)%=mod;(x*=x)%=mod;p>>=1;}return res;}
void Add_Edge(int x,int y) {next[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;next[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;}

void DFS(int x,int father)
{
	ql[x]=++dfscnt;
	q[dfscnt]=x;
	for (int i=head[x];i;i=next[i]) if (E[i]!=father) DFS(E[i],x);
	qr[x]=dfscnt;
}

void Build()
{
	DFS(1,0);
	for (int i=1;i<=n;i++) ql[q[i]]=i;
	T.n=n;
	for (int i=1;i<=n;i++) temp2[i]=temp[q[i]];
	T.Build(1,1,n,temp2);
	T.Active(ql[1],1ll);
}

void Init()
{
	n=1;
	scanf("%I64d%d",&temp[1],&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%d",&Q[i].type);
		if (Q[i].type==1) scanf("%d%I64d",&Q[i].x,&temp[++n]),Add_Edge(Q[i].x,n);else scanf("%d",&Q[i].x);
	}
	Build();
	inv[1]=1ll;
	for (int i=2;i<=n+1;i++) inv[i]=(LL)(mod-mod/i)*inv[mod%i]%mod;
}

void Work()
{
	for (int i=1,fa=Q[1].x,cnt=1;i<=m;fa=Q[++i].x)
	if (Q[i].type==1)
	{
		d[fa]++;cnt++;
		T.Active(ql[cnt],T.Getm(ql[fa]));
		T.Change(ql[fa],qr[fa],(d[fa]+1ll)*inv[d[fa]]%mod);
	}
	else printf("%I64d\n",T.Query(ql[fa],qr[fa])*((d[fa]+1ll)*getinv(T.Getm(ql[fa]))%mod)%mod);
}

int main()
{
	Init();
	Work();
	return 0;
}