好忙-_-,可能没有那么详细,有问题欢迎指出
A题:A+B Again?
题意
计算一个两位数的数位和
思路
先用string读入,然后依次减去'0'
代码
inline void solve() {string s; cin >> s;cout << s[0] + s[1] - '0' - '0' << endl;return;
}
B题:Card Game
思路
总共就4种情况,直接暴力写就行
代码
inline void solve() {int a[2], b[2];cin >> a[0] >> a[1] >> b[0] >> b[1];int ans = 0;if (a[0] >= b[0] && a[1] >= b[1] && (a[0] != b[0] || a[1] != b[1])) ans += 1;if (a[0] >= b[1] && a[1] >= b[0] && (a[0] != b[1] || a[1] != b[0])) ans += 1;if (a[1] >= b[0] && a[0] >= b[1] && (a[1] != b[0] || a[0] != b[1])) ans += 1;if (a[1] >= b[1] && a[0] >= b[0] && (a[1] != b[1] || a[0] != b[0])) ans += 1;cout << ans << endl;return;
}
C题:Showering
代码
inline void solve() {int n, s, m; cin >> n >> s >> m;int last = 0;bool flag = false;for (int i = 1; i <= n; i ++ ) {int a, b; cin >> a >> b;if (a - last >= s) flag = true;last = b;if (i == n) {if (m - last >= s) flag = true;}}cout << (flag ? "YES" : "NO") << endl;return;
}
D题:Slavic's Exam
思路
贪心,因为是子序列,那么就要越早匹配越好
代码
inline void solve() {string s, t; cin >> s >> t;int n = s.size(), m = t.size();s = ' ' + s, t = ' ' + t;int j = 1;bool ok = false;for (int i = 1; i <= n; i ++ ) {if (s[i] == t[j]) j += 1;else if (s[i] == '?') {s[i] = t[j];j += 1;}if (j == m + 1) {ok = true;break;}}if (!ok) cout << "NO" << endl;else {cout << "YES" << endl;for (int i = 1; i <= n; i ++ ) {if (s[i] == '?') s[i] = 'a';}string ans = s.substr(1);cout << ans << endl;}return;
}
E题:Triple Operations
思路
贪心,肯定是要先把一个变成0的,否则这边除3,那么还要乘3.
先变,那就是变最小的,在变的过程中,因为还要乘,答案是两倍的
剩下的都除3就行,预处理lg3
加上的是lg3[i]+1,因为是要变成0
代码
const int N = 2e5 + 9;
int lg3[N];
inline void solve() {int l, r; cin >> l >> r;ll ans = 0;for (int i = l; i <= r; i ++ ) ans += lg3[i];ans += lg3[l] + 1;cout << ans + (r - l + 1) << endl;return;
}inline void pre_work() {for (int i = 3; i < N; i ++ ) lg3[i] = lg3[i / 3] + 1;
}
F题:Expected Median
思路
组合数
然后能加的情况是0的数量小于1的数量
代码
const int N = 2e5 + 9;
ll fact[N], infact[N];
ll C(int a, int b) {return fact[a] * infact[a - b] % mod * infact[b] % mod;
}
inline void solve() {int n, k; cin >> n >> k;int cnt[2] = {};for (int i = 1; i <= n; i ++ ) {int x; cin >> x;cnt[x] += 1;}ll ans = 0;for (int i = 0; i <= min(k, cnt[0]); i ++ ) {int cnt1 = k - i;if (cnt1 > cnt[1]) continue;if (i < cnt1) ans = (ans + C(cnt[0], i) * C(cnt[1], cnt1) % mod) % mod;}cout << ans << endl;return;
}inline void pre_work() {mod = MOD;fact[0] = infact[0] = 1;for (int i = 1; i < N; i ++ ) {fact[i] = fact[i - 1] * i % mod;infact[i] = infact[i - 1] * inv(i) % mod;}
}
G题: Ruler (hard version)
思路
三分
每次查询,比如输入? a b
可能是a*b,(a+1)*b,(a+1)*(b+1)
刚好对应三种情况,可以以此来调整l和r
代码
int ask(int l, int r) {cout << "? " << l << ' ' << r << endl;int res; cin >> res;return res;
}
void ans(int q) {cout << "! " << q << endl;
}inline void solve() {int l = 2, r = 999, m1, m2, res = 999;while (l < r) {int len = (r - l + 1) / 3;m1 = l + len;m2 = r - len;int ans = ask(m1, m2);if (m1 * m2 == ans) {l = m2 + 1;}else if (m1 * (m2 + 1) == ans) {l = m1 + 1, r = m2;res = m2;}else if ((m1 + 1) * (m2 + 1) == ans) {r = m1;res = m1;}}ans(res);
}