A. Gardener and the Capybaras
题意：
给定一个由 ab 串，将该字符串拆分成 3 个部分，使中间部分的字典序最大或者最小。
分析：
- 考虑简单的最小情况：中间只有一个 a ，两边总会 \(≥\) 中间;
- 中间最大：若在中间无法找到 a ，说明中间全是 b ，这样不管第一个和最后一个字符是什么中间总大于两边
void solve()
{
cin >> s;
s = " " + s;
int len = s.size() - 1;
int pos = 0;
for (int i = 2; i < len; i++)
{
if (s[i] == 'a')
{
pos = i;
break;
}
}
if (pos)
{
for (int i = 1; i < pos; i++)
cout << s[i];
cout << " a ";
for (int i = pos + 1; i <= len; i++)
cout << s[i];
cout << endl;
}
else
{
cout << s[1] << " ";
for (int i = 2; i < len; i++)
cout << s[i];
cout << " " << s[len];
cout << endl;
}
}
C. Interesting Sequence
题意：
给定 a b,求出大于 a 的最小的 num 使:
\(n\) & \(n+1\) & \(n+2\) & \(...\) & \(num\) \(=\) \(b\)
分析：
&运算只能使 1 变成 0，而不能使 0 变成 1，首先在二进制表示的 a 与 b 中，若 b 的第 k 位为 1 而 a 的第 k 位为 0 ，直接输出-1;
a 上数之后，a 中的 1 只会越来越少，不可能大于原来的数量；
在逐位分析：
- ak = 0 && bk = 0，这一位就不用考虑
- ak = 0 && bk = 1，不可能
- ak = 1 && bk = 0，要在范围之内至少存在一个数的第 k 位为 1
- ak = 1 && bk = 1，要在范围之内所有数的第 k 位都是 1
从高位开始考虑，所有发生情况 4 的位都是需要保留的位，发生情况 3 的位都是要通过 ++ 来使这一位与上 0，此时必定会将上一位的 1 变成 0 ，或将 0 变成 1 ，所以此时如果前一位是需要保留的位，直接FALSE，要保证需要保留的最低位比情况 3 发生的最高位高至少 2 位，此时，需要改变的最高位的前一位必定是 0，也是改变为 1 后最接近 a 的数
void solve()
{
idxa = idxb = 0;
cin >> a >> b;
if (a < b)
{
cout << "-1" << endl;
return;
}
if (a == b)
{
cout << a << endl;
return;
}
int aa = a, bb = b;
while (aa)
{
if (aa % 2)
idxa++;
aa /= 2;
}
while (bb)
{
if (bb % 2)
idxb++;
bb /= 2;
}
if (idxa < idxb)
{
cout << "-1" << endl;
return;
}
else
{
vector<int> va, vb;
while (a)
{
va.push_back(a % 2);
a /= 2;
}
while (b)
{
vb.push_back(b % 2);
b /= 2;
}
int maxsize = max(va.size(), vb.size());
while (va.size() <= maxsize)
va.push_back(0);
while (vb.size() <= maxsize)
vb.push_back(0);
int ne = 100, ch = 100;
bool f = true;
for (int i = maxsize; i >= 0; i--)
{
if (va[i] == 1 && vb[i] == 1)
ne = i;
if (va[i] == 1 && vb[i] == 0 && ch == 100)
ch = i;
if (va[i] == 0 && vb[i] == 1)
{
cout << "-1" << endl;
return;
}
if (va[i] == 1 && vb[i] == 0)
f = false;
if (!f && va[i] == 1 && vb[i] == 1)
{
cout << "-1" << endl;
return;
}
}
if (ch >= ne - 1)
{
cout << "-1" << endl;
return;
}
int res = 0;
for (int i = maxsize; i >= 0; i--)
{
if (va[i] == 1 && vb[i] == 1)
res += pow(2, i);
if (va[i] == 1 && vb[i] == 0)
{
res += pow(2, i + 1);
break;
}
}
cout << res << endl;
return;
}
}
E. The Human Equation
题意：
给定一个序列，每次操作先选择一个子序列，然后对奇数位置的数 +1，对偶数位置的数 -1，或对奇数位置的数 -1，对偶数位置的数 +1，求最少操作次数使得所有数变为 0
分析：
结论题QWQ（没想到）
选定随意区间进行操作，那么对于任意的区间和只有三种情况：+1，-1，不变
放到子序列上也对应这三种情况。。。
所以如果要把全部的区间和都变成 0 ，只要让需要的区间和变为 0
void solve()
{
mst(s, 0);
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
s[i] = s[i - 1] + a[i];
}
int minv = 0, maxv = 0;
for (int i = 1; i <= n; i++)
{
maxv = max(maxv, s[i]);
minv = min(minv, s[i]);
}
cout << maxv - minv << endl;
}
D. Friendly Spiders
题意：
n 个点，两辆不互质的点之间可以互相到达，给定 S 和 T ，求最短距离和路径
分析：
\(n^2\) 建图必 T ，这题首先分析数据范围，最多 3e5 的点，点最大也是 3e5 ，对这一范围内的数每个数分解因数是 \(nlogn\) ，任意两个不互质的数必定会连接到一个共同因数上去，若这个因数是质数那么他自己相当于‘根’，若这个数不是质数则会连到他的因数上去，最终所有数都被连接到自己的最小质因数上；
复杂度：线性筛，分解质因数 + 建双向边，dijkstra，记录路径
不考虑重边最后边数：\(2*nlogn\) ，拓展点数 + 总点数：\(n + logn\)
（本题若一开始建立带权边会 T ，由于边权的性质只有能到达和不能到达，所以可以在 dijkstra 更新距离时 ＋1 来优化）
#include <bits/stdc++.h>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF 0x3f3f3f3f
#define x first
#define y second
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2000010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
typedef unordered_map<int, int> Ump;
int S, T;
int n, a[N];
map<PII, bool> mp;
int pre[N];
int st[N], primes[N], cnt;
int h[N], e[N], ne[N], idx;
int d[N];
bool vis[N];
// void add(int a, int b, int c)
// {
// e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
// }
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void get_primes()
{
for (int i = 2; i < N; i++)
{
if (!st[i])
primes[cnt++] = i, st[i] = i;
for (int j = 0; primes[j] * i < N; j++)
{
st[primes[j] * i] = primes[j];
if (i % primes[j] == 0)
break;
}
}
}
int dijkstra(int S, int T)
{
mst(d, 0x3f), mst(vis, false);
d[S] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({d[S], S});
while (heap.size())
{
auto t = heap.top();
heap.pop();
int id = t.second, dist = t.first;
if (vis[id])
continue;
vis[id] = true;
for (int i = h[id]; ~i; i = ne[i])
{
int j = e[i];
if (d[j] > dist + 1)
{
d[j] = dist + 1; // 优化
heap.push({d[j], j});
pre[j] = id;
}
}
}
if (d[T] > INF)
return -1;
return d[T];
}
void solve()
{
mst(h, -1);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
cin >> S >> T;
if (S == T)
{
cout << 1 << endl
<< S << endl;
return;
}
if (a[S] == a[T])
{
if (a[S] == 1)
{
cout << -1 << endl;
return;
}
cout << 2 << endl;
cout << S << " " << T << endl;
return;
}
for (int i = 1; i <= n; i++)
{
for (int j = a[i]; j >= 2; j /= st[j])
{
if (mp[{i, st[j]}])
continue;
// cout << i << " " << st[j] << endl;
add(i, st[j] + n);
add(st[j] + n, i);
mp[{i, st[j]}] = true;
}
}
int res = dijkstra(S, T);
// cout << res << endl;
if (res == -1)
cout << "-1" << endl;
else
{
vector<int> road;
int cur = T;
while (cur != S)
{
if (cur <= n)
road.push_back(cur);
cur = pre[cur];
}
road.push_back(S);
cout << road.size() << endl;
reverse(road.begin(), road.end());
for (auto t : road)
cout << t << " ";
cout << endl;
}
}
signed main()
{
FAST;
get_primes();
solve();
return 0;
}