A. Only Pluses

每次操作选择一个数 \(+1\)，执行五次，使得 \(a*b*c\) 最大，只需要在每次操作对 \(a,b,c\) 中最小的一个 \(+1\) 即可

code:

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>

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int a[3];

signed main()
{
    cin >> T;
    while (T--)
    {
        for (int i = 0; i < 3; i++) cin >> a[i];
        for (int i = 0; i < 5; i++)
        {
            sort(a, a + 3);
            a[0]++;
        }
        
        cout << a[0] * a[1] * a[2] << endl;
    }

    return 0;
}

B. Angry Monk

从一个长度大于 \(x\) 的切片中切出 \(x\) 个长度为 \(1\) 的土豆需要切 \(x\) 次，而使用长度等于 \(x\) 的切片只用切 \(x-1\) 次，因此可以发现，每把一个切片切成全部为 \(1\) 的切片，就可以少操作一次，因此优先选择操作长度小的切片

code:

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
#include <bits/stdc++.h>

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n, k;
int a[N];

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        for (int i = 0; i < k; i++) cin >> a[i];
        
        sort(a, a + k);
        
        int res = 0, sum = a[k - 1];
        for (int i = 0; i < k - 1; i++)
        {
            if (sum + a[i] <= n) 
            {
                sum += a[i];
                res += a[i] * 2 - 1;
            }
            else 
            {
                res += (n - sum) * 2;
                break;
            }
        }
        
        cout << res << endl;
    }

    return 0;
}

C. Gorilla and Permutation

构造，对于大于等于\(k\)的数，越早出现越好，对于小于等于 \(m\) 的数，越晚出现越好：

  • 当\(k>m\)时，先倒序输出 \([k,n]\)，接着对于 \((k,m)\)，这些数对答案没有影响，不用考虑顺序，随意输出即可，最后正序输出 \([1,m]\)
  • 当\(k<=m\)时，先倒叙输出 \((m,n]\)，接着对于 \([k,m]\)，这些数在 \(g\) 和 \(f\) 中都要被加入，相减时会被抵消，因此不影响答案，可以随意输出，最后正序输出 \([1,k)\)

code:

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
#include <bits/stdc++.h>

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n, m, k;
int a[N];

signed main()
{
    cin >> T;
    while (T--)
    {
        cin >> n >> m >> k;
        
        for (int i = n; i > min(m, k); i--) cout << i << ' ';
        
        int x = min(m, k);
        if (m >= k) cout << x-- << endl;
        for (int i = 1; i <= x; i++) cout << i << ' ';
        cout << endl;
    }

    return 0;
}

D. Test of Love

简单\(dp\)，没什么好说的

code:

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
#include <bits/stdc++.h>

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 200010;

int T;
int n, m, k;
string s;
int f[N];

signed main()
{
	cin >> T;
	while (T--)
	{
        cin >> n >> m >> k;
        cin >> s;
        
        f[0] = 1;
        for (int i = 1; i <= n + 1; i++) f[i] = 0;
        s = 'L' + s;
        
        for (int i = 1; i <= n + 1; i++)
        {
            if (f[i] == 'C') continue;
            
            bool flag = false;
            if (s[i - 1] == 'W' && k && f[i - 1]) f[i] = flag = 1;
            for (int j = 1; j <= min(i, m); j++)
            {
                if (!f[i - j]) continue;
                if (s[i - j] == 'L') 
                {
                    f[i] = 1;
                    if (flag) flag = false;
                }
            }
            if (flag) k--;
        }
        
        if (f[n + 1]) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
	
	return 0;
}

E. Novice's Mistake

由于 \(n*a\) 最大值是 \(1e6\)，而 \(b <= (min(1000,n*a))\)，因此 \(n*a-b\) 最多就是六位数，直接枚举即可

code:

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
#include <bits/stdc++.h>

#define x first
#define y second
#define int long long
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;

int T;
int n;

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

    cin >> T;
    while (T--)
    {
        cin >> n;
        
        vector<PII> res;
        string s = to_string(n);
        for(int i = 1; i <= 10000; i++)
        {
            string k;
            while (k.size() < 10) k += s;
            for(int j = 1; j <= 6; j++)
            {
                int b = i * s.size() - j;
                int ans = n * i - b;
                if(b < 1 || b > min((int)10000, n * i)) continue;
                string s1 = to_string(ans);
                string s2 = k.substr(0,j);
                if(s1 == s2) res.push_back({i, b});
            }	
        }
        
        cout << res.size() <<endl;
        for (int i = 0; i < res.size(); i++)
            cout << res[i].x << ' ' << res[i].y << endl;
    }

    return 0;
}

F. Ultra-Meow

模拟，维护 \(x\) 的因子即可

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
#include <bits/stdc++.h>

#define x first
#define y second
#define int long long
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int T;
int n, x;
int a[N];

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

    cin >> T;
    while (T--)
    {
        cin >> n >> x;
        for (int i = 0; i < n; i++) cin >> a[i];
        
        int res = 1;
        map<int, int> p;
        p[1]++;
        
        for (int i = 0; i < n; i++)
        {
            if (x % a[i]) continue;
            
            map<int, int> c;
            for (auto it: p)
            {
                if (x % (a[i] * it.x)) continue;
                else c[a[i] * it.x]++;
            }
            for (auto it: c) p[it.x]++;
            
            if (p.count(x))
            {
                res++;
                p.clear();
                p[a[i]]++, p[1]++;
            }
        }
        
        cout << res << endl;
    }

    return 0;
}

G. Ultra-Meow

组合数学，不难发现，\(Mex(b,|b|+1)\) 的最大值为 \((|b|+1)*2+1\)

假设当前数组的大小为 \(i\)，\(MEX\) 值为 \(j\), 那么在 \([1,j-1]\) 之间应该有 \(j-(i+1)=j-i-1\) 个数，在 \([j+1,n]\) 之间应该有 \(i-(j-i-1)=i*2+1-j\) 个数，公式为

\(\sum_{i}^{n}\sum_{i+1}^{i*2+1}j \times C[min(n, j - 1)][j - i - 1] \times C[max((int)0, n - j)][i * 2 + 1 - j]\mod MOD\)

code:

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
#include <bits/stdc++.h>

#define int long long 

using namespace std;

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

int T;
int n;
int c[N][N];

void init()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j <= i; j++)
        {
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
}

int mul(int a, int b)
{
    return a * b % mod;
}

signed main()
{
    init();

    cin >> T;
    while (T--)
    {
        cin >> n;
        
        int res = 1;
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= i * 2 + 1; j++)
                res = (res + mul(j, mul(c[min(n, j - 1)][j - i - 1], c[max((int)0, n - j)][i * 2 + 1 - j]))) % mod;
        
        cout << res << endl;
    }

    return 0;
}