简单：C,A
中等：E
难：B,D,F
C - Remove the Ends
首先要明白，在任何时候，我们都应该要么移除最左边的正数元素，要么移除最右边的负数元素。因为如果我们选取的不是最左边的正数元素，那么我们本可以先选取最左边的那个正数元素，这样能得到更高的分数；对于选取最右边的负数元素，也有类似的道理。
现在，如果你进行上述操作若干次，最终总会先取到一些正数构成的前缀，然后再取到剩余的由负数构成的后缀。所以，为了计算结果，我们只需要检查将数组分成前缀和后缀的所有 (n + 1) 种方式，然后从所有情况中取最大值，而这在 (O(n)) 的时间复杂度内很容易实现。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+4;
int f[N] = {0},z[N] = {0};
signed main(){
int T;
cin >> T;
while(T--){
int n;
cin >> n;
int a[n+5];
memset(f,0,sizeof(f)),memset(z,0,sizeof(z));
for(int i = 1;i <= n;i++){
cin >> a[i];
}
for(int i = 1;i <= n;i++){
z[i] = z[i-1];
if(a[i] > 0) z[i] += a[i];
// cout << z[i] << ' ';
}
// cout << '\n';
for(int i = n;i >= 1;i--){
f[i] = f[i+1];
if(a[i] < 0) f[i] += abs(a[i]);
}
int ans = 0;
for(int i = 1;i <= n;i++) ans = max(ans,z[i]+f[i]);
cout << ans << '\n';
}
}
A - Beautiful Sequence
让我们稍微修改一下优美序列的定义。我们可以证明，“除了第一个元素之外，对于每个元素，其左边都存在一个比它小的元素”这一条件，等价于“第一个元素比序列中的其他所有元素都小”。我们可以通过归纳法来证明这两个条件是等价的：
- 对于序列的第二个元素 (s_2)，其左边唯一的元素是第一个元素 (s_1)，所以 (s_1 < s_2)；
- 假设我们已经证明了，对于每个 (i \in [2, k])，都有 (s_1 < s_i)。现在让我们证明 (s_1 < s_{i + 1})。假设 (s_{i+1}) 左边比 (s_{i + 1}) 小的元素是 (s_j)；如果 (j = 1)，显然 (s_1 < s_{i + 1})；否则，(s_1 < s_j) 且 (s_j < s_{i + 1})，所以 (s_1 < s_{i + 1})。
使用类似的归纳法，我们可以证明“除了最后一个元素之外，对于每个元素，其右边都存在一个比它大的元素”，等同于“最后一个元素比序列中的其他所有元素都大”。
由于数组仅由 1、2 和 3 组成，我们可以注意到，只有一种可能的优美序列模式：122…223（即一个 1，接着任意数量的连续的 2，最后是一个 3 ）。任何其他模式都是无效的：最左边的元素应该严格小于中间的每个元素（从第二个元素到倒数第二个元素 ），最右边的元素应该严格大于中间的每个元素；所以，最左边的元素应该是 1，最右边的元素应该是 3，中间的每个元素都应该是 2。
为了计算符合上述模式的子序列的数量，我们可以使用动态规划。设 (dp_{i,j}) 为考虑数组的前 (i) 个元素，且当前状态为 (j) 时的子序列数量（例如，状态 0 表示序列为空，状态 1 表示我们已经选取了等于 1 的元素，状态 2 表示我们已经选取了若干个 2，状态 3 表示我们已经选取了元素 3 且序列已完成 ）。这个动态规划中的状态转移非常简单，每个状态的转移都可以在 (O(1)) 时间内完成。
所以，该解法的总时间复杂度是 (O(n))。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
signed main(){
int T;
cin >> T;
while(T--){
int n;
cin >> n;
vector<int> p(4,0);
p[0] = 1;
for(int i = 1;i <= n;i++){
int x;
cin >> x;
if(x == 2) p[x] += p[x],p[x] %= mod;
p[x] += p[x-1],p[x] %= mod;
}
cout << p[3] << '\n';
}
}
E - Devyatkino
思路一
答案不会超过 9，因为我们可以每次加上 9 并关注末位数字。每次加 9 时，末位数字会减 1（从 0 变到 9 ），所以经过 9 次加法操作后，末位数字会完成一个完整的循环，并且在这个过程中恰好会出现一次 7。
思路二
要简要说明像加上 99...99 这样的数会如何影响任意一个数的各个数位，是相当困难的。然而，存在一种在算术上类似的操作，即加上形如 (10^x) 的数，这种操作对数字的影响更容易预测。要是在运算中我们能加上 10 的幂次方，而不是 99...99 就好了。
将这两个思路结合起来就能解决这个问题。
我们来遍历答案的可能取值。对于从 0 到 9 的每个 (k)，我们想要确定：是否恰好加上 (k) 个由 9 组成的数就能得到数字 7 ？一种操作是加上形如 (10^x - 1) 的数。由于我们知道恰好要进行 (k) 次操作，我们可以把这个过程看作是给数字 (n - k) 加上 (k) 个 10 的幂次方。
加上一个 10 的幂次方会使这个数的某一个数位（包括前导 0 ）加 1 。它也可能会把某些 9 变成 0，这实际上在模 10 的意义下也是数位加 1 。因此，不难理解，要在一个数中得到数字 7 ，所需加上 10 的幂次方的最少次数，是对这个数的所有数位（包括前导 0 ）求 (\min((7 - \text{digit}) \bmod{10})) 。
总之，我们需要让 (k) 从 0 到 9 遍历，将 (k) 与 (\min((7 - \text{digit}) \bmod{10})) （其中 (\text{digit}) 是 (n - k) 的任意一个数位，包括前导 0 ）进行比较，然后输出合适的最小的 (k) 值。
有趣的是，在求解过程中可以清楚地看到，答案是 (\leq 7) ，因为 (\text{digit}) 总能取到 0 。然而，这只在 (n \geq 7) 的条件下成立，因为在求解过程中我们隐含地依赖于 (n - k) 不为负这一事实！当 (n = 5) 和 (n = 6) 时，答案实际上是 8 。
此外，上述解法也证明了另一种凭直觉就能想到的解法。假设在最优答案中，我们每次都加上同一个数，也就是说我们不会把加 9 和加 99 混合起来。基于这种假设，我们可以遍历所加的数，不断地加上它，直到得到数字 7 。然后从所有可能的情况中取最小值作为答案。
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
int T;
cin >> T;
while(T--){
int n;
cin >> n;
for(int i = 0;i <= 9;i++){
string s = to_string(n-i);
int ma = 0;
for(int j = 0;j < s.size();j++){
if(s[j] <= '7') ma = max(ma,(int)(s[j]-'0'));
}
if(i >= 7-ma) { cout << i << '\n';break;}
}
}
}
B - Palindrome Shuffle
我将给出一个时间复杂度为 (O(n \log n)) 的解法。通过精心实现双指针法，该问题也可以在 (O(n)) 的时间复杂度内解决，但在我看来，(O(n \log n)) 的解法更直观、更容易理解。
首先，当字符串的第一个字符和最后一个字符相等时，我们把这两个字符都去掉 —— 很明显，我们不应该去动它们。
在那之后，我们得到一个字符串，其第一个字符和最后一个字符不相等。它们中至少有一个需要被改变 —— 所以，我们需要重排的子串要么是字符串的前缀，要么是后缀。假设我们重排的是前缀（如果我们需要重排后缀，我们可以通过反转字符串，然后尝试重排反转后字符串的前缀来进行检查 ）。
假设通过重排长度为 (m) 的前缀，我们得到了答案。那么，通过重排长度为 (m + 1) 的前缀，我们也能够使字符串成为回文串。这意味着我们可以通过二分查找来找到需要重排的最短前缀长度。
在二分查找过程中，我们需要检查通过重排特定长度的前缀是否能使字符串成为回文串。我们可以通过验证以下两个条件，在 (O(n)) 的时间内进行检查：
- 对于每一对 ((s_i, s_{n - i + 1}))，如果 (s_i \neq s_{n - i + 1})，那么至少其中一个字符需要被改变，所以它应该属于前缀；
- 对于从 (a) 到 (z) 的每一个字符 (c)，我们来计算这样的字符对的数量，即这个字符需要同时填充这两个位置（也就是，在 ((s_i, s_{n - i + 1})) 对中，至少有一个字符等于 (c) 且不受我们重排操作影响的对数 ）。这个对数不应超过整个字符串中字符 (c) 的对数，否则我们就没有足够的字符 (c) 来填充所有这些位置对。
显然，这两个条件是必要的，但我们也可以证明它们是充分的：如果这两个条件都满足，我们就有足够的字符来填充所有需要特定字符的位置对，并且所有剩余的位置对都可以用任何剩余的字符对来填充（题目保证输入字符串中每个字符的数量都是偶数，所以总是可以将所有字符对分开 ）。
所以，我们需要检查某个子串是否是可能的答案，这个检查需要进行 (O(\log n)) 次，并且每次检查都可以在 (O(n)) 的时间内完成。因此，我们的解法的时间复杂度为 (O(n \log n))。
#include<bits/stdc++.h>
using namespace std;
string s;
int mi = LONG_MAX;
void js(int n){
int l = 0,r = n;
while(l <= r){
int m = (l+r)/2;
map<char,int> p;
for(int i = 0;i < m;i++) p[s[i]]++;
bool pd = true;
for(int i = 0;i < min(n/2,n-m);i++){
if(i < m){
if(p[s[n-i-1]]) p[s[n-i-1]]--;
else pd = false;
}
else{
if(s[i] != s[n-1-i]) pd = false;
}
if(!pd) break;
}
for(auto it:p) if(it.second % 2!=0) pd = false;
if(!pd) l = m+1;
else r = m-1;
}
mi = min(mi,r+1);
}
int main(){
int T;
cin >> T;
while(T--){
cin >> s;
int n = s.size(),t;
for(t = 0;t < n/2;t++) if(s[t] != s[n-t-1]) break;
n -= 2 * t;
s = s.substr(t,n);
// cout << s << '\n';
mi = n;
js(n);
reverse(s.begin(), s.end());
js(n);
cout << mi << '\n';
}
}
D - Eating
首先注意到，如果我们无法吃掉下一个史莱姆，那么这个史莱姆的最高有效位（most significant bit，简称msb ）至少要和当前 (x) 的值一样大。由此可知，如果一个史莱姆的最高有效位严格小于 (x)，我们总是可以吃掉它。
现在来看，如果我们吃掉一个最高有效位比 (x) 低的史莱姆，那么 (x) 的最高有效位永远不会减小；而如果我们吃掉一个最高有效位与 (x) 相等的史莱姆，那么 (x) 的最高有效位将会减小。这启发我们进行如下操作：
在任何时刻，我们都应该尽可能多地吃掉左边最高有效位较小的史莱姆（为了计算完成此操作后 (x) 的新值，我们可以进行诸如前缀和之类的范围异或查询）。在此之后，下一个史莱姆的最高有效位总是大于或等于 (x)，所以我们要么无法吃掉它，要么吃掉它后 (x) 的最高有效位会减小。由于每次操作后最高有效位总会减小，所以我们最多只需要进行 (\log(x)) 次这样的操作！
因此，我们应该尝试找到一种快速计算左边第一个最高有效位大于或等于当前 (x) 的最高有效位的史莱姆的方法。有很多方法可以做到这一点，但我认为最简洁的方法是使用前缀和。对于每一个 (i) 和 (j)，其中 (1 \leq i \leq n)，(1 \leq j \leq \log(W))（这里 (W) 是 (w_i) 和 (x) 的最大值 ），记录在此之前最高有效位大于或等于 (j) 的最大索引，我们将其记为 (\text{pre}_{i,j})。
现在我们可以按如下方式更新：
- 如果 (\text{msb}(w_i) < j)，那么 (\text{pre}{i,j} = \text{pre}{i - 1,j})
- 否则 (\text{pre}_{i,j} = i)
最终的时间复杂度是 (O((n + q)\log(W))) 。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int W = 30;
void solve(){
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int &x : a) cin >> x;
vector<int> pre(n + 1);
pre[0] = a[0];
for (int i = 1; i < n; i++){
pre[i] = pre[i - 1] ^a[i];
}
vector<array<int, W>> last(n);
for (int i = 0; i < n; i++){
fill(last[i].begin(), last[i].end(), 0);
if (i > 0) last[i] = last[i - 1];
last[i][__lg(a[i])] = i;
for (int j = W - 2; j >= 0; j--){
last[i][j] = max(last[i][j], last[i][j + 1]);
}
}
while (q--) {
int x;
cin >> x;
int idx = n - 1;
while (idx >= 0 && x > 0){
int msb = __lg(x);
int nxt = last[idx][msb];
x ^= pre[idx] ^ pre[nxt];
idx = nxt;
if (nxt == -1 || a[nxt] > x) break;
x ^= a[nxt];
idx--;
}
cout << n - idx - 1 << "\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) solve();
}
F - Object Identification
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> x(n + 1), isx(n + 1);
for (int i = 1; i <= n; i++) {
cin >> x[i];
isx[x[i]] = 1;
}
if (accumulate(isx.begin(), isx.end(), 0) == n) {
int i1 = 0, in = 0;
for (int i = 1; i <= n; i++) {
if (x[i] == 1) {
i1 = i;
}
if (x[i] == n) {
in = i;
}
}
cout << "? " << i1 << ' ' << in << endl;
int ans;
cin >> ans;
if (ans < n - 1) {
cout << "! A" << endl;
} else if (ans > n - 1) {
cout << "! B" << endl;
} else {
cout << "? " << in << ' ' << i1 << endl;
cin >> ans;
if (ans == n - 1) {
cout << "! B" << endl;
} else {
cout << "! A" << endl;
}
}
} else {
for (int i = 1; i <= n; i++) {
if (!isx[i]) {
cout << "? " << i << ' ' << 1 + (i == 1) << endl;
int ans;
cin >> ans;
if (ans == 0) {
cout << "! A" << endl;
} else {
cout << "! B" << endl;
}
return;
}
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
京公网安备 11010502036488号