526互联

AtCoder Beginner Contest(abc) 297

发布时间 2023-06-28 22:19:46作者: mostimali



B - chess960

题目大意

给定一串字符串, 里面一定包含2个' B ', 2个' R ', 1个' K ', 问该字符串是否满足以下两个条件, 一是两个'B'所在位置奇偶性不同; 二是'K'的位置在两个'R'之间

解题思路

签到题不多嗦了;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 100+ 10, mod = 998244353;
int n, m;
bool check(int a, int b) {
	bool f1, f2;
	if (a % 2 == 1) f1 = true;
	else f1 = false;
	if (b % 2 == 1) f2 = true;
	else f2 = false;
	if (f1 != f2) return true;
	else return false;
}
signed main(){
	string s;
	cin >> s;
	int x, y, z;
	x = s.find_first_of('B');
	y = s.find_last_of('B');
	if (check(x, y)) {
		x = s.find_first_of('R');
		y = s.find_last_of('R');
		z = s.find('K');
		if (x <= z && z <= y) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	else cout << "No" << endl;
	return 0;
}



D - Count Subtractions

题目大意

给定两个数a, b; 如果a > b, 则a -= b; 如果b > a, 则b -= a; 问经过多少次操作才能使得a = b;
保证一定有解;

解题思路

直接减肯定会超时, 所以需要用除法来加速;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 100+ 10, mod = 998244353;
int n, m, k;
signed main(){
	cin >> n >> m;
	int a = max(n, m);
	int b = min(n, m);
	while (a != b) {
		int c = a / b;
		if (a % b == 0) c--;
		k += c;
		a -= c * b;
		swap(a, b);
	}
	cout << k << endl;
	return 0;
}



E - Kth Takoyaki Set

题目大意

小莫去买礼物, 现在给定n个礼物以及它们的价格; 并且小莫至少会买一个礼物; 问小莫的多种选择方案种花销第m少的花费是多少; 如果有多种选择方案的花销是相同的, 那么这个花销只能算一次;

解题思路

据说这是一个经典题目. 但是这个题我想的太复杂了, 题解是用set来维护当前最小值; 先把最初的n个价格放进set中, 找到最小值; 这就是最少的花销, 我们把这个数存起来后再把它从set中删去; 然后再遍历最初的n个价格, 让他们都加上当前的最小值, 然后在放进set; 重复上述过程就找到了第2少的花销, 直到找到第m少即可;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5+ 10, mod = 998244353;
int n, m, k;
int q[N];
set<int> s;
signed main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> q[i];
		s.insert(q[i]);
	}
	for (int i = 1; i < m; i++) {
		int t = *s.begin();
		s.erase(s.begin());
		for (int j = 1; j <= n; j++) {
			s.insert(t + q[j]);
		}
	}
	cout << *s.begin();
	return 0;
}