A. Uniform String（暴力）

题目连接：https://codeforces.com/contest/1092/problem/A

题目大意：T组数据，每组数据n，m，输出一个长为n的字符串，每个字符串中有m种字符，要让每个字符的出现频率最大，输出字符串。

分析：直接暴力，循环每次输出一排，然后在输出，可以保证，最少的字符出现次数最多。

AC：

int main()
{
	int T;
	while(cin>>T){
		while(T--){
			int n,k;
			cin>>n>>k;
			for(int i=0;i<n;++i){
				int j=i%k;
				cout<<char('a'+j);
			}
			cout<<endl;
		}
	}
}

B. Teams Forming（排序暴力）

题目链接：https://codeforces.com/contest/1092/problem/B

题目大意：给出一个数组，将这个数组种的元素两两配对，要求配对的两个元素值相等，+1可以使一个元素的值+1，问最少需要加多少，才可以配对成功。

思路：从小到大排序，然后前后必定是相差最少的。因为题目保证必定2*n，所以直接相加即可。（我又在想，如果不是2*n的话，组成小组，花费最小应该怎么解决。。）

AC：

int arr[MAXN];

int main()
{
	int n;
	while(cin>>n){
		clean(arr,0);
		for(int i=1;i<=n;++i)
			cin>>arr[i];
		sort(arr+1,arr+n+1);
		ll ans=0;
		for(int i=1;i<n;i+=2){
			ans+=arr[i+1]-arr[i];
			//cout<<ans<<endl;
		}
		cout<<ans<<endl;
	}
}

C. Prefixes and Suffixes（思维，暴力）

题目链接：https://codeforces.com/contest/1092/problem/C

题目大意：一个n个元素的字符串，里面有n-1个前缀，n-1个后缀，我们已知这些前后缀，然后，跟据这些前后缀，组装成原本的字符串，然后再对每个字串，输出是前缀（P）||后缀（S）

思路：选区两个最长的字串，将他们拼接道一起，然后有两种拼接方式，对于每种拼接方式，遍历所有的子串，看是否所有的字串都被包含，如果都被包含，则确定这个串是原来的字符串。

AC：

//#pragma comment(linker, "/STACK:1024000000,1024000000")
  
#include<stdio.h>
#include<string.h> 
#include<math.h> 
   
//#include<map>  
#include<set>
#include<deque> 
#include<queue> 
#include<stack> 
#include<bitset>
#include<string> 
#include<fstream>
#include<iostream> 
#include<algorithm> 
using namespace std; 
  
#define ll long long 
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// ˮӡ
//std::ios::sync_with_stdio(false);
//  register
const int MAXN=2e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
const double PI=acos(-1.0);

struct node{
	char s[110];
	int l;
}arr[MAXN];
char res[110];
string ans;
int n;
set<string> Set1,Set2;
multiset<string> Mul;

int judge(int a,int b){
	Set1.clear();Set2.clear();Mul.clear();
	clean(res,'\0');
	for(int i=0;i<arr[a].l;++i)
		res[i]=arr[a].s[i];
	res[n-1]=arr[b].s[n-2];
	string ans1="",ans2="";
	for(int i=0;i<n-1;++i){
		ans1+=res[i];
		ans2=res[n-i-1]+ans2;
		Set1.insert(ans1);
		Set2.insert(ans2);
		Mul.insert(ans1);
		Mul.insert(ans2);
	}
	for(int i=1;i<=2*n-2;++i){
		multiset<string>::iterator Find=Mul.find(arr[i].s);
		if(Find==Mul.end())
			return 0;
		Mul.erase(Find);
	}
	set<string>::iterator s1,s2;
	int vis[110]={0};
	ans="";
	for(int i=1;i<=2*n-2;++i){
		s1=Set1.find(arr[i].s),s2=Set2.find(arr[i].s);
		if(s1!=Set1.end()&&s2==Set2.end()){//��ǰ׺ 
			ans+="P";
			vis[arr[i].l]=1;
			//cout<<"find1:"<<*s1<<endl;
		}
		else if(s1==Set1.end()&&s2!=Set2.end()){//�Ǻ�׺ 
			ans+="S";
			vis[arr[i].l]=2;
			//cout<<"find2:"<<*s2<<endl;
		}
		else{
			if(vis[arr[i].l]==1){//����ǰ׺ 
				ans+="S";
			}
			else{
				ans+="P";
				if(vis[arr[i].l]==0)//û�г��ֹ� 
					vis[arr[i].l]=1;
			}
				
		}
	}
	//cout<<ans<<endl;
	return 1;
}

int main(){
	while(cin>>n){
		int fir=0,sec=0;
		for(int i=1;i<=2*n-2;++i){
			cin>>arr[i].s;
			arr[i].l=strlen(arr[i].s);
			if(arr[i].l==n-1){
				if(fir==0)	fir=i;
				else		sec=i;
			}
		}
		//cout<<"----------------------"<<endl;
		if(judge(fir,sec)==0){//firΪǰ׺ 
			judge(sec,fir);
		}
		cout<<ans<<endl;
	}
}

D1. Great Vova Wall (Version 1)（思维，规律）

题目链接：https://codeforces.com/contest/1092/problem/D1

题目大意：给你n堆东西的高度，问最终能否使这n堆东西的高度一致，你可以使用1*2或2*1的小方块覆盖在上面。

思路：所有相邻的两个高度，都可以变成高度差<=1的高度，然后高度差1的永远也无法填上，因此，维护一个栈，每次看栈顶和输入元素高度差是否为奇数。奇数入栈，偶数出栈顶。

AC：

stack<int> st;

int main()
{
	int n;
	while(cin>>n){
		while(st.size())
			st.pop();
		int h;
		for(int i=1;i<=n;++i){
			cin>>h;
			if(st.size()==0)
				st.push(h);
			else{
				if(st.top()%2==h%2){
					st.pop();
				}
				else
					st.push(h);
			}
		}
		if(st.size()<=1)
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
	}
}

D2. Great Vova Wall (Version 2)（思维，条件）

题目链接：https://codeforces.com/contest/1092/problem/D2

题目大意：D1的变形，不过不能用1*2的小方块了，只能用2*1的（横着的）

思路1：这样的话，就有了几种情况，即：1.该行为偶数2. 该行为奇数，但前面那行为偶数3.该行为奇数&&前面那行也为奇数，4.该行于前面那行的高度一样。

1的话，两行合并取高的（如果前面的较低，让前面的变高即可，平齐||+1），2.无法合并3.无法合并4.直接合并。维护一个栈即可，看最后栈中的元素还剩多少个。

思路2：D1的思路，加一些条件：显然，1.如果新加入的这个比栈顶元素还大的话，必定不可能抵消（能抵消的出栈了，能抵消意味着它的高度可以是任意的>=它本身）2.如果最后，栈中只有一个元素&&该元素>=所有的元素，则可以被抵消，若小于，则前面的不能与他抵消，不符合。

AC：

int arr[MAXN];
stack<int> st;

int main()
{
	int n;
	while(cin>>n){
		clean(arr,0);
		while(st.size())
			st.pop();
		int h,maxx=0,f=1;
		for(int i=1;i<=n;++i){
			cin>>h;
			maxx=max(maxx,h);
			if(st.size()==0){
				st.push(h);
			}
			else{
				if(st.top()==h){
					st.pop();
				}
				else{
					if(h>st.top())
						f=0;
					st.push(h);
				}
			}
		}
		if(f==0)
			cout<<"NO"<<endl;
		else if(st.size()==0)
			cout<<"YES"<<endl;
		else if(st.size()==1&&st.top()>=maxx)
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;			
	}
}

F. Tree with Maximum Cost（树根移动，思维）

题目链接：https://codeforces.com/contest/1092/problem/F

题目大意：给你一棵树，有一个答案：,来使得答案最大话。

思路：第一次DFS得出一棵树。然后第二次DFS得出树根向不同子节点偏移的值，取最大的即可。

ACCode：