牛客小白月赛105（A~E）

牛客小白月赛105

A lz的吃饭问题

思路

签到题，比较大小即可

code

void solve(){int a,b,c,d;cin >> a >> b >> c >> d;if(a*b<c*d) cout << "lz" << endl;else cout << "gzy" << endl;return ;
}

B lz的数字问题

思路

在 $a,b$ 后面补0，将小数点后7位数全部删除

最后比较大小即可

code

void solve(){string a,b;cin >> a >> b;int k1=a.find('.');int k2=b.find('.');if(k1==-1) a+=".0000000";else a+="0000000";if(k2==-1) b+=".0000000";else b+="0000000";k1=a.find('.');k2=b.find('.');a.erase(k1+7);b.erase(k2+7);if(a==b) cout << "YES" << endl;else cout << "NO" << endl;return ;
}

C lz的蛋挞问题

思路

对于改变蛋挞联通块的情况，大致分为2种:：

. . .  与 x . x 情况一致，这为一种情况 (将中间的.换成x)x         x  
. .  与 . . 情况一致，这为另一种情况 (左边的图将左上角的.换成x；右边的图将右上角的.换成x)
. x     x .

最后就是边界问题

. x 与 x .  只要邻边是x就满足
x        x

纯模拟即可

code

void solve(){int n;cin >> n;string s,t;cin >> s >> t;int ans=0;for(int j=0;j<s.size();++j){if(s[j]=='x') continue;if(j==0||j==n-1){if(t[j]=='x' && s[j+1]=='x' || t[j]=='x' && s[j-1]=='x') ans++;else if(s[j+1]=='.' && t[j]=='.' && t[j+1]=='x') ans++;else if(s[j-1]=='.' && t[j]=='.' && t[j-1]=='x') ans++;}else if(t[j]=='x' && s[j+1]==s[j-1]) ans++;else if(s[j+1]=='.' && t[j]=='.' && t[j+1]=='x') ans++;else if(s[j-1]=='.' && t[j]=='.' && t[j-1]=='x') ans++;}for(int j=0;j<t.size();++j){if(t[j]=='x') continue;if(j==0||j==n-1){if(s[j]=='x' && t[j+1]=='x'||s[j]=='x' && t[j-1]=='x') ans++;else if(t[j+1]=='.' && s[j]=='.' && s[j+1]=='x') ans++;else if(t[j-1]=='.' && s[j]=='.' && s[j-1]=='x') ans++;}else if(s[j]=='x' && t[j+1]==t[j-1]) ans++;else if(t[j+1]=='.' && s[j]=='.' && s[j+1]=='x') ans++;else if(t[j-1]=='.' && s[j]=='.' && s[j-1]=='x') ans++;}cout << ans << endl;return ;
}

D lz的染色问题

思路

建图，将每天要观察的花的序号看成图

例如：
一个序列 1 2 3 4 5 6 7 8
观察的花的序号为：
1 2
2 3
1 4
5 6
6 7

对于前三组序列来说：1到2有一条边，2到3有一条边，1到4也有一条边
这四个点不在到达其他点，那么这四个点构成一个联通块，我们在这个联通块里找出现次数最多的花色
将其他花色变为出现次数最多的花色即可
后2组序列同理：5 6 7 三个点构成另一个联通块
在这个联通块里也将其他花色变为出现次数最多的花色

将花的序号分为多个联通块，考虑每个联通块中将其他花色变为出现次数最多的花色，用一个ans变量累加转换的次数，最后输出ans即可

code

const int N=1e6+5;
int a[N],vis[N];
vector<int> e[N];
map<int,int> m;
void dfs(int x){m[a[x]]++;vis[x]=1;for(auto y : e[x]){if(!vis[y]) dfs(y);}
}
void solve(){int n,q;cin >> n >> q;for(int i=1;i<=n;++i) cin >> a[i];while(q--){int u,v;cin >> u >> v;e[u].push_back(v);e[v].push_back(u);} int ans=0;for(int i=1;i<=n;++i){if(!vis[i]){m.clear();dfs(i);int sum=0,mx=0;for(auto i : m){sum+=i.se;mx=max(mx,i.se);}ans+=sum-mx;}}cout << ans << endl;return ;
}

E lz的括号问题

思路

用栈模拟括号匹配

栈里面存的是左括号出现的顺序

如果当前遍历到右括号时，栈顶为空，说明括号匹配不满足，直接输出-1
反之，当前栈顶的元素可删去的括号数等于 $n-栈的大小$ (除了包含这个括号的括号对不能删除，其他都能在它前面删除)

最后顺序输出即可

code

const int N=1e6+5;
int a[N];
void solve(){int n;cin >> n;string s;cin >> s;stack<int> st;vector<int> ans(n+1);int k=1;for(auto i : s){if(i=='(') st.push(k++);else{if(st.empty()){cout << -1 << endl;return ;}else{ans[st.top()]=n-st.size();st.pop();}}}for(int i=1;i<=n;++i) cout << ans[i] << " ";return ;
}

总结

这场牛客打的稀碎，C题题目看错了，感觉不好写就没看了
D题赛时没想到建图，卡死在D题
E题实际上挺简单的，赛时也没时间看了
思维还是不够敏捷，题目练太少了，特别是图论，基本上我都没往那方面去想，下去多看看图论的题，找找手感（太菜了）