ecjtu-2020訓練賽（1）解題報告

A題 CF1382A Common Subsequence

思路：
因為要求兩個陣列中的最短的公共子序列，如果有公共子序列的話，一定是1最短，也就是說只要同一個數即在a陣列出現過，又在b陣列中出現過，那么答案就是1，如果a陣列和b陣列中的任何一個數都不相同，就沒有公共子序列，輸出NO！

const int N = 1e3+5;

int n, m, a, b;
bool vis[N];

void solve()
{
	memset(vis, 0, sizeof vis);
	
	cin >> n >> m;
	
	int flag = 0, res;
	for(int i = 1; i <= n; i++)
	{
		cin >> a;
		vis[a] = true;	
	}
	for(int i = 1; i <= m; i++)
	{
		cin >> b;
		if(vis[b])	flag = 1, res = b;
	}
	
	if(flag)
	{
		cout << "YES" << endl << "1 " << res << endl;
	}
	else	cout << "NO" << endl;
}

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

B題 Sequential Nim

思路：
先嘗試著推一下：

當只有一堆石子時：
很明顯，First勝

當有兩堆石子時：
如果第一堆的石子數a>1，那么First可以拿a-1個，留下1個給Second拿，接下來First又回到了只有一堆石子的必勝狀態，First勝，
如果第一堆的石子數a=1，那么Second勝

當有三堆石子時：
且先不看第一堆，因為是博弈游戲，根據后兩堆石子的數量，一定可以得出是先手會贏還是后手會贏，那么如果第三堆的石子數a>1,那么先手此時可以扭轉局面——他可以讓自己成為后手或者繼續做先手，比如說他拿a-1和石子，那么到下一輪他又成為了下一堆的先手，而如果他拿完a個石子，那么到了拿下一堆的時候他成為了后手，

類似的，當有n堆石子時，只要兩者中的某一個人遇到了（注意是第一次遇到時）石子數a>1的情況，那么他就可以根據后面剩余石子的數量來判斷是先手能贏還是后手能贏，以此來決定自己是成為先手還是后手，此時游戲的最侄訓勝者就確定了，

void solve()
{
	int n; cin >> n;
	
	int a;
	bool flag = 1, find = 0;
	for(int i = 1; i <= n; i++)
	{
		cin >> a;
		if(find || i == n)	continue; // 如果已經遇到了石子數>1的情況 或者 當前已經是最后一堆石子了
		if(a > 1)	find = 1; // 遇到a>1，標記一下
		else	flag ^= 1; //在沒遇到a>1之前，兩者交替執行，1代表First，0代表Second
	}
	if(flag)	cout << "First" << endl;
	else	cout << "Second" <<endl;
}

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

C題 CF1385A Three Pairwise Maximums

這個就不多說了，按x，y，z的大小關系分類討論，然后根據式子推一下就好了

可以分為3種情況：
① x > y

可得b>a且b>c
所以z = x，如果題目給的z不等于x就無解
最后令 a = y, b = x, c = y;

② x < y

和①類似
可得c>a且c>b
所以 z = y, 如果題目給的z不等于y就無解
最后令 a = x, b = x, c = y;

③ x = y

如果x = z ,說明3者相同，直接輸出 a = x, b = x, c = x;
如果x < z,會出現矛盾，x<z，說明c>a且c>b，但是我們的前提條件是x = y,這樣會使的x ！=y
如果x > z,輸出 a = x, b = z, c = z;

D題 CF1385B Restore the Permutation by Merger

題目要求p陣列中每一個數在原陣列中的相對位置不變，且題目保證了有解，也就是說每個數都會出現2次，我們在讀入a陣列記住每個數是不是第一次出現，如果是，在p陣列直接中加入它

const int N = 110;

vector<int> p;
bool vis[N];

void solve()
{
	p.clear(); memset(vis, 0, sizeof vis);
	
	int n; cin >> n;
	
	for(int i = 1, x; i <= 2*n; i++)
	{
		cin >> x;
		if(vis[x])	continue;
		vis[x] = true;
		p.push_back(x);
	}
	
	for(int i = 0; i < p.size(); i++)	cout << p[i] << " ";
	cout << endl;
}

int main()
{
	IOS;
	int t = 1; cin >> t;
	while(t--)	solve();
	return 0;
}

E題 CF1388A Captain Flint and Crew Recruitment

題目問正整數n是否可以寫成四個互不相同的正整數的和，并滿足這四個正整數中至少有三個是類質數，
我們可以求出前幾個類質數
2×3 = 6
2×5 = 10
2 × 7 = 14
3 × 5 = 15

因為最少要三個，我們可以求出最小的一個滿足條件的數為 6 + 10 + 14 + 1 = 31，如果給出的數比31還小，那么一定無法組成了，

題目說至少三個類質數，第四個可以是也可以不是，
我們可以直接讓組成n的三個類質數就是 6,10,14， 然后第4個等于n-6-10-14，因為第四個可以是類質數也可以不是，那么我們得到的這個數無論如何都是滿足條件的，除非它和前面的某一個數重復了，因為不能有重復數字出現，這個時候只需要將14換成15然后第四個數-1就不會重復了

const int N = 2e5 + 5;

int limit = 31;

void solve()
{
	int n; cin >> n;
	if(n < limit)	cout << "NO" <<endl;
	else
	{
		cout <<"YES" << endl;
		if(!(n - 30 == 6 || n - 30 == 10 || n - 30 == 14))
		{
			cout << 6 << " " << 10 << " " << 14 << " " << n - 30 << endl;
		}
		else
		{
			cout << 6 << " " << 10 << " " << 15 << " " << n - 31 << endl;
		}
	
	}
	
}

int main()
{
	IOS;
	
	int t = 1; cin >> t;
	while(t--)	solve();
	return 0;
}

F題 CF1388B Captain Flint and a Long Voyage

要求r最大時x最小
先來看如何r才能最大？
很明顯，對于一個數，如果位數越多，那么他就越大，所以我們首先要保證去掉k后面的n位二進制數后，留下的位數最大，那么對于n的每一位，我們只能要么填9，要么填8，因為8和9的二進制都有四位

又因為在保證r最大的前提下x最小，因為后面的n位要去掉，所以只要和后邊的n位有交集的都填8，其余的填9

void solve()
{
	int n; cin >> n;
	
	int pos = 1;
	while(4 * pos < n)	pos ++; // 找到8和9的分界線
	
	for(int i = n; i > pos; i--)	cout << 9;
	for(int i = pos ; i; i--)	cout << 8;
	cout << endl;
}

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