Diary of March 15th

3
15
2016

UPD 7:46 马上就要模拟赛了希望这次能考得好一点

UPD 14:20 233感觉博客的保佑非常有效，实力进前十以后也这么干

BZOJ4154

也是一道KD-Tree

先 $O(n)$ 预处理出DFS序和深度，

这样就能知道每个点的子树以及与它的距离

把第 $i$ 个点当做 $(st_i,dep_i)$ 放到平面上

然后每次修改时修改$ \{st_u,dep_u,en_u,dep_u+l\} $这个矩阵内的点就可以了

不过要注意直接找是找不到的

因为深度可能会一样，而 $nth\_element$ 找的不一定是深度一样中最右边那一个

也就是说深度和某个点一样的可能在它的右子树而不是左子树

所以要记录一下编号

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
#define MOD 1000000007
using namespace std;
inline int IN(){
	int x=0,ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=100005;
int D,n,c,q;
struct KDT{
	int d[2],col,lzc,Mn[2],Mx[2],t,lzt,id;
	KDT *Fa,*l,*r;
	bool operator <(const KDT&x)const{return d[D]==x.d[D]?d[D^1]<x.d[D^1]:d[D]<x.d[D];}
}a[N],*R,qry;
int to[N],next[N],head[N],cnt,pos[N];
inline void AddEdge(int u,int v){
	to[cnt]=v;next[cnt]=head[u];head[u]=cnt++;
}
int st[N],en[N],Tm,dep[N];
void DFS(int u){
	st[u]=++Tm;
	Cross(i,u) dep[to[i]]=dep[u]+1,DFS(to[i]);
	en[u]=Tm;
}
void Update(KDT *x,KDT *y){
	if (!y) return;
	Rep(i,0,1)
		x->Mn[i]=min(x->Mn[i],y->Mn[i]),
		x->Mx[i]=max(x->Mx[i],y->Mx[i]);
}
KDT *Build(int l,int r,int nd,KDT *f){
	if (r<l) return 0;
	D=nd;int mid=l+r>>1;
	nth_element(a+l,a+mid,a+r+1);
	a[mid].col=a[mid].lzc=1;
	pos[a[mid].id]=mid;
	Rep(i,0,1) a[mid].Mn[i]=a[mid].Mx[i]=a[mid].d[i];
	a[mid].Fa=f;
	a[mid].l=Build(l,mid-1,nd^1,a+mid);
	a[mid].r=Build(mid+1,r,nd^1,a+mid);
	Update(a+mid,a[mid].l),Update(a+mid,a[mid].r);
	return a+mid; 
}
int Query(KDT *qry){
	D=0;
	int Mxt=qry->t,ret=qry->col;
	KDT *now=qry;
	while (now->Fa){
		now=now->Fa;
		if (now->lzt>Mxt) Mxt=now->lzt,ret=now->lzc;
		D^=1;
	}
	return ret;
}
void Modify(KDT *u,int X1,int Y1,int X2,int Y2,int col){
	if (!u) return;
	if (u->Mx[0]<X1||u->Mn[0]>X2||u->Mx[1]<Y1||u->Mn[1]>Y2) return;
	if (u->Mn[0]>=X1&&u->Mx[0]<=X2&&u->Mn[1]>=Y1&&u->Mx[1]<=Y2){
		u->lzt=u->t=Tm,u->col=u->lzc=col;
		return;
	}
	if (u->d[0]>=X1&&u->d[0]<=X2&&u->d[1]>=Y1&&u->d[1]<=Y2){u->t=Tm,u->col=col;}
	Modify(u->l,X1,Y1,X2,Y2,col),Modify(u->r,X1,Y1,X2,Y2,col);
}
int main(){
	int T=IN();
	while (T--){
		n=IN(),c=IN(),q=IN();
		memset(head,-1,sizeof head);cnt=0;
		Rep(i,2,n){
			int u=IN();
			AddEdge(u,i);
		}
		Tm=0,dep[1]=1,DFS(1);
		memset(a,0,sizeof a);
		Rep(i,1,n) a[i].d[0]=st[i],a[i].d[1]=dep[i],a[i].id=i;
		R=Build(1,n,0,0);
		Tm=0;
		int Ans=0;
		Rep(i,1,q){
			Tm++;
			int u=IN(),l=IN(),c=IN();
			if (c==0) (Ans+=1ll*Query(a+pos[u])*i%MOD)%=MOD;
				else Modify(R,st[u],dep[u],en[u],dep[u]+l,c);
		}
		OUT(Ans),putchar('\n');
	}
}

Codeforces183D

今天模拟赛出了这道题……离上次做的183E仅仅只有一墙之隔……

然而Dirak说上次我给他说了183E之后他不小心去看了D的题解

好气啊！！！！（虽然也就比我高了10分）

概率DP+贪心

令 $g_{i,j,k}$ 表示当前是第 $i$ 种袜子，问到第 $j$ 个人，初始有 $k$ 双袜子的送出期望

$g_{i,j,k}=(g_{i,j-1,k-1}+1)*a_{j,i}+g_{i,j-1,k}*(1-a_{j,i})$

比较显然的就是同一种袜子，拿得越多与上一次的相差就越小

于是就先预处理出$g_{i,n,1} (1≤i≤m)$

一开始什么都不拿

然后每次把贡献最大那种袜子的加到答案里，更新一下拿下一只这种袜子的贡献

复杂度$O(n^2+n*m)$

需要滚存

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline int IN(){
	int x=0,ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=3005,M=305;
int n,m,p;
double a[N][M],g[M][N][2],Ans;
bool G[M];
int main(){
	n=IN(),m=IN();
	Rep(i,1,n) Rep(j,1,m) a[i][j]=IN()/1000.0;
	Rep(i,1,m) Rep(j,1,n) g[i][j][G[i]]=(g[i][j-1][G[i]^1]+1)*a[j][i]+g[i][j-1][G[i]]*(1-a[j][i]);
	Rep(i,1,n){
		double Mx=0;
		Rep(j,1,m) if (g[j][n][G[j]]-g[j][n][G[j]^1]>Mx) Mx=g[j][n][G[j]]-g[j][n][G[j]^1],p=j;
		Ans+=Mx,G[p]^=1;
		Rep(j,1,n) g[p][j][G[p]]=(g[p][j-1][G[p]^1]+1)*a[j][p]+g[p][j-1][G[p]]*(1-a[j][p]);
	}
	printf("%.15lf\n",Ans);
	return 0;
}

BZOJ1030

为了复习~~（预习？）~~一下AC自动机而做的一道题

答案就是所有可能的文本减去没有单词出现的文本

先构造AC自动机，然后 $dp_{i,j}$ 表示走了 $i$ 步，当前在节点 $j$ 的方案数

搞一搞就好了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define oo (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
#define MOD 10007
using namespace std;
inline int IN(){
	int x=0,ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=65,L=105;
int n,m,Cnt=0,dp[L][L*N];
char s[L];
struct Trie{
	Trie *next[26],*fail;
	bool fin;
}a[N*L],*R;
void Insert(char *s){
	int len=strlen(s);
	Trie *now=a;
	Rep(i,0,len-1){
		if (!now->next[s[i]-'A']) now->next[s[i]-'A']=++Cnt+a;
		now=now->next[s[i]-'A'];
	}
	now->fin=1;
}
queue<Trie*>q;
void Build(){
	Rep(i,0,25){
		Trie *&v=a[0].next[i];
		if (v) v->fail=a,q.push(v);
			else v=a;
	}
	while (!q.empty()){
		Trie *now=q.front();q.pop();
		Rep(i,0,25){
			Trie *&v=now->next[i];
			if (v){
				q.push(v);
				Trie *Fa=now->fail;
				while (Fa!=a&&!Fa->next[i]) Fa=Fa->fail;
				v->fail=Fa->next[i];
				v->fin|=Fa->next[i]->fin;
			}
			else v=now->fail->next[i];
		}
	}
}
int main(){
	n=IN(),m=IN();
	R=a,Cnt=0;
	Rep(i,1,n){
		scanf("%s",s);
		Insert(s);
	}
	Build();
	dp[0][0]=1;
	Rep(i,1,m) Rep(j,0,Cnt){
		if (!dp[i-1][j]||a[j].fin) continue;
		Rep(k,0,25){
			Trie *v=a[j].next[k];
			if (!v->fin) (dp[i][v-a]+=dp[i-1][j])%=MOD;
		}
	}
	int Ans=1;
	Rep(i,1,m) (Ans*=26)%=MOD;
	Rep(i,0,Cnt) if (!a[i].fin) (Ans+=MOD-dp[m][i])%=MOD;
	OUT(Ans); 
}

Category: Diary | Tags: DFS序 kd-tree DP 贪心概率/期望 AC自动机 | Read Count: 545

WTRC's Memory

三世烟火沧笙踏歌