牛客周赛128
锐评
题目难度：E > F > D > C > B > A
A
题目链接：https://ac.nowcoder.com/acm/contest/127240/A
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve() {
string s;
std::cin >> s;
if(s[1] == s[2]){
std::cout << "Yes\n";
}else{
std::cout << "No\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 t = 1;
// std::cin >> t;
while(t --){
solve<int>();
}
return 0;
}
B
题目链接：
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve() {
int x[3];
int y[3];
for(int i = 0;i < 3;i ++){
std::cin >> x[i] >> y[i];
}
if(x[0] * 2 == x[1] + x[2] && y[0] * 2 == y[1] + y[2]){
std::cout << "1\n";
return ;
}
if(x[1] * 2 == x[0] + x[2] && y[1] * 2 == y[0] + y[2]){
std::cout << "2\n";
return ;
}
if(x[2] * 2 == x[1] + x[0] && y[2] * 2 == y[1] + y[0]){
std::cout << "3\n";
return ;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 t = 1;
// std::cin >> t;
while(t --){
solve<int>();
}
return 0;
}
C
题目链接：https://ac.nowcoder.com/acm/contest/127240/C
思路：先找到中间值，再往两边找值赋为中间值。
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve() {
int n;
std::cin >> n;
int a[n],p[n];
std::map<int, int> mp;
for(int i = 0;i < n; i++) std::cin >> a[i];
for(int i = 0;i < n; i++){
mp[a[i]] = i;
p[i] = a[i];
}
int ans = n / 2 + 1;
if(n & 1){
ans = 0;
int l = n / 2, r = n / 2 + 2;
while(ans * 2 < n - 1){
if(ans % 2 == 0) a[mp[l--]] = n / 2 + 1;
else a[mp[r++]] = n / 2 + 1;
//l --;
//r ++;
ans ++;
}
}else{
ans = 0;
int l = n / 2, r = n / 2 + 1;
while(ans * 2 < n){
if(ans % 2 == 0) a[mp[l--]] = n / 2;
else a[mp[r++]] = n / 2;
//l --;
//r ++;
ans ++;
}
}
for(int i = 0;i < n; i++) std::cout << a[i] << " \n"[i == n-1];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 t = 1;
// std::cin >> t;
while(t --){
solve<int>();
}
return 0;
}
D
题目链接：https://ac.nowcoder.com/acm/contest/127240/D
思路：记录每个结点为根的树有多少个结点，在dfs。
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve() {
int n;
std::cin >> n;
std::vector<vector<int>> adj(n+1);
for(int i = 1;i < n; i++){
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
std::vector<int> tree(n+1);
function<int(int, int)> dfs = [&](int v, int parent){
if(adj[v].size() == 0){
tree[v] = 1;
return 1;
}
int ans = 0;
for(auto &x : adj[v]){
if(x != parent){
ans += dfs(x, v);
}
}
tree[v] = ans + 1;
return tree[v];
};
tree[1] = dfs(1, 1);
int cnt = 0;
function<void(int, int)> dfs1 = [&](int v, int parent){
bool ok = true;
for(auto &x : adj[v]){
if(x != parent){
if((tree[x]) % 2 == 0 && tree[x] > 0) ok = false;
}
}
int k = n - tree[v];
if(k % 2 == 0 && v != 1 && k > 0) ok = false;
if(ok) cnt ++;
for(auto &x : adj[v]){
if(x != parent){
dfs1(x, v);
}
}
};
dfs1(1, 1);
if(n == 1) cnt = 1;
std::cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 t = 1;
std::cin >> t;
while(t --){
solve<int>();
}
return 0;
}
E
题目链接：https://ac.nowcoder.com/acm/contest/127240/E
思路：
对于偶数个一，我们把前面一半的1删掉，后面的全变成2.
对于奇数个1，我们会保留一个1，保留的1就看有没有1后面为2的，有的话就找最近的那个保留，没有的话就保留第一个1.
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve() {
string s, m, p;
std::cin >> s;
//1往前放，2往后放
int len = s.size();
int ans = 0;
for(int i = 0;i < len; i++){
if(s[i] == '1') ans ++;
}
//不对，有0可以不删1,找到与0最近的1
//还是不对，1删了之后，保留的1前面的1可能为2
int cnt = ans;
ans /= 2;
for(int i = len-1;i >= 0; i--){
if(ans == 0) break;
if(s[i] == '1'){
ans--;
s[i] = '2';
if(ans == 0) break;
}
}
queue<int> q;
len = s.size();
for(int i = 0;i < len; i++){
if(s[i] == '1') q.push(i);
}
int n = 0;
if(cnt & 1){
bool ok = false;
n = q.front();
while(!q.empty()){
int cnt = q.front();
q.pop();
if(cnt + 1 < len && s[cnt+1] == '2'){
ok = true;
n = cnt;
break;
}
n = cnt;
}
for(int i = 0;i < len; i++){
if(s[i] == '1' && i != n){
continue;
}else{
//if(s[i] != '1')
m += s[i];
}
}
}else{
for(int i = 0;i < len; i++){
if(s[i] == '1'){
continue;
}else{
m += s[i];
}
}
}
std::cout << m << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 t = 1;
// std::cin >> t;
while(t --){
solve<int>();
}
return 0;
}
F
题目链接：https://ac.nowcoder.com/acm/contest/127240/F
思路：双指针从左往右找10的这种，有的话就删1，删除后会不会重组01，会的话继续删。后面的1变2.
代码：
/*Don’t cut corners, don’t over-rely on AI. Stay grounded, and keep challenging yourself with every single problem.*/
#include <bits/stdc++.h>
//当遇到感觉可以写但总是卡壳的题时，不妨先冷静下来仔细思考。
//当把题目真正读懂的时候，你已经写出来了一半。
//学习他人的做法也是一种提升。
//过程是很痛苦，但唯有坚持。
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 INF = 998244353;
constexpr int N = 300005;
constexpr double IP = 2.7182818;
constexpr i64 MAXN = 1E6 + 7;
constexpr i64 MOD = 1E9 + 7;
template<class T>
void solve() {
string s, m, p;
std::cin >> s;
//1往前放，2往后放
int len = s.size();
//不对，有0可以不删1,找到与0最近的1
//还是不对，1删了之后，保留的1前面的1可能为2
int l = 0, r = len-1;
for(int i = 0;i < len; i++){
if(s[i] == '1'){
l = i;
break;
}
}
for(int i = l;i <= r; i++){
bool ok = false;
if(s[i] == '0'){
int j = i;
while(j >= l){
if(s[j] == '2') break;
while(j >= l && s[j] != '1' && s[j] != '2'){
j --;
}
if(s[j] == '2') break;
if(j >= l && s[j] == '1'){
ok = true;
}
if(ok){
while(r > i && s[r] != '1'){
r --;
}
if(r > i && s[r] == '1'){
s[r] = '2';
s[j] = '#';
j--;
ok = false;
}else{
j--;
ok = false;
}
}else{
ok = false;
break;
}
if(s[j] == '2') break;
}
l = i;
}
}
for(int i = 0;i < len;i ++){
if(s[i] != '#') m += s[i];
}
std::cout << m << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 t = 1;
// std::cin >> t;
while(t --){
solve<int>();
}
return 0;
}
