7.30 正睿暑期集训营 A班训练赛

目录

• 2018.7.30 正睿暑期集训营 A班训练赛
  • T1 A.蔡老板分果子(Hash)
  • T2 B.蔡老板送外卖(并查集 最小生成树)
  • T3 C.蔡老板学数学(DP NTT)
  • 考试代码
    • T2
    • T3

---

2018.7.30 正睿暑期集训营 A班训练赛

时间：8:00~13:00

期望得分：100+5+5

实际得分：100+5+0

比赛链接

很多人Hash被卡了（写得丑怪谁呢），水了个A班前10 2333.

T1 A.蔡老板分果子(Hash)

题目链接

对下标集合进行Hash。只需要为每个下标随机一个权值即可。

不放心写了双哈希，其实单哈希就够了。异或或者加，随机权值或设定都行。

一个赋随机unsigned long long权值方式：for(int j=1; j<=5; ++j) val[i]=val[i]<<15^rand();

#include <map>
#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++)
#define base1 (786433)
#define base2 (1572869)
typedef long long LL;
typedef unsigned long long ull;
const int N=2e5+5;
const ull P1[7]={31,193,331,769,12289};
const ull P2[7]={131,97,53,389,49157};

int n;
long long Ans;
ull pw1[N],pw2[N],sum1[N],sum2[N];
std::map<ull,int> vis1,vis2;
char IN[MAXIN],*SS=IN,*TT=IN;
struct Edge
{
	int Enum,H[N],nxt[N<<1],to[N<<1];
	inline void AddEdge(int u,int v)
	{
		to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
		to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
	}
}T1,T2;

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;
}
void DFS1(int x,int f)
{
	sum1[x]=pw1[x]*base1, sum2[x]=pw2[x]*base2;
	for(int v,i=T1.H[x]; i; i=T1.nxt[i])
		if((v=T1.to[i])!=f) DFS1(v,x), sum1[x]+=sum1[v], sum2[x]+=sum2[v];
	++vis1[sum1[x]], ++vis2[sum2[x]];
}
void DFS2(int x,int f)
{
	static std::map<ull,int>::iterator it1,it2;

	sum1[x]=pw1[x]*base1, sum2[x]=pw2[x]*base2;
	for(int v,i=T2.H[x]; i; i=T2.nxt[i])
		if((v=T2.to[i])!=f) DFS2(v,x), sum1[x]+=sum1[v], sum2[x]+=sum2[v];
	if((it1=vis1.find(sum1[x]))!=vis1.end() && (it2=vis2.find(sum2[x]))!=vis2.end())
		Ans+=(LL)std::min(it1->second,it2->second);//, printf("Add! %d:%d\n",x,it->second);
}

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

	n=read(); pw1[0]=pw2[0]=1;
	for(int i=1; i<=n; ++i) pw1[i]=pw1[i-1]*base1+P1[i%5]*i, pw2[i]=pw2[i-1]*base2+P2[i%5]*i;;
	for(int i=1; i<n; ++i) T1.AddEdge(read(),read());
	for(int i=1; i<n; ++i) T2.AddEdge(read(),read());
	DFS1(1,1), --vis1[sum1[1]], --vis2[sum2[1]], DFS2(1,1);
	printf("%lld\n",Ans);

	return 0;
}

T2 B.蔡老板送外卖(并查集 最小生成树)

题目链接

我们要求删掉i后的最小生成树的最大边的权值。我们对所有的点一起考虑。

先求出最小生成树。考虑删掉每个点后其余非树边能对它的贡献。

我们存下非树边，对于边(u,v),w=LCA(u,v)，假设dep[u]>dep[v]，那么有两种情况：

1.w==v，暂且称这条边为返祖边，它会对u->v(w)(不包括u,v)这条链的点贡献合并上下两个连通块的边。

2.w!=v，称这条边为横边，同理会对u->w,v->w(不包括u,v)上的点贡献合并u,v所在连通块的边。

如果把边从小到大插入，比如一些点被较小的返祖边覆盖过，那么更大的返祖边对它显然没什么用。我们跳过之前更新过的一条链，这可以用并查集。

具体是对于当前节点x，x=Get_fa(x)，然后合并x与fa[x]，再找到fa[x]所在集合的代表节点，合并其与其父节点...

对fa[]更新这条边的答案，u,v不会被计算，但是会被合并，但是没问题，u,v作为父节点会被更新一次。

不清楚的话，画个图就好了。

判断无解可以记每个点被合并连通块的次数就可以了。

对于返祖边有一次次数贡献；对于横边，我们更新完链后将u,v合并，若u,v之前未被合并则对w有一次次数贡献。

每条返祖边只被枚举一次，每条横边相当于只在LCA处枚举一次。复杂度O(mlogn*α(n))。

要注意并查集每次要把深度高的点的fa[]指向深度低的点；跳fa的时候是树上的不要和并查集的混了。

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

int n,m,Enum,H[N],to[N<<1],nxt[N<<1],cnt,dgr[N],fa[N];
char IN[MAXIN],*SS=IN,*TT=IN;
struct Edge
{
	int fr,to,val;
	bool operator <(const Edge &x)const{
		return val<x.val;
	}
}e[N],g[N];

#define AddEdge(u,v) to[++Enum]=v,nxt[Enum]=H[u],H[u]=Enum,to[++Enum]=u,nxt[Enum]=H[v],H[v]=Enum
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;
}
int Get_fa(int x){
	return x==fa[x]?x:fa[x]=Get_fa(fa[x]);
}
void Merge(int u,int v){
	if(Get_fa(u)!=Get_fa(v)) fa[fa[u]]=fa[v];
}
int Kruskal()
{
	std::sort(e+1,e+1+m);
	for(int i=1; i<=n; ++i) fa[i]=i;
	int res=0,k=1;
	for(int i=1,u,v; i<=m; ++i)
	{
		if(Get_fa(u=e[i].fr)==Get_fa(v=e[i].to)) {g[++cnt]=e[i]; continue;}
		++k, ++dgr[u], ++dgr[v], AddEdge(u,v);
		fa[fa[u]]=fa[v], res=std::max(res,e[i].val);
//		if(++k==n) return res;//g
	}
	return k==n?res:-1;
}
namespace HLD//Heavy-Light Decomposition
{
	int fa[N],sz[N],son[N],dep[N],top[N];
	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]?v:u;
	}
	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],v; i; i=nxt[i])
				if((v=to[i])!=fa[x] && v!=son[x]) DFS2(v,v);
		}
	}
}
using HLD::dep;
using HLD::LCA;

int main()
{
	n=read(), m=read();
	for(int i=1; i<=m; ++i) e[i]=(Edge){read(),read(),read()};
	int MinTree=Kruskal();
	if(MinTree==-1) return printf("%d\n",-n),0;

	HLD::DFS1(1), HLD::DFS2(1,1);

	static int tot[N],Ans[N];
	for(int i=1; i<=n; ++i) fa[i]=i;
	for(int i=1,u,v,tu,tv,w,val; i<=cnt; ++i)
	{
		if(dep[u=g[i].fr]<dep[v=g[i].to]) std::swap(u,v);
		w=LCA(u,v), val=g[i].val;
		if(v==w)
		{
			u=Get_fa(u);
			for(int p=HLD::fa[u]; dep[p]>dep[v]; u=Get_fa(u), p=HLD::fa[u])
				Ans[p]=val, ++tot[p], Merge(u,p);
		}
		else
		{
			u=Get_fa(tu=u), v=Get_fa(tv=v);
			for(int p=HLD::fa[u]; dep[p]>dep[w]; u=Get_fa(u), p=HLD::fa[u])
				Ans[p]=val, ++tot[p], Merge(u,p);
			for(int p=HLD::fa[v]; dep[p]>dep[w]; v=Get_fa(v), p=HLD::fa[v])
				Ans[p]=val, ++tot[p], Merge(v,p);
			if((u=Get_fa(tu))==(v=Get_fa(tv))) continue;
			Ans[w]=val, ++tot[w];
			if(dep[u]<dep[v]) std::swap(u,v);
			fa[fa[u]]=fa[v];
		}
	}
	long long res=0;
	for(int i=1; i<=n; ++i)
		res += dgr[i]==1?MinTree:(tot[i]<dgr[i]-1?-1:std::max(MinTree,Ans[i]));
	printf("%lld\n",res);

	return 0;
}

T3 C.蔡老板学数学(DP NTT)

题目链接

？？？

考试代码

T2

/*
对于每个点i，求其MST上的最大边。其MST上i的度数只能为1。
对于每个连通块单独求其MST，当根节点不在其中时显然它就可以是答案。然而这没啥用，很容易有个大连通块。应该是二档部分分？
根节点只能连出一条，它的边只有把它与连通块连起来，而不能再帮助其它点并入连通块、so直接选其最小边即可。那么去掉根节点做个MST。
即求：i=1~n，去掉点i的最小生成树的最大边。只求和，算贡献？
LCT!不对啊，cut掉i的边 还是要枚举m条连起来。。而且忘了怎么写了。我还是咸鱼吧。
瞎写的 没调完 也没啥意思。
*/
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
#define gc() getchar()
//#define MAXIN 400000
//#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
#define Vec std::vector<int>
typedef long long LL;
const int N=1e6+5,S=4*N,INF=0x3f3f3f3f;

int n,m,Enum,H[N],nxt[N<<1],to[N<<1],len[N<<1],tmp[N<<1],mn[N],Index,low[N],dfn[N],top,sk[N],fa[N],scnt,val[N],ff[N],Ans[N];
Vec scc[N],edge[N],bel[N];
//char IN[MAXIN],*SS=IN,*TT=IN;
struct Edge
{
	int fr,to,val;
	Edge() {}
	Edge(int f,int t,int v):fr(f),to(t),val(v) {}
	bool operator <(const Edge &a)const{
		return val<a.val;
	}
}e[N];

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)
{
	mn[v]=std::min(mn[v],w), to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum, len[Enum]=w;
	mn[u]=std::min(mn[u],w), to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum, len[Enum]=w;
	e[Enum>>1]=Edge(u,v,w);
}
namespace NoSolution
{
	bool ok[N];
	void DDFS(int x)
	{
		ok[x]=1;
		for(int i=H[x]; i; i=nxt[i])
			if(!ok[to[i]]) DDFS(to[i]);
	}
	bool Check()
	{
		DDFS(1);
		for(int i=2; i<=n; ++i) if(!ok[i]) return 1;
		return 0;
	}
}
namespace Violence
{
	int fa[N];
	int Get_fa(int x){
		return x==fa[x]?x:fa[x]=Get_fa(fa[x]);
	}
	int Kruskal(int id)
	{
		for(int i=1; i<=n; ++i) fa[i]=i;
		int res=0;
		for(int r1,r2,k=2,i=1; i<=m; ++i)
		{
			if(e[i].fr==id||e[i].to==id) continue;
			if((r1=Get_fa(e[i].fr))==(r2=Get_fa(e[i].to))) continue;
			fa[r1]=r2, res=std::max(res,e[i].val);
			if(++k==n) return std::max(mn[id],res);
		}
		return -1;
	}
	void Main()
	{
		LL res=0;
		for(int t,i=1; i<=n; ++i) res+=Kruskal(i);
		printf("%lld\n",res);
	}
}
int Get_fa(int x){
	return x==ff[x]?x:ff[x]=Get_fa(ff[x]);
}
bool cmp_e(int a,int b){
	return e[a].val<e[b].val;
}
inline bool Check(int x,int s)
{
	for(int i=0,lim=bel[x].size(); i<lim; ++i) if(bel[x][i]==s) return 1;
	return 0;
}
int Kruskal(int now,int id)//某连通块内MST
{
	Vec &s=scc[now]; int tot=s.size(),res=0,m=0;
	for(int i=1; i<=n; ++i) ff[i]=i;//
	for(int i=0,x; i<tot; ++i)
	{
		ff[x=s[i]]=x;
		for(int j=0,lim=edge[x].size(); j<lim; ++j)
			tmp[++m]=edge[x][j];
	}
	std::sort(tmp+1,tmp+1+m,cmp_e);
	for(int k=1,j=1,r1,r2; j<=m; ++j)
	{
		int i=tmp[j];
		if(e[i].fr==id||e[i].to==id||!Check(e[i].fr,now)||!Check(e[i].to,now)) continue;
		if((r1=Get_fa(e[i].fr))==(r2=Get_fa(e[i].to))) continue;
		fa[r1]=r2, res=std::max(res,e[i].val);
		if(++k==tot) return res;
	}
	return -1;
}
void Tarjan(int x)
{
	low[x]=dfn[x]=++Index, sk[++top]=x;
	for(int v,i=H[x]; i; i=nxt[i])
		if(!dfn[v=to[i]])
		{
			fa[v]=x, Tarjan(v), low[x]=std::min(low[x],low[v]);
			if(dfn[x]==low[v])
			{
				scc[++scnt].push_back(x), bel[x].push_back(scnt);
				do{
					scc[scnt].push_back(sk[top]), bel[sk[top--]].push_back(scnt);
				}while(sk[top+1]!=v);
				val[scnt]=Kruskal(scnt,0);
				printf("scnt:%d %d\n",scnt,val[scnt]);
			}
			else if(dfn[x]<low[v]) --top/*!*/;
		}
		else if(v!=fa[x]) low[x]=std::min(low[x],dfn[v]);
}
int Calc(int now)
{
	static int vis[N],Time=0;
	++Time; int res=0;
	for(int i=0,tmp,lim=bel[now].size(),x; i<lim; ++i)
	{
		x=bel[now][i];
		if((tmp=Kruskal(x,now))==-1) return -1;
		res=std::max(res,tmp), vis[x]=Time;
	}
	for(int i=1; i<=scnt; ++i) if(vis[i]!=Time) res=std::max(res,val[i]);
	printf("Calc(%d):%d\n",now,res);
	return std::max(res,mn[now]);
}

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

	n=read(), m=read(); memset(mn,0x3f,sizeof mn);
	for(int i=1; i<=m; ++i) AddEdge(read(),read(),read());
	if(NoSolution::Check()) return printf("%d\n",-n),0;

	std::sort(e+1,e+1+m);
//	if(1ll*n*m<=1e8) return Violence::Main(),0;
	for(int i=1; i<=m; ++i) edge[e[i].fr].push_back(i), edge[e[i].to].push_back(i);
	Tarjan(1);
	for(int i=1; i<=scnt; ++i)
		for(int j=0; j<scc[i].size(); ++j) printf("scc:%d:%d\n",i,scc[i][j]);
	LL res=0;
	for(int i=1; i<=n; ++i) res+=Calc(i);
	printf("%lld\n",res);

	return 0;
}

T3

0pts:(迷)

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
#define mod (998244353)
typedef long long LL;
const int N=1e6+5;

int n,K,sz,S[12],pos[12];

int Check(LL x)
{
	static int tm[7];
	for(int i=1; i<=sz; ++i) tm[i]=0;
	for(; x; x/=10) ++tm[pos[x%10]];
	for(int i=1; i<=sz; ++i) if(tm[i]%3) return 0;
	return 1;
}
int Solve(LL K)
{
	LL res=0,lim=1;
	while(n--) lim*=10ll;
	LL bef=lim/10, start=bef/K;
	while(start*K<bef) ++start;
	for(LL i=start; i*K<lim; ++i) res+=Check(i*K);
	return res%mod;
}

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

	char s[12];
	scanf("%d%d%s",&n,&K,s+1); sz=strlen(s+1);
	for(int i=1; i<=sz; ++i) pos[S[i]=s[i]-'0']=i;
	if(n>15) return puts("0"),0;
	printf("%d\n",Solve(K));

	return 0;
}

15pts:

//数组感觉爆炸 没敢交。。然而sb了完全可以
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
#define mod (998244353)
typedef long long LL;
const int N=1e6+5;

int n,K,sz,S[12],pos[12];
int f[102][250][3][3][3][3][3][3];//2e8
bool vis[102][250][3][3][3][3][3][3];

int DFS(int p,int rem,int r1,int r2,int r3,int r4,int r5,int r6)
{
	if(!p) return !rem&&!r1&&!r2&&!r3&&!r4&&!r5&&!r6;
	if(vis[p][rem][r1][r2][r3][r4][r5][r6])
		return f[p][rem][r1][r2][r3][r4][r5][r6];

	long long res=0;
	for(int i=1; i<=sz; ++i)
		switch(i)
		{
			case 1: res+=DFS(p-1,(rem*10+S[1])%K,(r1+1)%3,r2,r3,r4,r5,r6); break;
			case 2: res+=DFS(p-1,(rem*10+S[2])%K,r1,(r2+1)%3,r3,r4,r5,r6); break;
			case 3: res+=DFS(p-1,(rem*10+S[3])%K,r1,r2,(r3+1)%3,r4,r5,r6); break;
			case 4: res+=DFS(p-1,(rem*10+S[4])%K,r1,r2,r3,(r4+1)%3,r5,r6); break;
			case 5: res+=DFS(p-1,(rem*10+S[5])%K,r1,r2,r3,r4,(r5+1)%3,r6); break;
			case 6: res+=DFS(p-1,(rem*10+S[6])%K,r1,r2,r3,r4,r5,(r6+1)%3); break;
		}
	for(int i=0; i<=9; ++i)
		if(!pos[i]) res+=DFS(p-1,(rem*10+i)%K,r1,r2,r3,r4,r5,r6);

//	printf("DFS(%d,%d,%d,%d,%d,%d,%d,%d):%I64d\n",p,rem,r1,r2,r3,r4,r5,r6,res%mod);
	vis[p][rem][r1][r2][r3][r4][r5][r6]=1;
	return f[p][rem][r1][r2][r3][r4][r5][r6]=res%mod;
}

int main()
{
	char s[12];
	scanf("%d%d%s",&n,&K,s+1); sz=strlen(s+1);
	for(int i=1; i<=sz; ++i) pos[S[i]=s[i]-'0']=i;
	printf("%d\n",DFS(n,0,0,0,0,0,0,0));

	return 0;
}