牛客周赛 Round 36

赛况

        C题可惜，比赛时模拟没有想明白，只对了一半，赛后看了大佬们的题解后恍然大悟，而F题是压根没思路，况且F题部分分也比较难拿。

题目列表

A-小红的数位删除

思路

        将读入的数字整除10做三次后输出即可

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+5,INF = 0x3f3f3f3f;
int n; 
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin >> n;int cnt = 0;while(cnt!=3){cnt++;n/=10;}cout << n << '\n';return 0;
}

B-小红的小红矩阵构造

思路

        如果元素和不等于x，则输出wrong answer，否则判断其每行和每列的异或和是否与第一行和第一列相等，若不相等，则输出wrong answer，最后所有条件都满足，则输出accepted

参考题解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e2+5,INF = 0x3f3f3f3f;
int a[N][N];
int n,m,x;
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin >> n >> m >> x;for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){cin >> a[i][j];}}int sum=0;for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){sum+=a[i][j];}}if(sum!=x){cout << "wrong answer\n";return 0;}int rowxor=0,columnxor=0;for(int i = 1;i<=m;i++) rowxor^=a[i][1];for(int i = 1;i<=n;i++) columnxor^=a[1][i];for(int i = 2;i<=n;i++){int nowxor=0;for(int j = 1;j<=m;j++){nowxor^=a[i][j];}if(nowxor!=rowxor){cout << "wrong answer\n";return 0;}}for(int i = 2;i<=m;i++){int nowxor=0;for(int j = 1;j<=n;j++){nowxor^=a[j][i];}if(nowxor!=columnxor){cout << "wrong answer\n";return 0;}}cout << "accepted\n";return 0;
}

C-小红的白色字符串

思路

        如果遇到大写字母，它前面若不是' '(空格)，那么答案ans++，并且把当前大写字母用' '覆盖，最终输出ans即可

参考题解

#include <bits/stdc++.h>
using namespace std;
string s;
int main() {ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin >> s;int ans = 0;for(int i = 1;i<s.size();i++){if(s[i]>='A'&&s[i]<='Z'&&s[i-1]!=' '){ans++,s[i]=' ';}}cout << ans << '\n';return 0;
}

D-小红走矩阵

思路

        BFS模板题，直接全程默写

参考题解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e3+5,INF = 0x3f3f3f3f;
struct Node{int x,y,s;
}t,t1;
char graph[N][N];
bool vis[N][N];
queue<Node> q;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int sx,sy,ex,ey;
int n,m;
void bfs(){sx=1,sy=1,ex=n,ey=m;t.x=sx,t.y=sy,t.s=0;q.push(t);vis[sx][sy]=1;while(!q.empty()){t = q.front();
//		cout << t.x << ' ' << t.y << '\n';q.pop();if(t.x==ex&&t.y==ey){cout << t.s << '\n';return;}for(int i = 0;i<4;i++){int u=t.x+dx[i],v=t.y+dy[i];if(u<1||u>n||v<1||v>m||vis[u][v]||graph[u][v]==graph[t.x][t.y]) continue;vis[u][v]=1;t1.x=u,t1.y=v,t1.s=t.s+1;q.push(t1);}}cout << "-1\n";
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin >> n >> m;for(int i = 1;i<=n;i++) for(int j = 1;j<=m;j++) cin >> graph[i][j];bfs();return 0;
}

E-小红的小红走矩阵

思路

        我们自己随便定一条步数介于n+m-2至n*m-2直接的一条通路即可，当然注意生成的字母最好稀疏一点，我找的路如下图。

        路的生成就是模拟遍历，确保第1、2、3行的第2至m-1列的字母都相同，其余拐点位置为上个位置的下一个字母，注意转换的时候对26取模，避免超出'a'到'z'的范围。剩余其他所有位置，循环从'a'到'z'生成即可。 

参考题解

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e3+5,INF = 0x3f3f3f3f,mod = 26;
char graph[N][N];
int n,m;int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin >> n >> m;for(int i = 1;i<=m;i++) graph[1][i]='a'+(i-1)%mod;graph[2][m]='a'+(graph[1][m]-'a'+1)%mod;for(int i = m-1;i>=1;i--) graph[2][i]=graph[1][i];for(int i = m;i>=2;i--) graph[3][i]=graph[2][i];graph[3][1]='b';for(int i = 4;i<=n;i++) graph[i][1]='a'+(i-2)%mod;for(int i = 2;i<=m;i++) graph[n][i]='a'+(graph[n][1]-'a'+i-1)%mod;int cnt=0;for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){if(graph[i][j]>='a'&&graph[i][j]<='z') continue;if(cnt==26){cnt=0;}graph[i][j]='a'+cnt;cnt++;}}for(int i = 1;i<=n;i++){for(int j = 1;j<=m;j++){cout << graph[i][j];}cout << '\n';}return 0;
}

F-小红的好子串询问

思路

        预处理出不是回文串的只含三个字母且不重复的字符串。修改和查询都使用树状数组实现

参考题解

（感谢橙名大佬牛客288141082号提供的题解）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;#define N 100000int 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';}}
}