牛客小白月赛95

A

判断一下情况即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	int a,b;
    cin>>a>>b;
    if(a==1&&b==2||a==2&&b==3||a==3&&b==1)
    {
        cout<<'a';
    }
    else if(a==b){
        cout<<'p';
    }
    else{
        cout<<'b';
    }
	return 0;
}

B

考虑两种走法

1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    long long a,b;
    cin>>a>>b;
    long long ans = min(a*11,a+b*5);
    cout<<ans;
     
    return 0;
}

C

选择一对相等的数字然后进行删除。

这个题其实暂时不需要思考那么多，因为只有1和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
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 9;
int a[N];
 
int main()
{
    int n; cin >> n;
     
    for(int i = 1; i <= n; i ++) cin >> a[i];
     
    if(n == 1)
    {
        cout << -1 << '\n';
        return 0;
    }
     
    if(a[1] == a[n])
    {
        cout << 1 << '\n';
        return 0;
    }
     
    for(int i = 2; i <= n - 2; i ++)
    {
        if(a[1] == a[i] && a[i + 1] == a[n])
        {
            cout << 2 << '\n';
            return 0;
        }
    }
    cout << -1 << '\n';
     
    return 0;
}

D

这个曼哈顿距离看起来挺好差分加前缀和的

直接对每行进行差分修改

然后最后进行一次二维前缀和，并计算奇数和偶数即可。

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>
using namespace std;
typedef long long ll;
const int N = 3e3 + 5, M = 5e5 + 5;
 
int n, m;
int a[N][N];
 
int main() 
{

    int n, m;
    cin >> n >> m;
    while (m --) 
    {
        int x, y, r;
        cin >> x >> y >> r;
        for (int i = max(1, x - r); i <= min(n, x + r); i ++) 
        {
            int l = r - abs(x - i);
            a[i][max(y - l, 1)] ++, a[i][min(y + l + 1, n + 1)] --;
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++) {
            a[i][j] += a[i][j - 1];
            if (a[i][j] & 1) a[i][j] = 1;
            else a[i][j] = 0;
            res += a[i][j];
        }
    cout << res;
    return 0;
}

E

这一道题是C题的加强，哎，二进制多好。这样子感觉就需要进行dp操作了

这个dp的定义不难以想象，就是dp[i]为删除1-i的数字需要的最小次数

dp[i]=min(dp[j]+1)，找到之前那个最小的，可以进行删除的

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
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 5e5 + 10;
const long long MOD = 1e9 + 7;
 
int a[MAXN], f[MAXN], m[MAXN];
 
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    memset(f, 0x3f, sizeof(f));
    memset(m, 0x3f, sizeof(m));
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = m[a[i]] + 1;
        m[a[i]] = min(m[a[i]], f[i - 1]);
    }
    if (f[n] >= 0x3f3f3f3f) {
        cout << -1;
    } else {
        cout << f[n];
    }
    return 0;
}

F

曼哈顿距离转切比雪夫？

本题还是有点技巧性的，这个知识点也已经考过，可以记。

估计还是这样进行二维差分，不然这题很难写，应该是将菱形区域变成矩形区域进行二维差分，最后进行二维前缀和判断？

曼哈顿距离：

横纵坐标差之和

img

切比雪夫距离：

横纵坐标坐标差的最大值

img

我们考虑最简单的情况，在一个二维坐标系中，设原点为(0,0)

如果用曼哈顿距离表示，则与原点距离为1的点会构成一个边长为√2的正方形

如果用切比雪夫距离表示，则与原点距离为1的点会构成一个边长为2的正方形

alt

将一个点(x,y)的坐标变为(x+y,x−y)后,原坐标系中的曼哈顿距离 = 新坐标系中的切比雪夫距离

将一个点(x,y)的坐标变为(（x+y）/2,（x−y）/2) 后,原坐标系中的切比雪夫距离 = 新坐标系中的曼哈顿距离

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
#include<bits/stdc++.h>
using namespace std;
const int N = 6e3 + 10;
int f[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        int x, y, r;
        cin >> x >> y >> r;
        // 曼哈顿距离转换成切比雪夫距离
        int nx = x + y, ny = x - y + 3000;
        f[max(1, nx - r)][max(1, ny - r)] ^= 1;
        f[min(6000, nx + r + 1)][max(1, ny-r)] ^= 1;
        f[max(1, nx-r)][min(6000, ny + r + 1)] ^= 1;
        f[min(6000, nx + r + 1)][min(6000, ny + r + 1)] ^= 1;
    }
    int ans = 0;
    for(int i = 1; i <= 6000; i ++)
        for(int j = 1; j <= 6000; j ++)
        {
            f[i][j] = f[i-1][j]^f[i-1][j-1]^f[i][j-1]^f[i][j];
            //曼哈顿距离转换成切比雪夫距离
            int x = (i + j - 3000) / 2, y = (i - j + 3000) / 2;
            if(f[i][j] && (i&1) == (j&1) && x > 0 && x <= n && y > 0 && y <= n)
                ans ++;
        }
    cout << ans << '\n';
    return 0;
}