牛客周赛36

A 小红的数位删除

输出删除后三位数字的数

string n;cin >> n;
for (int i = 0;i < n.size() - 3;i++)cout << n[i];

B 小红的小红矩阵构造

检测是否满足所有元素之和恰好等于 x，且每行、每列的异或和全部相等

int a[110][110];
void solve() {
    int n, m, s;cin >> n >> m >> s;
    int sum = 0;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> a[i][j];
            sum += a[i][j];
        }
    }
    if (sum != s) {
        cout << "wrong answer\n";return;
    }
    int x = a[1][1];
    for (int i = 2;i <= n;i++) {
        x ^= a[1][i];
    }
    for (int i = 1;i <= n;i++) {
        int r = a[i][1];
        for (int j = 2;j <= m;j++) {
            r ^= a[i][j];
        }
        if (r != x) {
            cout << "wrong answer\n";return;
        }
    }
    for (int i = 1;i <= n;i++) {
        int r = a[1][i];
        for (int j = 2;j <= m;j++) {
            r ^= a[j][i];
        }
        if (r != x) {
            cout << "wrong answer\n";return;
        }
    }
    cout << "accepted\n";
}

C 小红的白色字符串

小红拿到了一个字符串，她准备将一些字母变成白色，变成白色的字母看上去就和空格一样，这样字符串就变成了一些单词。
现在小红希望，每个单词都满足以下两种情况中的一种：

开头第一个大写，其余为小写（长度为 1 的大写字母也是合法的）。
所有字符全部是小写。

小红想知道，最少需要将多少字母变成白色？

void solve() {
    string s;cin >> s;
    s = ' ' + s;
    int ans = 0, cnt = 0;
    for (int i = 1;i < s.size();i++) {
        cnt = 0;int ok = 0;
        while (isupper(s[i])) {
            if (i == 1) {
                ok = 1;
            }
            cnt++;i++;
        }
        ans += (cnt - ok + 1) / 2;
    }
    cout << ans << '\n';
}

D 小红走矩阵

小红来到了一个n∗m 的矩阵，她初始站在左上角，每次行走可以按“上下左右”中的一个方向走一步，但必须走到和当前格子不同的字符，也不能走到矩阵外。

小红想知道，从左上角走到右下角最少需要走多少步？

BFS 板子

#define pll pair<int,int> 
char g[1010][1010];
int n, m;
int vis[1010][1010], dis[1010][1010];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int bfs(int x, int y) {
    queue<pll> q;
    vis[x][y] = 1;
    q.push({x,y});
    dis[x][y] = 0;
    while (q.size()) {
        auto t = q.front();q.pop();
        for (int i = 0;i < 4;i++) {
            int a = t.first + dx[i];
            int b = t.second + dy[i];
            if (a<1 || a>n || b<1 || b>m)continue;
            if (vis[a][b])continue;
            if (g[a][b] == g[t.first][t.second])continue;
            vis[a][b] = 1;
            dis[a][b] = dis[t.first][t.second] + 1;
            q.push({a,b});
        }
    }
    if (!dis[n][m])dis[n][m] = -1;
    return dis[n][m];
}
void solve() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> g[i][j];
        }
    }
    cout << bfs(1, 1) << "\n";
}

E 小红的小红走矩阵

造 D 的数据，要求：

直接输出 n + m - 2 会返回答案错误，换句话说，“小红走矩阵”这题的正确代码运行后的结果不是 n + m - 2。
直接输出 n * m - 1 也会返回答案错误，换句话说，“小红走矩阵”这题的正确代码运行后的结果不是 n * m - 1。
生成的矩阵中，不存在“绝对众数”。（即，没有任何字符的出现次数大于 n * m / 2 向上取整）
生成的矩阵必须能从 (1,1) 走到 (n, m)，换句话说，“小红走矩阵”这题的正确代码运行后的结果不是 -1。

Solution

构造

我赛时的想法：(当 n 和 m 比较小的时候就不可行)

int n, m;
char a[1010][1010];
void solve() {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            a[i][j] = 'A';
        }
    }
    for (int i = 1;i <= m;i++) {
        if (i % 2)a[1][i] = 'a';
        else a[1][i] = 'b';
    }
    for (int i = 2;i <= n;i++) {
        if (i % 2 == 0)a[i][m] = (a[1][m] == 'a' ? 'b' : 'a');
        else a[i][m] = (a[1][m] == 'a' ? 'a' : 'b');
    }
    a[n - 1][m] = a[n][m];
    a[n - 2][m - 1] = (a[n - 1][m] == 'a' ? 'b' : 'a');
    a[n - 1][m - 1] = (a[n - 2][m - 1] == 'a' ? 'b' : 'a');
    a[n][m - 1] = (a[n - 1][m - 1] == 'a' ? 'b' : 'a');
    for (int i = 2;i <= n;i++) {
        for (int j = 1;j < m;j++) {
            if (isupper(a[i][j])) {
                if (i % 4 == 2 || i % 4 == 3)
                    a[i][j] = 'c';
                else a[i][j] = 'd';
            }
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cout << a[i][j];
        }cout << '\n';
    }
}

其实按照样例来构造就可以了...

将样例给出的 9 个字符放进去之后，后面随意构造即可。

char a[1010][1010];
void solve() {
    int n, m;cin >> n >> m;
    a[1][1] = 'a';a[1][2] = 'b';a[1][3] = 'b';
    a[2][1] = 'a';a[2][2] = 'c';a[2][3] = 'c';
    a[3][1] = 'b';a[3][2] = 'c';a[3][3] = 'b';
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (!islower(a[i][j])) {
                a[i][j] = 'A';
            }
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (isupper(a[i][j])) {
                a[i][j] = 'a' + (i + j) % 26;
            }
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cout << a[i][j];
        }cout << '\n';
    }
}

F 小红的好子串询问

小红定义一个字符串是“好串”，当且仅当该字符串不包含长度不小于 2 的回文子串。
现在小红拿到了一个仅包含"red"三种字符的字符串，她有如下两个操作：

输入 1 x chr：将第 x 个字符修改为 chr
输入 2 l r：询问第 l 个字符到第 r 个字符的子串再修改最少多少个字符可以变成好串（每次修改后也必须是"red"三种字符中的一种）。

Solution

树状数组/线段树

看不懂...坐等视频()
待补：小白月赛 88，ARC

要满足这题的要求，只能是 "red","rde","dre","der","erd","edr" 六种字符串循环才能保证不会出现长度不小于 2 的回文子串。

就枚举六种情况，看哪一种使用的次数最少即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

#define N 100000

int i, j, k, n, m, t;

string s, s1, _s[7] = {"","red","rde","dre","der","erd","edr"};

int f[7][N + 50];

void add(int f[], int x, int y) { for (;x <= n;x += (-x & x)) { f[x] += y; } }
int get(int f[], int x, int y = 0) { for (;x;x -= (-x & x)) { y += f[x]; }return y; }

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> t >> s; s = "$" + s;
    for (i = 1;i <= n;i++) {
        for (j = 1;j <= 6;j++) {
            add(f[j], i, s[i] != _s[j][i % 3]);
        }
    }
    while (t--) {
        int l, r, res, op;
        cin >> op;
        if (op == 1) {
            cin >> l >> s1;
            for (j = 1;j <= 6;j++) {
                add(f[j], l, -(s[l] != _s[j][l % 3]));
            }
            s[l] = s1[0];
            for (j = 1;j <= 6;j++) {
                add(f[j], l, (s[l] != _s[j][l % 3]));
            }
        } else {
            cin >> l >> r;
            res = 1e9;
            for (i = 1;i <= 6;i++) {
                res = min(res, get(f[i], r) - get(f[i], l - 1));
            }
            cout << res << '\n';
        }
    }
}