A - Chompers
- 预估难度：
入门 - 标签：字符串
题意
给定一个由小写英文字母组成的字符串 \(S\) 以及一个正整数 \(N\)。字符串 \(S\) 的长度至少为 \(2N+1\)。
请删除 \(S\) 的开头的 \(N\) 个字符以及末尾的 \(N\) 个字符，将剩余字符串输出。
代码
void solve()
{string s;int n;cin >> s >> n;cout << s.substr(n, s.size() - 2 * n);
}
B - Count Adjacent Cells
- 预估难度：
入门 - 标签：枚举
题意
有一张 \(H\) 行 \(W\) 列的网格图。从上往下数第 \(i\) 行、从左往右数第 \(j\) 列的单元格记作单元格 \((i, j)\)。
当 \(|x_1 - x_2| + |y_1 - y_2| = 1\) 时，称单元格 \((x_1, y_1)\) 和 \((x_2, y_2)\) 是边相邻的。
请对每一个单元格，求出与其边相邻的单元格的数量。
思路
枚举每个单元格，然后判断上下左右四个单元格中有多少个位于网格内部。
代码
int n, m;// 检查坐标 (x, y) 是否在地图内
bool check(int x, int y)
{return x >= 1 && x <= n && y >= 1 && y <= m;
}void solve()
{cin >> n >> m;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cout << check(i - 1, j) +check(i + 1, j) +check(i, j - 1) +check(i, j + 1) << " ";}cout << "\n";}
}
C - C Stands for Center
- 预估难度：
普及- - 标签：枚举
题意
给定一个由大写英文字母组成的字符串 \(S\)。
请统计 \(S\) 中有多少子串（连续子序列）满足以下两个条件：
- 字符串的长度为奇数。
- 字符串正中间的字符是
C。
即使两个子串作为字符串是完全相同的，但只要它们来自原字符串的不同的位置，就可以被分别计数。
思路
由于 C 位于正中间，且字符串长度是奇数，说明字符 C 左右两侧的字符个数相同。
假设字符串下标在 \([0, n-1]\) 范围内，且此时有个字符 C 位于下标 \(p\) 位置，那么以这个 C 作为中点的字符串下标区间应当可以描述为 \([p-k, p+k]\)，其中 \(k\) 满足：
- \(k \ge 0\)
- \(p-k \ge 0\)，即 \(k \le p\)
- \(p + k \lt n\)，即 \(k \lt n - p\)
因此 \(k\) 的取值范围为 \(0 \le k \le \min(p, n-p-1)\)，共 \(\min(p, n-p-1)+1\) 种。
于是我们便可以通过遍历来找出字符串中每一个字符 C 的下标位置，即可直接计算答案。
时间复杂度 \(O(|S|)\)。
代码
void solve()
{string s;cin >> s;int n = s.size();long long ans = 0;for(int i = 0; i < n; i++)if(s[i] == 'C')ans += min(i, n - i - 1) + 1;cout << ans;
}
D - Chalkboard Median
- 预估难度：
普及/提高- - 标签：对顶堆
题意
黑板上写着一个整数 \(X\)。
你需要按顺序处理 \(Q\) 次操作。第 \(i\) 次操作如下所示：
给定两个整数 \(A_i\) 和 \(B_i\)，将这两个新的整数写在黑板上。
然后，输出此时黑板上所有 \(2i+1\) 个整数的中位数。
思路
对顶堆数据结构模板题，具体可参考习题“中位数”。
我们可以假设目前的 \(2i+1\) 个整数已排序，并将排序后的数组分为左右两部分，左边包含 \(i\) 个数，右边包含 \(i+1\) 个数。
接下来使用一个大根堆，维护左边的 \(i\) 个数，堆顶朝右；再使用一个小根堆，维护右边的 \(i+1\) 个数，堆顶朝左。
于是我们便可以方便地借助这两个堆，将整个数组从中间“折断”，通过保证以下两个条件成立，来控制折断的位置一定在中位数旁：
- 两个堆的大小差值不能超过 \(1\)
- 要么两个堆具有相同数量的数字，要么控制右边的堆内数字数量比左边的堆多 \(1\)。
- 左边的大根堆内所有数字 \(\le\) 右边的小根堆内所有数字
- 也就是控制让两个堆能够形象地维护一个有序数组。
- 由于堆已自动排序，因此该条件也可以当作是让 左侧堆顶 \(\le\) 右侧堆顶
对于维护方法，由于每次会给定两个新数字，刚好可以给左边右边两个堆各一个，以保证上面的第一个条件成立。
接下来对于上面第二个条件，只要发现左侧堆顶 \(\gt\) 右侧堆顶，表示此时两个堆还没维护出一个有序数组，此时需要将两堆的堆顶进行交换，来让小的数字能到左半段去，大的数字到右半段去。
由于每次添加数字要么不会打乱数组的有序性，要么最多只会打乱一次，因此交换操作的执行次数最大只会在 \(O(Q)\) 的级别。
时间复杂度 \(O(Q\log Q)\)。
代码
priority_queue<int> ql; // 左侧大根堆
priority_queue<int, vector<int>, greater<int>> qr; // 右侧小根堆void balance()
{while(ql.top() > qr.top()) // 如果左侧堆顶 > 右侧堆顶，则交换两堆顶{int a = ql.top();int b = qr.top();ql.pop();qr.pop();ql.push(b);qr.push(a);}
}void solve()
{int x;cin >> x;qr.push(x);int q;cin >> q;while(q--){cin >> x;ql.push(x);cin >> x;qr.push(x);// 左右两个堆各放一个，保持数量平衡balance(); // 通过交换两堆堆顶，使 左边堆内最大值 <= 右边堆内最小值cout << qr.top() << "\n";}
}
E - Count 123
- 预估难度：
普及+/提高 - 标签：组合数学
题意
求满足以下条件的长度为 \(X_1+X_2+X_3\) 的序列 \(A = (a_1, \cdots, a_{X_1 + X_2 + X_3})\) 的数量。
- \(A\) 中恰好包含 \(X_1\) 个 \(1\)，\(X_2\) 个 \(2\)，以及 \(X_3\) 个 \(3\)。
- 相邻元素的差值绝对值至多为 \(1\)。
结果对 \(998244353\) 取模。
思路
根据题意，相邻元素差值绝对值必须 \(\le 1\)，换句话说就是数字 \(1\) 和 \(3\) 不能相邻。那么数字 \(2\) 便成为了最特殊的数字，因为 \(2\) 与其它两种数字均可相邻。
于是我们可以选择把 \(2\) 当作挡板，先把所有 \(2\) 摆成一排，总共形成了 \(X_2+1\) 个空位（包括首尾）。
每个空位只能够填 \(1\) 或者 \(3\) 的其中一种数字，且一个空位里可以放多个相同的数字，当然也可以不放任何数字。
接下来，我们假设要从中选出 \(i\) 个空位专门放 \(1\)，空位的选取方案数为 \(C_{X_2+1}^{i}\)。在选出这些空位后，需要将 \(X_1\) 个 \(1\) 分成 \(i\) 份填入空位，这里可以采取隔板法，从 \(X_1-1\) 个空隙中选出 \(i-1\) 个放置隔板，填空方案数为 \(C_{X_1 - 1}^{i-1}\)。
同理，在放完 \(1\) 后，可以假设在剩余的 \(X_2+1-i\) 个空位中再选 \(j\) 个空位专门放 \(3\)，同上，空位选取方案数为 \(C_{X_2+1-i}^j\)，填空方案数为 \(C_{X_3-1}^{j-1}\)。
至此，序列方案总数可以通过 \(\displaystyle\sum_{i=1}^{X_2 + 1} \sum_{j=1}^{X_2+1-i} C_{X_2+1}^{i}C_{X_1 - 1}^{i-1}C_{X_2+1-i}^jC_{X_3-1}^{j-1}\) 求得。
考虑化简公式：
考虑内层公式。
令 \(A = X_2+1-i\)，\(B = X_3 - 1\)，那么内层公式可以看作：
根据组合数 \(C_n^m = C_n^{n-m}\)：
根据范德蒙德恒等式 \(\displaystyle\sum_{i=0}^k C_n^iC_m^{k-i} = C_{n+m}^k\)：
回到原式，则原式等于：
公式求解过程时间复杂度 \(O(|X_2|)\)。
代码
typedef long long ll;ll fac[2000050];
ll inv[2000050];ll qpow(ll a, ll n)
{ll r = 1;while(n){if(n & 1)r = r * a % mod;a = a * a % mod;n >>= 1;}return r;
}void init()
{fac[0] = 1;for(int i = 1; i <= 2000000; i++)fac[i] = fac[i - 1] * i % mod;inv[2000000] = qpow(fac[2000000], mod - 2);for(int i = 1999999; i >= 0; i--)inv[i] = inv[i + 1] * (i + 1) % mod;
}ll getC(int n, int m)
{if(n - m < 0)return 0;return fac[n] * inv[m] % mod * inv[n - m] % mod;
}void solve()
{init();int X1, X2, X3;cin >> X1 >> X2 >> X3;long long ans = 0;for(int i = 1; i <= X2 + 1; i++){ans += getC(X2 + 1, i) * getC(X1 - 1, i - 1) % mod * getC(X2 + X3 - i, X2 - i) % mod;ans %= mod;}cout << ans;
}