A. 会赢吗？

签到，比大小

code:

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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:

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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:

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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:

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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:

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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小数模板题，考虑用可持久化线段树

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#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;
}