Codeworks round 638 (Div. 2) cute new problem solution

Codeforces Round #638 (Div. 2) Cute new problem solution ~
The official solution of the author ~
This time A-D They are all greedy ！
A. Phoenix and Balance
The question ： With 2 The first item ,2 An equal ratio sequence of common ratio , It is required to be divided into two series , To minimize the difference between the sum of these two series .
tips: You can find , The th of this arithmetic sequence n Items are larger than the previous sum , So it must be the first n Xiang Heqian n/2-1 Items form a sequence , The rest is another sequence .

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

int t,n;
ll quick_pow(int x, int n){
    
	ll res = 1;
	while(n){
    
		if(n & 1)	res = res * x;
		n >>= 1;
		x *= x;
	}
	return res;
}
int main(){
    
	scanf("%d",&t);
	while(t--){
    
		scanf("%d",&n);
		ll ans = 0,tmp1,tmp2;
		tmp1 = 2 * (quick_pow(2, n - 1) - 1);
		tmp2 = 2 * (quick_pow(2, n / 2 - 1) - 1);
		printf("%lld\n",quick_pow(2, n) - tmp1 + 2 * tmp2);
	}
	return 0;
}
 

P.S. Yes 2 The power of can be directly done by bit operation , No quick power ~ I was stupid when I did it .
B. Phoenix and Beauty
The question ： Add no more than n The number of , So that all the lengths are k The subsequence of and are equal .
Such as ： 1 2 2 1 k=3, be Added as 1 2 1 2 1, And for 4.
tips: Notice that it must be periodic It's OK . And there are Different numbers cannot be more than k individual （ Otherwise, it is impossible to construct a period of k Sequence of numbers ）. Be careful Don't be the shortest .
I wrote it so ugly that I didn't let it go Thinking is more troublesome , It's the number that keeps recurring in cycles
The idea of the answer is very clever ！ If the original sequence just k individual Different numbers , Just repeat the output directly ; If not enough k individual , It's just Each cycle is followed by k-size individual 1(or Arbitrary number ). Constitute a cycle of k Sequence of numbers . So the original sequence n Number , Each one must correspond to 1 A cycle （ Because the shortest time is not required ）.

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

void solve(){
    
  int N,K;
  cin>>N>>K;
  set<int>s;
  for (int i=0;i<N;i++){
    
    int a;
    cin>>a;
    s.insert(a);
  }
  //if more than K distinct numbers, print -1
  if (s.size()>K){
    
    cout<<-1<<endl;
    return;
  }
  cout<<N*K<<endl;
  for (int i=0;i<N;i++){
    
    //print the distinct numbers
    for (int b:s)
      cout<<b<<' ';
    //print the extra 1s
    for (int j=0;j<K-(int)s.size();j++)
      cout<<1<<' ';
  }
  cout<<endl;
}

int main(){
    
  int t; cin>>t;
  while (t--)
    solve();
}

C. Phoenix and Distribution
The question ： Give a string , It is required to arrange and combine the letters in any order to form k A string （ Does not require It's a substring of the original string ）, Make this k The string with the largest dictionary order is the smallest ~
tips： At first, the algorithm was wrong ~
Pay attention to the classified discussion ：
1. If after sorting book[1] != book[k] The answer is book[k]（ You can put the latter ones in the first string ）;
hold book[1]-book[k] be assigned to k In a string , And then from the k+1 Start ：
2. If the later ones are not the same , Then put them all in the first string , Is the answer （ Pay attention to and 3 distinguish ）;
3. If the later ones are the same , Share equally as much as possible k In a string , Finally, more than one is placed in the first string , The first string is the answer .
e.g. aaaab k = 2 The output should be aaab; and aaaaa k = 2 Then it should output aaa instead of aaaa.

At first, the wrong idea was that if the number of letters was k The multiple of is divided equally . Counter examples can be cited ：
aaabbbccc k = 3, The output should be abbbccc instead of abc.

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

int t,n,k;
char c,book[100005];

void solve(){
    
	scanf("%d%d",&n,&k);
	getchar();
	for(int i = 1; i <= n; ++i)
		scanf("%c",&book[i]);
	sort(book + 1, book + 1 + n);
	if(book[1] != book[k]){
    				// Corresponding to the above situation 1
		printf("%c\n",book[k]);
		return ;
	}
	printf("%c",book[1]);				// Corresponding to the above situation 3
	if(book[k + 1] == book[n]){
    
		int tmp = ceil((double)(n - k) / k);	// Pay attention to cast. Otherwise, divide two integers ……
		for(int i = 1; i <= tmp; ++i)
			printf("%c",book[k + 1]);	// Corresponding to the above situation 2
	}else{
    
		for(int i = k + 1; i <= n; ++i)
			printf("%c",book[i]);
	}
	putchar('\n');
}
int main(){
    
	scanf("%d",&t);
	while(t--){
    
		solve();
	}
	return 0;
}

D. Phoenix and Science
The question ： bacteria The initial mass is 1, The initial number is 1. Day Any number of bacteria can choose to divide （ The quality is divided into two ）. evening The mass of each bacterium +1. Ask if it happens to take several days , The sum of all bacterial masses is x.（ Certainly . Even if it doesn't split, it's always 1+1+1 Fine ） If possible , Find the shortest number of days and how many bacterial divisions per day .
tips:
1. Notice the split in the daytime , Gain weight at night , There is no conflict between the two ;
2. Division can be only partial .
Observation can reveal , If there has been only one bacterium , Then each weight gain is 1, The total weight is 1+1+1+……1
If it split into two , Then the total weight ：1+2+2+……+2
And so on , The shortest number of days is Every day all split （ And growth is a 2 An equal ratio sequence of common ratio ）, Until one day, if all split, it will exceed the requirements . Then sort , The number of splits per day is book[i] - book[i-1]（ If not split ,book[i] == book[i-1], More represents the number of multiple divisions . Because every split one , Total weight that night +1.book The array represents the day increase Weight of ）
e.g. 20 Can be divided into 1 2 4 8 5, After sorting, it becomes 1 2 4 5 8
be ： Day one split 1 individual , The next day split 2 individual , The third day split 1 individual （5-4）, The fourth day split 3 individual （8-5）.
Greedy code ：

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

int t,n,cnt,book[100005];

void solve(){
    
	scanf("%d",&n);
	cnt = 0;
	for(int i = 1; i <= n; i <<= 1){
    
		book[++cnt] = i;
		n -= i;			// This step is very important , Always update what is still needed n value （ Additional weight ）
	}
	if(n > 0)	book[++cnt] = n;
	sort(book + 1, book + 1 + cnt);
	printf("%d\n",cnt - 1);
	for(int i = 1; i < cnt; ++i)
		printf("%d ",book[i + 1] - book[i]);
	putchar('\n');
} 
int main(){
    
	scanf("%d",&t);
	while(t--){
    
		solve();
	}
	return 0;
}