文章目录
记录下大半年后的首场复出以及首次蓝名，通知中的妹子很戳，感谢名单也够皮，就是开完AB后很痛苦，差点反向上大分。（日常问候SPyofgame）
A Marin and Photoshoot
题意：给定一个 01 串，可以在其中添加若干个 1 ，使得任意大于等于二的区间内，0 的个数不超过 1 的个数
分析：两个 0 之间必须要有两个及以上的 1 ，构成 0110 结构。而若 0 位于两端则无需，如 0
#include <bits/stdc++.h>
using namespace std;
#define si(a) scanf("%d", &a)
#define ss(a) scanf("%s", a)
using namespace std;
int t, n; char s[110];
int main()
{
si(t);
while (t--)
{
si(n); ss(s);
int ans = 0, num = 2;
for (int i = 0; i < strlen(s); i++)
{
if (s[i] == '0')
{
if (num < 2) ans += 2 - num;
num = 0;
}
else num++;
}
printf("%d\n", ans);
}
}
B Marin and Anti-coprime Permutation
题意：求使得gcd(p1, 2 * p2, … , n * pn)>1的序列个数
分析：奇偶数对换（即奇数放偶数位置，偶数放在奇数位置），可知 n 为奇数时为0，偶数时为 pow((n/2)!,2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define si(a) scanf("%d", &a)
const int mod = 998244353;
using namespace std;
int t, n;
int main()
{
si(t);
while (t--)
{
si(n);
if (n%2==0)
{
ll ans = 1;
for (int i = 1; i <= n / 2; i++) ans = ans * i % mod;
printf("%lld\n", ans * ans % mod);
}
else puts("0");
}
}
C Shinju and the Lost Permutation
题意：好复杂，不想解释了…再说现在机翻也挺方便的（疯狂暗示）
分析：首先，拿到的值数列有且仅能有一个 1，对应原序列最大的数。然后讨论拼接情况，若后面拿上来的数比原队首的数字小，则对应原序列后一个数会比前一个大1；反之则不变或减小。综上可知仅a[i]-a[i-1]>1非法，其他均可构造。
#include <bits/stdc++.h>
using namespace std;
#define si(a) scanf("%d", &a)
using namespace std;
int t, n, cnt, pos, a[100010];
int main()
{
si(t);
while (t--)
{
si(n); cnt = 0;
for (int i = 1; i <= n; i++)
{
si(a[i]);
if (a[i] == 1) cnt++, pos = i;
}
if (cnt != 1) puts("No");
else
{
bool f = 1;
rotate(a + 1, a + pos, a + n + 1);
for (int i = 2; i <= n; i++)
if (a[i] - a[i - 1] > 1) f = 0;
f ? puts("Yes") : puts("No");
}
}
}
D 388535
题意：给定两个数 l, r 以及数组 a[ ]，找出一个数 x，使 a[ ] ^ x = {l , … , r}
分析：对每个二进制位进行验证，当第i位为1的数组 a[ ] 的个数大于 l - r 中的个数时，表示 x 的第 i 位为 1。
#include <bits/stdc++.h>
using namespace std;
#define si(a) scanf("%d", &a)
using namespace std;
int t, l, r, ans, a[1000010];
int main()
{
si(t);
while (t--)
{
si(l), si(r); ans = 0;
for (int i = 1; i <= r-l+1; i++) si(a[i]);
for (int i = 0; i <= 18; i++)
{
int cnt = 0;
for (int j = l; j <= r; j++) if (1 << i & j) cnt--;
for (int j = 1; j <= r - l + 1; j++) if (1 << i & a[j]) cnt++;
if (cnt) ans ^= 1 << i;
}
printf("%d\n", ans);
}
}