A. Forbidden Subsequence

A. Forbidden Subsequence

题意：

这道题的意思是给定两个字符串s，t，其中t只由abc组成，且长度为三，我们需要对s进行排列需，使得在 t 不是 s 的子序列的同时，s 的字典序列最小。

思路分析：

我们可以先对s进行排序，然后在判断 t 是否为其子序列，如果是，把最后在 s 中出现 t 子序列，并返回该子序列的第二个字符出现的位置，然后将其往后面的挪动，如果 s 的长度小于 t 时，直接输出。

代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int Subsequence(char* s, char* t){
	int arr[3];
	int indexarr = 2;
	int indexs = strlen(s) - 1, indext = strlen(t) - 1;
	for (; indexs >= 0; indexs--){
		if (s[indexs] == t[indext]){
			arr[indexarr--] = indexs;
			indext--;
		}
		if (s[indexs] == t[indext + 1]){
			arr[indexarr + 1] = indexs;
		}
		if (indext == -1)break;
	}
	//cout << arr[0] << arr[1] << arr[2] << endl;
	if (indext == -1)return arr[1];
	return -1;
}

int main(){
	int T;
	cin >> T;
	while (T--){
		char s[1005], t[4];
		cin >> s >> t;
		int len = strlen(s);
		sort(s, s + len);
		//cout << s << endl;
		int index = Subsequence(s, t);
		while (index != -1){
			char tmp = s[index];
			for (int i = index + 1; i < len; i++){
				if (s[i] > tmp){
					s[index] = s[i];
					s[i] = tmp;
					break;
				}
			}
			//cout << s << endl;
			index = Subsequence(s, t);
		}
		cout << s << endl;

	}
	return 0;
}

B. GCD Problem

B. GCD Problem

题意：

这道题的意思是，给定一个数字n，找出三个数a，b，c，三个数的和等于n，且c = gcd(a,b)。

思路分析：

我们可以发现，总存在c = 1，能够满足给定条件下的答案，同时我们还需推测出，当n % 2 == 0 时，a = n - 3，b = n - 2，c = 1。
当n % 4 == 1时，a = n / 2 - 1，b = n / 2 + 1，c = 1。
当n % 4 == 3时，a = n / 2 - 2，b = n / 2 + 2，c = 1。

代码如下：

#include <bits/stdc++.h>

using namespace std;

void solve(){
	int n;
	cin >> n;
	if(n % 2 == 0){
		cout << "2 " << n-1-2 << " 1\n";
	}
	else{
		int cnt = (n - 1) / 2;
		if(cnt % 2 == 0){
			cout << cnt - 1 << " " << cnt + 1 << " " << "1\n";
		}
		else{
			cout << cnt - 2 << " " << cnt + 2 << " " << "1\n";
		}
	}
}

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