牛客周赛 Round 58 题解

A. 会赢吗？

签到，比大小

code:

#include <bits/stdc++.h>

using namespace std;

double a, b;

int main()
{
    cin >> a >> b;
    
    if (a < b) cout << "YES" << endl;
    else cout << "NO" << endl;
    
    return 0;
}

B. 能做到的吧

判断是否有\(i,j\)满足\(1<=i<j<=n\)，并且\(s[i]<s[j]\)，如果有就输出\(YES\)，否则输出\(NO\)

code:

#include <bits/stdc++.h>

using namespace std;

int T;
string s;

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> s;

        bool flag = false;
        for (int i = 0; i < s.size() - 1; i++)
        {
            if (flag) break;
            for (int j = i + 1; j < s.size(); j++)
                if (s[i] < s[j])
                {
                    flag = true;
                    break;
                }
        }

        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;
}

C 会赢的！

两人轮流向下或向右移动棋子

• 当终点\((x,y)\)有一个是负坐标时，棋子不可能到达终点，只能平局

• 当\((x,y)\)满足\((x + y)\%2=0\)时，阿龙不可能获胜，因此要想办法平局，可以发现，只有当\(x=y\)时，阿龙没有办法平局

• 当\((x,y)\)满足\((x+y)\%2=1\)时，小歪不可能获胜，只有当\(abs(x-y)<=1\)时，小歪没办法平局

code:

#include <bits/stdc++.h>

using namespace std;

int T;
int x, y;

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> x >> y;
        
        if (x < 0 || y < 0) cout << "PING" << endl;
        else if ((x + y) % 2)
        {
            if (abs(x - y) <= 1) cout << "YES" << endl;
            else cout << "PING" << endl;
        }
        else
        {
            if (x == y) cout << "NO" << endl;
            else cout << "PING" << endl;
        }
    }

    return 0;
}

D. 好好好数

先看\(k-\)好数定义：可以表示为若干个不同的\(k\)的整数次幂之和的数字

为了把\(n\)拆成若干个\(k-\)好数之和，可以考虑把\(n\)转化为\(k\)进制表示

由于好数要求次幂数不同，因此，\(n\)的\(k\)进制每一位一次最多只能取\(1\)来构成好数

若要使\(n\)拆出的\(k-\)好数最少，则每一次构造好数时要把\(n\)的\(k\)进制中能拿的所有位都拿一遍，最少构造次数就是\(n\)的\(k\)进制所有位中最大的数字

code:

#include <bits/stdc++.h>

#define int long long

using namespace std;

int T;
int n, k;

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        
        if (k == 1)
        {
            cout << 1 << endl;
            continue;
        }
        
        int res = 0;
        while (n)
        {
            res = max(res, n % k);
            n /= k;
        }

        cout << res << endl;
    }

    return 0;
}

E. 好好好数组

打表找规律

• 存在\(1\)个不同的数字，只能构造出\(0,0,0,...,0\)
  
• 存在\(2\)个不同的数字，可以构造出前\(i\)位是\(0\)，后\(n-i\)位是\(i\)的序列，其中\(1<=i<=n-1\)，因此有\(n-1\)种情况
  
• 存在\(2\)个不同的数字，只能构造出\(0,1,...,n\)
• 存在超过\(3\)个不同的数字，可以发现构不成序列

code:

#include <bits/stdc++.h>

#define int long long

using namespace std;

int T;
int n, m;

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        
        if (m == 1) cout << n + 1 << endl;
        else if (m == 2) cout << n << endl;
        else if (m == 3) cout << 1 << endl;
        else cout << 0 << endl;
    }
    
    return 0;
}

F. 随机化游戏时间？

用区间第\(k\)小数模板题，考虑用可持久化线段树

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 200010, mod = 1e9 + 7;

int T;
int n, m;
int a[N];
int root[N], tot;
int ls[N * 25], rs[N * 25], sum[N * 25];

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

void modify(int &u, int v, int l, int r, int p)
{
    u = ++tot;
    ls[u] = ls[v], rs[u] = rs[v], sum[u] = sum[v] + 1;
    if (l == r) return;
    int mid = l + r >> 1;
    if (p <= mid) modify(ls[u], ls[v], l, mid, p);
    else modify(rs[u], rs[v], mid + 1, r, p);
}

int query(int u, int v, int l, int r, int k)
{
    if (l == r) return l;
    int s = sum[ls[u]] - sum[ls[v]];
    int mid = l + r >> 1;
    if (k <= s) return query(ls[u], ls[v], l, mid, k);
    else return query(rs[u], rs[v], mid + 1, r, k - s);
}

int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) cin >> a[i];
        
        for (int i = 1; i <= n; i++)
            modify(root[i], root[i - 1], 1, n, a[i]);
        
        int L = 1, R = n;
        while (m--)
        {
            int l, r, k;
            cin >> l >> r >> k;
            int x1 = query(root[r], root[l - 1], 1, n, k), x2;
            if (k == r - l + 1) x2 = n + 1;
            else x2 = query(root[r], root[l - 1], 1, n, k + 1);
            L = max(L, x1), R = min(R, x2 - 1);
        }
        
        if (L == R) cout << "1 " << L << endl; 
        else cout << qmi(R - L + 1, mod - 2) << endl;
    }

    return 0;
}