2023牛客暑期多校训练营3
A.World Fragments I
题意:
给定两个非负二进制数a和b，每次从a中选择某个数位x(0/1)，并令a = a + x或a = a - x,问将a变成b的最小操作数，无解输出-1。
分析：
①a = b时输出0
②a ≠ b时，若a = 0，b ≠ 0则无解，否则输出|a - b|
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL get(string &s) {
LL res = 0;
reverse(s.begin(), s.end());
for (int i = 0; i < s.size(); i ++) {
if (s[i] == '1')
res += (LL)1 << i;
}
return res;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
string s1, s2;
cin >> s1 >> s2;
LL a = get(s1), b = get(s2);
if (a == 0 && b != 0)
cout << -1;
else
cout << abs(a - b);
return 0;
}
D.Ama no Jaku
题意:
给你一个01矩阵，你可以进行若干次操作，每次操作翻转某一行或者某一列，问能否使该矩阵行代表的二进制数\(r_i\)和列代表的二进制数\(c_i\)满足min(\(r_i\)) \(\geqslant\) max(\(c_i\))，如果可以输出最小操作数，否则输出-1。
分析:
①全为0或者1显然满足
②若非全0，min(\(r_i\)) \(\geqslant\) max(\(c_i\)) > 0
\(\Rightarrow\) 每行至少有一个1
\(\Rightarrow\) min(\(c_i\)) \(\geqslant\) \(2^n\),
\(\Rightarrow\) 要满足大小关系，则至少每行第一个元素都是1
\(\Rightarrow\) max(\(c_i\)) = \(2^{n + 1} - 1\)
\(\Rightarrow\) 要满足大小关系则矩阵必须全为1
综上，要满足要求最后矩阵必须全为0或者1
通过模拟可以发现，能通过翻转使其全为0或者1的矩阵应满足：每行要么和第一行相同要么和第一行取反相同，不妨这两类行数设为a和b。
因此若有解，答案就是min(第一行0的个数，第一行1的个数) + min(a, b)
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
string s[N];
bool check(int n) {
string s1 = s[0], s2;
for (int i = 0; i < n; i ++) {
s2 += !(s[0][i] - '0') + '0';
}
for (int i = 1; i < n; i ++) {
bool flag1 = s[i] == s1, flag2 = s[i] == s2;
if (!flag1 && !flag2)
return false;
}
return true;
}
int cal(int n) {
int cnt0 = 0, cnt1 = 0;
for (int i = 0; i < n; i ++) {
if (s[0][i] == '0')
cnt0 ++;
else
cnt1 ++;
}
return min(cnt0, cnt1);
}
int cal1(int n) {
int cnt = 0, cnt1 = 0;
for (int i = 0; i < n; i ++) {
if (s[i] == s[0])
cnt ++;
else
cnt1 ++;
}
return min(cnt, cnt1);
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i ++) {
cin >> s[i];
}
if (n == 1)
cout << 0;
else {
if (check(n)) {
cout << cal(n) + cal1(n);
}
else
cout << -1;
}
return 0;
}
E.Koraidon, Miraidon and DFS Shortest Path
题意:
给定一张图，使用dfs求解从1到其他点的最短路，问给定的图能否在任意边的遍历顺序下都能正确求解最短路。
分析:
正解用到支配树(还没学会...)。附上赛时水过的代码。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int h[N], e[N], ne[N], idx;
int d[N];
bool success, st[N], st2[N];;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void bfs(int n) {
queue<int> q;
for (int i = 1; i <= n; i ++) {
d[i] = 0x3f3f3f3f;
}
d[1] = 0;
q.push(1);
while (q.size()) {
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] > d[t] + 1) {
d[j] = d[t] + 1;
if (!st[j]) {
st[j] = true;
q.push(j);
}
}
}
}
}
void dfs(int u) {
st2[u] = true;
if (!success)
return;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (st2[j])
continue;
if (d[j] != d[u] + 1) {
success = false;
return;
}
dfs(j);
st2[j] = false;
}
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t --) {
int n, m;
cin >> n >> m;
idx = 0;
for (int i = 1; i <= n; i ++) {
h[i] = -1;
st[i] = st2[i] = false;
}
while (m --) {
int a, b;
cin >> a >> b;
add(a, b);
}
bfs(n);
success = true;
dfs(1);
if (success)
cout << "Yes" << "\n";
else
cout << "No" << "\n";
}
return 0;
}
H.Until the Blue Moon Rises
题意:
给你n个数，你可以进行若干次操作，每次让一个数+1或者-1，问能否构造出n个质数
分析:
本题考“哥德巴赫猜想”。
哥德巴赫猜想的现代陈述为：任一大于5的整数都可写成三个质数之和。
由此可以得到两种情况：
1.强哥德巴赫猜想（强哥猜）：任一大于2的偶数都可写成两个质数之和；（未被证明，但是同时也没有被推翻，即在本题的范围内强哥猜成立）
2.弱哥德巴赫猜想（弱哥猜）:任一个大于5的奇数都能被表示成三个奇质数的和。（一个质数可以被多次使用）;（已经被证明）
因此这题可以进行如下讨论：
设n个元素的和为s
①n = 1，直接判断s是否为质数
②n = 2，若s为偶数则用强哥猜（特判s是否大于等于4），否则判断s - 2是否为质数（奇数 + 偶数 = 奇数，偶质数只有2）。
③n > 2，则用哥猜。当n = 3时，由于任一大于5的整数都可写成三个质数之和，则s至少为6即最小的方案为“2，2，2”，以此类推，可知当s \(\geqslant\) 2n 时有解。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
bool check(LL a) {
if (a < 2)
return false;
for (int i = 2; i * i <= a; i ++) {
if (a % i == 0)
return false;
}
return true;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
LL s = 0;
for (int i = 0; i < n; i ++) {
int a;
cin >> a;
s += a;
}
if (n == 1) {
if (check(s))
cout << "Yes";
else
cout << "No";
} else if (n == 2) {
if (s % 2 == 0) {
if (s >= 4)
cout << "Yes";
else
cout << "No";
} else if (check(s - 2)) {
cout << "Yes";
} else {
cout << "No";
}
} else {
if (s >= 2 * n) {
cout << "Yes";
} else {
cout << "No";
}
}
return 0;
}
J.Fine Logic
题意:
给定n个点和m个偏序关系，要求构造序列数最少的k个序列，使得m个偏序关系都能在这个k个序列中找到。
分析:
按偏序关系建图：
若不存在环则输出拓扑排序即可，此时k = 1
若存在环，输出1到n的正序序列和n到1的倒序序列即可，因为<u, v>可以在正序序列中找到，<v, u>可以在逆序序列中找到，因此包含了所有情况，此时k = 2
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, M = 2e6 + 5;
int h[N], e[M], ne[M], idx;
int n, m, q[N], d[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool topsort() {
int hh = 0, tt = -1;
for (int i = 1; i <= n; i ++) {
if (!d[i]) {
q[++ tt] = i;
}
}
while (hh <= tt) {
int t = q[hh ++];
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (-- d[j] == 0) {
q[++ tt] = j;
}
}
}
return tt == n - 1;
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
memset(h, -1, sizeof h);
while (m --) {
int a, b;
cin >> a >> b;
add(a, b);
d[b] ++;
}
if (topsort()) {
cout << 1 << "\n";
for (int i = 0; i < n; i ++)
cout << q[i] << " ";
} else {
cout << 2 << "\n";
for (int i = 1; i <= n; i ++)
cout << i << " ";
cout << "\n";
for (int i = n; i >= 1; i --)
cout << i << " ";
}
return 0;
}