题解 | #牛客周赛Round 36#

小红的数位删除

https://ac.nowcoder.com/acm/contest/76609/A

前言：

题解主要参考来源：

A - 小红的数位删除

思路:

截取一部分字符串输出即可

以下是代码部分

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

int main()
{
    string s;
    cin >> s;
    cout << s.substr(0, s.size() - 3);

    return 0;
}

B - 小红的小红矩阵构造

思路：

纯模拟判断即可

以下是代码部分

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

const int N = 1e2 + 10;
using ll = long long;

ll mp[N][N];
ll n, m, x;
bool check()
{
  //检查和是否为x
    ll sum = 0, ans = 0;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            sum += mp[i][j];
    if(sum != x) return false;
    //异或值
    for(int i = 1; i <= m; i ++) ans ^= mp[1][i];
    //行和列的异或是否符合标准
    for(int i = 1; i <= n; i ++)
    {
        ll temp1 = 0;
        for(int j = 1; j <= m; j ++) temp1 ^= mp[i][j];
        if(temp1 != ans) return false;
    }
    for(int j = 1; j <= m; j ++)
    {
        ll temp1 = 0;
        for(int i = 1; i <= n; i ++) temp1 ^= mp[i][j];
        if(temp1 != ans) return false;
    }

    return true;
}

int main()
{
    cin >> n >> m >> x;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin >> mp[i][j];
    cout << (check() ? "accepted" : "wrong answer");

    return 0;
}

更优的写法——比那名居的桃子

以下是代码部分

#include<bits/stdc++.h>
using namespace std;
int a[101][101];
int main(){
    int n, m, x;
    cin >> n >> m >> x;
    long long s = 0;
    //判断和是否符合标准
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> a[i][j], s += a[i][j];
    if(x!=s) return cout<<"wrong answer",0;
    set<int>st;
    //存储每行or每列的异或值
    for(int i = 0; i < n; i++)
    {
        int temp=0;
        for(int j = 0; j < m; j++)
            temp ^= a[i][j];
        st.insert(temp);
    }
    for(int j = 0; j < m; j++)
    {
        int temp=0;
        for(int i = 0; i < n; i++)
            temp^=a[i][j];
        st.insert(temp);
    }
    //如果并不是都相等
    if(st.size() > 1)
        return cout<<"wrong answer",0;
    cout<<"accepted";
    
    return 0;
}

C - 小红的白色字符串

思路；

类似贪心的思维
从后往前分情况模拟即可

以下是代码部分

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

string s;

int main()
{
    cin >> s;
    int len = (int)s.length(), ans = 0;
    for(int i = len - 1; i > 0; i --)
    {
        if(isupper(s[i]) && isupper(s[i - 1]))
            s[i - 1] = ' ', ans ++;
        else if(isupper(s[i]) && islower(s[i - 1]))
            s[i] = ' ', ans ++;
    }
    cout << ans;

    return 0;
}

从前往后遍历，跳过第一个字符的方法

更优的写法——比那名居的桃子

以下是代码部分

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

int main()
{
    string s; cin >> s;
    int cnt = 0;
    for(int i = 1; i < s.length(); i++) if(isupper(s[i])) cnt++, i++;
    cout << cnt;
    return 0;
}

D - 小红走矩阵

思路：

BFS(广度优先搜索)求边权全部相等的最短路
- bilibili的BFS解决迷宫问题视频链接

以下是代码部分，代码参考来源——比那名居的桃子

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

const int N = 1e3 + 10;
string s[N];
int dis[N][N];
int op[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int main()
{
    int n, m;
    cin >> n >> m;
    //初始化距离为无穷
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            dis[i][j] = 1e9;
    //输入地图
    for(int i = 0; i < n; i ++) cin >> s[i];
    //储存坐标
    queue<pair<int, int>> q;
    //初始坐标为(0, 0) 从左上角开始
    q.emplace(0, 0);
    //距离起点的距离为0
    dis[0][0] = 0;
    while(!q.empty())
    {
        //拿出队首
        pair<int, int> temp = q.front();
        //删除队首
        q.pop();
        //四个方向一次扩展
        for(int i = 0; i < 4; i ++)
        {
            int x = temp.first + op[i][0], y = temp.second + op[i][1];
            //是否越界
            if (x < 0 || x >= n || y < 0 || y >= m) continue;
            //满足题意，字母不同，同时保证不走重复的路段
            if (s[x][y] != s[temp.first][temp.second] && dis[x][y] > dis[temp.first][temp.second] + 1)
            {
                //更新路径的值
                dis[x][y] = dis[temp.first][temp.second] + 1;
                //记得放入队列中
                q.emplace(x, y);
            }
        }
    }
    //输出即可
    if(dis[n - 1][m - 1] > 8e8) cout << -1;
    else cout << dis[n - 1][m - 1];

    return 0;
}

E - 小红的小红走矩阵

思路：

选取一条规定的路线，其他部分做到填充后，依旧以选取的路线为最短路径的地图 -
此为本人选取的一条合法路径

以下是代码部分

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

const int N = 1e3 + 10;
using ll = long long;

char mp[N][N];

void solve()
{
    int n, m;
    cin >> n >> m;
    if(n == 3 && m == 3)
    {
        cout << "aac\nbba\nacc\n";
        return ;
    }
    for(int i = 1; i <= n; i ++)
        mp[i][1] = (i&1 ? 'a' : 'b');
    for(int i = 2; i <= m - 2; i ++)
    {
        if (n & 1) mp[n][i] = (i & 1 ? 'b' : 'a');
        else mp[n][i] = (i & 1 ? 'a' : 'b');
    }
    mp[n][m - 1] = mp[n][m] = 'f';
    mp[n - 1][m] = 'a';
    for(int i = 2; i < m; i ++)
        mp[n - 1][i] = 'c';
    for(int i = 1; i <= n - 2; i ++)
        for(int j = 2; j <= m; j ++)
            mp[i][j] = (i&1 ? 'e' : 'd');

    mp[n - 1][1] = mp[n - 2][m - 1] = mp[n - 2][m] = 'c';
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
            cout << mp[i][j];
        cout << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t --)
        solve();

    return 0;
}

F - 小红的好子串询问

思路:

可以去看——牛客官方视频讲解
已知一个长度为n的回文串，那么它必有n-2长度的回文串
逆否命题，若没有长度为n-2的回文串，则没有长度为n的回文串
因此可得，为一个由'r', 'e', 'd'组成的长度为3的排列构成的回文串
- red
- rde
- erd
- edr
- der
- dre
排列总共六种，可以开六个树状数组。

以下是代码部分，代码参考来源——比那名居的桃子

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

string str[6] = {"red", "rde", "edr", "erd", "der", "dre"};
const int N = 4e5 + 10;
int tree[N][6];
//树状数组的修改操作
void add(int x, int id, int p)
{
    for(int i = x; i <= 2e5; i += i&-i)
        tree[i][id] += p;
}
//树状数组查询值的操作
int ask(int x, int id)
{
    int res = 0;
    for(int i = x; i > 0; i -= i&-i)
        res += tree[i][id];
    return res;
}
//树状数组查询区间的操作
int ask(int l, int r, int id)
{
    int res = ask(r, id);
    res -= ask(l - 1, id);
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    s = ' ' + s;
    //前缀和，储存每种排列方式需要修改的次数
    //运用前缀和可以方便区段查询
    for(int i = 1; i <= n; i ++)
        for(int j = 0; j < 6; j ++)
            if(s[i] != str[j][i%3])
                add(i, j, 1);

    while(q --)
    {
        int op;
        cin >> op;
        if(op == 1)
        {
            int x;
            char ch;
            cin >> x >> ch;
            //修改x点的字符时，对前缀和进行单点修改
            for(int i = 0; i < 6; i ++)
            {
                //注意修改的时候要先把先前的记录减去
                if(s[x] != str[i][x % 3])
                    add(x, i,-1);
                if(ch != str[i][x % 3])
                    add(x, i, 1);
            }
            //s上的字符不要忘记修改
            s[x] = ch;
        }
        else
        {
            int l, r;
            cin >> l >> r;
            int res = 1e9;
            //区段查询6个树状数组中的最小状况
            for(int i = 0; i < 6; i ++)
                res = min(res, ask(l, r, i));
            cout << res << '\n';
        }
    }

    return 0;
}

牛客周赛题解便于查看文章被收录于专栏

方便本人自己查看复习知识点。