1999(964div4)

A. A+B Again?

给定一个两位数正整数 $n$ ，求其位数之和。

void solve() {
    string s;cin >> s;
    int sum = 0;
    for (int i = 0;i < s.size();i++)sum += s[i] - '0';
    cout << sum << '\n';
}

B. Card Game

Suneet 和斯拉夫玩纸牌游戏。游戏规则如下

每张牌的整数值介于 $1$ 和 $10$ 之间。
每位玩家收到的 $2$ 张牌都是面朝下的（因此玩家不知道自己的牌）。
游戏采用回合制，由个回合组成。在一个回合中，双方随机抽取一张未翻开的牌并翻开。翻开的牌中数字严格意义上更大的一方获胜。如果数字相等，则无人获胜。
如果一名玩家赢得的回合数最多（即严格意义上大于另一名玩家），则该玩家赢得游戏。如果相等，则无人获胜。

由于 Suneet 和 Slavic 并不是最好的朋友，您需要计算 Suneet 最终成为赢家的可能性有多少。

为了更好地理解，请查看注释部分。

一共就四个回合：若两个同时相等，则不加人分数即可。

void solve() {
    int a1, a2, b1, b2;cin >> a1 >> a2 >> b1 >> b2;
    int ans = 0;
    if (a1 >= b1 && a2 >= b2) {
        if (a1 != b1 || a2 != b2)
            ans += 2;
    }
    if (a1 >= b2 && a2 >= b1) {
        if (a1 != b2 || a2 != b1)
            ans += 2;
    }
    cout << ans << '\n';
}

C. Showering

作为一名计算机科学专业的学生，亚历克斯面临着一个严峻的挑战--洗澡。他努力每天洗澡，但尽管他尽了最大努力，却总是遇到困难。他需要花 $s$ 分钟洗澡，而一天只有 $m$ 分钟！

他已经计划好了一天的任务 $n$ 。任务 $i$ 被表示为一个时间间隔 $(l_{i}$ , $r_{i})$ ，这意味着亚历克斯很忙，不能在这个时间间隔内（严格来说是在 $l_{i}$ 和 $r_{i}$ 之间的任何时间点）洗澡。**没有两项任务重叠。

给定所有 $n$ 时间间隔，亚历克斯当天能洗澡吗？换句话说，亚历克斯是否有一个长度至少为 $s$ 的空闲时间间隔？

void solve() {
    int n, s, m;cin >> n >> s >> m;
    vector<pair<int, int>> a(n + 2);
    int mx = 0, mi = 1e9;
    for (int i = 1;i <= n;i++) {
        int l, r;cin >> l >> r;
        a[i] = {l,r};
    }
    a[n + 1].first = m;
    sort(a.begin(), a.end());
    for (int i = 1;i <= n + 1;i++) {
        if (a[i].first - a[i - 1].second >= s) {
            cout << "YES\n";return;
        }
    }
    cout << "NO\n";
}

D. Slavic's Exam

斯拉夫的考试非常难，他需要您的帮助才能通过考试。下面是他正在苦苦思索的问题：

存在一个字符串 $s$ ，它由小写英文字母和可能是零个或多个"? "组成。

要求斯拉夫人将每个"? "改为小写英文字母，使字符串 $t$ 成为字符串 $s$ 的子序列（不一定连续）。

输出任何这样的字符串，如果没有符合条件的字符串存在，则说不可能。

非常板的双指针

void solve() {
    string s, t;cin >> s >> t;
    int j = 0;
    for (int i = 0;i < s.size() && j < t.size();i++) {
        if (s[i] == '?')s[i] = t[j], j++;
        else if (s[i] == t[j])j++;
    }
    for (int i = 0;i < s.size();i++) {
        if (s[i] == '?')s[i] = 'a';
    }
    if (j == t.size()) {
        cout << "YES\n" << s << '\n';
    } else {
        cout << "NO\n";
    }
}

E. Triple Operations

艾维在黑板上写下了从 $l$ 到 $r$ （含）的所有整数。

在一次运算中，她做了以下操作：

在黑板上选出两个数字 $x$ 和 $y$ ，擦掉它们，然后在它们的位置上写下数字 $3 x$ 和 $⌊ \frac{y}{3} ⌋$ 。(这里的 $⌊ ∙ ⌋$ 表示四舍五入到最接近的整数）。

要使黑板上的所有数字都等于 $0$ ，艾维最少需要进行多少次运算？我们可以证明这总是可能的。

这个题目显而易见就是第一个数计算两次，其他数字只计算一次。

关键在于在 $O (\log n)$ 的时间复杂度里计算出来。

可以知道答案分别为 $x, x, x \dots, x + 1, x + 1, \dots, x + 2, \dots \dots x + k$ ，每到 $3^{m}$ 就会多一次操作次数，因此可以直接构造 $3^{m}$ 的数字，判定 $l, r$ 分别处于哪个部分即可。
即 $x \times (r - l + 1 + 1)$ 加上后面每个部分乘以 $(r - i)$ 即可

#define int long long
int a[16];//3^i
void solve() {
    int l, r;cin >> l >> r;
    int ans = 0;
    int ll = 0, rr = 0;
    for (int i = 1;i <= 15;i++) {
        if (l < a[i] && l >= a[i - 1]) {
            ll = i;
        }
        if (r < a[i] && r >= a[i - 1]) {
            rr = i - 1;
        }
    }

    for (int i = ll;i <= rr;i++) {
        ans += (r - a[i] + 1);
    }
    
    int i = l, res = 0;
    while (i) {
        i /= 3;res++;
    }
    res *= r - l + 2;

    cout << res + ans << '\n';
}

F. Expected Median

Arul 有一个二进制数组 $^{∗}$ 。 $a$ 长度为 $n$ 。

他将取该数组长度为 $k$ （ $k$ 为奇数）的所有子序列 $^{†}$ ，并求出它们的中位数 $^{‡}$ 。

所有这些值的和是多少？

其实非常简单，不过做的时候看错题了，将中位数看作第 $\frac{k + 1}{2}$ 项去了，其实只要 $1$ 的个数大于 $0$ 的个数即可。

情况个数其实不多: 最多就 $\frac{k + 1}{2}$ 种（ 1 的个数 $[\frac{k + 1}{2}, n]$ ）

void solve() {
    int n, k;cin >> n >> k;
    int cnt = 0;
    for (int i = 1;i <= n;i++) {
        int x;cin >> x;
        if (x)cnt++;
    }
    int ans = 0;
    for (int i = (k + 1) / 2;i <= min(cnt, k);i++) {
        ans += c(n - cnt, k - i) * c(cnt, i) % mod;ans %= mod;
    }
    cout << ans << '\n';
}

G. Ruler

我们有一把暗尺，它缺少一个数字 $x$ ( $2 \leq x \leq 999$ )。当你测量一个长度为 $y$ 的物体时，尺子会报告以下值：

如果是 $y < x$ ，标尺（正确）测量的物体长度为 $y$ 。
如果为 $y \geq x$ ，则标尺错误地测量物体的长度为 $y + 1$ 。

您需要找到 $x$ 的值。为此，您可以进行以下形式的查询：

$? a b$ - 作为回应，我们将用尺子测量一个 $a \times b$ 矩形的边长，并将结果相乘，向您报告测量出的矩形面积。

求 $x$ 的值。您最多可以查询 $10 / 7$ 次。

Solution

有史以来最简单的压轴

easy 版本直接二分即可，每次查询的时候都是 $1 m i d$ 即可。 $⌈ \log_{2} 1000 ⌉ = 10$

int query(int a, int b) {
    cout << "? " << a << " " << b << endl;
    int x;cin >> x;return x;
}
void solve() {
    int l = 1, r = 1000;
    while (l < r) {
        int mid = l + r >> 1;
        if (query(1, mid) != mid)r = mid;
        else l = mid + 1;
    }

    cout << "! " << l << endl;
}

hard 版本要求 7 次查询

像是三分法，但是实际上是魔改的二分 $⌈ \log_{3} 1000 ⌉ \approx 7$

....

分为三种情况：

$a < b < x ⟹ a \times b$
$a < x \leq b ⟹ (a + 1) \times b$
$x \leq a < b ⟹ (a + 1) (b + 1)$

int query(int a, int b) {
    cout << "? " << a << " " << b << endl;
    int x;cin >> x;return x;
}
void solve() {
    int l = 1, r = 1000;
    while (r - l > 2) {
        int a = (2 * l + r) / 3;
        int b = (l + 2 * r) / 3;
        int res = query(a, b);
        if (res == (a + 1) * (b + 1)) {
            r = a;
        } else if (res == a * b) {
            l = b;
        } else {
            l = a, r = b;
        }
    }
    if (r - l == 2) {
        if (query(1, l + 1) == l + 1) {
            l = l + 1;
        } else {
            r = l + 1;
        }
    }
    cout << "! " << r << endl;
}