牛客周赛58

A 会赢吗？

小歪正在玩《$\mathsf{\ast }\mathsf{\ast }\mathsf{\ast }:\mathsf{\ast }\mathsf{\ast }$》。他知道下一个头目伤害最高的那一段招式可以造成 $w$ 点伤害，而自己现在只有 $h$ 点生命。当生命小于等于 $0$ 时，就寄了。

想整个花活，无伤过关，但吃下伤害最高的那一段招式一次。会赢吗？

void solve() {
    double a;int b;cin >> a >> b;
    if (a < b) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

B 能做到的吧

小苯有一个正整数 $x$，他希望用最多一次交换数位操作（即选择 $x$ 中的两个数位交换位置）把 $x$ 变大，请问他能否做到呢。

void solve() {
    string s;cin >> s;
    for (int i = 0;i + 1 < s.size();i++) {
        if (s[i] < s[i + 1]) {
            cout << "YES\n";return;
        }
    }
    cout << "NO\n";
}

C 会赢的！

在一个无限大的二维网格内，阿龙和小歪正在玩一场游戏。我们使用 $(i,j)$ 表示网格中从上往下数第 $i$ 行和从左往右数第 $j$ 列的单元格。规则如下：

• 两人共同操作一个棋子，开始位置为 $(0,0)$ ；
• 每个回合每人可以将棋子向下或向右移动一格，向下移动一格即抵达 $(x+1,y)$ 、向右移动一格即抵达 $(x,y+1)$ ；
• 对于给定的终点 $(x,y)$ ，在谁的回合中有机会将棋子走到，谁就能胜利；如果谁都不能到达，则视为平局；
• 阿龙先手，双方均采取最优决策（尽可能让自己赢，自己赢不了则尽可能平局）；

谁能赢呢。

void solve() {
    int x, y;cin >> x >> y;
    if (x < 0 || y < 0) {
        cout << "PING\n";return;
    }
    if (x == y) {
        cout << "NO\n";
    } else if (abs(x - y) == 1) {
        cout << "YES\n";
    } else {
        cout << "PING\n";
    }
}

D 好好好数

小苯有一个数字 $n$ ，他定义 $\mathtt{\text{k-}}$ 好数为：可以表示为若干个不同的 $k$ 的整数次幂之和的数字。

例如：$30=3^3+3^1$ ，因此 $30$ 是一个 $\mathtt{\text{3-}}$ 好数，而 $2$ 不是一个 $\mathtt{\text{3-}}$ 好数（虽然有：$2=3^0+3^0$，但好数要求次幂数字不同）。

小苯有一个整数 $n$，他想知道 $n$ 最少可以被表示成几个 $\mathtt{\text{k-}}$ 好数的和，请你帮帮他吧。

k-好数的条件：在 k 进制下所有位<=1

#define int long long
void solve() {
    int n, k;cin >> n >> k;
    if (k == 1) {
        cout << "1\n";return;
    }
    vector<int> ans;
    while (n) {
        ans.push_back(n % k);n /= k;
    }
    cout << *max_element(ans.begin(), ans.end()) << '\n';
}

E 好好好数组

对于数组 $\{a_1,a_2,\dots ,a_n\}$ ，我们定义它是好的，当且仅当：对于全部的 $i\in [1,n)$ ，$a_i=a_{i+1}modi$ 总是成立；

现在，你可以选择 $n$ 个整数组成一个数组，使得这个数组是好的；同时，你还需要保证：

• 数组中至少存在 $m$ 个不同的数字；
• 数组中的每一个数字都满足 $\in [0,n]$ 。

可以打表知道，对于 $n$，最多有 $n+1$ 种方法 (最后一个数为 $0\sim n$)+

$n+1$ 种分别为：

$0,0,0,\dots 0$

$0,1,1,1\dots ,1$

$0,0,2,2,\dots ,2$

$\dots$

$0,0,\dots ,0,n-1$

$0,1,1,\dots ,1,n$

所以判定条件：$\ge 1,\ge 2,\ge 3,>3$

void solve() {
    int n, m;cin >> n >> m;
    if (m == 1) {
        cout << n + 1 << '\n';
    } else if (m == 2) {
        cout << n << '\n';
    } else if (m == 3) {
        cout << "1\n";
    } else {
        cout << "0\n";
    }
}

F 随机化游戏时间？

注：本题和 $\mathsf{h}\mathsf{a}\mathsf{r}\mathsf{d}$ 版本的区别在于排列已知，询问概率。

小 $\mathcal{L}$ 有一个 $1\sim n$ 的排列，她从中选择了一个数字作为自己的幸运数。

小 $\mathcal{H}$ 每次会询问小 $\mathcal{L}$ 一个区间 $[l,r]$ ，随后小 $\mathcal{L}$ 会告诉他这个区间里有多少个数小于等于她的幸运数。

直到 $m$ 次询问全部完成，如果小 $\mathcal{H}$ 依旧无法唯一确定幸运数是什么，他会在全部可能的数字里等概率随机挑选一个。

你需要直接输出 $m$ 次询问后他猜对数字的概率，保证数据有解。

Solution

可持久化线段树/区间第 $k$ 小值

很容易知道，每次查询都会使得幸运数的可能区间缩小，直到得到答案。

求解区间第 $k$ 小的 "杀手"：小波树(Wavelet Matrix)

G 随机化游戏时间！

注：本题和 $\mathsf{e}\mathsf{a}\mathsf{s}\mathsf{y}$ 版本的区别在于排列未知，输出全部可能的数字。

小 $\mathcal{L}$ 有一个 $1\sim n$ 的排列，她从中选择了一个数字作为自己的幸运数。

小 $\mathcal{H}$ 每次会询问小 $\mathcal{L}$ 一个区间 $[l,r]$ ，随后小 $\mathcal{L}$ 会告诉他这个区间里有多少个数小于等于她的幸运数。

直到 $m$ 次询问全部完成，直接从小到大输出全部可能的幸运数。保证数据有解。

本题作为了解差分约束

差分约束板子：P1250 种树 - 洛谷 | 计算机科学教育新生态