烟尘墨

2024-09-05 20:28 已编辑嘉应学院 Web前端发布于广东

关注

题解 | 牛客周赛 Round 58

感觉有点思维的一场。（QWQ）

A. 会赢吗？

思路

判断 $h$ 是否大于 $w$ 即可，由于是与 $6$ 位浮点数比较大小，所以需要通过判断两者差值的绝对值是否不超过 $10^{-7}$ 来判断两者是否相等。

代码实现

// Problem: 会赢吗？
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/89510/A
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    double w, h;
    cin >> w >> h;
    if (h > w && fabs(h - w) > 1e-7)
        cout << "YES";
    else
        cout << "NO\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

B. 能做到的吧

思路

只要存在一个数位的数字，后面的数位存在比该数字大的数字，那么交换之后就可以把 $x$ 变大。

代码实现

// Problem: 能做到的吧
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/89510/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

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

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

C. 会赢的！

会赢的，牢师！

思路

原先想着 $dfs$ 抛出所有的博弈状态，但是发现还存在平手的问题。

转换思路，可以发现从 $(0,0)$ 走到 $(x,y)$ 的步数是确定的 $x + y$ 步。

如果不是选择最优策略，而是轮到那个人，就往 $(x,y)$ 的方向走一步，那么这种情况下赢的人是根据 $x + y$ 的奇偶性确定，奇数先手赢，偶数后手赢。

下面分类讨论（令 $x \le y$ ）：

1， $x + y$ 为奇数

如果后手不动手脚的话是先手赢，后手此时最优的情况只可能是平手，而要实现平手，把棋子走越界即可，最少走越界的方法显然是向 $x$ 方向，对应走 $x + 1$ 步，而先手对应的最优决策则是向 $y$ 方向走。

如果后手能走 $x + 1$ 步使得棋子越界，那么在后手走 $x$ 步时，先手无法多走一步到达终点，也就是说 $(x,x + 1)$ 不是终点。

因此，这种情况下，如果 $x = y + 1$ 则先手赢，否则平局。

2， $x+y$ 为偶数

和奇数思路同理，不过是交换先后手，如果 $x=y$ ，终点为 $(x,x)$ ，则先手无法在到达终点之前让棋子越界，否则先手则可以有多走几步的空间，使得棋子越界。

因此，这种情况下，如果 $x==y$ 则先手输，否则平局。

3， $x<0$ 或者 $y<0$

此时一定无法移动到终点，绝对平局。

代码实现

// Problem: 会赢的！
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/89510/C
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

// Problem: 能做到的吧
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/89510/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

int x, y;

void solve()
{
    cin >> x >> y;
    if (x > y)
        swap(x, y);
    if (x < 0 || y < 0) {
        cout << "PING\n";
    } else if (x == y) {
        cout << "NO\n";
    } else {
        if ((x + y) % 2) {
            cout << (y == x + 1 ? "YES" : "PING") << '\n';
        } else {
            cout << (x == y ? "NO" : "PING") << '\n';
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

D. 好好好数

思路

$k-$ 好数，实则就是 $k$ 进制下每个数位上不超过 $1$ 的数字。

如果 $n$ 在 $k$ 进制下，所有的数位上的最大数字为 $x$ ，那么最少就需要 $x$ 个 $k-$ 数来凑出 $n$ 。

特殊情况则是 $k=1$ 的时候，此时所有数都可以表示为 $k-$ 好数， $n$ 可以表示为 $n = 1^0 + 1^1 + ... + 1^{n-1}$ 。

代码实现

// Problem: 好好好数
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/89510/D
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
    int n, k;
    cin >> n >> k;
    if (k == 1) {
        cout << 1 << '\n';
        return;
    }
    int ni = n;
    int ans = 0;
    while (ni) {
        ans = max(ans, ni % k);
        // 找出 k 进制下数位的最大数字
        ni /= k;
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

E. 好好好数组

思路

手玩一下，可以发现，不同数字最多为 $3$ 个。

不同数字为一个的情况只有一种，即 $n$ 个 $0$ 。

不同数字为两个的情况有 $n-1$ 种，即起初为一段 $0$ ，然后到 $x$ 的位置之后都是 $x$ 。例如像 $0,0,2,2,2$ 这样子。

不同数字为三个的情况只有一种，即开头为 $0$ ，中间一段都为 $1$ ，末尾为 $n$ ，即 $0,1,1,1,...,n$ 这样子。

而题目中是不少于 $m$ 个，因此如果 $m$ 不大于 $i$ 个，则总情况数增加 $i$ 个对应的情况数。

代码实现

// Problem: 好好好数组
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/89510/E
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e7 + 5;

int n, m;

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

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

F. 随机化游戏时间？

思路

令 $[L,R]$ 为当前幸运数的范围，初始为 $[1,n]$ 。

如果区间 $[l,r]$ 存在 $k$ 个数字小于等于幸运数，那么幸运数一定不小于区间的第 $k$ 大，且小于区间的第 $k+1$ 大。

令区间的第 $k$ 大为 v，第 $k+1$ 大为 $v_1$ ，那么幸运数的范围变化为 $[max(v,l),min(r,v_1-1)$ ]。（注意当 $k$ 如果为 $0$ 或者 $r-l+1$ 时，对应的左边界或者右边界不需要更新）

查询静态区间第 $k$ 大，可以使用可持久化线段树处理。

最后得到幸运数的范围 $[L,R]$ ，猜对数字的概率即为 $\frac{1}{R-L+1}$ ，如果范围长度为 $1$ 则直接输出幸运数。

因为最后答案是对 $10^9 + 7$ 取模，涉及到分数求逆元，可以用快速幂解决。

代码实现

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e6 + 5;

#define ls(x) (tr[x].l)
#define rs(x) (tr[x].r)
#define sum(x) tr[x].sum

int n, m;
int a[N];

int tot;
int root[N];

struct {
    int l, r, sum;
} tr[25 * N];

void pushup(int u)
{
    sum(u) = sum(ls(u)) + sum(rs(u));
}

void modify(int now, int last, int l, int r, int p)
{
    if (l == r) {
        sum(now) = sum(last) + 1;
    } else {
        ls(now) = ls(last), rs(now) = rs(last);
        int mid = (l + r - 1) / 2;
        if (p <= mid) {
            ls(now) = ++tot;
            modify(ls(now), ls(last), l, mid, p);
        } else {
            rs(now) = ++tot;
            modify(rs(now), rs(last), mid + 1, r, p);
        }
        pushup(now);
    }
}

const int L = -1e9, R = 1e9;

int kth(int now, int last, int l, int r, int k)
{
    if (l == r)
        return l;
    int mid = (l + r - 1) / 2;
    int cur = sum(ls(now)) - sum(ls(last));
    if (cur >= k)
        return kth(ls(now), ls(last), l, mid, k);
    else
        return kth(rs(now), rs(last), mid + 1, r, k - cur);
}

int query(int now, int last, int l, int r, int li, int ri)
{
    if (li <= l && r <= ri)
        return sum(now) - sum(last);
    int res = 0;
    int mid = (l + r - 1) / 2;
    if (li <= mid)
        res += query(ls(now), ls(last), l, mid, li, ri);
    if (ri > mid)
        res += query(rs(now), rs(last), mid + 1, r, li, ri);
    return res;
}

int kth(int now, int last, int k)
{
    int l = L, r = R;
    while (l < r) {
        int mid = (l + r - 1) / 2;
        int val = query(now, last, L, R, L, mid);
        if (val < k)
            l = mid + 1;
        else
            r = mid;
    }
    return r;
}

int mod = 1e9 + 7;

int qmi(long long a, int b)
{
    int res = 1;
    while (b) {
        if (b & 1)
            res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}

void solve()
{
    tot = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        root[i] = ++tot;
        modify(root[i], root[i - 1], L, R, a[i]);
    }
    int L = 1, R = n;
    while (m--) {
        int l, r, k;
        cin >> l >> r >> k;
        if (k == r - l + 1)
            L = max(L, kth(root[r], root[l - 1], k));
        else if (k == 0)
            R = min(R, kth(root[r], root[l - 1], k + 1) - 1);
        else {
            L = max(L, kth(root[r], root[l - 1], k));
            R = min(R, kth(root[r], root[l - 1], k + 1) - 1);
        }
    }
    int len = R - L + 1;
    if (len != 1)
        cout << qmi(R - L + 1, mod - 2) << '\n';
    else
        cout << 1 << ' ' << R << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}