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;
}