C/C++教程

Codeforces Round #761 (Div. 2)

本文主要是介绍Codeforces Round #761 (Div. 2),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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;
}
这篇关于Codeforces Round #761 (Div. 2)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!