这场也打了，再简单记录一下
A
给一个区间\([l, r]\)，求\((a, b)\)满足\(1 \leq a \leq b \leq r\)，使\(b \mod a\)最大。
观察样例\((l = 8, r = 26)\)，容易发现不考虑\(l\)的限制的情况，对于一个\(r\)答案最大的情况是取到\(2n + 1 \leq r\)的最大的\(n\)，在这种情况下不妨取\(b = r\)可使\(l\)的限制最松。考虑到\(r\)的奇偶性会使上面的\(a\)的取值发生变化，不妨先取\(n = \lfloor \frac{r}{2} \rfloor, b = r\)，若\(l \leq n + 1\)，取\(a = n + 1\)可使答案取到最大值，否则\(a = l\)。
int T;
read(T);
for (int l, r; T--; ) {
read(l), read(r);
if (l == r) puts("0");
else {
int n = r / 2;
int b = r, a = max(l, n + 1);
printf("%d\n", b % a);
}
}
B
给出一个\(k\)位的不含\(0\)的十进制数，想要删掉尽可能多的位数，使得剩下的数不是一个素数。
若这个数中含有\(1, 4, 6, 8, 9\)，直接删到这一位即可；否则这些数中只有\(2, 3, 5, 7\)，此时一定满足\(k \geq 2\)，寻找这些数位组成的合法两位数即可。
scanf("%d", &T);
for (; T--; ) {
scanf("%d", &n);
scanf("%s", s + 1);
for (int i = 1; i <= n; i++) a[i] = s[i] - ‘0‘;
bool ok = 0;
for (int i = 1; i <= n; i++) {
if (a[i] == 1 || a[i] == 4 || a[i] == 6 || a[i] == 8 || a[i] == 9) {
ok = 1;
printf("1\n%d\n", a[i]);
break;
}
}
if (ok) continue;
for (int i = 1; i <= n; i++) {
if (a[i] == 2) {
for (int j = i + 1; j <= n; j++)
if (a[j] == 2 || a[j] == 5 || a[j] == 7) {
ok = 1;
printf("2\n%d%d\n", a[i], a[j]);
break;
}
if (ok) break;
} else if (a[i] == 3) {
for (int j = i + 1; j <= n; j++)
if (a[j] == 2 || a[j] == 5 || a[j] == 3) {
ok = 1;
printf("2\n%d%d\n", a[i], a[j]);
break;
}
if (ok) break;
} else if (a[i] == 5) {
for (int j = i + 1; j <= n; j++)
if (a[j] == 2 || a[j] == 5 || a[j] == 7) {
ok = 1;
printf("2\n%d%d\n", a[i], a[j]);
break;
}
if (ok) break;
} else if (a[i] == 7) {
for (int j = i + 1; j <= n; j++)
if (a[j] == 2 || a[j] == 5 || a[j] == 7) {
ok = 1;
printf("2\n%d%d\n", a[i], a[j]);
break;
}
if (ok) break;
}
}
if (ok) continue;
// assert(0);
}
C
给出一个长度为\(n\)的\(01\)串，找两个区间长度\(\geq \lfloor \frac{n}{2} \rfloor\)的不完全相同的区间\([l_1, r_1]\)和\([l_2, r_2]\)满足\(f(l_1 : r_1)\)是\(f(l_2, r_2)\)的若干倍，倍数不可以是\(0\)，其中\(f(l : r)\)表示从\(l\)位到\(r\)位的\(01\)构成的二进制数的大小，可以有前导\(0\)。
第一想法是在靠近结尾的位置找个\(0\)，假设\(0\)的位置是\(p\)，那么\([1, p], [1, p - 1]\)就是一个合法的答案；然后发现\(0\)放在开头也没有影响，如果\(p \leq \frac{(n + 1)}{2}\)，那么\([p, n], [p + 1, n]\)也是合法的答案；最后就是找不到\(0\)的全\(1\)串，只要输出\([1, mid], [mid + 1, n]\)就可以了。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pin;
#ifndef ONLINE_JUDGE
bool MEMORY_ST;
#endif
const int N = 2e4 + 5;
const ll P = 998244353LL;
int T, n;
char s[N];
inline int get() {
for (int i = 1; i <= n; i++)
if (s[i] == ‘0‘)
return i;
return 0;
}
#ifndef ONLINE_JUDGE
bool MEMORY_ED;
#endif
int main() {
#ifndef ONLINE_JUDGE
freopen("sample.in", "r", stdin);
clock_t st_clock = clock();
#endif
scanf("%d", &T);
for (; T--; ) {
scanf("%d", &n);
scanf("%s", s + 1);
int p = get();
if (p == 0) {
int mid;
if (n & 1) {
mid = (n + 1) / 2;
printf("%d %d %d %d\n", 1, mid - 1, mid + 1, n);
} else {
mid = n / 2;
printf("%d %d %d %d\n", 1, mid, mid + 1, n);
}
} else {
int mid;
if (n & 1) {
mid = (n + 1) / 2;
if (p <= mid) printf("%d %d %d %d\n", p, n, p + 1, n);
else printf("%d %d %d %d\n", 1, p, 1, p - 1);
} else {
mid = n / 2;
if (p <= mid) printf("%d %d %d %d\n", p, n, p + 1, n);
else printf("%d %d %d %d\n", 1, p, 1, p - 1);
}
}
}
#ifndef ONLINE_JUDGE
clock_t ed_clock = clock();
printf("time = %f ms\n", (double)(ed_clock - st_clock) / CLOCKS_PER_SEC * 1000);
printf("memory = %.2f MB\n", (&MEMORY_ED - &MEMORY_ST) / 1024.0 / 1024.0);
#endif
return 0;
}