A.Musical Puzzle

题意：

用最少的长度为2的字符串按一定规则拼出s。规则是：前一个字符串的尾与后一个字符串的首相同。

分析：

统计s中长度为2的不同字符串数量。

代码：

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

typedef long long LL;
const int N = 1e5; 

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
   	int t;
   	cin >> t;
   	
   	while (t --)
   	{
   		unordered_map<string, bool> mp;
   		int n;
		cin >> n;
		string s;
		cin >> s;	
		
		int cnt = 0;
		
		for (int i = 0; i < n - 1; i ++)
		{
			string s2 = s.substr(i, 2);
			if (!mp[s2])
			{
				cnt ++;
				mp[s2] = true;
			}
		}
		
		cout << cnt << endl;
	}
        
    return 0;
}

B. Restore the Weather

题意：

给定数组a[n]和b[n]，重排b后，令任意|ai−bi|≤k成立(1≤k≤n)数据保证一定有解。

分析：

将a和b分别按从小到大的顺序匹配便是最优的，一定能满足|ai−bi|≤k成立。只需注意要恢复原来的顺序输出。

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

typedef long long LL;
const int N = 1e5 + 5;
struct Node
{
	int id, v, v2;
}a[N];
int b[N];

bool cmp(Node A, Node B)
{
	return A.v < B.v;
}

bool cmp2(Node A, Node B)
{
	return A.id < B.id;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
   	int t;
   	cin >> t;
   	
   	while (t --)
   	{
   		int n, k;
   		cin >> n >> k;
   		
   		for (int i = 0; i < n; i ++)
   		{
   			a[i].id = i;
   			cin >> a[i].v;
		}
   			
   		for (int i = 0; i < n; i ++)
   			cin >> b[i];
   			
   		sort(b, b + n);
   		sort(a, a + n, cmp);
   		
   		for (int i = 0; i < n; i ++)
   			a[i].v2 = b[i];
   			
   		sort(a, a + n, cmp2);
   		
   		for (int i = 0; i < n; i ++)
   			cout << a[i].v2 << " ";
   		cout << endl;
	}
        
    return 0;
}

C. Vlad Building Beautiful Array

题意:

给定一个a序列，你要构造一个b序列：所有元素均为正数，且要么全是偶数要么全是奇数
构造的方式：令bi = ai - aj (1≤j≤n)

分析:

2只有减奇数才能改变奇偶性。值得注意的是，根据题目要求我们无法将一个奇数序列变成偶数序列，因此只有以下三种情况：
①原本全是奇数
②原本全是偶数
③有奇有偶：这时只能将偶序列变成奇序列。我们将每一个偶数与最小的奇数消减，只要最后的结果全为正数则有解，否则无解。

代码:

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

typedef long long LL;
const int N = 2e5 + 5;
int a[N];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
   	int t;
   	cin >> t;
   	
   	while (t --)
   	{
   		int n;
   		cin >> n;
   		
   		bool check = false;
   		
   		for (int i = 0; i < n; i ++)
   			cin >> a[i];
   			
   		int cnt1 = 0, min_odd = 0x3f3f3f3f;
   		for (int i = 0; i < n; i ++)
   		{
   			if (a[i] & 1)
			{
				cnt1 ++;
				min_odd = min(min_odd, a[i]);
			}	
		}
		
		if (cnt1 == 0 || cnt1 == n)
		{
			check = true;
		}
		
		if (!check)
		{
			bool flag = true;
			for (int i = 0; i < n; i ++)
			{
				if (a[i] % 2 == 0 && a[i] <= min_odd)
				{
					flag = false;
					break;	
				}
			}
			check = flag;
		}
		
		if (check)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
        
    return 0;
}

D. Flipper

题意:

分析：

在解空间中，以n/n-1开头的排列字典序比其他可行解大，因此最优解在以n/n-1开头的解空间里。
所以本题右端点是固定的，若元素n不在开头，则r在元素n所在的位置，若n在开头，则r在元素n - 1所在的位置。
固定了r后我们再去枚举左端点l，在所有可行解中取字典序最大的那个排列即可。

代码：

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

vector<int> a;
int n;

vector<int> get(int l, int r)
{
	vector<int> res(n);
	
	int m = 0;
	for (int i = r + 1; i < n; i ++)
		res[m ++] = a[i];
		
	for (int i = r; i >= l; i --)
		res[m ++] = a[i];
		
	for (int i = 0; i < l; i ++)
		res[m ++] = a[i];
	
	return res;
}

int main() 
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		cin >> n;
		
		a.resize(n, 0);
		vector<int> res(n, 0);
		
		for (int i = 0; i < n; i ++)
			cin >> a[i];
		
		int r;
		
		for (int i = 0; i < n; i ++)
		{
			if (a[i] == n)
			{
				r = i;
				break;
			}
		}
		
		if (r == 0)
		{
			for (int i = 0; i < n; i ++)
			{
				if (a[i] == n - 1)
				{
					r = i;
					break;
				}
			}
		}
		
		if (r != n - 1)
			r --;
		
		for (int i = 0; i <= r; i ++)
		{
			auto tmp = get(i, r);
			
			if (tmp > res)
				res = tmp;
		}
		
		for (int i = 0; i < n; i ++)
			cout << res[i] << " ";
		cout << endl;
	}
	
	return 0;
}

E. Round Dance

题意:

给定一个序列a[n]，这个序列描述的是，编号为i(1<=i<=n)的节点与编号为a[i]的节点之间有一条无向边，问能构造出的联通块最少是多少和能构造出的连通块最多是多少？

分析:

最多的连通块数便是不加任何操作，当前图的连通块数。
要构造出最少的连通块，我们可以将那些不存在环的连通块合并在一起拉成一条链。
因此我们可以统计出当前图中，连通块的数量m1，存在环的连通块的数量m2，则最少的连通块的数量为m2 + 1，最多的连通块的数量为m1
统计连通块的数量有很多方法，这里用的是dfs。建图时要处理重边，map处理二元元素比较麻烦，可以采用将两个int变量哈希成一个long long值的方式来处理：value = ((LL)a << 32) + (LL)b

代码：

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

typedef long long LL;
const int N = 2e6 + 5, M = 4e6 + 5;
int h[N], e[M], ne[M], idx;
bool st[N];
int m1, m2;
bool flag;

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int fa)
{
	st[u] = true;
	
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		
		if (j != fa)
		{
			if (st[j])
			{
				flag = true;
			}
			else
				dfs(j, u);
		}
	}
} 

int main() 
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n;
		cin >> n;
		
		for (int i = 1; i <= n; i ++)
			h[i] = -1;
		idx = m1 = m2 = 0;
		
		unordered_map<LL, bool> mp;
		
		for (int i = 1; i <= n; i ++)
		{
			st[i] = false;
			int j;
			cin >> j;
			
			LL H = ((LL)i << 32) + (LL)j, H2 = ((LL)j << 32) + (LL)i;
			
			if (!mp[H] && !mp[H2])
			{
				add(i, j), add(j, i);
				mp[H] = mp[H2] = true;
			}
		}
		
		for (int i = 1; i <= n; i ++)
		{
			if (!st[i])
			{
				flag = false;
				dfs(i, -1);
				if (flag)
					m2 ++;
				m1 ++;
			}
		}
		
		if (m2 < m1)
			cout << m2 + 1 << " " << m1 << endl;
		else
			cout << m1 << " " << m1 << endl;
	}
	
	return 0;
}

F. Ira and Flamenco

题意：

给定一个a序列，求优美子序列总数对1e9 + 7取模的结果。优美子序列应满足：
子序列的大小为m
子序列中的元素各不相同
子序列中任意两个元素差的绝对值严格小于m

分析：

我们不妨先从小到大将其排个序，记录每个元素的个数并去重。子序列abcd出现的次数即子序列中每个元素出现次数的累乘。由于每个元素各不相同，因此任意两个元素至少相差1，所以我们选择的方案在排序去重后实际上时连续的。因此我们可以维护一个前缀积，在新序列里枚举长度为m的连续序列，只要最大值与最小值差的绝对值小于m则统计。

代码：

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

typedef long long LL;
const int mod = 1e9 + 7;

LL qmi(LL m, LL k)
{
	LL res = 1, t = m;
	
	while (k)
	{
		if (k & 1)
			res = res * t % mod;
		t = t * t % mod;
		k >>= 1;
	}
	
	return res;
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n, m;
		cin >> n >> m;
		
		vector<int> a(n + 1);
		vector<LL> f(n + 1);
		unordered_map<int, int> mp;
		
		for (int i = 1; i <= n; i ++)
		{
			cin >> a[i];
			
			mp[a[i]] ++;
		}
		
		sort(a.begin() + 1, a.begin() + n + 1);
		
		a.erase(unique(a.begin() + 1, a.end()), a.end());
		
		f[0] = 1;
		for (int i = 1; i < a.size(); i ++)
			f[i] = f[i - 1] * mp[a[i]] % mod;
			
		LL res = 0;
			
		for (int i = m; i < a.size(); i ++)
		{
			if (a[i] - a[i - m + 1] < m)
			{
				res = (res + f[i] * qmi(f[i - m], mod - 2) % mod) % mod;
			}
		}
		
		cout << res << endl;
	}
	
	return 0;
}

G. Ksyusha and Chinchilla

题意：

给定一个含有n个顶点的树，求一个合法的删边方案保证删完这些边后为若干个长度为3的链。输出合法的删边方案或告诉这是不可能的。

分析：

我们可以自下向上去维护子树的节点总数，合法的情况只有：

倘若当前子树节点总数为3，则将其与父节点的边砍掉并记录。

代码：

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

typedef long long LL;
const int N = 2e5 + 5, M = 4e5 + 5;
int h[N], e[M], ne[M], idx;
int k;
LL res[N];
bool check;
bool cut[N];

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u, int fa)
{
	int cnt = 1;
	
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		
		if (j != fa)
		{
			cnt += dfs(j, u);
			if (cut[j])
				res[k ++] = ((LL)u << 32) + (LL)j;
		}
	}
	
	if (cnt > 3)
	{
		check = true;
		return 0;
	}
	else if (cnt == 3 && u != 1)
	{
		cut[u] = true;
		return 0;
	}
	return cnt;
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n;
		cin >> n;
		
		memset(h, -1, sizeof h);
		memset(cut, false, sizeof cut);
		idx = k = 0;
		check = false;
		unordered_map<LL, int> mp;
				
		for (int i = 1; i < n; i ++)
		{
			int a, b;
			cin >> a >> b;
			
			LL H1 = ((LL)a << 32) + (LL)b, H2 = ((LL)b << 32) + (LL)a;
			mp[H1] = mp[H2] = i;
			
			add(a, b), add(b, a);
		}
		
		int remain = dfs(1, -1);
		
		if (check || remain != 3)
			cout << -1 << endl;
		else
		{
			cout << k << endl;
			if (k == 0)
				cout << " " << endl;
			else
			{
				for (int i = 0; i < k; i ++)
				{
					cout << mp[res[i]] << " ";
				}
				cout << endl;
			}
		}
	}
	
	return 0;
}