4
27
2016
2

论逗逼的自我修养之ZJOI2016D2

第二次场外鏼题..感觉ZJOI的题比HNOI的题高明到不知道哪里去了啊..

题面戳这里:http://pan.baidu.com/s/1c1TdinA

【D2T1】大森林

首先可以发现第二种操作中生长节点不存在就不动这个条件是没用的,因为只要和插入节点[tex]x[/tex]的区间求一下交就好了。

对于第[tex]i[/tex]棵森林,我们把所有影响到它的修改操作(前两种操作)按照顺序写下来,我们发现每一个插入节点操作的父亲是这次操作前第一个修改生长节点位置的操作。

我们按照下标顺序扫过每一棵树,每一次把相邻两棵树中不同的操作插入当前的操作序列或者从操作序列中删除。第一种操作(插入操作)的插入删除相当于在树中接上了一个新的叶子节点,第二种操作相当于把编号在某一个区间内的节点的父亲修改成另外一个节点。

这可以用ETT来做,也可以把这棵树以左儿子右兄弟的方式表示,这样就可以用LCT来搞了,不过在求路径长度时要加一些特判。

因为自信出题人不会卡,所以我考场上写的是[tex]O(n^2)[/tex]的LCT,按道理来说应该改成双旋而且每一次递归查询都应该把查询到的点旋转到根。然而实际上出题人的确没有卡。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
struct tree{
	int l,r,w,father,sum;
}t[210000];
int rev[210000],n,m,where[210000],N,L[210000],R[210000],x[210000],pd[210000],ans[210000];
vector<int>u[110000],v[110000],y[110000];
struct atom{
	int where,w;
};
struct ask{
	int where,p,pd;
}A[410000];
set<int>S;
void change(int k1){
	t[k1].sum=t[t[k1].l].sum+t[t[k1].r].sum+t[k1].w;
}
void reverse(int k1){
	rev[k1]^=1; swap(t[k1].l,t[k1].r);
}
void pushdown(int k1){
	if (rev[k1]){
		reverse(t[k1].l); reverse(t[k1].r); rev[k1]=0;
	}
}
void zig(int k){
	int f=t[k].father; pushdown(f); pushdown(k);
	if (t[t[f].father].l==f) t[t[f].father].l=k; else if (t[t[f].father].r==f) t[t[f].father].r=k;
	t[k].father=t[f].father; t[f].l=t[k].r; t[t[f].l].father=f; t[k].r=f; t[f].father=k;
	change(f);
}
void zag(int k){
	int f=t[k].father; pushdown(f); pushdown(k);
	if (t[t[f].father].l==f) t[t[f].father].l=k; else if (t[t[f].father].r==f) t[t[f].father].r=k;
	t[k].father=t[f].father; t[f].r=t[k].l; t[t[f].r].father=f; t[k].l=f; t[f].father=k;
	change(f);
}
int splay_root(int k){
	return t[k].father&&(t[t[k].father].l==k||t[t[k].father].r==k);
}
void splay(int k){
	pushdown(k);
	while (splay_root(k))
		if (t[t[k].father].l==k) zig(k); else zag(k);
	change(k);
}
int access(int k){
	int now=0;
	while (k){
		splay(k); t[k].r=now; now=k; change(k);
		k=t[k].father;
	}
	return now;
}
void makeroot(int k){
	reverse(access(k)); splay(k);
}
void link(int k1,int k2){
	makeroot(k1); t[k1].father=k2;
}
void cut(int k1,int k2){
	makeroot(k1); access(k2); splay(k2);
	t[k1].father=0; t[k2].l=0; change(k2);
}
int compare(ask k1,ask k2){
	return k1.where<k2.where||(k1.where==k2.where&&k1.pd<k2.pd);
}
void change(int k1,int k2){
	makeroot(k1); t[k1].w=k2; change(k1);
}
void delP(int k1){
//	cout<<"delP "<<k1<<endl;
	S.erase(k1); 
	set<int>::iterator k=S.lower_bound(k1);
	int l=-1,r=-1; k1=x[k1];
	if (k!=S.end()&&pd[(*k)]==0) r=(*k);
	k--; l=(*k);
	if (r!=-1) cut(k1,x[r]);
	cut(k1,x[l]);
	if (r!=-1){
		if (pd[l]==0) link(x[l],x[r]);
		else {
			change(x[r],1); link(x[l],x[r]);
		}
	}
}
void insertP(int k1){
//	cout<<"insertP "<<k1<<endl;
	set<int>::iterator k=S.lower_bound(k1);
	int l=-1,r=-1;
	if (k!=S.end()&&pd[(*k)]==0) r=(*k);
	k--; l=(*k); int pre=k1; k1=x[k1];
	t[k1]=(tree){0,0,0,0,0};
	if (pd[l]==1) t[k1].w=1,t[k1].sum=1;
	if (r!=-1){
		cut(x[l],x[r]);
		if (pd[l]==1) change(x[r],0);
		link(k1,x[r]);
	}
	link(x[l],k1); S.insert(pre);
}
void insertO(int k1){
//	cout<<"insertO "<<k1<<endl;
	set<int>::iterator k=S.lower_bound(k1);
	int l=-1,r=-1;
	if (k!=S.end()&&pd[(*k)]==0) r=(*k);
	k--; l=(*k);
	if (r!=-1){
		cut(x[l],x[r]);
		if (pd[l]==0) change(x[r],1);
		link(x[k1],x[r]);
	}
	S.insert(k1);
}
void delO(int k1){
//	cout<<"delO "<<k1<<endl;
	S.erase(k1);
	set<int>::iterator k=S.lower_bound(k1);
	int l=-1,r=-1;
	if (k!=S.end()&&pd[(*k)]==0) r=(*k);
	k--; l=(*k); k1=x[k1];
	if (r!=-1){
		cut(k1,x[r]);
		if (pd[l]==0) change(x[r],0);
		link(x[l],x[r]);
	}
}
int findl(int k1){
	if (k1==0) return 1;
	while (t[k1].l){
		pushdown(k1); k1=t[k1].l;
	}
	return t[k1].w;
}
int findr(int k1){
	if (k1==0) return 1;
	while (t[k1].r){
		pushdown(k1); k1=t[k1].r;
	}
	return t[k1].w;
}
int find(int k1,int k2){
//	cout<<"find "<<k1<<" "<<k2<<endl;
	makeroot(1); access(k1); int k3=access(k2);
	reverse(k3); access(k1); splay(k3);
	int ans=t[k3].sum-t[k3].w;
	int pd=findl(t[k3].r)&findr(t[k3].l);
	if (pd==1) return ans; else return ans+2;
}
void printtree(){
	for (int i=1;i<=N;i++) cout<<t[i].l<<" "<<t[i].r<<" "<<t[i].father<<" "<<t[i].w<<" "<<t[i].sum<<endl;
}
int main(){
	freopen("forest.in","r",stdin);
	freopen("forest.out","w",stdout);
	scanf("%d%d",&n,&m); S.insert(0); N=1; int pre=m; m=0; L[1]=0; R[1]=1e9;
	x[0]=1; pd[0]=1;
	for (int i=1;i<=pre;i++){
		int k1; scanf("%d",&k1);
		if (k1==0){
			int k2,k3;
			scanf("%d%d",&k2,&k3); 
			N++; L[N]=k2; R[N]=k3;
			A[++m]=(ask){k2,i,0};
			A[++m]=(ask){k3+1,i,-4};
			x[i]=N; pd[i]=0;
		} else if (k1==1){
			int k2,k3,k4; scanf("%d%d%d",&k2,&k3,&k4);
			k2=max(k2,L[k4]); k3=min(k3,R[k4]);
			if (k2>k3) continue;
			A[++m]=(ask){k2,i,1};
			A[++m]=(ask){k3+1,i,-5};
			x[i]=k4; pd[i]=1;
		} else if (k1==2){
			int k2,k3,k4; scanf("%d%d%d",&k2,&k3,&k4);
			u[k2].push_back(k3); v[k2].push_back(k4); y[k2].push_back(i);
		}
	}
	sort(A+1,A+m+1,compare); int now=1;
	memset(ans,0xff,sizeof ans);
	for (int i=1;i<=n;i++){
	//	cout<<i<<endl;
		while (now<=m&&A[now].where==i){
			if (A[now].pd==-4) delP(A[now].p);
			else if (A[now].pd==0) insertP(A[now].p);
			else if (A[now].pd==1) insertO(A[now].p);
			else if (A[now].pd==-5) delO(A[now].p);
			now++;
		}
		for (int j=0;j<u[i].size();j++)
			ans[y[i][j]]=find(u[i][j],v[i][j]);
	//	cout<<"solve "<<i<<endl;
	//	printtree();
	}
	for (int i=1;i<=pre;i++) if (ans[i]!=-1) printf("%d\n",ans[i]);
	return 0;
}

【D2T2】线段树

刚才丝薄了,现在更正一下题解。

还是考虑求每一个位置[tex]i[/tex]最后是每一个数[tex]j[/tex]的方案数,我们可以发现DP的状态只有操作次数,这一个位置左边的第一个大于它的数和右边第一个大于它的数,优化一下转移就可以做到每一次[tex]O(n^2q)[/tex]。

然后我们可以发现对于每一个[tex]j[/tex]我们可以一次求出对每一个位置的贡献。因为数据随机,所以每一次DP有用的状态数之和只有[tex]O(n^2q)[/tex],转移可以优化到[tex]O(1)[/tex],所以时间复杂度是[tex]O(n^2q)[/tex]的,时限比较紧,似乎有点卡常数。

随便瞎JB写了一个,常数好像很萎的样子QAQ懒得卡了。

#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int dp[2][410][410],n,Q,x[410],num[410],y[410],a[410],ans[410],way[410][410],A[410][410];
const int mo=1e9+7;
int compare(int k1,int k2){
	return x[k1]<x[k2];
}
void solve(int l,int r,int where){
	int now=0;
	for (int i=l-1;i<=r+1;i++)
		for (int j=l-1;j<=r+1;j++) dp[0][i][j]=0,dp[1][i][j]=0;
	dp[0][l][r]=1;
	for (int k=1;k<=Q;k++){
		int ne=now^1;
		for (int i=l;i<=r;i++){
			long long k1=0;
			for (int j=r;j>=i;j--){
				dp[ne][i][j]=k1%mo; k1=(k1+1ll*dp[now][i][j]*(n-j));
			}
		}
		for (int j=l;j<=r;j++){
			long long k1=0;
			for (int i=l;i<=j;i++){
				dp[ne][i][j]=(dp[ne][i][j]+k1)%mo; k1=(k1+1ll*dp[now][i][j]*(i-1));
			}
		}
		for (int j=l;j<=r;j++)
			for (int i=l;i<=j;i++)
				dp[ne][i][j]=(dp[ne][i][j]+1ll*dp[now][i][j]*A[i][j])%mo;
		now^=1;
	}
	for (int i=l;i<=r;i++){
		int k1=0;
		for (int j=r;j>=i;j--){
			k1=(k1+dp[now][i][j])%mo;
			way[j][y[where]]=(way[j][y[where]]+k1)%mo;
		}
	}
}
int main(){
//	freopen("segment10.in","r",stdin);
//	freopen("segment10.out","w",stdout);
	scanf("%d%d",&n,&Q);
	for (int i=1;i<=n;i++) scanf("%d",&x[i]);
	for (int i=1;i<=n;i++) a[i]=i;
	sort(a+1,a+n+1,compare);
	for (int i=1;i<=n;i++) y[a[i]]=i;
	for (int i=1;i<=n;i++)
		for (int j=i;j<=n;j++) dp[0][i][j]=1;
	for (int i=1;i<=n;i++) num[i]=i*(i+1)/2;
	for (int i=1;i<=n;i++)
		for (int j=i;j<=n;j++) A[i][j]=(num[i-1]+num[j-i+1]+num[n-j]);
	for (int i=1;i<=n;i++){
		int l=i,r=i;
		while (l&&x[l]<=x[i]) l--;
		while (r<=n&&x[r]<=x[i]) r++;
		solve(l+1,r-1,i);
	}
	for (int i=1;i<=n;i++){
		int ans=0;
		for (int j=1;j<=n;j++){
			if (way[i][j]==0) continue;
			for (int k=1;k<j;k++)
				way[i][j]=(way[i][j]-way[i][k])%mo;
			ans=(ans+1ll*x[a[j]]*way[i][j])%mo;
		}
		printf("%d ",(ans+mo)%mo);
	}
	printf("\n");
	return 0;
}

【D2T3】电阻网络

最开始猜了一个结论:一个点对不合法两且仅当它们之间有两条简单路径以相反的方向经过了一条边。

然后根本不会好的判断方法,只会10分爆枚。

后来发现直接按照定义暴力拆就能做到30分(%%%乐滋滋)。

令[tex](s,t)[/tex]表示两个点是否合法,我们先把[tex](s,t)[/tex]之间所有割点删掉,表示串联,拆开的部分都是子问题。如果删不了,就把[tex](s,t)[/tex]删掉,表示并联,拆开的部分也是子问题。暴力递归就好了。

时间复杂度[tex]O(n^2m)[/tex]。

根本不会标算QAQ

Category: 论逗逼的自我修养系列 | Tags: | Read Count: 3297
Avatar_small
浙江蒟蒻 说:
2016年4月29日 03:15

@CreationAugust: 前排%CA娘


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com