Contestant. Rank 1053. Rating +125.
A. Double Click
题意
定义两个点击时刻 \(s_1, s_2\) 的差小于等于某个值 \(D\) 时视为在靠后的时间点 \(s_2\) 时触发双击。
给定一个点击时刻的序列，判断哪个时刻触发了第一次双击。无双击输出 \(-1\)。
思路
如题，模拟即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;
void init(){}
void solve() {
int n, d;
cin >> n >> d;
int ans = -1;
int pre;
cin >> pre;
for(int i=1;i<n;i++){
int cur;
cin >> cur;
if(cur - pre <= d && ans == -1) ans = cur;
pre = cur;
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t = 1;
//cin >> t;
while(t --) solve();
}再点一次返回到主页面
B. chess960
题意
给定一个由 \(KQRRBBNN\) 经过任意排列后的字符串，输出其是否满足下面的要求：
\(B\) 的两个下标的奇偶性不同；
\(K\) 在两个 \(R\) 中间
思路
如题，模拟即可。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;
void init(){}
void solve() {
string s;
cin >> s;
int k, q;
vector<int> r, b, n;
for(int i=0;i<8;i++){
char x = s[i];
if(x == 'K') k = i;
else if(x == 'Q') q = i;
else if(x == 'R') r.emplace_back(i);
else if(x == 'B') b.emplace_back(i);
else if(x == 'N') n.emplace_back(i);
}
bool ans = true;
if(b[0] % 2 == b[1] % 2) ans = false;
if(k < r[0] || k > r[1]) ans = false;
cout << (ans ?"Yes\n" : "No\n");
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t = 1;
//cin >> t;
while(t --) solve();
}两面包夹芝士
C. PC on the Table
题意
给定 \(H\) 个由 "." 和 "T" 组成的字符串，规定两个相邻的 \(T\) 可以替换为 \(PC\)，输出替换次数最多的一种方案。
思路
直接暴力枚举替换即可。
时间复杂度：\(O(nm)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;
void init(){}
void solve() {
int n, m;
cin >> n >> m;
for(int i=0;i<n;i++){
string s;
cin >> s;
for(int j=1;j<m;j++){
if(s[j] == s[j - 1] && s[j] == 'T'){
s[j - 1] = 'P';
s[j] = 'C';
j ++;
}
}
cout << s << '\n';
}
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t = 1;
//cin >> t;
while(t --) solve();
}PC?
D. Count Subtractions
题意
给定两个数 \(A, B\)，规定一次操作为将较大的数减去较小的数。
输出让两数相等的最小操作数。
思路
这题可以等价为重复操作直到某一个数变为 \(0\)，那么我们将计算得到的结果 \(-1\) 即可。
若 \(A > B\)，那么在 \(A\) 减到小于等于 \(B\) 后，值恰好为 \(A \bmod b\)，此时操作数就是 \(\lfloor\frac{a}{b}\rfloor\)。
如上，我们暴力即可。
时间复杂度：反正还行吧（
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;
void init(){}
void solve() {
int a, b;
cin >> a >> b;
int ans = 0;
while(a != 0 && b != 0) {
if(b > a) swap(a, b);
ans += a / b;
a %= b;
}
cout << ans - 1 << '\n';
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t = 1;
//cin >> t;
while(t --) solve();
}暴力暴力
E. Kth Takoyaki Set
题意
给定一个序列，通过任选数量、任选元素相加得到新的序列，序列升序且无重复元素，输出序列中第 \(k\) 个数，其中 \(k\) 给定。
思路
我们可以直接暴力。
首先，我们希望可以找到一个与当前最大值最接近的那个数，或者说，将组成最大值的某个数替换，这样通过递推就可以使构造出来的序列的相邻元素差值最小。
所以，我们不妨用 \(set\) 去重并顺便排序，对于查找与当前最大值最接近的那个数，我们可以用二分。
思路具有一定的贪心性，此处暂时不给出证明（
时间复杂度：\(O(pn \log p)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;
void init(){}
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for(int i=0;i<n;i++) cin >> a[i];
set<int> st;
st.emplace(0);
while(st.size() != k + 1){
int mx = *st.rbegin(), now = inf;
for(int i=0;i<n;i++){
now = min(now, *st.upper_bound(mx - a[i]) + a[i]);
}
st.emplace(now);
}
cout << *st.rbegin() << '\n';
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
int t = 1;
//cin >> t;
while(t --) solve();
}其实是不会证（x