[国庆集训]Day1解题报告

发表于 | 阅读次数：

题目链接

戳我n(≧▽≦)n

T1

好吧这是我唯一在场A的题（,,ԾㅂԾ,,他们怎么都A了）

开始还想着打表。。。然后想想实际上这就是一个欧拉筛的模板啊，$O(N)$时间复杂度内能够筛出$1 \sim N$的素数，在筛除合数的过程中特判一下就可以求出$1 \sim 10^7$内的所有小W喜欢的数了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <iostream>
#define Re register int
#define MAX_X 10000000

int Q,L,R,isPrime[MAX_X+1],Prime[2568904],Sum[MAX_X+1],len;

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	var=w?-x:x;
}
void Euler_sieve()
{
	for (Re i=2; i<=MAX_X; ++i) isPrime[i]=1;
	for (Re i=2; i<=MAX_X; ++i)
	{
		if (isPrime[i])
		{
			Prime[++len]=i;
			if (isPrime[i]==1)
			{
				for (Re j=1; i*Prime[j]<=MAX_X&&j<=len; ++j)
				{
					if (isPrime[Prime[j]]==2) continue;
					isPrime[i*Prime[j]]=2;
					if (i%Prime[j]==0) break;
				}
			}
			else
				for (Re j=1; i*Prime[j]<=MAX_X&&j<=len; ++j)
				{
				   	isPrime[i*Prime[j]]=0;
					if (i%Prime[j]==0) break;
				}
		}
		else
			for (Re j=1; i*Prime[j]<=MAX_X&&j<=len; ++j)
			{
				isPrime[i*Prime[j]]=0;
				if (i%Prime[j]==0) break;
			}
	} return;
}
int main(int argc, char const *argv[])
{
	Euler_sieve();
	for (Re i=1; i<=MAX_X; ++i)
		if (isPrime[i]) Sum[i]=Sum[i-1]+1;
		else Sum[i]=Sum[i-1];
	read(Q);
	while (Q--)
	{
		read(L); read(R);
		printf("%d\n",Sum[R]-Sum[L-1]);
	}
	return 0;
}

T2

emmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm………………………………………………………….

我居然天真的以为BFS过不了这题。。。一看到这题，还有$K \le 10$的范围。。。自然想到状压。

But我tm就是认为暴力过不了。。。（或许是看到了0.5s的时限。。。）太dog了(─.─|||。。。这里也不多做说明了。

状压+BFS妥妥过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <queue>
#include <ctype.h>
#include <stdio.h>
#include <string.h>
#define Re register int
using namespace std;

struct Edge{
	int to,next,key;
}e[6005];
int cnt,head[5005];
int N,M,K,GetKey[5005],dis[5005][1024];

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	var=w?-x:x;
}
inline void AddEdge(int u,int v)
{
	int key=0;
	for (Re i=1,x; i<=K; ++i) read(x),key<<=1,key|=x;
	e[++cnt]=(Edge){v,head[u],key};
	head[u]=cnt;
}
void BFS()
{
	queue< pair<int,int> > q; q.push(make_pair(1,0)); dis[1][0]=1;
	while (!q.empty())
	{
		int now=q.front().first,nowkey=q.front().second,nw=nowkey;
		q.pop(); nowkey|=GetKey[now];
		for (Re i=head[now];i;i=e[i].next)
			if ((e[i].key&nowkey)==e[i].key&&!dis[e[i].to][nowkey])
				if (e[i].to==N) {printf("%d\n",dis[now][nw]); return;}
				else q.push(make_pair(e[i].to,nowkey)),dis[e[i].to][nowkey]=dis[now][nw]+1;
	}
	printf("No Solution\n"); return;
}
int main(int argc, char const *argv[])
{
	read(N),read(M),read(K);
	for (Re i=1,x; i<=N; ++i)
		for (Re j=1; j<=K; ++j)
			read(x),GetKey[i]<<=1,GetKey[i]|=x;
	for (Re i=1,u,v; i<=M; ++i)
		read(u),read(v),AddEdge(u,v);
	BFS(); return 0;
}

T3

很裸的LCA，借这个机会复习一下LCA。

给一个LCA的模板吧，博主自己写的哦~~~ヾ(·∀·o)+

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void dfs(int now,int fa)
{
	f[now][0]=fa; d[now]=d[fa]+1; maxd=max(maxd,d[now]);
	for (Re i=head[now];i;i=e[i].next)
		if (e[i].to!=fa) dfs(e[i].to,now);
}
int LCA(int u,int v) //写了很多种LCA的版本，还是觉得这个比较好
{
	if (d[u]>d[v]) swap(u,v);
	for (int i=20; i>=0; --i)
		if (d[f[v][i]]>=d[u]) v=f[v][i];
	for (int i=20; i>=0; --i)
		if (f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
	if (u==v) return u; else return f[u][0];
    //至于为什么会存在u==v，是存在LCA(u,v)=u或者v的情况
}
void Initialization()
{
    dfs(1,0);
    for (int j=1; (1<<j)<=maxd; ++j) //maxd为树的最大深度
        for (int i=1; i<=N; ++i)
            f[i][j]=f[f[i][j-1]][j-1];
}

对于这道题目，其实只需要求两条路径重合部分的长度就好了

所以我就不多进行解释，放代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
#include <iostream>
#define Re register int

struct Edge{
	int to,next;
}e[400005];
int cnt,head[200005];
int N,Q,NUM,maxd,d[200005],f[200005][21],ans;

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	var=w?-x:x;
}
inline void AddEdge(int u,int v) {e[++cnt]=(Edge){v,head[u]}; head[u]=cnt;}
void dfs(int now,int fa)
{
	f[now][0]=fa; d[now]=d[fa]+1; maxd=std::max(maxd,d[now]);
	for (Re i=head[now];i;i=e[i].next)
		if (e[i].to!=fa) dfs(e[i].to,now);
}
int LCA(int u,int v)
{
	if (d[u]>d[v]) std::swap(u,v);
	for (int i=20; i>=0; --i)
		if (d[f[v][i]]>=d[u]) v=f[v][i];
	for (int i=20; i>=0; --i)
		if (f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
	if (u==v) return u; else return f[u][0];
}
int dist(int u,int v) {return d[u]+d[v]-2*d[LCA(u,v)];}
int main(int argc, char const *argv[])
{
	read(N),read(Q),read(NUM);
	for (Re i=1,u,v; i<N; ++i)
		read(u),read(v),AddEdge(u,v),AddEdge(v,u);
	dfs(1,0);
	for (Re j=1; (1<<j)<=maxd; ++j)
		for (Re i=1; i<=N; ++i)
			f[i][j]=f[f[i][j-1]][j-1];
	for (Re i=1,A,B,C; i<=Q; ++i)
	{
		read(A),read(B),read(C);
		printf("%d\n",(dist(A,B)+dist(C,B)-dist(A,C))/2+1);
	}
	return 0;
}