前言：
题解主要参考来源：
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(广度优先搜索)求边权全部相等的最短路
以下是代码部分，代码参考来源——比那名居的桃子
#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;
}
京公网安备 11010502036488号