旅行传送门
A. The Miracle and the Sleeper
题意：给定两个整数 \(l\) 、\(r\) ：在所有整数对 \((a,b)\) 中找到 \(a\) \(mod\) \(b\) 的最大值，其中 \(l \leq a \leq b \leq r\) 。
题目分析：一开始写假了orz，考虑取模的性质，不难发现：如果 $ \frac{r}{2} $ + \(1 \geq l\) ，此时答案为 \(r\) \(mod\) $(\frac{r}{2} $ + \(1)\) ，否则答案为 \(r\) \(mod\) \(l\) 。
AC代码：
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
const int maxn = 1e9 + 5;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch))
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
int main(int argc, char const *argv[])
{
int T = read();
while (T--)
{
int a = read(), b = read();
int tmp = b / 2 + 1;
if (tmp < a)
printf("%d\n", b % a);
else
printf("%d\n", b % tmp);
}
return 0;
}
B. Scenes From a Memory
题意：给你一个不含零的正整数 \(k\) ，问最多去掉多少位后，它才能变成一个非素数。
题目分析：比赛的时候猜了下最后删完剩下的位数应该不会大于 \(2\) ，然后瞎搞了下过了XD
嗯，经典先写后证了，由于题目保证必有解，我们不妨考虑什么情况下只会剩一位数字呢？答案很明显，即 \(n\) 中包含数字 \(1、4、6、8、9\) ，因为这五个数均为非素数。
那如果没有上述五个数，这时就要考虑两位数了，因为 \(k\) 的位数很少，我们直接暴力就好，可以证明，两位数符合情况的有：
- \(k\) 中存在两个相同的数（可被11整除）
- \(k\) 中存在数字 \(2\) 或 \(5\) ，且其不位于首位（即以 \(2\) 或 \(5\) 结尾的两位数）
如果上述情况都不符合，那么我们发现一个三位数的 \(k\) 必是 \(237、273、537、573\) 之一，不难看出它们均可组成一个被 \(3\) 整除的两位数。
AC代码：
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
using namespace std;
int vis[105], prime[105], cnt = 0;
void eulerSieve(int n)
{
rep(i, 2, n)
{
if (!vis[i])
prime[++cnt] = i;
rep(j, 1, cnt)
{
if (i * prime[j] > n)
break;
vis[i * prime[j]] = 1;
if (i % prime[j] == 0)
break;
}
}
}
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
cin.tie(0);
eulerSieve(100);
int T;
cin >> T;
while (T--)
{
int n, ans = 0;
cin >> n;
string s, t;
cin >> s;
rep(i, 0, n - 1)
{
int c = s[i] - '0';
if (c == 1 || c == 4 || c == 6 || c == 8 || c == 9)
ans = c;
if (ans)
break;
}
if (ans)
{
printf("%d\n%d\n", 1, ans);
continue;
}
rep(i, 0, n - 1)
{
rep(j, i + 1, n - 1)
{
t = s[i];
t += s[j];
if (vis[stoi(t)])
ans = stoi(t);
if (ans)
break;
}
if (ans)
break;
}
printf("%d\n%d\n", 2, ans);
}
return 0;
}
C. Rings
题意：给你一个长为 \(n\) 的二进制字符串，你可以从中截取不同区间且长度均 $ \geq \lfloor \frac{n}{2} \rfloor$ 的两段，但要保证这两段子串转换为十进制后成倍数关系，问应该截取哪两段？
题目分析：根据序列是否为非零序列，可以分为以下两种情况：
-
若序列中大于 \(\frac{n}{2}\) 的位置有 \(pos\) 出现过 \(0\) ，则截取的两段分别为 \([1,pos]\) 与 \([1,pos+1]\) ，小于 \(\frac{n}{2}\) 同理。
-
若序列为非零序列（即全由 \(1\) 组成），则截取的两段分别为 \([1,\lfloor \frac{n}{2} \rfloor]\) 与 \([1,2 \times \lfloor \frac{n}{2} \rfloor]\)
为什么这样取呢，因为若存在 \(0\) ，我们可以利用位移一位相乘/相除 \(2\) 的关系构造一组解，若不存在 \(0\) ，就截取 \(\lfloor \frac{n}{2} \rfloor\) 长度的 \(1\) 与 $ 2 \times \lfloor \frac{n}{2} \rfloor$ 长度的 \(1\) ，比如有这样一个序列：\(111111111\) ，我们可以截取 \(4\) 个 \(1\) 和 \(8\) 个 \(1\) ， \(8\) 个 \(1\) 可以看作是 \(4\) 个 \(1\) 左移四位再加上自己后得到，从而形成了倍数关系。
需要注意本题是向下取整，这点十分重要。
AC代码：
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
using namespace std;
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
cin.tie(0);
int T, n;
cin >> T;
while (T--)
{
string s;
cin >> n >> s;
int flag = 0, pos = 0;
rep(i, 0, n - 1) if (s[i] - '0' == 0)
{
flag = 1;
pos = i;
break;
}
if (flag)
if (pos >= n / 2)
printf("%d %d %d %d\n", 1, pos + 1, 1, pos);
else
printf("%d %d %d %d\n", pos + 1, n, pos + 2, n);
else
n <= 3 ? printf("%d %d %d %d\n", 1, n, 1, 1) : printf("%d %d %d %d\n", 1, n / 2 * 2, 1, n / 2);
}
return 0;
}
D1. Two Hundred Twenty One (easy version)
题意：给你一个由 \(+\) \(-\) 组成的字符串 \(s\) ， \(s[i]\) 为 \(+\) 代表 \(a_i\) 值为 \(1\) ， \(s[i]\) 为 \(-\) 代表 \(a_i\) 为 \(-1\) ，每次询问一个区间 \([l,r]\) ，问最少移除序列中多少个字符后，可以使得 \(a_l + a_{l+1} + ... + a_{r-1} + a_r\) 之和，即 \(\sum_{i=l}^ra_i\) 为 \(0\) ？
题目分析：这道题的分析用到了 \(dp\) 的思想，对于任意一段序列，不难发现最终答案只与它的区间和有关，与长度无关，对于奇数和的情况，我们一定能找到一个位置 \(i\) ，在保证 \(a_i\) 有贡献的情况下，使得 \([l,i]\) 与 \([i+1,r]\) 的值相差为1，这时候删去位置 \(i\) 的值，就能保证 \(i\) 前后序列之和大小相等、符号相反，此时的 \(cost\) 为 \(1\) ，当情况为偶数和的时候，其删去头尾之一即退化为奇数和，所以总 \(cost\) 是 \(2\) 。
什么叫有贡献呢？比如 + - + - （+ +） + - + 虽然 \(sum[4]\) 和 \(sum[6]\) 的前缀和相等，但中间括号括起来的两个 + 就属于没有贡献的值，因为这对 + 相互抵消了，所以我们要找的位置 \(i\) = \(4\) 。
其实再举个通俗点的例子：比如你区间符号和是 \(9\) ，然后你找一个区间符号和为 \(5\) 的位置， \(5\) 这一个位置就是因为存在 \(a_i\) 这个元素，使得原来是 \(4\) 的现在变成 \(5\) 了，它很碍事，所以我们拿掉它，那么之后的 \(4\) 个贡献现在被取反了，正好和前面相互抵消了 。
AC代码：
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
using namespace std;
const int maxn = 3e5 + 5;
string s;
int t, n, q, sum[maxn]; //sum为前缀和
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t;
while (t--)
{
cin >> n >> q >> s;
rep(i, 1, n) sum[i] = sum[i - 1] + (i & 1 ? (s[i - 1] == '+' ? 1 : -1) : (s[i - 1] == '+' ? -1 : 1));
int l, r;
rep(i, 1, q)
{
cin >> l >> r;
int res = sum[r] - sum[l - 1];
puts(res ? (res & 1 ? "1" : "2") : "0");
}
}
return 0;
}
D2. Two Hundred Twenty One (hard version)
题目分析：其实如果D1想明白了，D2就很简单了，根据之前的理论，我们只需要分析奇数和的情况就好了，开个数组记录下每个值的位置 \(pos\) ，设 \(res\) = \(sum[r] - sum[l-1]\) ，每次询问偶数和先化奇数和，然后奇数和就找询问区间内前缀和为 $ \frac{res}{2} + 1$ 出现的第一个位置就好了。
需要注意的是前缀和可能会出现负数的情况，因此我们不妨给所有的前缀和加上 \(n\) 后再进行操作。
AC代码：
#include <bits/stdc++.h>
#define rep(i, x, y) for (register int i = (x); i <= (y); i++)
#define down(i, x, y) for (register int i = (x); i >= (y); i--)
using namespace std;
const int maxn = 3e5 + 5;
string s;
int t, n, q, sum[maxn];
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> t;
while (t--)
{
cin >> n >> q >> s;
vector<vector<int>> pos(2 * n + 1);
//处理负数
pos[n].push_back(0);
sum[0] = n;
rep(i, 1, n) sum[i] = sum[i - 1] + (i & 1 ? (s[i - 1] == '+' ? 1 : -1) : (s[i - 1] == '+' ? -1 : 1)), pos[sum[i]].push_back(i);
int l, r, ans;
rep(i, 1, q)
{
cin >> l >> r;
int res = sum[r] - sum[l - 1];
if (!res)
cout << "0" << endl;
else if (abs(res) & 1)
{
cout << "1" << endl;
//根据区间和的正负性进行不同操作，不要漏掉之前的前缀和sum[l - 1]
//6 / 2 + 1 = 4, -6 / 2 - 1 = -4
int tmp = sum[l - 1] + (res > 0 ? res / 2 + 1 : res / 2 - 1);
cout << *lower_bound(pos[tmp].begin(), pos[tmp].end(), l) << endl;
}
else
{
cout << "2" << endl;
--r; //化为奇数和的情况
res = sum[r] - sum[l - 1];
int tmp = sum[l - 1] + (res > 0 ? res / 2 + 1 : res / 2 - 1);
cout << *lower_bound(pos[tmp].begin(), pos[tmp].end(), l) << " " << r + 1 << endl;
}
}
}
return 0;
}