Codeforces Round #764 (Div. 3)（A B C D E F G）

A - Plus One on the SubsetB - Make APC - Division by Two and PermutationD - Palindromes ColoringE - Masha-forgetfulF - Interacdive ProblemG - MinOr Tree

题意：给定一个数组，你每次可以选择任意位置任意数量的数字加1，问需要几次能把数组所有的元素变成同样大小。

题解：最小的元素变成最大的元素的次数就是答案，其他的元素在这个过程中就也能变成最大的。

代码：

#include
using namespace std;

#define endl "n"
#define ll long long
#define inf 0x3f3f3f3f
#define infll 1e15+7
#define IOS ios::sync_with_stdio(0); cin.tie(0)
#define debug(a) cout<<"*****tdebug: "<
const double eps = 1e-7;
const double pi = acos(-1.0);
const int mod = 1e9+7;
const int N = 5 + 2e5;



int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif
	IOS;
// ---------------------------------------------------------------
	int T; cin>>T;
	while(T--)
	{
		int n; cin>>n;
		int maxx = -inf, minn = inf;
		for(int i = 0; i < n; i++)
		{
			int x; cin>>x;
			maxx = max(maxx, x);
			minn = min(minn, x);
		}
		cout< 
B - Make AP 
题意：给定三个数，你可以任意选择一个，乘以m（m > 0），如果操作之后的序列满足等差数列，输出 YES，否则输出 NO。
 
题解：分类讨论一下即可，注意乘以 m之后的那个数要大于0
 
代码：
 
#include
using namespace std;

#define endl "n"
#define ll long long
#define inf 0x3f3f3f3f
#define infll 1e15+7
#define IOS ios::sync_with_stdio(0); cin.tie(0)
#define debug(a) cout<<"*****tdebug: "<
const double eps = 1e-7;
const double pi = acos(-1.0);
const int mod = 1e9+7;
const int N = 5 + 2e5;



int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif
	IOS;
// ---------------------------------------------------------------
	int T; cin>>T;
	while(T--)
	{
		ll a, b, c; cin>>a>>b>>c;
		ll d1 = c - a;
		if((c-a)%2 == 0)
		{
			ll bb = a + (c-a)/2;
			if(bb%b == 0 && bb > 0) 
			{
				cout<<"YES"< 0) 
		{
			cout<<"YES"< 0)
		{
			cout<<"YES"< 
C - Division by Two and Permutation 
题意：给定一个长度为 n的数组，你可以任意次将数组中的数除以2（向下取整），如果数组元素可以变成 1 2 3 … n,输出YES，否则输出NO。
 
题解：先把大于 n的数，向下取整直到小于等于 n。用 map先记录此时数组每个元素对应的
 1到 n。然后从大往小遍历，如果数 x对应的 mp[x]大于1，x用一个，把多余的分给 x/2。(具体看代码)
 
代码：
 
#include
using namespace std;

#define endl "n"
#define ll long long
#define inf 0x3f3f3f3f
#define infll 1e15+7
#define IOS ios::sync_with_stdio(0); cin.tie(0)
#define debug(a) cout<<"*****tdebug: "<
const double eps = 1e-7;
const double pi = acos(-1.0);
const int mod = 1e9+7;
const int N = 5 + 50;

int a[N], vis[N];
map mp;

int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif
	IOS;
// ---------------------------------------------------------------
	int T; cin>>T;
	while(T--)
	{
		int n; cin>>n;
		int cnt = 0;
		mp.clear();
		memset(vis, 0,sizeof vis);
		for(int i = 0; i < n; i++) 
		{
			cin>>a[i];
			while(a[i] > n) a[i]>>=1;
			mp[a[i]]++;
		}
		for(int i = n; i >= 1; i--)
		{
			while(mp[i] > 1)
			{
				mp[i]--;
				mp[i/2]++;
			}
		}
		bool flag = 0;
		for(int i = 1; i <= n; i++)
		{
			if(mp[i] == 0)
			{
				flag = 1;
				break;
			}
		}
		if(flag) cout<<"NO"< 
D - Palindromes Coloring 
题意：给定一个字符串，k种颜色，然后给字符串染色。每种颜色至少用 1次，但可以不把所有字符都染色。染色之后把相同颜色的字符当作一组，可以组内任意交换位置，保证每组都为回文串。求长度最短的一组的最大长度（尽可能保证均分就长度最大。
 
题解：统计一下一共有几对相同的字符。然后均分给 k组，然后统计剩余的单个字符个数（包括没用到的成对字符），如果大于 k，就每组都再分一个字符（放中间还是回文串）。
 
代码：
 
#include
using namespace std;

#define endl "n"
#define ll long long
#define inf 0x3f3f3f3f
#define infll 1e15+7
#define IOS ios::sync_with_stdio(0); cin.tie(0)
#define debug(a) cout<<"*****tdebug: "<
const double eps = 1e-7;
const double pi = acos(-1.0);
const int mod = 1e9+7;
const int N = 5 + 50;

map mp, vis;

int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.in", "r", stdin);
	freopen("out.out", "w", stdout);
#endif
	IOS;
// ---------------------------------------------------------------
	int T; cin>>T;
	while(T--)
	{
		int n, k; cin>>n>>k;
		string s; cin>>s;
		mp.clear();
		vis.clear();
		int len = s.size();
		for(int i = 0; i < len; i++) mp[s[i]]++;
		int ans = 0;
		for(int i = 0; i < len; i++) 
		{
			if(!vis[s[i]])
			{
				vis[s[i]] = 1;
				ans += mp[s[i]]/2;
			}
		}
		int cnt = len-(ans - ans%k)*2;
		if(cnt >= k) cout<<(ans/k)*2+1< 
E - Masha-forgetful 
先占个坑一会码）
 
F - Interacdive Problem 
先占个坑一会码）
 
G - MinOr Tree 
先占个坑一会码）