国庆泉州集训 d a y 1 day1 day1
写博客前的吐槽:
题面可以说是发挥了出题人所有的想象力了
emmmm
题目背景真是有趣
T1: H S Y HSY HSY的质数
emmmm基础数论
裸的线性筛法,注意只要求质数的个数,那我们线性筛选的时候就不用把每个质数都标记出来,我们只需要记录质数的个数即可
稍微改改线性筛法的板子即可
Code:
复制代码
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#include<iostream> #include<cstdio> #include<cstring> #define size 10000010 using namespace std; long long pri[size]; int tot,f[size]; //f[i]表示1~i的质数个数 //线性筛法 void prepare(int n) { memset(pri,1,sizeof(pri)); pri[1]=0; for(int i=2;i<=n;i++) { if(pri[i]) { f[i]++; for(int j=2;j<=n/i;j++) pri[i*j]=0; //筛质数 for(int j=1;j<=i&& i*j<=n;j++) if(pri[j]) f[j*i]++; //处理题目要求的特殊情况 } } } int main() { prepare(1e7); for(int i=1;i<=size;i++) f[i]+=f[i-1]; //累加前缀和 int q; scanf("%d",&q); while(q--) { long long l,r; scanf("%lld%lld",&l,&r); printf("%dn",f[r]-f[l-1]); //前缀和的小应用 } return 0; }
T2: H S Y HSY HSY的密室
emmmm
状压+最短路可以A掉
然后其实BFS就可以过…
因为边权都是1…
至于如何状压和为何状压…
首先数据范围 k < = 10 k<=10 k<=10 这就很明显了
然后我们按照正常思路去处理这些钥匙的话,是很难实现的
所以状压可以搞一搞
-
用二进制去记录房间每种钥匙的数量
-
通过 a a a& b b b= a a a的方法判定是否可以通过
-
通过 a ∣ b a|b a∣b的方式获得该房间内的钥匙
spfa Code:
复制代码
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int INF=0x7ffffff; const int N=6000; int room[N],d[N][1<<10]; bool vis[N][1<<10]; int n,m,k,head[N],ver[N*2],Next[N*2],tot,edge[N]; struct fengzi { int x,num; }; void add(int x,int y,int z) { ver[++tot]=y; Next[tot]=head[x]; edge[tot]=z; head[x]=tot; } void spfa() { queue<fengzi> qwq; for (int i = 1; i <= n; i++) for(int j=0;j<(1<<k);j++) d[i][j]=INF; fengzi now; now.x=1; now.num=room[1]; vis[1][room[1]]=1; d[1][room[1]]=0; qwq.push(now); while(!qwq.empty()) { fengzi QwQ=qwq.front(); qwq.pop(); int x=QwQ.x,num=QwQ.num; vis[x][num]=0; for(int i=head[x];i;i=Next[i]) { int y=ver[i]; if((edge[i] & num)==edge[i])//如果钥匙数量符合 { int res=num | room[y]; //累加钥匙 if(d[y][res]>d[x][num]+1) { d[y][res]=d[x][num]+1; if(!vis[y][res]) { vis[y][res]=1; fengzi pwp; pwp.x=y; pwp.num=res; qwq.push(pwp); } } } } } } int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) { int res=0; for(int j=1;j<=k;j++) { int t; scanf("%d",&t); res=(res<<1)+t;//状压处理方式 } room[i]=res; } for(int i=1;i<=m;i++) { int x,y,res=0; scanf("%d%d",&x,&y); for(int j=1;j<=k;j++) { int t; scanf("%d",&t); res=(res<<1)+t;//状压处理方式 } add(x,y,res); } spfa(); int ans=INF; for(int i=0;i<(1<<k);i++) ans=min(ans,d[n][i]); if(ans==INF) puts("No Solution"); else printf("%dn",ans); return 0; }
T3: H S Y HSY HSY的佛光
隐藏起来的LCA…
手推一推即可发现规律…
-
1.其实题目就是在求从 A A A到 B B B和从 C C C到 A A A的重复路径
-
2.画图找规律
假设 A A A和 B B B的 L C A LCA LCA是 L 1 L_1 L1,那我们可以发现从 L 1 L_1 L1出发,到A 和 和 和B$的路径是不相交的
依次类推,我们假设 B B B和 C C C的 L C A LCA LCA是 L 2 L_2 L2,假设 A A A和 C C C的 L C A LCA LCA是 L 3 L_3 L3
那么我们可以从 L 1 , L 2 , L 3 L_1,L_2,L_3 L1,L2,L3中找到一个点,使得这个点到 A , B , C A,B,C A,B,C的路径不相交,那么我们要求的就是从这个点到 B B B的距离,这个就不用证明了吧QwQ…
然后问题就转换成了裸的LCA
Code:
复制代码
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
61
62
63
64
65
66
67
68
69
70
71#include<iostream> #include<cstdio> #define size 200010 using namespace std; int n,q,num; int tot,ver[size*2],Next[size*2],head[size*2]; int fa[size][22],d[size]; void add(int x,int y) { ver[++tot]=y; Next[tot]=head[x]; head[x]=tot; } void dfs(int f,int fath) { d[f]=d[fath]+1; fa[f][0]=fath; for(int i=1;i<=20;i++) fa[f][i]=fa[fa[f][i-1]][i-1]; for(int i=head[f];i;i=Next[i]) { int y=ver[i]; if(y!=fath) dfs(y,f); } } int lca(int x,int y) { if(d[x]<d[y]) swap(x,y); for(int i=20;i>=0;i--) if(d[fa[x][i]]>=d[y]) x=fa[x][i]; if(x==y) return x; for(int i=20;i>=0;i--) { if(fa[x][i]!=fa[y][i]) { x=fa[x][i]; y=fa[y][i]; } } return fa[x][0]; } int dist(int x,int y) { int mid=lca(x,y); return d[x]+d[y]-2*d[mid]; } int main() { scanf("%d%d%d",&n,&q,&num); for(int i=1;i<=n-1;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } dfs(1,0); for(int i=1;i<=q;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); int qwq_1=lca(a,b); int qwq_2=lca(b,c); int qwq_3=lca(a,c); if(d[qwq_2]>d[qwq_1]) qwq_1=qwq_2; if(d[qwq_3]>d[qwq_1]) qwq_1=qwq_3; printf("%dn",1+dist(qwq_1,b)); } return 0; }
最后
以上就是善良时光最近收集整理的关于泉州集训之HSY的day1的全部内容,更多相关泉州集训之HSY内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复