这场的题不错,就是一直在 i n q u e u e in queue inqueue,体验感很是不好,导致我 B C B C BC两题一个小时才过, 还好写了 7 7 7题,差一点点就 A K AK AK了
A. A+B Again?
思路: 输出数位之和
void solve() {
int ans = 0;
string s; cin >> s;
for (auto i : s) ans += (i - '0');
cout << ans << '\n';
}
B. Card Game
思路: 写成答辩了,直接按照题意模拟
void solve() {
int a1, a2, a3, a4; cin >> a1 >> a2 >> a3 >> a4;
int ans = 0, r1 = 0, r2 = 0;
if (a1 > a3) r1 ++;
else if (a1 < a3) r2 ++;
if (a2 > a4) r1 ++;
else if (a2 < a4) r2 ++;
if (r1 > r2) ans ++;
r1 = 0, r2 = 0;
if (a1 > a4) r1 ++;
else if (a1 < a4) r2 ++;
if (a2 > a3) r1 ++;
else if (a2 < a3) r2 ++;
if (r1 > r2) ans ++;
r1 = 0, r2 = 0;
if (a2 > a3) r1 ++;
else if (a2 < a3) r2 ++;
if (a1 > a4) r1 ++;
else if (a1 < a4) r2 ++;
if (r1 > r2) ans ++;
r1 = 0, r2 = 0;
if (a2 > a4) r1 ++;
else if (a2 < a4) r2 ++;
if (a1 > a3) r1 ++;
else if (a1 < a3) r2 ++;
if (r1 > r2) ans ++;
cout << ans << '\n';
}
C. Showering
思路:看看再 0 0 0 ~ m m m之间有没有连续一段空闲的时间超过 s s s就行,模拟
void solve() {
int n, s, m; cin >> n >> s >> m;
int lst = 0;
bool ok = false;
for (int i = 1; i <= n; i ++) {
int l, r; cin >> l >> r;
if (l - lst >= s) ok = true;
lst = r;
}
if (m - lst >= s) ok = true;
if (ok) cout << "YES\n";
else cout << "NO\n";
}
D. Slavic’s Exam
思路: 将字符串 t t t 插入到 s s s 串为 ? ? ? 的地方, t t t 串能被插完就可以,否则不行
void solve() {
string s, t; cin >> s >> t;
for (int i = 0, j = 0; i < s.size() && j < t.size(); i ++) {
if (s[i] == t[j]) j ++;
else {
if (s[i] == '?') s[i] = t[j ++];
}
}
for (int i = 0; i < s.size(); i ++) {
if (s[i] == '?') s[i] = 'a';
}
int j = 0;
for (int i = 0; i < s.size() && j < t.size(); i ++) {
if (s[i] == t[j]) j ++;
}
if (j == (int)t.size()) {
cout << "YES" << '\n';
cout << s << '\n';
} else cout << "NO" << '\n';
}
E. Triple Operations
思路:肯定是先把一个较小的数变为零以后,剩下的数直接一直除 3 3 3即可,但要记得把每个数能被 3 3 3除的次数预处理,不然会 t l e tle tle
// #pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define debug1(a) cout << #a << '=' << a << endl
#define debug2(a, b) cout << #a << '=' << a << ' ' << #b << '=' << b << endl
#define lf(x) fixed << setprecision(x)
#define int long long
const int N = 200010;
const int INF = 0x3f3f3f3f;
using namespace std;
int get(int x) {
int cnt = 0;
while (x) {
cnt ++;
x /= 3;
}
return cnt;
}
int s[N];
void solve() {
int l, r; cin >> l >> r;
int ans = 0, pos;
if (l == 1) ans += 3, pos = 3;
else {
int x = get(l);
int r = l + 1;
for (int i = 1; i <= x; i ++) r *= 3;
int y = get(r);
ans += x + y;
pos = l + 2;
}
ans += s[r] - s[pos - 1];
cout << ans << '\n';
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int h_h = 1;
for (int i = 1; i < N; i ++) {
s[i] = get(i);
s[i] += s[i - 1];
}
cin >> h_h;
while (h_h--)solve();
return 0;
}
F. Expected Median
思路:把 0 0 0和 1 1 1的个数统计出来,再至少保证有 ( k + 1 ) / 2 (k + 1) / 2 (k+1)/2个 1 1 1的前提下把 0 0 0和 1 1 1进行排列组合就行,记得取模
int fac[N], inf[N];
int ksm(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void init() {
fac[0] = inf[0] = 1;
for (int i = 1; i < N; i++) {
fac[i] = fac[i - 1] * i % mod;
inf[i] = inf[i - 1] * ksm(i, mod - 2) % mod;
}
}
int C(int n, int m) {
return fac[n] * inf[m] % mod * inf[n - m] % mod;
}
void solve() {
int n, k; cin >> n >> k;
int c0 = 0, c1 = 0;
for (int i = 1, x; i <= n; i ++) {
cin >> x;
if (x == 0) c0 ++;
else c1 ++;
}
int zw = (k + 1) / 2;
if (c1 < zw) {
cout << 0 << '\n';
return ;
}
int ans = 0;
for (int i = zw; i <= c1 && i <= k; i ++) {
if (c0 >= k - i) ans = (ans + C(c1, i) * C(c0, k - i) % mod) % mod;
}
cout << ans << '\n';
}
G1. Ruler (easy version)
思路: 询问至多 10 10 10次,数据范围 999 999 999,直接二分,注意交互题的格式就行
void solve() {
int l = 1, r = 999, ans = -1;
while (l <= r) {
int mid = l + r >> 1;
cout << '?' << ' ' << mid << ' ' << mid << endl;
cout << endl;
int s; cin >> s;
if (mid * mid != s) r = mid - 1;
else l = mid + 1, ans = mid;
}
cout << '!' << ' ' << ans + 1 << endl;
}
G2. Ruler (hard version)
思路: 询问至多 7 7 7次,数据范围 999 999 999,直接三分,注意交互题的格式就行,比赛时写拉了,哭泣
void solve() {
int l = 1, r = 999;
while (l < r) {
int mid = l + r >> 1;
int midl = l + (r - l) / 3;
int midr = r - (r - l) / 3;
cout << '?' << ' ' << midl << ' ' << midr << endl;
int x; cin >> x;
if (x == midl * midr) l = midr;
else if (x == midl * (midr + 1)) l = midl, r = midr - 1;
else r = midl - 1, ans = midl;
}
cout << '!' << ' ' << l + 1 << '\n';
}