Codeforces Global Round 16(A - E)

71 阅读 0 评论 47 点赞

我是靠谱客的博主粗暴香水，最近开发中收集的这篇文章主要介绍Codeforces Global Round 16(A - E)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A. Median Maximization

简单的贪心构造题意让求中位数最大为多少已知序列中所有数字均为非负则我们可以让中位数之前的数全为0 然后中位数则可以最大取到总数除以剩下数向下取整
代码

#include <bits/stdc++.h>
using namespace std;
int n, s;
void solve()
{
cin >> n >> s;
if (n % 2 == 1)
{
int m = n - n / 2;
cout << s / m << endl;
}
else
{
int m = n - (n / 2 - 1);
cout << s / m << endl;
}
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T -- )
{
solve();
}
return 0;
}

B. MIN-MEX Cut

依旧是贪心题意为给定一个字符串可以分为若干小字符串其中每个字符串的价值为 mex(当前字符串包含的数字) 对于01我们可以取到2 对于0我们可以取到1 对于1我们可以取到0 需要求最小价值和
因此我们可以看看有多少连续的只包含0的子字符串如果数量大于2我们可以直接取整个字符串价值为2 如果小于2我们可以取连续0的块数

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
string s;
void solve()
{
cin >> s;
int tot = 0;
for (int i = 1; i < s.size(); i ++ )
if (s[i] == '1' && s[i] != s[i - 1]) tot ++ ;
if (s[s.size() - 1] == '0') tot ++ ;
if (tot < 2) cout << tot << endl;
else cout << 2 << endl;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T -- )
{
solve();
}
return 0;
}

C - MAX-MEX Cut

和b差不多给定两行字符串 mex为[l, r]中上下两行所有01的mex 让我们分为若干子字符串求最大的价值和
简单构造题对于上下均为0(用a0 b0表示)的我们可以选择保留看看后面是否为a1 b1如果是的话我们用这两行可以取到2 如果是a0 b0 我们可以选择ans加上前面a0 b0（价值为1）然后再看当前行之后是否有a1 b1 如果遇到a0 b1 或者a1 b0可以直接加上2
代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
string a, b;
void solve()
{
cin >> n;
cin >> a >> b;
int t1 = -1, t2 = -1; // t1是前一排 t2是后一排
int ans = 0;
for (int i = 0; i < n; i ++ )
{
if (a[i] != b[i]) t2 = 2;
else if (a[i] == '1') t2 = 0;
else t2 = 1;
if (t2 == 2)
{
if (t1 != -1) ans += t1;
ans += t2;
t1 = t2 = -1;
}
else if (t1 != -1 && t1 ^ t2)
{
ans += 2;
t1 = t2 = -1;
}
else if (t1 != -1 && t1 == t2)
{
if (t1 == 1) ans += t1, t1 = 1;
t1 = -1;
}
t1 = t2;
}
if (t1 != -1) ans += t1;
cout << ans << endl;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T -- )
{
solve();
}
return 0;
}

D1. Seating Arrangements (easy version)

阅读理解题感觉有点脑残
思路很简单直接暴力即可仅有一行人每个人都要按视力来排序排序后前面每有一个序列号小于他的价值就要加一求最小价值和
代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int n, m;
int a[N];
void solve()
{
cin >> n >> m;
for (int i = 1; i <= m; i ++ ) cin >> a[i];
int ans = 0;
for (int i = 1; i <= m; i ++ )
for (int j = 1; j < i; j ++ )
if (a[j] < a[i]) ans ++ ;
cout << ans << endl;
}
signed main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T -- )
{
solve();
}
return 0;
}

D2. Seating Arrangements (hard version)

D1的难度增加版有n行每个人经过前面人时ans要++ 排序依然是按照视力来排序最后对于当前视力大小的序列是一定的我们为了减小价值和需要通过一定的排序来优化对于第i行的最后一人和第i+1行的第一人假如两人视力相等则显然当第i行最后一人的排队序号较小时可以使得价值和较小对于同一排的第i人和第i+1人显然当第i人的排队序号较大时可以使得价值和较小
则我们建立两个排序分别对总序列以及每排的序列进行排序求ans
代码

#include <bits/stdc++.h>
using namespace std;
const int N = 350;
int n, m;
struct Node
{
int value, idx;
}a[N * N];
bool cmp1(Node x, Node y)
{
if (x.value == y.value) return x.idx < y.idx;
return x.value < y.value;
}
bool cmp2(Node x, Node y)
{
if (x.value == y.value) return x.idx > y.idx;
return x.value < y.value;
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n * m; i ++ )
{
cin >> a[i].value;
a[i].idx = i;
}
sort(a + 1, a + 1 + n * m, cmp1);
int ans = 0;
for (int i = 1; i <= n; i ++ )
{
sort(a + 1 + (i - 1) * m, a + 1 + i * m, cmp2);
int l = (i - 1) * m + 1, r = i * m;
for (int j = l; j <= r; j ++ )
for (int k = l; k < j; k ++ )
if (a[j].idx > a[k].idx) ans ++ ;
}
cout << ans << endl;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t -- )
{
solve();
}
return 0;
}

E. Buds Re-hanging

题意很好懂令每个花蕾为子节点只包含叶子结点且子节点个数大于1 然后可以移动花蕾结点至其他叶子结点问进行若干次移动之后最小的叶子结点数目为多少
这个题我们可以把所有花蕾以及可以变为花蕾的节点包含它的叶子结点都给分离出来然后随便再组合每次组合都会使得ans-1 可以从下往上找然后再加起来即为最优解
代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = N * 2;
int n, ans;
int h[N], e[M], ne[M], idx;
void init()
{
memset(h, -1, sizeof h);
idx = 0, ans = 1;
}
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int dfs(int cur, int fa)
{
int cnt = 0;
for (int i = h[cur]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
cnt += dfs(j, cur);
}
if (cnt)
{
ans += (cnt - 1);
return 0;
}
return 1;
}
void solve()
{
init();
cin >> n;
for (int i = 1; i < n; i ++ )
{
int u, v;
cin >> u >> v;
add(u, v), add(v, u);
}
dfs(1, 0);
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
while (T -- )
{
solve();
}
return 0;
}