《蒸汽鸟报》记者夏洛蒂，堂堂登场！
感觉夏洛蒂就一纯纯工具人，剧情开端之友。可怜滴捏！
A. 学习求余
http://222.180.160.110:1024/contest/4272/problem/1
今天我们来学习求余！这种题放普及 T1 不合适吧！
令 \(k=\left\lfloor \dfrac n2 \right\rfloor + 1\)，直接输出 \(k\times (n - k)\) 即可。
我是不是证复杂了…
我们可以简单地发现一个道理，对于任意 \(\dfrac n2<x\le n\)，\(n\bmod x\) 的值是 \(n - x\)；
根据基本不等式（王金山直接感动得哭出声来）或小学知识「和不变，差小积大」，我们可以知道当 \(x=\left\lfloor \dfrac n2 \right\rfloor + 1\) 时，\(x\times (n-x)\) 取最大值。
故有：当 \(x=\left\lfloor \dfrac n2 \right\rfloor + 1\) 时，\(x\times (n\bmod x)\) 取最大值。
而对于 \(y\le \dfrac n2\)，由余数小于除数得，\(n\bmod y<y\le \dfrac n2\)。由于 \(0<y<x=\left\lfloor \dfrac n2 \right\rfloor + 1\) 且 \(0\le n\bmod y\le \left\lfloor \dfrac n2 \right\rfloor - 1\le n - \left\lfloor \dfrac n2 \right\rfloor - 1=n\bmod x\)，由不等式的基本性质得 \(x\times(n\bmod x)>y\times (n\bmod y)\)。
综上，对于 \(1\le x\le n\)，当 \(x=\left\lfloor \dfrac n2 \right\rfloor + 1\) 时，\(x\times (n\bmod x)\) 有最大值。
然后如果你要问我怎么发现这一点的呢，我当时没有思路，然后随手输出了 \(n=100\) 时 \(n\bmod i\) 的所有值。然后发现 \(k=51\) 时余数是 \(49\)…… 然后就会了。
#define int long long
namespace XSC062 {
using namespace fastIO;
int n, k;
int main() {
read(n), k = n / 2 + 1;
print(k * (n % k));
return 0;
}
} // namespace XSC062
#undef int
头一次在题解里贴这么短的代码
B. 提取数字
http://222.180.160.110:1024/contest/4272/problem/2
我被这道题（疑似 T1）坑到了！交了三遍才过！这合理吗？
首先要开 long long！然后注意，你的判定条件应为「当前是否已存储数」而非「当前存数变量是否为 0」！因为数据中会有单个 0 的情况出现！
然后就没有了。
#define int long long
namespace XSC062 {
using namespace fastIO;
const int maxn = 1e5 + 5;
bool flag;
char s[maxn];
int n, ans, cnt;
int main() {
scanf("%*s %s", s + 1);
n = strlen(s + 1);
for (int i = 1; i <= n; ++i) {
if (s[i] >= '0' && s[i] <= '9')
cnt = cnt * 10 + s[i] - '0', flag = 1;
else if (flag)
ans += (cnt + 5), cnt = 0, flag = 0;
}
if (flag) ans += (cnt + 5);
print(ans, '\n');
return 0;
}
} // namespace XSC062
#undef int
C. 武器选择
http://222.180.160.110:1024/contest/4272/problem/3
首先是我想了半个小时的狂拽酷炫吊炸天的法一：离线
我当时一边打一边怀疑现在的普及组是什么神仙，T3 考这么神奇的离线，难道是我落后于时代了？
（之所以认为这是 T3 是因为括号那道题确实是正常 T4 风格）
我们预处理出对于每一个可能获得武器 \(i\) 的位置，应该从哪个位置第一次捡到武器 \(i\)，由于这一段内的所有武器 \(i\) 都需要被拾取，我们将其作为区间 \([L_i, R_i]\) 来记录。
那么询问可以转化为，在 \([l, r]\) 内 不同颜色 \([L_i, R_i]\) 的数量。
考虑将询问离线。将询问按左端点从大到小排序，信息区间 \([L_i, R_i]\) 也按左端点从大到小排序。
对于每次询问 \(l, r\)，在树状数组中将被 \([l, n]\) 完全包含的所有 \([L_i, R_i]\)（其实就是 \(l\le L_i\) 的所有 \(L_i\)）在右端点 \(R_i\) 处加一，我们就统计到了可以捡到武器的所有位置。
怎么区分颜色呢？很简单，我们让每个颜色只被算一次。算哪一次呢？就算当前已加入的 \([L_i, R_i]\) 内，比选中概率最大的一次。
我们树状数组统计的是 \([1, r]\) 内的值，所以我们要让概率最大的话，就要让 \(R_i\) 尽量的小。
我们记录每个颜色当前合法 \([L_i, R_i]\) 的最小右端点 \(\min_R\)。加入一个新的 \([L_i, R_i]\) 时，如果 \(R_i\ge \min_R\)，那么不会产生影响，跳过；否则，当 \(R_i<\min_R\) 时，我们就要先消除当前 \(\min_R\) 的影响（即在树状数组中将该位置加上的 1 减去），再加上 \(R_i\) 的影响（即在树状数组中加上该位置的 1）。
此时我们对 \([1, r]\) 的询问就是答案。
复杂度 \(\mathcal O(n\log n + m\log m + m\log n)\)，其中 \(n\log n\) 来自于对 \([L_i, R_i]\) 的排序，\(m\log m\) 来自于对询问的排序，\(m\log n\) 来自于离线树状数组。
接下来讲题解给的正解…… 这个是真的妙。
考虑所有种类数，在 \(n\) 个数内满足条件的种类 \(x\) 最优条件下也不过 \(\dfrac {x\times (x+1)}2=n\)，所以满足条件武器的数量最多只有 \(\sqrt n\) 级别。
所以我们对所有合法种类做前缀和，每次询问检查所有合法种类是否在该区间内出现对应次数，然后统计答案。复杂度 \(\mathcal O(m\sqrt n + n\sqrt n)\)。\(n\sqrt n\) 是前面前缀和来的，\(m\sqrt n\) 是暴力统计来的。
但是根号可耻，所以我的法一更 NB！！！???
狂拽酷炫吊炸天的法一代码
#define int long long
namespace XSC062 {
using namespace fastIO;
const int maxn = 1e5 + 5;
struct _ {
int l, r, k, i;
bool operator< (const _ &q) const {
return l < q.l;
}
};
struct __ {
int l, r, nxt, x;
bool operator< (const __ &q) const {
return l < q.l;
}
};
_ q[maxn];
__ a[maxn];
std::map<int, int> t;
std::vector<int> u[maxn];
int ans[maxn], now[maxn];
int mnr[maxn], Bit[maxn];
int n, m, tot, x, cnt, pos;
int lowbit(int x) {
return x & -x;
}
void add(int x, int v) {
for (int i = x; i <= n; i += lowbit(i))
Bit[i] += v;
return;
}
int ask(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i))
res += Bit[i];
return res;
}
int calc(int x, int k) {
int res = 1;
for (int i = 1; i <= k; ++i)
res *= x--;
for (int i = 1; i <= k; ++i)
res /= i;
return res;
}
int main() {
read(n);
for (int i = 1; i <= n; ++i) {
read(x);
if (!t.count(x))
t[x] = ++tot;
int id = t[x];
u[id].push_back(i);
if ((int)u[id].size() >= x) {
a[++cnt].l =
u[id][(int)u[id].size() - x];
a[cnt].r = i, a[now[id]].nxt = cnt;
a[cnt].x = x, mnr[x] = n + 1;
now[id] = cnt;
}
}
read(m);
for (int i = 1; i <= m; ++i) {
read(q[i].l), read(q[i].r);
read(q[i].k), q[i].i = i;
}
std::sort(q + 1, q + m + 1);
std::sort(a + 1, a + cnt + 1);
pos = cnt;
for (int i = m; i; --i) {
while (a[pos].l >= q[i].l) {
if (a[pos].r < mnr[a[pos].x]) {
if (mnr[a[pos].x] <= n)
add(mnr[a[pos].x], -1);
add(a[pos].r, 1);
mnr[a[pos].x] = a[pos].r;
}
--pos;
}
ans[q[i].i] = calc(ask(q[i].r), q[i].k);
}
for (int i = 1; i <= m; ++i)
print(ans[i], '\n');
return 0;
}
} // namespace XSC062
#undef int
我甚至打完了就过了样例然后直接就 A 了，好久没有这么爽地过过这种大码量 正确性还未知 的题了。
而且我相信全场只有我一个 小丑 帅哥打离线，所以我是最强的！！！???
绝对不如法一的法二代码
#define int long long
namespace XSC062 {
using namespace fastIO;
const int maxm = 505;
const int maxn = 1e5 + 5;
int a[maxn];
int cnt[maxn];
int sum[maxm][maxn];
int n, tot, m, l, r, k, res;
int calc(int x, int k) {
int res = 1;
for (int i = 1; i <= k; ++i)
res *= x--;
for (int i = 1; i <= k; ++i)
res /= i;
return res;
}
int main() {
read(n);
for (int i = 1; i <= n; ++i) {
read(a[i]);
if (a[i] <= n) ++cnt[a[i]];
}
for (int i = 1; i <= n; ++i) {
if (cnt[i] >= i) {
sum[++tot][n + 1] = i;
for (int j = 1; j <= n; ++j) {
sum[tot][j] = sum[tot][j - 1] +
(a[j] == i);
}
}
}
read(m);
while (m--) {
read(l), read(r), read(k);
res = 0;
for (int i = 1; i <= tot; ++i) {
res += (sum[i][r] - sum[i][l - 1]
>= sum[i][n + 1]);
}
print(calc(res, k), '\n');
}
return 0;
}
} // namespace XSC062
#undef int
D. 括号序列
http://222.180.160.110:1024/contest/4272/problem/4
呃呃呃，这，有什么好讲的吗？做过原题的应该都会吧……
反正就是个比较裸的区间 DP，转移的时候注意一下究竟哪些是同一对括号，哪些是相邻括号就好。
复杂度 \(\mathcal O(n^2)\)。
namespace XSC062 {
using namespace fastIO;
const int maxn = 1e3 + 5;
int n, res;
char s[maxn];
std::stack<int> t;
int mat[maxn], c[5];
int f[maxn][maxn][3][3];
int max(int x, int y) {
return x > y ? x : y;
}
void upd(int &x, int y) {
x = max(x, y);
return;
}
int main() {
memset(f, -0x3f, sizeof (f));
scanf("%d %d %d", &n, &c[1], &c[2]);
scanf("%s", s + 1);
for (int i = 1; i <= n; ++i) {
if (s[i] == '(')
t.push(i);
else mat[t.top()] = i, t.pop();
}
for (int i = 1; i <= n; ++i) {
if (mat[i] == i + 1) {
for (int k = 0; k <= 2; ++k)
f[i][i + 1][k][k] = c[k];
}
}
for (int l = 4; l <= n; l += 2) {
for (int i = 1; i <= n - l + 1; ++i) {
int j = i + l - 1;
if (mat[i] == j) {
// ((...))
// xy...zx
for (int x = 0; x <= 2; ++x) {
for (int y = 0; y <= 2; ++y) {
if (y == x) continue;
for (int z = 0; z <= 2; ++z) {
if (z == x) continue;
upd(f[i][j][x][x], f[i + 1][j - 1][y][z] + c[x]);
}
}
}
}
else {
// ()(...)
// xxy...z
for (int x = 0; x <= 2; ++x) {
for (int y = 0; y <= 2; ++y) {
if (y == x) continue;
for (int z = 0; z <= 2; ++z)
upd(f[i][j][x][z], f[i][mat[i]][x][x] + f[mat[i] + 1][j][y][z]);
}
}
}
}
}
for (int i = 0; i <= 2; ++i) {
for (int j = 0; j <= 2; ++j)
res = max(res, f[1][n][i][j]);
}
print(res, '\n');
return 0;
}
} // namespace XSC062
我之前看到有给散起名 Charlotte 然后被强制改名了的，虽然但是，这个名字给他真的好奇怪……