\(\color{#FFC116}(1)\) CF1400D Zigzags
给出 \(n\) 个数 \(a_1,a_2,\cdots,a_n\)。求问有多少个四元组 \((i,j,k,l)\)，使得这个四元组满足下列条件：
- \(1 \leq i<j<k<l \leq n\)；
- \(a_i=a_k\) 并且 \(a_j=a_l\)。
\(a_i \le n \le 3000\)。
显然可以枚举 \(j, k\)，所以此时 \(a_j, a_k\) 为定值。那么 \(i\) 必须要满足 \(i < j\) 且 \(a_i = a_k\)，\(l\) 必须要满足 \(l > k\) 且 \(a_l = a_j\)。所以我们要做的就是统计一段区间内某个数字的出现次数。
套路。用 vector 存储每个数字出现的位置，那么每次查询相当于是问某个 vector 中有多少数在 \([l, r]\) 范围内。二分即可。
$\color{blue}\text{Code}$
vector<int> mp[N];
int calc(int l, int r, int x) {
if (!mp[x].size()) return 0;
return upper_bound(mp[x].begin(), mp[x].end(), r) - lower_bound(mp[x].begin(), mp[x].end(), l);
}
void Luogu_UID_748509() {
fin >> n;
for (int i = 1; i <= n; ++ i ) {
fin >> a[i];
mp[a[i]].push_back(i);
}
res = 0;
for (int j = 2; j < n; ++ j )
for (int k = j + 1; k < n; ++ k )
res += calc(1, j - 1, a[k]) * 1.0 * calc(k + 1, n, a[j]);
fout << res << '\n';
for (int i = 1; i <= n; ++ i ) mp[i].clear();
}
\(\color{#52A41A} (2)\) CF1327E Count The Blocks
- 对于一个数 \(t\)，定义一个块是 \(t\) 中的连续相等的一串数字。写下 \(0\cdots10^n-1\) 的所有数，不足 \(n\) 位的用前导 \(0\) 补足 \(n\) 位。对于每个 \(i=1\cdots n\)，求这 \(10^n\) 个数中一共有多少个长为 \(i\) 的块。
- \(n \le 2 \times 10^5\)。
首先发现 \(10^n\) 个数是假的，你可以将其看作是有 \(n\) 个位置，每个位置可以填 \(0 \sim 9\) 的数字。
显然枚举题中的 \(i\)。分析这 \(n\) 个数字：
-
有连续的 \(i\) 个数字是相同的，也就是说有 \(10\) 种取值；
-
这个长度为 \(i\) 的块的左边的位置（可能不存在）不能填这个数字，即有 \(9\) 种取值；
-
这个长度为 \(i\) 的块的右边的位置（可能不存在）不能填这个数字，即有 \(9\) 种取值；
-
其余的位置任意填，即每个位置都有 \(10\) 种取值。
然后乘法原理即可。
$\color{blue}\text{Code}$
void Luogu_UID_748509() {
fin >> n;
for (int i = 1; i < n; ++ i ) {
fout << 10ll * ((n - i - 1) * 81ll % P * fpm(10, n - i - 2) % P + 18ll * fpm(10, n - i - 1) % P) % P << ' ';
}
puts("10");
}
\(\color{#52A41A}(3)\) CF1545B AquaMoon and Chess
有一个 \(1 \times n\) 的棋盘。有的格子上有棋子。你可以选择一个有棋子的位置 \(i\)，并进行以下操作：
- 如果 \(i+2 \leq n\) 和 \((i+1)\) 上有棋子，且 \((i+2)\) 上没有棋子，将棋子移动到 \((i + 2)\)；
- 如果 \(i-2 \ge 1\) 和 \((i-1)\) 上有棋子，且 \((i-2)\) 上没有棋子，将棋子移动到 \((i - 2)\)；
求最终局面数。
\(n \le 10^5\)。
首先发现棋子的移动可以看作是 \([\texttt{1 1}]\) 的移动。例如：
\[\begin{matrix} 0&\color{red}[1&\color{red}1]&0&1\end{matrix} \Longrightarrow \begin{matrix} 0&0&\color{red}[1&\color{red}1]&1\end{matrix} \]但是还会有一些剩余的 \([\texttt{1}]\)，例如：
\[\begin{matrix} \color{red}[1&\color{red}1]&\color{blue}1&0&1\end{matrix} \Longrightarrow \begin{matrix} \color{blue}1&\color{red}[1&\color{red}1]&0&1 \end{matrix} \Longrightarrow \begin{matrix} \color{blue}1&0&\color{red}[1&\color{red}1]&1 \end{matrix} \]发现这个单独的 \([\texttt{1}]\) 的位置是可以随 \([\texttt{1 1}]\) 而唯一确定的。所以我们只需要考虑 \([\texttt{1 1}]\)。
设有 \(a\) 个 \([\texttt{1 1}]\)（也就是有 \(2a\) 个数），\(b\) 个剩余的 \([\texttt1]\)，那么答案为 \(\dbinom{n-a-b}a\)，表示将这 \(a\) 个 \([\texttt{1 1}]\) 随便放。
$\color{blue}\text{Code}$
void Luogu_UID_748509() {
scanf("%d%s", &n, s + 1);
int a = 0, b = 0;
for (int i = 1; i <= n; ++ i ) {
if (i < n && s[i] == '1' && s[i + 1] == '1') {
++ a;
++ i;
}
else if (s[i] == '1') {
++ b;
}
}
fout << C(n - a - b, a) << '\n';
}
\(\color{#9D3DCF}(4)\) CF1245F Daniel and Spring Cleaning
- 给定 \(l, r\)，求 \(\sum_{i=l}^r \sum_{j=l}^r [i+j = i \operatorname{xor} j]\)。
- \(r \le 10^9\)。
因为异或是不进位加法，所以只要 \(i, j\) 进行加法时不进位，就一定有 \(i+j = i \operatorname{xor} j\)。换言之，\(i \operatorname{and} j = 0\) 和 \(i+j = i \operatorname{xor} j\) 是等价的。
所以所求即 \(\sum_{i=l}^r \sum_{j=l}^r [i \operatorname{and} j = 0]\)。
设 \(f(x, y) = \sum_{i=\color{red}1}^x \sum_{j=\color{red}1}^y [i \operatorname{and} j = 0]\)。那么所求即 \(f(r, r) - f(r, l - 1) - f(l - 1, r) + f(l - 1, l - 1)\)。\(f(x, y)\) 的求解是简单数位 DP。
$\color{blue}\text{Code}$
int a[50], b[50], len;
int f[50][2][2];
int dp(int u, bool sb, bool bs) {
if (!u) return 1;
int& res = f[u][sb][bs];
if (~res) return res;
res = 0;
int t1 = sb ? a[u] : 1;
int t2 = bs ? b[u] : 1;
for (int i = 0; i <= t1; ++ i )
for (int j = 0; j <= t2; ++ j )
if (!i || !j) res += dp(u - 1, sb && (i == t1), bs && (j == t2));
return res;
}
int calc(int x, int y) {
if (x < 0 || y < 0) return 0;
memset(f, -1, sizeof f);
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
int l = 0;
while (x) {
a[ ++ l] = x & 1;
x >>= 1;
}
len = l, l = 0;
while (y) {
b[ ++ l] = y & 1;
y >>= 1;
}
len = max(len, l);
int res = dp(len, 1, 1);
return dp(len, 1, 1);
}
void Luogu_UID_748509() {
int l, r;
fin >> l >> r;
fout << (calc(l - 1, l - 1) + calc(r, r)) - (calc(l - 1, r) + calc(r, l - 1)) << '\n';
}
\(\color{#52A41A}(5)\) CF1444B Divide and Sum
- 给一个长度为 \(2n\) 的数列 \(a\)，将 \(a\) 中的数分为两串长度为 \(n\) 的数列 \(p\) 和 \(q\)。将 \(p\) 升序排序，\(q\) 降序排序。定义权值为 \(\sum_{i=1}^n |p_i - q_i|\)。求所有划分的权值和。
- \(n \le 1.5 \times 10^5\)。
首先每种划分的方案都是一定的，为 \(\sum_{v \in S_1} v - \sum_{v \in S_2} v\)。其中 \(S_1\) 表示 \(a\) 的前 \(n\) 大的数构成的集合，\(S_2\) 表示 \(a\) 的前 \(n\) 小的数构成的集合。
那么答案为 \(\dbinom {2n}n \cdot \sum_{v \in S_1} v - \sum_{v \in S_2} v\)。
首先 \(\sum |p_i - q_i| = \sum (\max (p_i,q_i) - \min(p_i, q_i))\)，而且可以证明 \(\max (p_i,q_i) \in S_1\) 以及 \(\min(p_i, q_i) \in S_2\)。
考虑反证：
- 如果 \(\max (p_i,q_i), \min(p_i, q_i) \in S_1\)，那么一定存在某个 \(j\) 使得 \(\max (p_j, q_j), \min(p_j, q_j) \in S_2\)。那么此时 \(i < j\) 或 \(i > j\) 都不能满足「\(p\) 升序排序，\(q\) 降序排序」这个条件。
- 如果 \(\max (p_i,q_i), \min(p_i, q_i) \in S_2\)，那么一定存在某个 \(j\) 使得 \(\max (p_j, q_j), \min(p_j, q_j) \in S_1\)。那么此时 \(i < j\) 或 \(i > j\) 都不能满足「\(p\) 升序排序，\(q\) 降序排序」这个条件。
$\color{blue}\text{Code}$
void Luogu_UID_748509() {
fin >> n;
for (int i = 1; i <= n * 2; ++ i ) fin >> a[i];
sort(a + 1, a + n * 2 + 1);
int res = 0;
for (int i = 1; i <= n; ++ i ) (res += a[i + n] - a[i]) %= P;
fout << (ll)res * C(2 * n, n) % P << '\n';
}