C++

2022.01.10cf

Posted by zhangmh on 2022-01-11
Estimated Reading Time 6 Minutes
Words 1.4k In Total
Viewed Times

终于到了寒假啦，前面打的几次cf都没补题，欠了好多任务，，，倒着来吧（可能不全，后面会补，，，）

A. Plus One on the Subset

img

主要意思是说可以任选数组中的某些元素+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
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;
int t;
int n;
ll a[100]; 

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

废话可跳过：一直期末复习然后昨天写代码都生疏了，，，其实找最大值最小值可以直接排序取第一个和最后一个值，当时没想起来。

B. Make AP

img

主要意思是说给出既定顺序的三个数，能否找到一个数m，当三个数中任意一个乘m，使得三个数为等差数列。

思路： 在操作中仅需改变三个数a，b，c其中的一个，所以满足等差数列会有三种情况：a，b不变，b，c不变，a，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
#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;
int a,b,c;

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

废话可跳过：我一开始做的时候按照三个数的大小顺序分类讨论，结果会漏掉情况，要注意从等差数列入手考虑！

C. Division by Two and Permutation

img

主要意思是说给定数列，是否可以通过除以2来使数组中的数满足存在1~n的数字（除以2向下取整）。

思路： 用STL的set做很容易理解，每输入一个数，当它大于n时除以2，小于n时判断set中是否有该数，若没有insert到set中，若有则继续除以2，若该数对于set中的数没有任何贡献，则必不满足条件。

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;
int t,n,a;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n;
    	set<int>ss;
    	int flag=true;
    	for(int i=1;i<=n;i++)
    	{
    		cin>>a;
    		while(a>n) a/=2;
    		while(ss.count(a)) a/=2;
    		if(a==0) flag=false;
    		else
    		ss.insert(a);
		}
    	cout<<(flag?"YES":"NO")<<'\n'; 
	}
	return 0;
}

废话可跳过：一开始想到用set去实现，但是具体的细节没想清楚，，，

D. Palindromes Coloring

img

主要意思是说给定字符串s，判断可以通过交换任意两个字符而形成的最短的回文字符串，但是注意要分成给定k个回文字符串。

思路：判断字符串中有多少成对的相同字母，多少奇数个字母，最长的最短回文串至少是成对相同字母除以k值的大小；关于奇数个字母，当剩余部分字母数大于要分成的回文串数时，给最短回文串长度加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
33
34
35
36
37
38
39
40
#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;
int n,k;
string s;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n>>k;
    	cin>>s;
    	int a[30]={0};
    	for(int i=0;i<n;i++)
    	a[s[i]-'a']++;//统计每个字母的个数
    	int odd=0;
    	int even=0;
    	for(int i=0;i<26;i++)
    	{
    		even+=a[i]/2;
    		odd+=a[i]%2;
		}
		int ans=even/k*2;
		if(even%k*2+odd>=k)
		ans++;
		cout<<ans<<'\n';
	}
	return 0;
}

废话可跳过：一开始没做出来，然后看别人的AC代码还理解了好久QAQ。。。

下面的3个题理解题就理解了好久，后面补吧

若有错误请赐教

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