牛客周赛52
A 两数之和
对于给定的正整数
如果不存在这样的
void solve() {
int z;cin >> z;
if (z <= 2) {
cout << "NO\n";
} else {
cout << "YES\n";
cout<<"1 "<< z - 1<<'\n';
}
}
B 小红装匣子
小红有
物块可以旋转使用,可以有剩余。
易得:
#define int long long
void solve() {
int a, b, n;cin >> a >> b >> n;
int mxb = min(b, n / 3 * 2);
if (mxb & 1)mxb--;
if (2 * a + 3 * mxb >= 2 * n) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
C 小红的数字对对碰
红有一个长度为
- 当
且存在二元组 ,满足 且 ,则可消去 和 。 - 当
且存在二元组 ,满足 且 ,则可消去 和 。
请你输出最小化后的数组的长度。
按照
由给出的条件:
综上:只有
有贪心的思想:正数是不利于答案的计算的,所以尽量先将正数去掉,即先将
#define int long long
void solve() {
int n;cin >> n;
int pos = 0, neg = 0, z = 0;
map<int, int>mp;
for (int i = 1;i <= n;i++) {
int x;cin >> x;
if (x == 0) {
z++;
} else if (x > 0) {
pos++;mp[x]++;
if (mp[x] == 2) {
pos -= 2, mp[x] = 0;
}
} else {
neg++;
}
}
if (pos <= neg) {
cout << (neg - pos + z) % 2 << '\n';
} else {
cout << pos - neg + z << '\n';
}
}
E 小红的图上加边
小红有一张
现在小红希望加边把这个图连成连通图,每次连接的代价是新形成的联通块的最大元素值,小红想知道最小需要消耗多少代价可以把这个图连成连通的。
这个题目居然是最简单的...
按照缩点的思想,每个块的权值是
则易得答案就是
#define int long long
void solve() {
int n, m;cin >> n >> m;
vector<int> a(n + 1);
for (int i = 1;i <= n;i++)cin >> a[i];
vector<vector<int>> g(n + 1);
for (int i = 1;i <= m;i++) {
int u, v;cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> vis(n + 1);
int sum = 0, mi = 1e18;
for (int i = 1;i <= n;i++) {
if (!vis[i]) {
int mx = a[i];
queue<int>q;vis[i] = 1;q.push(i);
while (q.size()) {
int u = q.front();q.pop();
for (auto v : g[u]) {
if (vis[v])continue;
vis[v] = 1;
mx = max(mx, a[v]);
q.push(v);
}
}
mi = min(mi, mx);
sum += mx;
}
}
cout << sum - mi << '\n';
}
D 小红的最大字典序
小红有
第
小红想要构造一个这样的字符串
Solution
堆+思维
这个题没写出来实在不应该...
看到小学哥写的,太秒了,实在太秒!
void solve() {
int n;cin >> n;
priority_queue<pair<char, string>>q;
for (int i = 1;i <= n;i++) {
string s;cin >> s;q.push({s[0],s});
}
string ans = "";
while (q.size()) {
auto [c, s] = q.top();q.pop();
s.erase(s.begin());
ans += c;
if (s.size()) {
q.push({s[0],s});
}
}
cout << ans << '\n';
}
F 小红的括号串
小红有一个只包含 '(' 、')' 和 '?' 的字符串,小红想知道有多少种将 '?' 替换成 '(' 或 ')' 的方式使得存在一种循环移位、让该字符串为合法的括号串。
假设一个长度为
Solution
可以参考小学哥的题解:题解 | 小红的括号串_牛客博客 ->具体数学 P301
新知识:Raney 引理:若
意在告诉我们只要满足序列和为 0 的均合法。
constexpr int mod = 1e9 + 7;
void solve() {
int n;cin >> n;
string s;cin >> s;
if (n & 1) {
cout << "0\n";return;
}
int x = 0, y = 0;
for (auto c : s) {
if (c == '(') x++;
else if (c == ')') y++;
}
cout << C(n - x - y, n / 2 - x) << '\n';
}