8.10 正睿暑期集训营 Day7

目录

• 2018.8.10 正睿暑期集训营 Day7
  • 总结
  • A 花园(思路)
  • B 归来(Tarjan 拓扑)
  • C 机场(凸函数 点分治)
  • 考试代码
    • A
    • B
    • C

---

2018.8.10 正睿暑期集训营 Day7

时间：2.5h(实际)(不行太闲了)

期望得分：...

实际得分：...

比赛链接

总结

倍增！之前还记得怎么又忘了。。

如果可以任意互换位置 具体什么样我们是不关心的。

A 花园(思路)

题目链接

只保留两条边，会剩下一个类似基环内向树的图。

每个点到达P的情况有三种可能：1.永远到不了P；2.只会到1次P；3.在某时刻t到达P，然后每隔时间l到达一次P。2是P在环外，3是P在环上。

对每个点分走最长边和次长边DFS两次，记录它到P的时间dis和到P时朝哪(下一次走最长边还是次长边dir)。可以在O(n)时间内预处理。

然后枚举每个点可以得到某一时刻朝哪到达P的有多少点cnt[t][0/1]，这个用每个点走最长边时算的dis和dir更新。

然后再用P相邻两点的dis,dir得到从P走最长边/次长边多长时间f[0/1]会回到P，及回到P时朝哪g[0/1]。

环长最长应该不超过2n，一个点到P开始循环的时间也不超过2n，所以预处理4n时间内的 某一时刻朝哪到达P的有多少点。可以通过类似DP用f[0/1],g[0/1]转移。

其实只求P所在的那个环或是能到P的点就可以了，建个反图，把每个点的两条出边改成两条入边。

DFS的时候记一下之前走的是最长边还是次长边(原图中x下一步要走最长边还是次长边)，如果是次长边则x只能是从最长边来的(还得会走这条边，即连接点要有这条边)；否则如果dgr[x]>1则可以任意从非x的最长边的边来。

当之前走的是最长边时用此时到P的距离更新cnt[t][0/1]。0/1是确定的，只从P DFS我们可以确定到达P时是朝哪的（下次走最长边还是次长边）。

记环长f[0/1]为len，输出的时候时刻应是。。k%len然后一直加len直到>=2n？。。

但是可以直接 \(k%len+[2n/len]*len\)。。我知道后面是\(n<x\leq 2n\)的，但是如果有个点最初需要\(>[2n/len]*len\)的时间到P，K很大的话不是会算不上这个点吗。。

不懂。。神特么看了1天这个题。

//109ms	13392kb
#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=150005,M=N<<1;

int n,m,P,Enum,H[N],nxt[M],to[M],dir[M],fir[N],dgr[N],len[2],cnt[N<<2][2],sum[N<<2][2];
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;
}
#define AddEdge(u,v,d) to[++Enum]=v,nxt[Enum]=H[u],H[u]=Enum,dir[Enum]=d
void DFS(int x,int dis,bool las,bool direct)//las=0:从x的最长边来(原图中x下一步走最长边)，那么到x的不是x最长边连的点
{
	if(!las) ++cnt[dis][direct];
	for(int v,i=H[x]; i; i=nxt[i])
		if((!las&&((v=to[i])!=fir[x]||dgr[x]==1))||(las&&(v=to[i])==fir[x]))
		{
			if(v==P && dir[i]==direct)//以direct的方向回到P
				len[direct]=dis+1;//不能return，还有其它到x的点要统计！
			else DFS(v,dis+1,dir[i],direct);
		}
}

int main()
{
	n=read(), m=read(), P=read();
	for(int u,v; m--; )
	{
		u=read(), v=read();
		if(!dgr[u]) AddEdge(v,u,0), fir[u]=v, ++dgr[u];
		else if(dgr[u]==1) AddEdge(v,u,1), ++dgr[u];
		if(!dgr[v]) AddEdge(u,v,0), fir[v]=u, ++dgr[v];
		else if(dgr[v]==1) AddEdge(u,v,1), ++dgr[v];
	}
	DFS(P,0,0,0);
	if(dgr[P]>1) DFS(P,0,1,1);
	int tot=n<<2, l0=len[0], l1=len[1];
	for(int i=0; i<tot; ++i)
	{
		sum[i][0]+=cnt[i][0], sum[i][1]+=cnt[i][1];
		if(l0 && i+l0<tot) sum[i+l0][0]+=sum[i][0];
		if(l1 && i+l1<tot) sum[i+l1][1]+=sum[i][1];
	}
	for(int Q=read(),K,t0=l0?2*n/l0*l0:0,t1=l1?2*n/l1*l1:0; Q--; )
	{
		if((K=read())<tot) printf("%d ",sum[K][0]+sum[K][1]);
		else printf("%d ",(t0?sum[K%l0+t0][0]:0)+(t1?sum[K%l1+t1][1]:0));
	}
	return 0;
}

B 归来(Tarjan 拓扑)

题目链接

将每种状态转移暴力连边，得到一张有向图，最长路就是答案。

同一强连通分量的点是可以任意转移的，对其缩点后得到DAG，拓扑/记忆化都可以求。\(O(4^n*m)\)，期望得分30~50.

注意到交换是任意的，所以只需要关心当前串每种字符的个数。

对于分别有a,b,c,d个A,B,C,D的串，其个数/排列数为\(\frac{n!}{a!b!c!d!}\)，但是直接算阶乘是爆longlong的。

最大的时候是\(\frac{n!}{7!7!8!8!}\approx 6e15\)，所以直接用组合数\(C_n^a*C_{n-a}^b*C_{n-a-b}^c\)是不会爆longlong的。

总点数是\(C_{30+4-1}^{4-1}=5456\)。同样对状态连边，缩点求最长路。

复杂度\(O(n^3m)\)。

#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
#define MAXIN 10000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define ID(a,b,c) (((a)*nn+(b))*nn+(c))//括号啊！！
typedef long long LL;
const int N=30005,M=810005;//n^3m

int n,nn,tot,m,cnt,top,sk[N],Index,dfn[N],low[N],bel[N];
bool ins[N];
LL val[N],sz[N],f[N];
std::queue<int> q;
char IN[MAXIN],*SS=IN,*TT=IN;
struct Graph
{
	int Enum,H[N],nxt[M],to[M],dgr[N];
	inline void AddEdge(int u,int v)
	{
		++dgr[v], to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
	}
}G,D;

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 Get(int *num)
{
	register char c=gc();
	for(; !isalpha(c); c=gc());
	for(; isalpha(c); ++num[c-'A'],c=gc());
}
void Init_val()
{
	static LL C[35][35];
	C[0][0]=1;
	for(int i=1; i<=n; ++i)
	{
		C[i][0]=C[i][i]=1;
		for(int j=1; j<i; ++j) C[i][j]=C[i-1][j]+C[i-1][j-1];
	}
	for(int a=0; a<=n; ++a)
		for(int b=0; a+b<=n; ++b)
			for(int c=0; a+b+c<=n; ++c)
				val[ID(a,b,c)]=C[n][a]*C[n-a][b]*C[n-a-b][c];
}
void Tarjan(int x)
{
	dfn[x]=low[x]=++Index, sk[++top]=x, ins[x]=1;
	for(int i=G.H[x],v; i; i=G.nxt[i])
		if(!dfn[v=G.to[i]]) Tarjan(v), low[x]=std::min(low[x],low[v]);
		else if(ins[v]) low[x]=std::min(low[x],dfn[v]);
	if(dfn[x]==low[x])
	{
		++cnt; int tmp;
		do
		{
			tmp=sk[top--];
			sz[cnt]+=val[tmp], ins[tmp]=0, bel[tmp]=cnt;
		}while(tmp!=x);
	}
}
void Toposort()
{
	LL ans=0;
	for(int i=1; i<=cnt; ++i) if(!D.dgr[i]) q.push(i);
	while(!q.empty())
	{
		int x=q.front(); q.pop();
		f[x]+=sz[x], ans=std::max(ans,f[x]);
		for(int i=D.H[x],v; i; i=D.nxt[i])
		{
			f[v=D.to[i]]=std::max(f[v],f[x]);
			if(!--D.dgr[v]) q.push(v);
		}
	}
	printf("%lld\n",ans);
}

int main()
{
//	freopen("ex_return3.in","r",stdin);

	n=read(), m=read(), nn=n+1, tot=n*nn*nn;
	for(int i=1; i<=m; ++i)
	{
		int num1[4]={0,0,0,0},num2[4]={0,0,0,0};
		Get(num1), Get(num2);
		if(num1[0]==num2[0]&&num1[1]==num2[1]&&num1[2]==num2[2]) continue;
		for(int a=num1[0]; a<=n; ++a)//枚举所有含Ai的串啊
			for(int b=num1[1]; a+b<=n; ++b)
				for(int c=num1[2]; a+b+c<=n; ++c)
				{
					if(n-a-b-c<num1[3]) break;
					G.AddEdge(ID(a,b,c),ID(a-num1[0]+num2[0],b-num1[1]+num2[1],c-num1[2]+num2[2]));
				}
	}
	Init_val();
	for(int i=0; i<=tot; ++i) if(!dfn[i]) Tarjan(i);//从0开始！(全D)
	for(int x=0,now=bel[x]; x<=tot; now=bel[++x])
		for(int i=G.H[x],v; i; i=G.nxt[i])
			if(now!=bel[G.to[i]]) D.AddEdge(now,bel[G.to[i]]);//正反当然没关系啊
	Toposort();

	return 0;
}

C 机场(凸函数 点分治)

题目链接

为什么函数是凸的，是有位置使得\(f'(0)<0\)。。

判断凹凸性还是去求二次导吧。

80pts代码：

/*
y=x^{3/2}是凸函数，所以$f(x)=\sum_{i=1}^n w[i]dis(x,i)^{3/2}$也(应该)是凸的。
凸函数有个性质：局部最优解就是全局最优解。
所以我们从任意一个点DFS，每次走到答案最小的儿子，一定能找到最优解。
每次直接跳到子树的重心，复杂度就是O(ndlogn)了（d是点的出度）。
期望得分80(注意不要DFS太多点)。
*/
#include <cmath>
#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=2e5+5;

int n,W[N],Enum,H[N],nxt[N<<1],to[N<<1],len[N<<1],dis[N],root,Min,sz[N],Cnt;
double Ans,Sum,f[N];
bool vis[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 void AddEdge(int w,int u,int v)
{
	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;
	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;
}
void Calc(int x,int f,int d)
{
	Sum+=1.0*d*sqrt(d)*W[x];//pow(d,1.5)
	for(int i=H[x]; i; i=nxt[i])
		if(to[i]!=f) Calc(to[i],x,d+len[i]);
}
void Get_root(int x,int f,int tot)
{
	int mx=0; sz[x]=1;
	for(int i=H[x],v; i; i=nxt[i])
		if(!vis[v=to[i]]&&v!=f)
		{
			Get_root(v,x,tot), sz[x]+=sz[v];
			if(sz[v]>mx) mx=sz[v];
		}
	mx=std::max(mx,tot-sz[x]);
	if(mx<Min) Min=mx, root=x;
}
void Solve(int x)
{
	vis[x]=1; double ans=Ans; int p=0;
	for(int i=H[x],v; i; i=nxt[i])
	{
		if(!f[v=to[i]])
			if(++Cnt>700) f[v]=Ans;//全DFS要T啊
			else Sum=0, Calc(v,0,0), f[v]=Sum;
		if(ans>f[v]) ans=f[p=v];
	}
	Ans=std::min(Ans,ans);
	if(p) Min=N, Get_root(p,0,sz[p]), Solve(root);
}

int main()
{
//	freopen("ex_airport2.in","r",stdin);

	n=read();
	for(int i=1; i<=n; ++i) W[i]=read();
	for(int i=1; i<n; ++i) AddEdge(read(),read(),read());
	Min=N, Get_root(1,0,n), Calc(root,0,0), f[root]=Ans=Sum, Solve(root);
	printf("%.7lf\n",Ans);

	return 0;
}

考试代码

A

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
#define gc() getchar()
const int N=150005;

int n,m,P,Q,K[2005],dgr[N],dis[N][2],ans[N];
std::vector<int> e[N];

#define AddEdge(u,v) e[u].push_back(v)
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;
}
namespace Subtask1
{
	int n,m,pre[N],pos[N];
	void Main()
	{
		for(int Q=read(); Q--; )
		{
			int K=read();
			for(int i=1; i<=n; ++i) pos[i]=i, pre[i]=0;
			while(K--)
			{
				for(int x=1,p; x<=n; ++x)
				{
					p=pos[x];
					if(dgr[p]==1||e[p][0]!=pre[x]) pre[x]=p, pos[x]=e[p][0];
					else pre[x]=p, pos[x]=e[p][1];
				}
			}
			int res=0;
			for(int i=1; i<=n; ++i) if(pos[i]==P) ++res;//printf("%d ",i-1), ++res; putchar('\n');
			printf("%d ",res);// putchar('\n');
		}
	}
}
//int DFS(int x,int f,int d,int anc,int toward)
//{
//	if(x==P) ans[anc]=d;
//	if(dis[x][toward]) return d+dis[x][toward];
//	printf("DFS(%d,%d,%d,%d)\n",x,f,d,anc);
//	if(dgr[x]==1||e[x][0]!=f)
//	{
//		if(x==anc&&d) return d;
//		return DFS(e[x][0],x,d+1,anc,0);
////		if(!dis[x][0]) dis[x][0]=DFS(e[x][0],x,d+1,x);
////		return d+dis[x][0];
//	}
//	else
//	{
//		return DFS(e[x][1],x,d+1,anc,1);
////		if(!dis[x][1]) dis[x][1]=DFS(e[x][1],x,d+1,x);
////		return d+dis[x][1];
//	}
//}

int main()
{
	freopen("ex_garden2.in","r",stdin);
//	freopen(".out","w",stdout);

	n=read(), m=read(), P=read()+1;
	for(int i=1,u,v; i<=m; ++i)
	{
		u=read()+1, v=read()+1;
		if(dgr[u]<2) ++dgr[u], AddEdge(u,v);
		if(dgr[v]<2) ++dgr[v], AddEdge(v,u);
	}
	if(n<=1000) {Subtask1::n=n, Subtask1::m=m, Subtask1::Main(); return 0;}

//	for(int i=1; i<=n; ++i) if(!dis[i][0]) dis[i][0]=DFS(i,i,0,i,0);
//	for(int i=1; i<=n; ++i) printf("dis[%d]: 0:%d 1:%d\n",i-1,dis[i][0],dis[i][1]);
//	for(int Q=read(),K; Q--; )
//	{
//		K=read();
//
//	}

	return 0;
}

B

#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
typedef long long LL;
const int N=10004,M=2e6+5;

int n,m,len[N];
char s[N],A[N][N],B[N][N];

namespace Subtask1
{
	int cnt,Enum,H[N],nxt[M],to[M],dgr[N],val[N];
	char s[N];
	bool vis[N];
	std::queue<int> q;

	inline bool OK(int p,int l,char *t)
	{
		for(int i=1; i<=l; ++i) if(s[p+i]!=t[i]) return 0;
		return 1;
	}
	inline int Encode(char *s)
	{
		int res=0;
		for(int i=1; i<=n; ++i) res=(res<<2)+(s[i]-'A');
		return res;
	}
	inline void AddEdge(int u,int v)
	{
		++dgr[u], to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
	}
	void Init_S(int now)
	{
		if(now>n)
		{
			int hs=Encode(s),hs2;
//			printf("%s:%d\n",s+1,hs);
			for(int i=1; i<n; ++i)
				if(s[i]!=s[i+1])
					std::swap(s[i],s[i+1]), hs2=Encode(s), AddEdge(hs,hs2), std::swap(s[i],s[i+1]);
			for(int p=0; p<n; ++p)
				for(int i=1; i<=m; ++i)
					if(p+len[i]<=n && OK(p,len[i],A[i]))
					{
//						printf("%s->",s+1);
						for(int j=1; j<=len[i]; ++j) s[p+j]=B[i][j];
//						printf("%s\n",s+1);
						hs2=Encode(s), AddEdge(hs,hs2);
						for(int j=1; j<=len[i]; ++j) s[p+j]=A[i][j];
					}

		}
		else for(int i=0; i<4; ++i) s[now]='A'+i, Init_S(now+1);
	}
	void DFS(int x)
	{
		vis[x]=1, ++cnt;
		for(int i=H[x]; i; i=nxt[i])
			if(!vis[to[i]]) DFS(to[i]);
	}
	void Main()
	{
		Init_S(1); char tmp[7]={"DDDDDD"};
		int tot=Encode(tmp);
		for(int i=0; i<=tot; ++i) val[i]=1;
		for(int i=0; i<=tot; ++i) if(!dgr[i]) q.push(i);
		for(int i=0; i<=tot; ++i) if(dgr[i]==1) q.push(i);
		int res=0;
		while(!q.empty())
		{
			int x=q.front(); q.pop();
			res=std::max(res,val[x]);
//			printf("now:%d\n",x);
			for(int v,i=H[x]; i; i=nxt[i])
				if(dgr[v=to[i]]>1)
				{
					val[v]=std::max(val[v],val[x]+1);
					res=std::max(res,val[v]);
//					printf("%d->%d val:%d\n",x,v,val[v]);
					if(!--dgr[v]||dgr[v]==1) q.push(v);
				}
		}
		for(int i=0; i<=tot; ++i)
			if(!vis[i]) cnt=0, DFS(i), res=std::max(res,cnt);
		printf("%d\n",res);
	}
}

int main()
{
//	freopen("ex_return2.in","r",stdin);
//	freopen(".out","w",stdout);

	scanf("%d%d",&n,&m);
	for(int i=1; i<=m; ++i) scanf("%s%s",A[i]+1,B[i]+1), len[i]=strlen(A[i]+1);
	if(n<=5) Subtask1::Main();
//	printf("%lld\n",Ans);

	return 0;
}

C

#include <cmath>
#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=2e5+5;

int n,W[N],Enum,H[N],nxt[N<<1],to[N<<1],len[N<<1],dis[N];
double Ans;
std::pair<int,int> A[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 void AddEdge(int w,int u,int v)
{
	to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;
	to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;
}
void DFS(int x,int f,int d)
{
	Ans+=1.0*pow(d,1.5)*W[x];
	for(int i=H[x]; i; i=nxt[i])
		if(to[i]!=f) DFS(to[i],x,d+len[i]);
}

int main()
{
//	freopen("ex_airport2.in","r",stdin);
//	freopen(".out","w",stdout);

	n=read();
	for(int i=1; i<=n; ++i) W[i]=read();
	for(int i=1; i<n; ++i) AddEdge(read(),read(),read());
	double res=1e18;
	if(n<=5000)
	{
		for(int i=1; i<=n; ++i)
			Ans=0, DFS(i,i,0), res=std::min(res,Ans);
	}
	else
	{
		for(int i=1; i<=n; ++i) A[i]=std::make_pair(W[i],i);
		std::sort(A+1,A+1+n,std::greater<std::pair<int,int> >());
		for(int T=1,v; T<=250; ++T)
			Ans=0, DFS(A[T].second,A[T].second,0), res=std::min(res,Ans);
	}
	printf("%.7lf\n",res);

	return 0;
}