1. Up to the Clouds
$$$x\oplus x=0$$$
$$$x\oplus x\oplus x=x$$$
The answer depends on parity.
If $$$m$$$ is even, then the result of the formula is always $$$0$$$. Otherwise, it can be any positive integer, because all the elements in the sequence $$$a$$$ is positive.
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
void run()
{
scanf("%d%d", &n, &m);
puts((m & 1) ^ (!n) ? "Yes" : "No");
}
int main()
{
int T = 1;
scanf("%d", &T);
while (T--)
run();
}
2. Song of Silent River
Lexicographically smallest.
If you can keep the current character a
, then do it.
Since a
is the lexicographically smallest character, then it's always optimal to insert a
instead of others.
Use #
in the string $$$b$$$ greedily.
#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 10;
int n, m, cts, idx;
string s, t;
int main()
{
cin >> n >> m >> s >> t;
for (int i = 0; i < n; i++)
{
cts += (t[i] == '#');
}
for (auto &i : s)
{
if (i != '#')
continue;
i = idx + 'a';
if (cts >= 25 - idx)
{
cts -= 25 - idx;
idx = 0;
continue;
}
idx++;
idx = (idx == 26 ? 0 : idx);
}
cout << s << '\n';
}
3. Drifting Clouds' Rhythm
Denote $$$c_{i,x}$$$ as the total number moments when exactly $$$x$$$ roses are blooming when or before the moment $$$i$$$.
If we have a virtual rose which blooms in the range $$$[1,i]$$$, then how to denote the number the answer will increase when we move that flower's blooming time to an infinitely faraway place?
The answer of the question raised in hint $$$1$$$ is $$$\sum_{j=2}^\infty c_{i,j}+c_{i,2}$$$.
Prefix sum.
We can calculate the sequence $$$c$$$ at each turning point. We call a moment a turning point when a rose blooms or fades at this moment.
Then, calculate value in hint $$$2$$$ for each turning point.
It can be proved that moving $$$[x,y]$$$ away is equivalent to move $$$[1,y]$$$ away then move $$$[1,x-1]$$$ back.
So use prefix sum to calculate answer for each rose.
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
using ll = long long;
int n, m, x, idx, cur;
ll mx, res[4], p2[N];
using pii = pair<int, int>;
pii dst[N << 2];
bool mp[N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &x);
dst[++idx] = {x, i};
dst[++idx] = {x + m, i};
}
sort(dst + 1, dst + idx + 1);
for (int i = 1; i <= idx; i++)
{
auto &[a, b] = dst[i];
res[min(cur, 3)] += a - dst[i - 1].first;
if (!mp[b])
{
cur++;
mp[b] = true;
p2[b] = res[2] * 2 + res[3];
continue;
}
mx = max(mx, res[2] * 2 + res[3] - p2[b]);
cur--;
}
printf("%lld\n", res[1] + mx);
}