暑假牛客多校第三场 2023-7-24
未补完
A. World Fragments I
算法：构造
做法：从x中某一个数位选一个数，这个数有可能是0或者是1。求x变到y的最小数，这个数有可能是负数，要取绝对值。
注意如果x是0，那么从x中取的数就只有0了，除非y也等于0，否则输出-1。
code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define fir first
#define sec second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
const int N = 1000010;
void solve()
{
LL ans = 0, a = 0, b = 0;
LL two = 1;
string x, y;
cin >> x >> y;
reverse(x.begin(), x.end()), reverse(y.begin(), y.end());
if (x.size() == 1 && x[0] == '0' && (y[0] == '1' || y.size() > 1))
{
cout << -1 << endl;
return;
}
for (int i = 0; i < x.size(); i++)
{
if (x[i] == '1')a += two;
two = 2 * two;
}
two = 1;
for (int i = 0; i < y.size(); i++)
{
if (y[i] == '1')b += two;
two = 2 * two;
}
cout << abs(a - b) << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
H. Until the Blue Moon Rises
算法：歌德巴赫猜想
1.哥德巴赫猜想的现代陈述为：任一大于5的整数都可写成三个质数之和。
2.强哥德巴赫猜想（强哥猜）：即任一大于2的偶数都可写成两个质数之和。（未被证明，但是同时也没有被推翻，即在本体的范围内强哥猜成立）
3.弱哥德巴赫猜想（弱哥猜）: 任何一个大于5的奇数都能被表示成三个奇质数的和。（一个质数可以被多次使用）（已经被证明）
做法：
首先如果 \(n = 1\) 时，如果单独这个数是质数则对，否则错。
当 \(n = 2\) 时，当两个数的和为偶数且大于等于4，则对，否则错。当两个数的和为奇数时，由于奇数必定由偶数加上奇数组合而成。所以这两个数必定有一个数是偶数，有一个是奇数。先考虑偶数，由于2是偶数中唯一 一个质数，所以偶数必定需要为2，那么奇数就为总和减去2，我们再判断这个总和是不是为质数就可以了。
当 \(n = 3\) 时，首先我们要保证所有数的总和要大于等于 \(2 * n\)，因为最小的质数是2，当所有数都是2时才能出现全部是质数的情况。在这个前提下，我们把所有数都变为2，那么总和减去 \(2 * n\) 即为剩下的数，我们设为 \(x\)。如果 \(x\) 是偶数，我们可以全部都加到数组的一个数上，即为 \(2 + x\)，结果设为 \(y\)， \(y\) 必然也是偶数。我们在找数组中的一个数，由于数组的数都是2，那么 \(2 + y\) 也必然是偶数，且大于4，可以分解成两个质数。如果 \(x\) 是奇数，那么我们把奇数的1移到数组的一个数上，3也为质数。\(x\) 变为了偶数。这时情况和上面 \(x\) 是偶数的情况一样，必定能得到数组中的数都为质数。
借鉴博客
code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define fir first
#define sec second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
const int N = 1010;
LL n;
LL w[N];
bool is_prime(LL x)
{
if (x == 1)return false;
for (LL i = 2; i <= x / i; i++)
{
if (x % i == 0)
return false;
}
return true;
}
void solve()
{
LL sum = 0;
cin >> n;
for (int i = 1; i <= n; i++)cin >> w[i], sum += w[i];
if (n == 1 && is_prime(w[1]))
{
cout << "Yes" << endl;
return;
}
else if(n == 1 && !is_prime(w[1]))
{
cout << "No" << endl;
return;
}
if (n == 2 && sum % 2 == 0)
{
if (sum >= 4)cout << "YES" << endl;
else cout << "No" << endl;
return;
}
else if (n == 2 && sum % 2 != 0)
{
if (is_prime(sum - 2))cout << "Yes" << endl;
else cout << "No" << endl;
return;
}
if (sum >= n * 2)cout << "Yes" << endl;
else cout << "No" << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}
J. Fine Logic
算法：拓扑排序
做法：先对图跑一边拓扑排序，如果拓扑排序最终排序的节点小于n，那么这个图中必定有环。有环就从1 - n正着输出一便和倒着输出一便。无环就输出其拓扑排序的结果。说一下为什么能正着输出一便和倒着输出一遍，对于图中的每一对节点，我们选任一一对节点，设为u和v（u != v）。u > v时，在正着输出时必有<v, u>，倒着输出必有<u, v>。v > u时，正着输出时必有<u, v>，倒着输出时必有<v, u>。扩展到每一对节点，这个说法均成立，因此倒着输出一便和正着输出一便是没错的。
code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <cmath>
#include <string>
#include <set>
#define fir first
#define sec second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<double, double> PDD;
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };
const int N = 1000010;
int n, m;
int h[N], e[N], ne[N], w[N], idx;
int qq[N], du[N], hh, tt;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool topsort()
{
hh = 0, tt = -1;
for (int i = 1; i <= n; i++)
{
if (du[i] == 0)
qq[++tt] = i;
}
while (hh <= tt)
{
int t = qq[hh++];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
du[j]--;
if (du[j] == 0)qq[++tt] = j;
}
}
return tt == n - 1;
}
void solve()
{
cin >> n >> m;
memset(h, -1, sizeof(h));
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
add(a, b);
du[b]++;
}
if (!topsort())
{
cout << 2 << endl;
for (int i = 1; i <= n; i++)cout << i << ' ';
cout << endl;
for (int i = n; i >= 1; i--)cout << i << ' ';
}
else
{
cout << 1 << endl;
for (int i = 0; i <= tt; i++)cout << qq[i] << ' ';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
solve();
return 0;
}