Codeforces Round #638 (Div. 2)(A-D题解构造题杀我)

题目大意：
有一堆 $2^1,2^2,2^3,...,2^n$21,22,23,...,2n的数，现在要你把这些数分成两堆，使得每堆的和的差最小。
思路：
注意到 $2^n>2^1+2^2+...+$2n>21+22+...+ $2$2^(n-1)。
所以直接用 $2^n+前面n/2-1个最小数$2n+前面n/2−1个最小数，然后另外一堆拿下剩下的，求一个差就行了。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
const int maxn = 2e5 + 10;
void solved(){
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		if(n == 2){
			cout<<"2"<<endl;continue;
		}
		ll sum1 = (1 << n), sum2 = 0;
		for(int i = 1; i < n / 2; i++){
			sum1 += (1 << i);
		}
		for(int i = n / 2; i < n; i++){
			sum2 += (1 << i);
		}
		cout<<abs(sum1 - sum2)<<endl;
	}
}
int main(){
	solved();
	return 0;
}

题目大意：
给你一个长度为 $n$n的数组，你可以插入任何多个数到数组中，数的取值属于 $[1,n]$[1,n]，要求你最终构造出来的数组满足任意连续个长度为 $k$k的子区间和相等。
思路：
注意到 $n$n的范围非常小，我们可以直接以 $k$k为循环周期循环100次，这样可以保证至少所以数都在构造出的数组中出现一次，并且保证所以子区间和相等，但是循环的数不能随便搞，必须是题目给的数去重后的才行。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
const int maxn = 2e5 + 10;
void solved(){
	int t;
	while(cin>>t){
		while(t--){
			int n,k;cin>>n>>k;
			map<int,int>mp;int x;
			for(int i = 1;i <= n; i++)cin>>x,mp[x]++;
			vector<int>ve;
			map<int,int>::iterator it = mp.begin();
			for(;it != mp.end();it++){
				ve.push_back(it->first);
			}
			if(mp.size() > k){
				cout<<"-1";
			}else{
				cout<<100 * k<<endl;
				for(int i = 1; i <= 100; i++)
					for(int j = 0; j < k; j++)
						cout<<ve[(j % ve.size())]<<" ";
			}
			cout<<endl;
		}
	}
}
int main(){
	solved();
	return 0;
}

题目大意：
给你一个长度为 $n$n的字符串，你可以对他进行任意的排列，现在这个字符串要被分成 $k$k个部分 $=s1,s2,s3,...sk$=s1,s2,s3,...sk，要你使得构造出的所有字符串中最大值最小。这里字符串的比较遵循字典序。
思路：
分类讨论 $+$+每个字符出现次数 $+$+贪心
当 $k=1$k=1直接输出排序后的字符串即可。
为了使得最大值最小，首先对字符串排序，然后分类讨论：
$cnt{[}^{\prime }{i}^{\prime }]:字符i出现的次数$cnt[′i′]:字符i出现的次数
$sum:字符总个数$sum:字符总个数
当 cnt[第一个字符]<k，说明字符串第一个位置必定存在不同，为了使得最大值最小化，我们希望最大值尽可能短，剩下的全部加到别的字符串上去，只需要 $[1,k]$[1,k]找到最大字符输出即可。
当 $cnt\left[第一个字符\right]>k$cnt[第一个字符]>k， $sum-cnt\left[第一个字符\right]=0$sum−cnt[第一个字符]=0时，说明只有一种字符，那么希望他尽可能短，如果 $!=0$!=0，必然有别的字符，为了使得第 $i$i个位置值最小，直接将后面字符全部加上来即可。
当 $cnt\left[第一个字符\right]=k$cnt[第一个字符]=k，如果只有两种字符并且都是 $k$k的倍数，直接均分，如果出现至少三种字符，直接全部加到一起会更优。
代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long int ll;
const int maxn = 2e5 + 10;
char s[maxn];
int cnt[40];
void solved(){
	int t;
	while(cin>>t){
		while(t--){
			int n,k;cin>>n>>k;
			scanf("%s",s + 1);
			sort(s + 1, s + 1 + n);
			int sum = n;
			for(int i = 0; i < 30; i++)cnt[i] = 0;
			for(int i = 1; i <= n; i++)cnt[s[i] - 'a']++;
			if(k == 1){for(int i = 1; i <= n; i++)cout<<s[i];cout<<endl;continue;}
			if(cnt[s[1] - 'a'] < k){
				char ans = 'a';
				for(int i = 1; i <= k; i++){
					ans = max(s[i],ans);
				}
				cout<<ans<<endl;
			} else if(cnt[s[1] - 'a'] > k){
				int len = sum - cnt[s[1] - 'a'];
				if(len != 0){
					for(int i = k ; i <= n; i++)cout<<s[i];cout<<endl;
				}else{
					for(int i = 1; i <= n; i += k)cout<<s[i];cout<<endl;
				}
			}else{
				char c;
				for(int i = 2; i <= n; i++){
					if(i != s[1]){
						c = s[i];
					}
				}
				int len = sum - cnt[s[1] - 'a'] - cnt[c - 'a' ];
				if(len != 0){
					for(int i = k ; i <= n; i++)cout<<s[i];cout<<endl;
				}else{
					for(int i = 1; i <= n; i += k)cout<<s[i];cout<<endl;
				}
			} 
		}
	}
}
int main(){
	solved();
	return 0;
}

题目大意：
一开始你有 $1$1个细菌，这个细菌每天可以分裂成 $2i$2i个细菌，每次分解后的细菌质量是 $m/2$m/2，即当前质量 $/2$/2，并且每天晚上所有细菌的质量 $+1$+1，问你为了使得所有细菌分解后的质量 $=m$=m最少需要多少天？
思路：
引用https://www.cnblogs.com/num73/p/12815737.html#4566301

代码：

#include<bits/stdc++.h>
using namespace std;
 
typedef long long int ll;
void solved(){
	int t;
	while(cin>>t){
		while(t--){
			ll n;cin>>n;
			vector<int>ve;
			ll sum = 0;
			for(int i = 1; i + sum <= n; i <<= 1){
				sum += i;
				ve.push_back(i);
			}
			if(n > sum){
				ve.push_back(n - sum);
			}
			sort(ve.begin(),ve.end());
		// for(int i = 0; i < ve.size(); i++)cout<<ve[i]<<" ";cout<<endl; 
			cout<<ve.size() - 1<<endl;
			for(int i = 1; i < ve.size(); i++){
				cout<<ve[i] - ve[i - 1]<<" ";
			}
			cout<<endl;
		}
	}
}
int main(){
	solved();
	return 0;
}