说在前面:

        本萌新第一次打CF,只A出来四题QAQ,不过好歹没有掉分哈哈哈,+13分

A. Plus One on the Subset.

Problem - A - Codeforceshttps://codeforces.com/contest/1624/problem/A题目大意是给定一个数列,每次可以选择任意个数+1,最少要进行多少次操作才能使所有数都相等

Solution:

妥妥的签到题,找最大数减去最小数就是操作次数了

Code:

#include<bits/stdc++.h>
using namespace std;
int minn = 0x3f3f3f3f;
int maxn;
int t;
int main()
{cin>>t;while(t--){minn = 0x3f3f3f3f;maxn = 0;int n;cin>>n;for(int i = 1;i<=n;++i){int x;cin>>x;minn = min(x,minn);maxn = max(maxn,x);}cout<<maxn-minn<<endl;}return 0;} 

B. Make APProblem - B - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1624/problem/B题目大意是给定一个三元组(a,b,c),请问令其中任意一个数乘以一个整数能否成为一个等差数列.

Solution:

        本题也不难,分别模拟以c-b为公差,b-a为公差,c-a为两倍公差时能推断出第三个数是多少,看第三个数是否是没作为公差的那个数的整数倍即可

 Code:

#include<bits/stdc++.h>
using namespace std;
int t;
int main()
{cin>>t;while(t--){int a,b,c;cin>>a>>b>>c;if(c<a)swap(a,c);if(a==b&&b==c)cout<<"YES"<<endl;else if(b==c){if(b%a==0)cout<<"YES"<<endl;elsecout<<"NO"<<endl;}else{if((b+b-a)>=c&&(b+b-a)%c==0)cout<<"YES"<<endl;else if((b-(c-b))>=a&&(b-(c-b))%a==0)cout<<"YES"<<endl;else if((c+a)>=b*2&&(c+a)%(b*2)==0)cout<<"YES"<<endl;elsecout<<"NO"<<endl; }}return 0;
}

C. Division by Two and Permutation
Problem - C - Codeforceshttps://codeforces.com/contest/1624/problem/C题目大意是给定一个长度为n的数列,能否通过对其中数做任意次除以2操作使其变成一个从1-n的排列

Solution:

        本题考虑贪心,首先大于n的数,是一定要除以2直到他到n以内的,因为每个数都必须在n以内才有可能是1-n的排列,对于每个数都除以2到n以内后用哈希表存储起来。然后从n开始往下遍历每一个数,假设说当前数有多余的.就全部往下除以2处理,因为排列只允许每个数只有一个.这样处理可以保证从大到小遍历的每一个数都不大于1,如果遇到了不存在的数,直接输出NO即可,因为多余的数全部都被除以2了,没有任何一个比当前数大的数可以通过除以2得到当前的数了.

Code:

#include<bits/stdc++.h>
using namespace std;
int t;
int a[51];
int has[51];
bool check(int y,int x)
{while(y){if(y==x)	return 1;y/=2;}return 0;
}
int main()
{cin>>t;while(t--){int n;memset(has,0,sizeof(has));cin>>n;for(int i = 1;i<=n;++i){cin>>a[i];while(a[i]>n)a[i]/=2;has[a[i]]++;}bool bflag = false;for(int i = n;i>=1;--i){if(!has[i]){cout<<"NO"<<endl;bflag = true;break;}while(has[i]>1){int p = i;while(p&&has[p])p/=2;has[p]++;has[i]--;}}if(!bflag)	cout<<"YES"<<endl;}return 0;
}

D. Palindromes Coloring
Problem - D - Codeforceshttps://codeforces.com/contest/1624/problem/D这题题面看着很复杂,实际上读懂题后就很简单了

        题意大概就是将一个字符串所有字符拿出,分成k组,每组都得是回文串,可以有字母不用,求k组回文子串中最短回文子串的最大值

Solution:
        捕捉到很重要的一个关键字,最短回文子串的最大值,最小化最大值,说明可以用二分答案来解决.把左端点设为1,右端点设为n.进行二分,接下来就如何验证答案了

        我们可以发现如果x个字母能组成长度为x的回文串,那也一定可以组成x-1大小的回文串

        如:

                ABBBA的回文串我去掉B

                ABBA也是回文串再去掉B

                ABA也是回文串

       其次,一个长度为x的回文串

        如果x为偶数时,一定是由x/2个相同字母对组成

        如果x为奇数时,一定是由x/2个相同字母对+一个落单字母组成

        那么我们字符串将所有的偶数对统计出来

        如ABCDDDD串

        偶数对有2对分别为DD，DD落单字母为A,B,C

        对长度进行分类讨论,落单字母不够就拆偶数对去补

        然后对一个长度x进行判断时看看是否有x/2个偶数对

        如果x为奇数判断落单字母够不够用,不够用就拆偶数对

Code:

#include<bits/stdc++.h>
using namespace std;
int has[129];
int t,n,k;
bool check(int x){int ans = 0;int ans1 = 0;int num = 0;if(x==1)	return 1;for(int i = 'a';i<='z';++i)if(has[i])ans+=has[i]/2,ans1+=has[i]%2;if(x%2){while(ans&&ans1<k){ans--;ans1+=2;}}num+=ans/(x/2);return num>=k;
}
int main()
{cin>>t;while(t--){cin>>n>>k;memset(has,0,sizeof(has));for(int i = 1;i<=n;++i){char ch;cin>>ch;has[ch]++;}int l = 1,r = n;while(l<=r){int mid = (l+r)/2;if(check(mid))	l = mid+1;else	r = mid-1;}cout<<r<<endl;}return 0;
}