[NOIP2018模拟赛10.19]只会暴力报告

闲扯

今天又是暴力满满(并不)的一天呢

昨天老师说了分数要正态分布,今天看起来...不过暴力分很多,虽然我人太傻逼又没打满

T1 woc?不是说送分的吗,看起来又是个树形DP神题,暴力告辞,链上的搞一搞

T2 woc?又是树纪中这么喜欢出图/树题的吗?第一眼暴力dij告辞

T3 woc?又又又是树?!看起来十分码农?!部分分还好很多,想到昨天老师提到了天天爱跑步的例子,感觉可以搞一搞...于是就开始爆肝了...结果期望30分开了个fread爆0了

\(30+30+0\)凉凉,T2堆改成\(paring\)_\(heap\)就50了,辣鸡STL.虽然有一个更优的暴力...

T1 lkf

又是道神奇树形DP,分析先咕会

懒得写了,看代码注释吧...

这道题好题啊

学会两个技巧

对于差值恰为\(k\)的毒瘤限制,转化为小于等于\(k\)的限制,答案就是小于等于k的减去小于等于k-1的
对于可能重复计算的状态强制安排一个顺序,如dfs序之类的防止算重

/*

  code by RyeCatcher

*/

inline char gc(){

    static char buf[SIZE],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;

}

#define gc getchar

template <class T>inline void read(T &x){

    x=0;int ne=0;char c;

    while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;

    while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;

}

const int maxn=3335;

const int inf=0x7fffffff;

const int P=19260817;

struct Edge{

	int ne,to;

}edge[maxn<<1];

int h[maxn],num_edge=1;

inline void add_edge(int f,int to){

	edge[++num_edge].ne=h[f];

	edge[num_edge].to=to;

	h[f]=num_edge;

}

int n,k,w[maxn],mx=-inf;

int id,o,lim;

ll f[maxn][maxn];

ll ans=0;

void dfs(int now,int fa){

	int v;ll p=1;

	//printf("%d %d\n",now,fa);

	for(ri i=h[now];i;i=edge[i].ne){

		v=edge[i].to;

		if(v==fa)continue;

		if(w[v]>=o&&w[v]<=o+lim&&(w[v]!=o||(w[v]==o&&v>id))){//前两个限制是因为状态的设计本身,第三个限制是防止联通块算重,如果还有一个点值为枚举的最小值,我们可能已经计算了那个联通块的个数

          //于是我们强制安排一个顺序使得不重不漏

			dfs(v,now);

			p=p*(f[v][lim]+1)%P;//乘法原理,连上v贡献为f[v][lim] 否则为1

		}

	}

	f[now][lim]=p;

	return ;

}

int main(){

	int x,y;

	read(n),read(k);

	for(ri i=1;i<=n;i++){

		read(w[i]);

	}

	for(ri i=1;i<n;i++){

		read(x),read(y);

		add_edge(x,y);

		add_edge(y,x);

	}

	for(ri i=1;i<=n;i++){

		o=w[i],id=i,lim=k;

		dfs(i,0);

		if(k==0){

			ans=(ans+f[i][k])%P;//f[i][k]表示最小值为i,最大值与最小值之差小于等于k的不同联通块

		}

		else{

			lim=k-1;

			dfs(i,0);

			ans=(ans+(f[i][k]-f[i][lim])%P+P)%P;//显然f[i]][k]-f[i][k-1]即为差值刚好为k的联通块个数

		}

	}

	printf("%lld\n",ans%P);

	return 0;

}

T2 worry

有个性质就是因为你树上边随便走,你断掉一条树边后你最多走一条非树边。\(naiive\)的做法就是枚举了,有没有更高明的呢?

我们边从小到大排序,发现对于边\((x,y)\),它影响\((x,y)\)路径上的边(也就是断掉路径上的任何一条边还可以通过\((x,y)\)联通),也就是\(x,y\)分别到\(lca(x,y)\)路径上的

树链剖分

那么链剖就可以搞喽,线段树维护一个永久标记,如果有标记了也不管(因为边权从小到大排序)

跑得还挺快

/*

  code by RyeCatcher

*/

inline char gc(){

    static char buf[SIZE],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;

}

template <class T>inline void read(T &x){

    x=0;int ne=0;char c;

    while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;

    while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;

}

const int maxn=200005;

const int inf=0x7fffffff;

int n,m;

struct Edge{

	int ne,to;

	ll dis;

}edge[maxn<<1];

int h[maxn],num_edge=1;

inline void add_edge(int f,int to,ll c){

	edge[++num_edge].ne=h[f];

	edge[num_edge].to=to;

	edge[num_edge].dis=c;

	h[f]=num_edge;

}

pair<int,int> qwq[maxn];

struct Niconiconi{

	int x,y;

	ll dis;

	Niconiconi(){x=y=dis=0;}

	Niconiconi(int _x,int _y,ll _c){x=_x,y=_y,dis=_c;}

	bool operator <(const Niconiconi &rhs)const{

		return dis<rhs.dis;

	}

}con[maxn<<1];

int dep[maxn],fa[maxn],son[maxn],size[maxn],top[maxn],dfn[maxn],rnk[maxn],tot=0;

void dfs1(int now){

	int v;

	size[now]=1;

	//printf("%d %d\n",now,fa[now]);

	for(ri i=h[now];i;i=edge[i].ne){

		v=edge[i].to;

		if(v==fa[now])continue;

		dep[v]=dep[now]+1,fa[v]=now;

		dfs1(v);

		size[now]+=size[v];

		if(!son[now]||size[son[now]]<size[v])son[now]=v;

	}

	return ;

}

void dfs2(int now,int t){

	int v;

	top[now]=t,dfn[now]=++tot,rnk[tot]=now;

	if(!son[now])return ;

	dfs2(son[now],t);

	for(ri i=h[now];i;i=edge[i].ne){

		v=edge[i].to;

		if(v==fa[now]||v==son[now])continue;

		dfs2(v,v);

	}

	return ;

}

int tag[maxn<<2],w[maxn];

int L,R,dta;

inline void pushdown(int now){

	if(!tag[now<<1])tag[now<<1]=tag[now];//tag[now<<1|1]=tag[now];

	if(!tag[now<<1|1])tag[now<<1|1]=tag[now];

}

void update(int now,int l,int r){

	if(tag[now])return ;

	if(L<=l&&r<=R){

		tag[now]=dta;

		return ;

	}

	int mid=(l+r)>>1;

	pushdown(now);

	if(L<=mid&&!tag[now<<1])update(now<<1,l,mid);

	if(mid<R&&!tag[now<<1|1])update(now<<1|1,mid+1,r);

	return ;

}

void ahaha(int now,int l,int r){

	if(l==r){

		if(tag[now])w[rnk[l]]=tag[now];

		else w[rnk[l]]=-1;

		return ;

	}

	int mid=(l+r)>>1;

	pushdown(now);

	ahaha(now<<1,l,mid);

	ahaha(now<<1|1,mid+1,r);

	return ;

}

inline void update_path(int x,int y){

	while(top[x]!=top[y]){

		if(dep[top[x]]<dep[top[y]])std::swap(x,y);

		L=dfn[top[x]],R=dfn[x];

		update(1,1,n);

		x=fa[top[x]];

	}

	if(dep[x]>dep[y])std::swap(x,y);

	L=dfn[x]+1,R=dfn[y];

	//printf("--%d %d--\n",rnk[L],rnk[R]);

	if(L>R)return ;

	update(1,1,n);

}

int main(){

	int x,y;ll z;

	FO(worry);

	read(n),read(m);

	for(ri i=1;i<n;i++){

		read(x),read(y);

		add_edge(x,y,0);

		add_edge(y,x,0);

		qwq[i]=pair<int,int>(x,y);

	}

	for(ri i=1;i<=m;i++){

		read(x),read(y),read(z);

		con[i]=Niconiconi(x,y,z);

	}

	std::sort(con+1,con+1+m);

	dep[1]=0,fa[1]=0;

	dfs1(1);

	dfs2(1,1);

	memset(tag,0,sizeof(tag));

	for(ri i=1;i<=m;i++){

		x=con[i].x,y=con[i].y,dta=con[i].dis;

		update_path(x,y);

	}

	ahaha(1,1,n);

	for(ri i=1;i<n;i++){

		x=qwq[i].first,y=qwq[i].second;

		if(dep[x]<dep[y])std::swap(x,y);

		printf("%d\n",w[x]);

	}

	return 0;

}

并查集

题解是更高明的并查集做法,我还是Too Young Too Simple,只会SB暴力树剖

每个点指向下一个没被打标记的点\(nxt[x]\)(以点代边),显然这是可传递的

这样的话每次查询直接往上跳就好了,连LCA都不用求

居然跑到rank1哈哈

/*

  code by RyeCatcher

*/

inline char gc(){

    static char buf[SIZE],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;

}

#define gc getchar

template <class T>inline void read(T &x){

    x=0;int ne=0;char c;

    while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;

    while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;

}

const int maxn=100005;

const int inf=0x7fffffff;

int n,m;

struct Edge{

	int ne,to;

}edge[maxn<<1];

int h[maxn],num_edge=1;

inline void add_edge(int f,int to){

	edge[++num_edge].ne=h[f];

	edge[num_edge].to=to;

	h[f]=num_edge;

}

struct Niconiconi{

	int x,y,z;

	bool operator <(const Niconiconi &qwq)const{

		return z<qwq.z;

	}

}nico[maxn];

int ans[maxn],dep[maxn],fa[maxn],nxt[maxn],fa_id[maxn];

int get(int x){return (nxt[x]==x)?nxt[x]:nxt[x]=get(nxt[x]);}

void dfs(int now){

	int v;

	for(ri i=h[now];i;i=edge[i].ne){

		if((v=edge[i].to)==fa[now])continue;

		fa[v]=now,dep[v]=dep[now]+1,fa_id[v]=i;

		dfs(v);

	}

	return ;

}

int main(){

	int x,y,z,p;

	FO(worry);

	read(n),read(m);nxt[n]=n;

	for(ri i=1;i<n;i++){

		read(x),read(y);

		add_edge(x,y),add_edge(y,x);

		nxt[i]=i;

	}

	for(ri i=1;i<=m;i++){

		read(nico[i].x),read(nico[i].y),read(nico[i].z);

	}

	std::sort(nico+1,nico+1+m);

	fa[1]=0,dfs(1);

	for(ri i=1;i<=m;i++){

		x=get(nico[i].x),y=get(nico[i].y),z=nico[i].z;

		while(x!=y){

			if(dep[x]<dep[y])std::swap(x,y);

			ans[fa_id[x]]=z;

			nxt[x]=x=get(fa[x]);

		}

	}

	p=2*n;

	for(ri i=2;i<p;i+=2){

		printf("%d\n",ans[i]?ans[i]:(ans[i^1]?ans[i^1]:-1));

	}

	return 0;

}

巴特西

[NOIP2018模拟赛10.19]只会暴力报告

闲扯

T1 lkf

T2 worry

树链剖分

并查集

最新文章

热门文章