9.9 牛客提高集训营1

目录

2018.9.9 牛客提高集训营1

时间：3.5h(实际)
实际得分：40+95+0

T1枚举区间求个中位数60分，写得好就是80分啊。我怎么想的→_→。。
T3又T又MLEsmg。虽然是个树剖+线段树+二分+bitset，但还是靠谱(不至于MLE)的吧。。莫名死循环...?

比赛链接

A 中位数(前缀和 二分)

题目链接

假设可能的答案为x，那么把>=x的数设为1，<x的数设为0，如果存在一个区间的和>0(si-sj>0)，则这个x合法。
于是我们可以二分x，求前缀和并维护最小的sj。
这个x只是检验是否存在>=x的答案，不是判x这个数是否可能为答案，所以是对的啊。

#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
const int N=1e5+5;

int n,L,ref[N],A[N],s[N];
char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
inline bool Check(int x)
{
	for(int i=1,mn=N; i<=n; ++i)
	{
		s[i]=s[i-1]+(A[i]>=x?1:-1);
		if(i>L) mn=std::min(mn,s[i-L]);
		if(s[i]>mn) return 1;
	}
	return 0;
}

int main()
{
	n=read(),L=read();
	for(int i=1; i<=n; ++i) ref[i]=A[i]=read();
	std::sort(ref+1,ref+1+n);
	int l=1,r=n,mid,ans=1;
	while(l<=r)
		if(Check(ref[mid=l+r>>1])) ans=mid,l=mid+1;
		else r=mid-1;
	printf("%d
",ref[ans]);

	return 0;
}

B 数数字(数位DP)

题目链接

/*
数位DP。发现可能的乘积数非常少，就...直接做了。
所有乘积都可以表示成2^{k1}*3^{k2}*5^{k3}*7^{k4}，状态同样有限，于是也可以DP转移每一位。
*/
#include <map>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define gc() getchar()
typedef long long LL;
const int N=20;

int cnt,bit[N],tot;
LL pw[N],f[N][50000];
bool vis[N][50000];
std::map<LL,bool> vis1,vis2[20];
std::unordered_map<LL,int> ref;

inline LL read()
{
	LL now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
void preDFS(int x,LL s)
{
	if(vis2[x][s]) return;
	vis2[x][s]=1;
	if(!x)
	{
		if(!ref[s]) ref[s]=++tot;
		return;
	}
	for(int i=1; i<=9; ++i) preDFS(x-1,s*i);
}
LL DFS(int x,bool lead,bool lim,LL s,LL L,LL R)
{
//	if(s>R) return 0;//R=0就不对啊 后面还可能*0。(其实判下R=0就可以了。反正跑得很快)
	if(x/*not最后一位!*/&&lead) s=1;
	if(!s&&L) return 0;
	if(s*pw[x]<L) return 0;
	if(!x) return s<=R;

	int id=ref[s];// printf("ref[%I64d]=%d
",s,id);
	if(!lim && !lead && vis[x][id]) return f[x][id];
	int up=lim?bit[x]:9; LL res=0;
	for(int i=0; i<=up; ++i)
		res+=DFS(x-1,!i&&lead,i==up&&lim,s*i,L,R);
	if(!lim && !lead) vis[x][id]=1, f[x][id]=res;
	return res;
}
LL Calc(LL x,LL l,LL r)
{
	if(x<0) return 0;
	if(!x) return !l;
	memset(vis,0,sizeof vis);
	for(cnt=0; x; x/=10) bit[++cnt]=x%10;
	return DFS(cnt,1,1,0,l,r);
}

int main()
{
	ref[0]=++tot, preDFS(18,1);// printf("%d
",tot);
	pw[0]=1;
	for(int i=1; i<=19; ++i) pw[i]=pw[i-1]*9ll;

	LL L=read(), R=read(), L1=read(), R1=read();
	std::cout << Calc(R,L1,R1)-Calc(L-1,L1,R1) << '
';

	return 0;
}/*
1 1000000000000000000 1 1000000000000000000
0 1 0 0
0 1 1 2
1 10000 0 0
*/

C 保护(标记 线段树合并)

题目链接

把每条链(x,y)拆成(x,lca)与(y,lca)。
对于一条链(x,w)(w=lca(x,y))，一条要判断的路径(u,v)(dep[u]>dep[v])，(x,w)完全覆盖(u,v)当且仅当x在u的子树内且y在点v或v的子树外（w在点v或v之上）。
怎么尽快判断呢。在x处打dep[w]的标记，那么覆盖(u,v)的链数就是u子树内<=dep[v]的标记数。
查子树内<=x的数的个数，可以线段树然后线段树合并。
发现询问其实就是找深度最小的k个标记，直接查第k小就行了，不需要枚举或者二分v。

#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 200000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define Bit std::bitset<N>
const int N=2e5+5;

int n,m,root[N],Enum,H[N],nxt[N<<1],to[N<<1],dep[N],fa[N],sz[N],son[N],top[N];
char IN[MAXIN],*SS=IN,*TT=IN;
struct Segment_Tree
{
	#define S N*70
	#define lson son[x][0]
	#define rson son[x][1]
	int tot,sz[S],son[S][2];

	void Insert(int &x,int l,int r,int p)
	{
		if(!x) x=++tot; ++sz[x];
		if(l==r) return;
		int m=l+r>>1;
		if(p<=m) Insert(lson,l,m,p);
		else Insert(rson,m+1,r,p);
	}
	int Merge(int x,int y)
	{
		if(!x||!y) return x^y;
		int now=++tot;//不能直接改x！x可能是之前子树里的点，还要单独用到不能覆盖。
		son[now][0]=Merge(lson,son[y][0]), son[now][1]=Merge(rson,son[y][1]);
		sz[now]=sz[x]+sz[y]; return now;
	}
	int Query(int x,int l,int r,int k)
	{
		if(k>sz[x]) return N/*MAX*/;
		if(l==r) return l;//l is a dep
		if(sz[lson]>=k) return Query(lson,l,(l+r)>>1,k);
		else return Query(rson,(l+r>>1)+1,r,k-sz[lson]);
	}
}T;

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
inline void AE(int u,int v)
{
	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
}
inline int LCA(int u,int v)
{
	while(top[u]!=top[v]) dep[top[u]]>dep[top[v]]?u=fa[top[u]]:v=fa[top[v]];
	return dep[u]<dep[v]?u:v;
}
void DFS1(int x)
{
	int mx=0; sz[x]=1;
	for(int i=H[x],v; i; i=nxt[i])
		if((v=to[i])!=fa[x])
		{
			fa[v]=x, dep[v]=dep[x]+1, DFS1(v), sz[x]+=sz[v];
			if(sz[v]>mx) mx=sz[v], son[x]=v;
		}
}
void DFS2(int x,int tp)
{
	top[x]=tp;
	if(son[x])
	{
		DFS2(son[x],tp);
		for(int i=H[x]; i; i=nxt[i])
			if(to[i]!=fa[x]&&to[i]!=son[x]) DFS2(to[i],to[i]);
	}
}
void DFS3(int x,int f)//合并一次 
{
	for(int i=H[x]; i; i=nxt[i])
		if(to[i]!=f) DFS3(to[i],x), root[x]=T.Merge(root[x],root[to[i]]);
}

int main()
{
	n=read(),m=read();
	for(int i=1; i<n; ++i) AE(read(),read());
	dep[1]=1, DFS1(1), DFS2(1,1);
	for(int i=1,u,v,w; i<=m; ++i)
		u=read(),v=read(),w=LCA(u,v),T.Insert(root[u],1,n,dep[w]),T.Insert(root[v],1,n,dep[w]);
	DFS3(1,1);
	for(int i=1,u,q=read(); i<=q; ++i)
		u=read(),printf("%d
",std::max(0,dep[u]-T.Query(root[u],1,n,read())));

	return 0;
}

考试代码

A

#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 300000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
const int N=1e5+5;

int n,L,cnt,ref[N],A[N],tm[N];
char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
inline int Find(int x)
{
	int l=1,r=cnt,mid;
	while(l<r)
		if(ref[mid=l+r>>1]<x) l=mid+1;
		else r=mid;
	return l;
}
namespace Subtask1
{
	bool Check(int x)
	{
		int l=L-1;
		for(int i=1; i+l<=n; ++i)
		{
			int t=0,len=l+2; bool f=0;
			for(int j=i; j<i+l; ++j)
				if(A[j]>=x) ++t, (!f&&A[j]==x)&&(f=1);
			for(int j=i+l; j<=n; ++j)
			{
				++len;
				if(A[j]>=x) ++t, (!f&&A[j]==x)&&(f=1);
				if(f && t>=(len>>1)) return 1;
			}
		}
		return 0;
	}
	void Main()
	{
		if(n<=700)
		{
			for(int i=cnt; i; --i) if(Check(i)) return (void)printf("%d
",ref[i]);
			putchar('0'); return;
		}
		int l=1,r=cnt,mid,ans=1;
		while(l<=r)
			if(Check(mid=l+r>>1)) ans=mid,l=mid+1;
			else r=mid-1;
		printf("%d
",ref[ans]);
	}
}

int main()
{
	n=read(),L=read();
	for(int i=1; i<=n; ++i) ref[i]=A[i]=read();
	std::sort(ref+1,ref+1+n); cnt=1;
	for(int i=2; i<=n; ++i) if(ref[i]!=ref[i-1]) ref[++cnt]=ref[i];
	for(int i=1; i<=n; ++i) A[i]=Find(A[i]);

	if(n<=3000||1) return Subtask1::Main(),0;
	

	return 0;
}

C

#include <cstdio>
#include <cctype>
#include <bitset>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 200000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define Bit std::bitset<N>
const int N=10005;//2e5+5;

int n,m,Enum,H[N],nxt[N<<1],to[N<<1],dep[N],fa[N],sz[N],son[N],top[N],in[N],ref[N],Index;
char IN[MAXIN],*SS=IN,*TT=IN;
struct Segment_Tree
{
	#define ls rt<<1
	#define rs rt<<1|1
	#define lson l,m,rt<<1
	#define rson m+1,r,rt<<1|1
//	int cover[N<<2];//~~标记永久化...?~~
	std::bitset<N> bt[N<<2];
	void Update(int l,int r,int rt,int L,int R,int id)
	{
//		++sum[rt];
		if(L<=l && r<=R) {bt[rt][id]=1; return;}
		int m=l+r>>1;
		if(L<=m) Update(lson,L,R,id);
		if(m<R) Update(rson,L,R,id);
	}
	Bit Query(int l,int r,int rt,int L,int R)
	{
		if(L<=l && r<=R) return bt[rt];
		int m=l+r>>1;
		if(L<=m)
			if(m<R) return Query(lson,L,R)&Query(rson,L,R);
			else return Query(lson,L,R);
		return Query(rson,L,R);
	}
//	int Query(int l,int r,int rt,int L,int R)
//	{
//		if(L<=l && r<=R) return l==L&&r==R?cover[rt]:0;
//		int m=l+r>>1;
//		if(L<=m)
//			if(m<R) return cover[rt];
//			else return cover[rt]+Query(lson,L,R);
//		return cover[rt]+Query(rson,L,R);
//	}
}T;

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
inline void AE(int u,int v)
{
	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
}
void DFS1(int x)
{
	int mx=0; sz[x]=1;
	for(int i=H[x],v; i; i=nxt[i])
		if((v=to[i])!=fa[x])
		{
			fa[v]=x, dep[v]=dep[x]+1, DFS1(v), sz[x]+=sz[v];
			if(sz[v]>mx) mx=sz[v], son[x]=v;
		}
}
void DFS2(int x,int tp)
{
	ref[in[x]=++Index]=x, top[x]=tp;
	if(son[x])
	{
		DFS2(son[x],tp);
		for(int i=H[x]; i; i=nxt[i])
			if(to[i]!=fa[x]&&to[i]!=son[x]) DFS2(to[i],to[i]);
	}
}
void Update(int u,int v,int id)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]]) std::swap(u,v);
		T.Update(1,n,1,in[top[u]],in[u],id), u=fa[top[u]];
	}
	if(dep[u]>dep[v]) std::swap(u,v);
	T.Update(1,n,1,in[u],in[v],id);
}
int Query(int u,int k)
{
	if(k>m) return 0;
	int d=dep[u];
	Bit now,tmp; now.set();
	while(u)//1
	{
		tmp=now&T.Query(1,n,1,in[top[u]],in[u]);
		if(tmp.count()<k)
		{
			int l=in[top[u]],r=in[u],mid;
			while(l<r)
			{
				mid=l+r>>1, tmp=now&T.Query(1,n,1,mid,in[u]);
				if(tmp.count()>=k) l=mid;
				else r=mid-1;
			}
			u=ref[l]; break;
		}
		now=tmp, u=fa[top[u]];
	}
	return d-dep[u];
}

int main()
{
	n=read(),m=read();
	for(int i=1; i<n; ++i) AE(read(),read());
	DFS1(1), DFS2(1,1);
	for(int i=0,u,v; i<m; ++i) Update(read(),read(),i);
	int Q=read();
	for(int i=1,u; i<=Q; ++i) u=read(),printf("%d
",Query(u,read()));

	return 0;
}
------------------------------------------------------------------------------------------------------------------------
无心插柳柳成荫才是美丽
有哪种美好会来自于刻意
这一生波澜壮阔或是不惊都没问题
只愿你能够拥抱那种美丽
------------------------------------------------------------------------------------------------------------------------
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/SovietPower/p/9614827.html