StarryCoding 算法小白周赛2 题解与代码（含视频题解）

比赛链接（含视频题解）：https://www.starrycoding.com/contest/4

A题题解：

题目大意

给你一个由 $n$ 个正整数组成的数组 $a$，询问这个数组是否是严格单调递增的。

思路

因为他会按照“拜访时间安排表”的顺序拜访每一位好友，而无法成功拜访某一好友时，必定是出现靠后拜访的时间早于靠前拜访的，或者两次拜访的时间相同，所以问题的本质就是判断数组是否严格单调递增，也就是 $a_1<a_2<\cdots <a_n$。

我们只需要遍历一下整个数组，判断相邻两个数是否都满足后者大于前者即可。

核心代码

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 2; i <= n; i++)
    {
        if (a[i] <= a[i - 1])
        {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

B：1的数量

由于数的范围很小，假如这个数合法，我们直接从此数$+1$开始枚举，直到合法为止

最坏情况下时间复杂度为$O(Tn/2)$

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
const int N = 2e5 + 10;
const int M = 15;
const int mod = 998244353;
using namespace std;
typedef pair<int, int>p;
typedef long long ll;

int a(int x)
{
    int res = 0;
    while (x)
    {
        if (x & 1)res++;
        x >>= 1;
    }
    return res;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;

        if (a(n)<=2)
        {
            n++;
            while (a(n) >= 3)n++;
            cout << n << endl;
        }
        else
        {
            cout << a(n) << endl;
        }
    }
}
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

C：1的数量

假如我们还是一个个枚举对于$2^{63}$$+$$2^{62}$这样的数，需要枚举约$2^{62}$次，我们是无法接受的

我们考虑在哪一位上加1是可行的

首先对于只有$0$位$1$或者$1$位$1$的情况，我们只需要无脑在第一位上加$1$即可，因为这保证了$1$的数量不会超过要求

对于$2$位$1$的情况：

$1$ : 假如我在最后一位$1$的后面任意位增加$1$，一定会使$1$的数量变成$3$，不符合要求

$2$ : 假如我在最后一位$1$上加$1$,能保证加的数量是最少的，并且$1$的数量一定不会增加，符合要求

所以对于$2$位1的情况我们加上lowbit(x)就行了

时间复杂度接近$O（T）$

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f
const int N = 2e5 + 10;
const int M = 15;
const int mod = 998244353;
using namespace std;
typedef pair<int, int>p;
typedef long long ll;

int lowbit(int x)
{
    return x & -x;
}

int a(int x)
{
    int res = 0;
    while (x)
    {
        if (x & 1)res++;
        x >>= 1;
    }
    return res;
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;

        if (a(n) < 3)
        {
            if (a(n) <= 1)cout << n + 1 << endl;
            else {
                n += lowbit(n);
                cout << n << endl;
            }
        }
        else
        {
            cout << a(n) << endl;
        }
    }
}
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

D题题解：

题目大意

给你一个由 $n$ 个正整数组成的数组 $a$，询问这个数组能否通过以下两个操作各至多一次变为严格单调递增：

• 将任意数量的 $a_i$ 变为 $a_i+1$。
• 删除其中一个数。

思路

由于我们已经知道了合法的时间安排满足数组 $a$ 严格单调递增，所以我们只需要判断是否能够将 $a$ 变为严格单调递增即可。

这个问题可以用简单的贪心法来解决。逐个处理元素。如果某个数比前一个数小，那么肯定不行，我们需要考虑删去这个元素或者它前面的那个数。如果相等，则考虑将其增加 $1$。如果大于，则最好不要更改，给后面的元素更多的空间。

最后我们只需要判断是否能通过最多一次删除操作使数组合法即可。

当然，还有一个小细节，当某个数比前一个数小时（$a_i>a_{i+1}$），应该删除这个数还是前一个数，因为我们想要的是让后面的数的合法值域更大，所以我们需要最小化留下的那个数，也就是说，如果靠后的数 $a_{i+1}$ 可以留下来，我们应该尽可能让其留下，也就是说

• 当 $a_i>a_{i+1}$ 且 $a_{i-1}<a_{i+1}$，时，我们应该删除 $a_i$ 不改变 $a_{i+1}$。
• 当 $a_i>a_{i+1}$ 且 $a_{i-1}=a_{i+1}$，时，我们应该删除 $a_i$ 将 $a_{i+1}$ 变为 $a_{i+1}+1$。
• 当 $a_i>a_{i+1}$ 且 $a_{i-1}>a_{i+1}$，时，由于我们将 $a_i$ 删去后 $a_{i+1}$ 仍然不合法，所以我们应该删除 $a_{i+1}$。

核心代码

void solve() {
    int n, k = 0;
    cin >> n;
    vector<int> a(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int b = a[1];
    for (int i = 2; i <= n; i++)
    {
        if (a[i] > b) {
            b = a[i];
            continue;
        }
        if (a[i] == b) {
            a[i]++;
            b = a[i];
        }
        else {
            k++;
            if (k == 2) {
                cout << "NO\n";
                return;
            }
            if (a[i] < a[i - 2]) {
                b = a[i - 1];
            }
            else if (a[i] == a[i - 2]) {
                a[i]++;
                b = a[i];
            }
            else {
                b = a[i];
            }
        }
    }
    cout << "YES\n";
    return;
}
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

E题题解：

观察到$k$并不大，并且是一个比较经典的网格dp

网格dp一般设：dp[i][j]表示从(1,1)点走到(i,j)点的最大价值/收益等，因题目而异。

在dp中，一般遇到模数问题，我们可以将模数作为状态保存在数组中。于是我们可以得到

dp[i][j][x]:表示从(1,1)走到(i,j)点切mod k = x的方案数

我们一开始就在(1,1)点，即dp[1][1][a[1][1] % k] = 1

状态转移如下

dp[i + 1][j][x * a[i + 1][j] % k] += dp[i][j] // 向下走
dp[i][j + 1][x * a[i][j + 1] % k] += dp[i][j] // 向右走
1
2

显然，最后的答案是：dp[n][n][0]。

AC Code

const int MOD = 998244353, N = 510; 

int a[N][N];
long long dp[N][N][30];

void solve(){
	int n, k;
	std::cin >> n >> k;
	for(int i = 1; i <= n; i ++ ){
		for(int j = 1; j <= n; j ++ ){
			std::cin >> a[i][j];
		}
	}
	for(int i = 1; i <= n; i ++ ){
		for(int j = 1; j <= n; j ++ ){
			if(i == 1 && j == 1){
				dp[1][1][a[1][1] % k] = 1;
			}
			for(int x = 0; x < 20; x ++ ){
				dp[i + 1][j][a[i + 1][j] * x % k] += dp[i][j][x];
				dp[i + 1][j][a[i + 1][j] * x % k] %= MOD;
				dp[i][j + 1][a[i][j + 1] * x % k] += dp[i][j][x];
				dp[i][j + 1][a[i][j + 1] * x % k] %= MOD;
			}
			
		}
	}
	std::cout << dp[n][n][0];
}
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

StarryCoding是面向计算机专业学生的综合学习与刷题平台，欢迎同学们的加入！
www.starrycoding.com