20zr普及组五连测day3

浪费生命的3h30min...

map

$n^2$ 比较巧妙


#include<bits/stdc++.h>
using namespace std;
//const int MAXN=1e5+7;
int n,m;
map<int,int> mp;
int main() {
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,opt; i<=n; ++i) {
		scanf("%d",&opt);
		if(opt==1) {
			scanf("%d%d",&x,&y);
			mp[x]=y;
		} else {
			scanf("%d",&x);
			if(mp.find(x)==mp.end()) {
				puts("0");
			} else printf("%d\n",mp[x]);
		}
	}
	return 0;
}

每个点记录状压2^k的状态

然后发现边长为1

可以广度优先搜索

code:


#include<bits/stdc++.h>
#define pii pair<int,int>
#define se second
#define fi first
#define mkp(x,y) (make_pair(x,y))
const int MAXS=1100;
const int MAXN=5007;
const int MAXM=6007;
using namespace std;

namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
	inline char nc() {
		if(p1==pend) {
			p1=buf;
			pend=buf+fread(buf,1,BUF_SIZE,stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x=0;
		char s=nc();
		for(; !isdigit(s); s=nc());
		for(; isdigit(s); s=nc())x=(x<<1)+(x<<3)+s-'0';
		return x;
	}
}
using namespace fastIO;

int n,ccnt,m,k,hd,tl;
int home[MAXN],nxt[MAXM],to[MAXM],w[MAXM],hve[MAXN];

int f[MAXN][MAXS],vis[MAXN][MAXS];//f_uS表示点u在已经有了S之后能不能走过去。。。
pii que[MAXS*MAXN];//不能炸吧。。。

inline void ct(int x,int y,int z) {
	++ccnt;
	nxt[ccnt]=home[x];
	home[x]=ccnt;
	to[ccnt]=y;
	w[ccnt]=z;
}

inline void solve() {
	memset(f,0x3f3f3f3f,sizeof(f));
	f[1][hve[1]]=0;
	vis[1][hve[1]]=1;
	hd=tl=1;
	que[hd]=mkp(1,hve[1]);
	while(hd<=tl) {
		int u=que[hd].fi,S=que[hd].se;
		hd++;
		if(u==n)break;
		for(int i=home[u]; i; i=nxt[i]) {
			int v=to[i],q=w[i];
			int nS=S|hve[v];
			if(!vis[v][nS] && ((q&S)==q)) {
				vis[v][nS]=1;
				que[++tl]=mkp(v,nS);
				f[v][nS]=f[u][S]+1;
			}
		}
	}
	int ans=1e9;
	for(int i=0; i<MAXS; ++i)ans=min(ans,f[n][i]);
	if(ans==1e9)printf("No Solution");
	else printf("%d\n",ans);
	return;
}

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

	n=read();
	m=read();
	k=read();
	for(int i=1,x; i<=n; ++i) {
		for(int j=0; j<k; ++j) {
			x=read();
			hve[i]|=(x<<j);
		}
	}
	for(int i=1,x,y,z; i<=m; ++i) {
		x=read();
		y=read();
		z=0;
		for(int j=0,p; j<k; ++j) {
			p=read();
			z|=(p<<j);
		}
		ct(x,y,z);//qaq
	}
	solve();//bfs
	return 0;
}

一个质数能被分解成两个质数的乘积

当且仅当质因数指数和为2

问题变得显然,线性筛每个数最小质因子即可

复杂度 $O(n+Q)$

code:


#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e7+7;
int q;
int sum[MAXN];
int pri[MAXN],isp[MAXN],mpr[MAXN];


namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
	inline char nc() {
		if(p1==pend) {
			p1=buf;
			pend=buf+fread(buf,1,BUF_SIZE,stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x=0;
		char s=nc();
		for(; !isdigit(s); s=nc());
		for(; isdigit(s); s=nc())x=(x<<1)+(x<<3)+s-'0';
		return x;
	}
}
using namespace fastIO;

inline void init() {
	int tot=0;
	for(int i=2; i<MAXN; ++i) {
		if(!isp[i]) {
			pri[++tot]=i;
			mpr[i]=i;
		}
		for(int j=1; j<=tot && i * pri[j] < MAXN; ++j) {
			isp[i*pri[j]]=1;
			mpr[i*pri[j]]=min(pri[j],mpr[i]);
			if(i%pri[j]==0) {
				mpr[i*pri[j]]=pri[j];
				continue;
			}
		}
	}
	for(int i=2; i<MAXN; ++i) {
		if(!isp[i]) {
			sum[i]=sum[i-1]+1;
		} else {
			int x=i;
			x/=mpr[x];
			x/=mpr[x];
			if(x==1) {
				sum[i]=sum[i-1]+1;
			} else sum[i]=sum[i-1];
		}
	}
	return;
}

int main() {
//	freopen("test2.in","r",stdin);
//	freopen("test1.out","w",stdout);
	init();
	q=read();
	for(int i=1,l,r; i<=q; ++i) {
		l=read();
		r=read();
		printf("%d\n",sum[r]-sum[l-1]);
	}
	return 0;
}

树上链交!

首先判断有没有空集,就是看两者 $lca$ 的深度哪个更浅

然后把浅的那个LCA和另外两个端点再做LCA,如果有一个等于本身就说明LCA在另外的链上

然后链交大小?

设两条路径为 $x,y$ , $u,v$

$LCA(x,u),LCA(x,v),LCA(u,y),LCA(v,y)$

四个点按照dfs序排下序,然后选取最后两个求dis即可

$O(nlogn)$

code:



#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+7;
int n,q,qwq,depp,ccnt;
int siz[MAXN],dfn[MAXN],dep[MAXN],fa[MAXN],son[MAXN],top[MAXN];
int home[MAXN],nxt[MAXN],to[MAXN];
int a[10];


namespace fastIO {
#define BUF_SIZE (1<<20)
	static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
	inline char nc() {
		if(p1==pend) {
			p1=buf;
			pend=buf+fread(buf,1,BUF_SIZE,stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x=0;
		char s=nc();
		for(; !isdigit(s); s=nc());
		for(; isdigit(s); s=nc())x=(x<<1)+(x<<3)+s-'0';
		return x;
	}
}
using namespace fastIO;

inline void ct(int x,int y) {
	ccnt++;
	nxt[ccnt]=home[x];
	home[x]=ccnt;
	to[ccnt]=y;
}

inline void dfs1(int u,int F) {
	siz[u]=1;
	dfn[u]=++depp;
	for(int i=home[u]; i; i=nxt[i]) {
		int v=to[i];
		if(v==F)continue;
		dep[v]=dep[u]+1;
		fa[v]=u;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])son[u]=v;
	}
	return ;
}

inline void dfs2(int u,int topf) {
	top[u]=topf;
	if(!son[u])return ;
	dfs2(son[u],topf);
	for(int i=home[u]; i; i=nxt[i]) {
		int v=to[i];
		if(v==fa[u] || v==son[u])continue;
		dfs2(v,v);
	}
}

inline int LCA(int x,int y) {
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]])
			x^=y^=x^=y;
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])x^=y^=x^=y;
	return x;
}

inline bool cmp(const int &x,const int &y) {
	return dfn[x]<dfn[y];
}

inline int DIS(int x,int y) {
	return dep[x]+dep[y]-2*dep[LCA(x,y)];
}

//this is a completely 链交大小
inline void solve(int u,int v,int x,int y) {
	a[1]=LCA(u,x);
	a[2]=LCA(u,y);
	a[3]=LCA(v,x);
	a[4]=LCA(v,y);
	sort(a+1,a+5,cmp);
	printf("%d\n",DIS(a[3],a[4])+1);
	return;
}

int main() {
//	freopen("test3.in","r",stdin);
//	freopen("test1.out","w",stdout);
	n=read();
	q=read();
	qwq=read();
	for(int i=1,x,y; i<n; ++i) {
		x=read();
		y=read();
		ct(x,y);
		ct(y,x);
	}
	dep[1]=1;
	dfs1(1,0);
	dfs2(1,1);
	for(int i=1,x,y,z; i<=q; ++i) {
		x=read();
		y=read();
		z=read();
		solve(x,y,z,y);//直接链交走人了。。。
	}
	return 0;
}

夏晓光(loveJY)的博客

【LGR-076】洛谷 ⑨ 月月赛 I & Cnoi2020