Codeforces Round 964 (Div. 4)

好忙-_-，可能没有那么详细，有问题欢迎指出

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