C++ 线段树 博弈

SDNU_ACM_2022_Winter_Practice_2nd

寒假第二次训练补题

Posted by zhangmh on 2022-02-03
Estimated Reading Time 13 Minutes
Words 2.5k In Total
Viewed Times

这次队长说题目不会像上次一样做的那么顺，，，出了很多看上去像是cf上的题，结果发现是很古早的cf Div3。。。

目录

[A-Decrease the Sum of Digits](#A-Decrease the Sum of Digits)

[B - Two Platforms](#B - Two Platforms)

[C-Yet Another Array Restoration](#C-Yet Another Array Restoration)

[D-Minimum Product](#D-Minimum Product)

[E-Yet Another Two Integers Problem](#E-Yet Another Two Integers Problem)

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

[M-Colorful Candies](#M-Colorful Candies)

N-取石子游戏

A-Decrease the Sum of Digits

img

给出n，求最少经过几次操作n的各位数之和小于等于s。

思路：分类讨论：1、原来的n各位数之和小于s，输出0；2、若各位数之和大于s，因为要求最小次数，则进位应该是最少次。

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
#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;
int t,s;
ll n,ans;

ll pmod(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b%2) res=res*a;
		b/=2;
		a=a*a;
	}
	return res;
}

int pan(ll n,int s)
{
	int ans=0;
	while(n)
	{
		ans+=n%10;
		n/=10;
	}
	return ans;
}

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n>>s;
    	ll sum=pan(n,s);
    	if(sum<=s) cout<<"0"<<'\n';
    	else
    	{
    		int cnt=0;
    		bool flag=0;
    		ll l=n;
    		while(n)
    		{
    			sum-=n%10;
    			cnt++;
    			n/=10;
    			if(sum+1<=s)
    			{
    				flag=1;
    				break;
				}
			}
			if(flag)
			{
				if(n) ans=(n+1)*pmod(10,cnt)-l;
				else ans=pmod(10,cnt)-l;
			}
			cout<<ans<<'\n';
		}
	}
	return 0;
}

B - Two Platforms

img

给出n个点的横纵坐标，以及两个平面的长度，点的横坐标在平面的范围内时可以被平面接住，问两平面最多可以接住多少个点。

思路：很容易得知，解题与y坐标无关，将x坐标由小到大排序，枚举第一块木板从第i个点开始，可以覆盖到第j个点，由于第二块木板覆盖初位置不定，那么我们就预处理一个a[i]，表示从第[i,n]个小球开始覆盖的最优取值，用这个数组来得到第二块木板的覆盖最优值。

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 t,n;
int k,x[N],y[N],a[N];

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    ios;
	cin>>t;
    while(t--)
    {
    	cin>>n>>k;
    	memset(a,0,sizeof(a));
    	for(int i=1;i<=n;i++) cin>>x[i];
    	for(int i=1;i<=n;i++) cin>>y[i];
    	sort(x+1,x+1+n);
    	for(int i=n;i>=1;i--)//枚举第二块板子覆盖
    	{
    		int now=x[i]+k;
    		int ind=upper_bound(x+1,x+1+n,now)-x;
    		a[i]=max(a[i+1],ind-i);
		}
		int ans=0;
		for(int i=1;i<=n;i++)//枚举第一块板子覆盖
		{
			int now=x[i]+k;
			int ind=upper_bound(x+1,x+1+n,now)-x;
			ans=max(ans,a[ind]+ind-i);
		}
		cout<<ans<<'\n';
	}
	return 0;
}

os：开始的时候想到对x数组排序，后面不知道怎么模拟木板覆盖了

C-Yet Another Array Restoration

img

给出排序后为等差数列中的任意两项，要求构造最大项最小的数列（SJ）。

思路：先看这两个数之间最多有多少项，不够的能放到小于较小值的就放到较小值左侧，再剩余的放到较大项右侧，注意细节，所有项都大于0！

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
#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=55;
ll t,n,x,y;
ll a[N];

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n>>x>>y;
    	ll dis=y-x,d;
    	ll q=n-1;
    	while(q)
    	{
    		if(dis%q==0) 
    		{
    			d=dis/q;
    			break;
			}
			q--;
		}
		ll num=dis/d+1;
		if(num==n)
		{
			for(ll i=0;i<n;i++)
			{
				ll ans=y-i*d;
				cout<<ans<<" \n"[i==n-1];
			}
		}
		else
		{
			if(x-(n-num)*d>0)
			{
				for(ll i=0;i<n;i++)
				{
					ll ans=y-i*d;
					cout<<ans<<" \n"[i==n-1];
				}
			}
			else 
			{
				if(x%d)
				{
					ll oth=n-x/d-num;
				    for(ll i=0;i<n;i++)
				    {
					    ll ans=y+d*oth-i*d;
					    cout<<ans<<" \n"[i==n-1];
				    }
				}
				else
				{
					ll oth=n-(x-1)/d-num;
				    for(ll i=0;i<n;i++)
				    {
					    ll ans=y+d*oth-i*d;
					    cout<<ans<<" \n"[i==n-1];
				    }
				}
			}
		}
	}
	return 0;
}

D-Minimum Product

img

给出a，b，x，y，无论怎样操作，a均满足不小于x，b均满足不小于y，给出操作数，问a，b操作后最小的积是多少。

思路：我们知道两个数差值越大，积越小。所以在先给a减去尽可能多的值和先给b减去尽可能多的值的两个结果取较小值即可。

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
#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;
int t;
ll a,b,x,y,n;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>a>>b>>x>>y>>n;
    	ll ans,ans1,ans2;
    	ans1=(b-min(n,b-y))*(a-min(a-x,n-min(n,b-y)));
    	ans2=(a-min(n,a-x))*(b-min(b-y,n-min(n,a-x)));
    	ans=min(ans1,ans2);
		cout<<ans<<'\n';
	}
	return 0;
}

os：一开始分了很多种情况讨论，会少情况，结果最后发现这样写几行就搞定了

E-Yet Another Two Integers Problem

img

a最少经过几次操作得到b。

思路： 贪心。（好水啊）

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
#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 t;
ll a,b;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>a>>b;
    	if(a==b) cout<<"0"<<'\n';
    	else
    	{
    		ll minn=min(a,b);
    		ll maxn=max(a,b);
    		if((maxn-minn)%10==0)
    		cout<<(maxn-minn)/10<<'\n';
    		else
    		cout<<(maxn-minn)/10+1<<'\n';
		}
	}
	return 0;
}

I - 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;
}

M-Colorful Candies

img点击并拖拽以移动编辑

img

取一段连续区间，取到不同数的最大个数是多少。

思路： 用map存每个数的个数，向map里面加一个从前面减一个。

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
#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=3e5+5;
int k,n,maxn;
ll a[N];

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
    	cin>>a[i];
	}
	map<int,int>mp;
	for(int i=0;i<n;i++)
	{
		mp[a[i]]++;
		if(i>=k-1)
		{
			if(maxn<mp.size()) maxn=mp.size();
			mp[a[i-k+1]]--;
			if(mp[a[i-k+1]]==0) mp.erase(a[i-k+1]);
		}
	}
	cout<<maxn<<'\n';
	return 0;
}

os：注意细节的处理

N-取石子游戏

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
#include<iostream>
#include<cmath>

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;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    while(cin>>a>>b)
    {
    	ll maxn=max(a,b);
    	ll minn=min(a,b);
    	ll x=(ll)((sqrt(5.0)+1)/2*(maxn-minn));
    	if(x==minn) cout<<"0"<<'\n';
    	else cout<<"1"<<'\n';
	}
	return 0;
}

os：博弈类型见一个记一个结论，，后面想整理一个博弈的专题

图论的相关题目，，唉基础太差准备去做一下专题把板子题整清楚吧

若有错误请指教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