C++ 算法 并查集 线段树

SDNU_ACM_2022_Winter_Practice_3rd

寒假第三次训练补题

Posted by zhangmh on 2022-01-24
Estimated Reading Time 18 Minutes
Words 3.5k In Total
Viewed Times

为什么会出上一次的原题哇，上次没及时补题QWQ

目录

[B-Matches Game](#B-Matches Game)

[C-Wireless Network](#C-Wireless Network)

[D - Cooking](#D - Cooking)

[E - Balanced Lineup](#E - Balanced Lineup)

[F - POW](#F - POW)

[G-Let’s Go Hiking](#G-Let’s Go Hiking)

[H-Common Subsequence](#H-Common Subsequence)

[K - Tour](#K - Tour)

[L-Diamond Miner](#L-Diamond Miner)

[M - Kth Excluded](#M - Kth Excluded)

B-Matches Game

img

主要意思是说有任意堆火柴，每个人可以从任意一堆取任意数量的火柴，问先手胜还是后手胜。

思路： 尼姆博弈板子题，参考讲解很详细

AC代码：

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
ll m,a;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    while(cin>>m)
    {
    	ll ans=0;
    	for(int i=1;i<=m;i++)
    	{
    		cin>>a;
    		ans^=a;
		}
		if(ans==0) cout<<"No"<<'\n';
		else cout<<"Yes"<<'\n';
	}
	return 0;
}

C-Wireless Network

img

主要意思是说现在要计算机恢复通信，每台计算机只能与距离不超过d米的计算机直接通信，但是每台计算机都可以被视为其他两台计算机之间通信的媒介，每次操作可以修复一台计算机通信，也可以询问两台计算机是否可以通信。

思路： 并查集板子题。

AC代码：

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int n,d;
int fa[32010];
bool vis[2010];
char s;
int a,b,c;

struct node
{
	int x,y;
} e[2010];

void init()
{
	for(int i=1;i<=n;i++) fa[i]=i;
}

int getfa(int x)
{
	if(fa[x]==x) return x;
	else
	{
		int xx=getfa(fa[x]);
		fa[x]=xx;
		return xx;
	}
}

void emerge(int x,int y)
{
	int xx=getfa(x);
	int yy=getfa(y);
	fa[yy]=xx;
}

int main()
{
//	freopen("test.in","r",stdin);
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++)
    {
    	scanf("%d%d",&e[i].x,&e[i].y);
	}
	while(scanf("%c",&s)!=EOF)
	{
		if(s=='O')
		{
			scanf("%d",&a);
			fa[a]=a;
			for(int i=1;i<=n;i++)
			{
				if((e[i].x-e[a].x)*(e[i].x-e[a].x)+(e[i].y-e[a].y)*(e[i].y-e[a].y)<=d*d&&fa[i])
				{
					emerge(i,a);
				}
			    
			}
		}
		else if(s=='S')
		{
		    scanf("%d%d",&b,&c);
			if(getfa(b)==getfa(c))
			printf("SUCCESS\n");
			else
			printf("FAIL\n");
		}
		
	}
	return 0;
}

os：这个题之前做过欸

D - Cooking

img

主要意思是说有两个烤箱和几道菜，每道菜都需要一定时间制作，问全部菜制作完成最少需要多少时间。

思路： 对于每种情况，最少的时间就是所有时间相加除以2，但是由于时间没那么平均，我们可以将这个题视为01背包问题，背包容量是所有时间相加除以2。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=2e3+5;
int n,ans;
int a[N],f[100006];

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],ans+=a[i];
    int m=ans/2;
    for(int i=1;i<=n;i++)
    {
    	for(int j=ans/2;j>=a[i];j--)
    	{
    		f[j]=max(f[j],f[j-a[i]]+a[i]);
		}
	}
	cout<<ans-f[ans/2]<<'\n';
	return 0;
}

os：想了好久才发现这是个DP问题

E - Balanced Lineup

img

主要意思是说给出一个序列，每次询问给出区间左端点和右端点，求区间内最大值和最小值的差。

思路：线段树应用。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=5e4+5;
int n,q,l,r,maxn,minn;
int a[N];

struct node
{
	int maxn,minn;
 } tree[N<<2];
 
void pushup(int i)
{
	tree[i].maxn=max(tree[i<<1].maxn,tree[i<<1|1].maxn);
    tree[i].minn=min(tree[i<<1].minn,tree[i<<1|1].minn);
}

void build(int i,int l,int r)
{
	if(l==r)
	{
		tree[i].minn=tree[i].maxn=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	pushup(i);
}

void query(int i,int l,int r,int L,int R)
{
	if(L<=l&&r<=R)
	{
		maxn=max(maxn,tree[i].maxn);
		minn=min(minn,tree[i].minn);
		return;
	}
	int mid=(l+r)>>1;
	if(L<=mid) query(i<<1,l,mid,L,R);
	if(R>mid) query(i<<1|1,mid+1,r,L,R);
}

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    while(q--)
    {
    	scanf("%d%d",&l,&r);
    	maxn=-INF;
    	minn=INF;
    	query(1,1,n,l,r);
    	printf("%d\n",maxn-minn);
	}
	return 0;
}

os：就是这个线段树的题，又出了一遍QWQ

F - POW

img

主要意思是说给出A,B,C三个数，比较A的C次方和B的C次方的大小。

思路： 分类讨论即可。

AC代码：

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<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
ll a,b,c;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>a>>b>>c;
    if(a>=0&&b>=0)
    {
    	if(a>b) cout<<">"<<'\n';
    	else if(a<b) cout<<"<"<<'\n';
    	else cout<<"="<<'\n';
	}
	else if(a<0&&b<0)
	{
		if(c%2) 
		{
			if(a>b) cout<<">"<<'\n';
    	    else if(a<b) cout<<"<"<<'\n';
    	    else cout<<"="<<'\n';
		}
		else
		{
			if(a>b) cout<<"<"<<'\n';
    	    else if(a<b) cout<<">"<<'\n';
    	    else cout<<"="<<'\n';
		}
	}
	else if(a>=0&&b<0)
	{
		if(c%2) cout<<">"<<'\n';
		else
		{
			if(abs(a)>abs(b)) cout<<">"<<'\n';
    	    else if(abs(a)<abs(b)) cout<<"<"<<'\n';
    	    else cout<<"="<<'\n';
		}
	}
	else if(b>=0&&a<0)
	{
		if(c%2) cout<<"<"<<'\n';
		else
		{
			if(abs(a)>abs(b)) cout<<">"<<'\n';
    	    else if(abs(a)<abs(b)) cout<<"<"<<'\n';
    	    else cout<<"="<<'\n';
		}
	}
	return 0;
}

G-Let’s Go Hiking

img

主要意思是说两人有不同的转化方式，Q转换的数字必须小于原数，D转换的数字必须大于原数，轮流转换，若一人无法转换则输，问Q是否能赢。

思路： 观察可得，Q只能选择某个顶点，且Q要选择一个单调递增或者单调递减长度最长的一侧转换，要不然D选择的长度会是最长的，那么D就必胜。只有在单调长度最长且为奇数，并且顶点两边单调性相反，Q是必胜。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=2e5+5;
int a[N],l[N],r[N];
int maxn,n,pos,cnt;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
    	if(a[i]>a[i-1]) l[i]=l[i-1]+1;
    	else l[i]=1;
	}
	for(int i=n;i>=1;i--)
	{
		if(a[i]>a[i+1]) r[i]=r[i+1]+1;
		else r[i]=1;
	}
	for(int i=1;i<=n;i++)
	{
		if(maxn<l[i]||maxn<r[i])
		{
			maxn=max(l[i],r[i]);
			cnt=1;
			pos=i;
		}
		else if(maxn==l[i]||maxn==r[i]) cnt++;
	}
	if(cnt==1&&maxn%2&&l[pos]==r[pos]) cout<<"1"<<'\n';
	else cout<<"0"<<'\n';
	return 0;
}

H-Common Subsequence

img

主要意思是给出公共子序列(LCS)的定义，求两字符串的最长公共子序列。

思路：对字符串的DP，求LCS。

AC代码：

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e3+5; 
char a[N],b[N];
int f[N][N];

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    while(~scanf("%s%s",a,b))
    {
    	int len1=strlen(a);
    	int len2=strlen(b);
    	memset(f,0,sizeof(f));
    	for(int i=1;i<=len1;i++)
    	{
    		for(int j=1;j<=len2;j++)
    		{
    			if(a[i-1]==b[j-1])
    			f[i][j]=f[i-1][j-1]+1;
    			else
    			f[i][j]=max(f[i-1][j],f[i][j-1]);
			}
		}
		cout<<f[len1][len2]<<'\n';
	}
	return 0;
}

os：确实没想到这个题直接O(n*m)就可以过，不过题里也没给数据范围啊，，，交的时候voj爆炸，去poj交又卡了半天，无语

K - Tour

img

img

给出一个有向图，问从某一起点到某一终点一共有多少条可以走的路线。

思路：见代码。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=2e3+5;
int n,m,u,v;
int f[N][N];
ll ans;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    	cin>>u>>v;
    	if(u==v) continue;
    	if(f[u][v]!=1) ans++;
    	f[u][v]=1;
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			if(k==i) continue;
			if(f[i][k]!=1) continue;
			for(int j=1;j<=n;j++)
			{
				if(i==j) continue;
				if(f[k][j]!=1) continue;
				if(f[i][j]==1) continue;
				if(f[i][k]==1&&f[k][j]==1)
				{
					f[i][j]=1;
					ans++;
				}
			}
		}
	}
	cout<<ans+n<<'\n';
	return 0;
}

os：看到了网友的代码，三层for循环套一起，continue大法破TLE，hhhhhhh（也有可能是数据太水了）

L-Diamond Miner

img

主要意思是说每个矿工捞一颗钻石，给出所有矿工和钻石的坐标，问怎样安排矿工捞钻石使得总路程最短。

思路： 贪心，让距离原点最近的矿工捞距离原点最近的钻石，以此类推。可用坐标的绝对值代替原坐标排序，注意这样做的前提是矿工全在y轴上，钻石全在x轴上。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e5+5;
int t,n,x,y;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n;
    	int cnt=0,tot=0;
    	double nx[N]={0},ny[N]={0};//注意两个数组开的是double型！！！
    	for(int i=1;i<=2*n;i++)
    	{
    		cin>>x>>y;
    		if(x==0)
    		ny[++cnt]=abs(y);
    		else
    		nx[++tot]=abs(x);
		}
		sort(nx+1,nx+1+n);
		sort(ny+1,ny+1+n);
		double ans=0;
		for(int i=1;i<=n;i++)
		{
			ans+=sqrt(nx[i]*nx[i]+ny[i]*ny[i]);
		}
		printf("%.12lf\n",ans);
	}
	return 0;
}

os：读题不仔细，，，没看到所有坐标都是在坐标轴上的

M - Kth Excluded

img

img

主要意思是说给出一个序列和k，求不在数列中的第k小的数，数值均为正整数。

思路：用到了差分数组，举例说明：

a[i]：3 5 6 7 //原数组

b[i]：2 1 0 0 //a[i]-a[i]-1，求的是该数与前一个数之间有多少元素

f[i]：2 3 3 3 //求b数组的前缀和，表示从头到该位置有多少个数未被剔除

想知道第n个数，先二分查找n-1的区间，加上偏移量即可。

AC代码：

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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=1e5+5;
ll a[N],b[N],f[N];
int n,q;
ll k;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1]-1;
    for(int i=1;i<=n;i++) f[i]=b[i]+f[i-1];
    while(q--)
    {
    	cin>>k;
    	int i=lower_bound(f,f+1+n,k)-f;
    	cout<<k+a[i-1]-f[i-1]<<'\n';
	}
	return 0;
}

若有错误请指教

Orz

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

FEATURED TAGS
C++ 算法 并查集 线段树
FRIENDS
ESC