A - 第 67 个整数问题

思路

无论江月诗选择什么 $y$，都有

$$\min(x,y)\le x.$$

因此答案对应的目标值不可能超过 $x$。直接令 $y=x$，便有

$$\min(x,x)=x,$$

恰好达到上界。

C++示例代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using ulll = unsigned __int128;

const int N = 1e6 + 10;

void solve(){
    int val;
    cin >> val;
    cout << val << endl;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}

B - 甜品

思路

江月诗每走一次长步，只会给一个坐标增加 $2$，不会改变这个坐标的奇偶性。

起点为 $(0,0)$，两个坐标都是偶数。短步每次只给一个坐标增加 $1$，会改变这一个坐标的奇偶性；而短步最多只能使用一次。

因此，最终最多只能有一个奇数坐标。判断条件为

$$(x\bmod2)+(y\bmod2)\le1.$$

也就是：只有 $x$ 和 $y$ 都是奇数时输出 NO，其余情况输出 YES。

C++示例代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using ulll = unsigned __int128;

const int N = 1e6 + 10;

void solve(){
    int x, y;
    cin >> x >> y;
    cout << (x % 2 == 1 && y % 2 == 1 ? "NO" : "YES") << endl;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}

C - 第 67 个“6–7”整数问题

思路

江月诗需要让恰好 $6$ 个数取反，等价于选择一个数保留，其余全部取反。

设原数组总和为

$$S=\sum_{i=1}^{7}a_i.$$

若保留 $a_k$，新总和为

$$a_k-\sum_{i\ne k}a_i =a_k-(S-a_k) =2a_k-S.$$

$S$ 不会随着选择改变。因此，只需要让保留的 $a_k$ 尽可能大。

最终答案为

$$\boxed{2\max(a_1,a_2,\ldots,a_7)-S}.$$

读入时同时维护总和与最大值即可，不需要排序或保存数组。

C++示例代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using ulll = unsigned __int128;

const int N = 1e6 + 10;

void solve(){
    int sum = 0, mx = INT_MIN;
    for(int i = 0; i < 7; i++){
        int x;
        cin >> x;
        sum += x;
        mx = max(mx, x);
    }
    cout << 2 * mx - sum << endl;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}

D - 派对图案

思路

江月诗进行调整时，选择的子串可以是整个字符串。

删除整个字符串后，剩下空串；再将所有字符逐个插回任意位置，就可以得到这些字符的任意排列。这里的多次“插回字符”属于同一次操作，不是多次操作。

于是，问题转化为：这些左括号和右括号能否重新排列成合法括号序列？

操作不会改变两种括号的数量。设左括号数为 $L$，右括号数为 $R$。答案为

$$\boxed{L=R}.$$

统计左括号数量 cnt，直接判断 2 * cnt == n 即可。

C++示例代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using ulll = unsigned __int128;

const int N = 1e6 + 10;

void solve(){
    int n;
    string str;
    cin >> n >> str;

    int cnt = 0;
    for(char& it : str){
        cnt += it == '(';
    }
    cout << (2 * cnt == n ? "YES" : "NO") << endl;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}

E - 降雪

关键观察：只关心因子 $2$ 和 $3$

因为 $6=2\times3$，一个子数组的乘积能够被 $6$ 整除，当且仅当乘积同时具有因子 $2$ 和因子 $3$。

因此，按整除性把元素分为四组：

分组	条件	示例
$S_6$	能被 $6$ 整除	$6,12,18$
$S_2$	能被 $2$ 整除，但不能被 $3$ 整除	$2,4,8$
$S_1$	既不能被 $2$ 整除，也不能被 $3$ 整除	$1,5,7$
$S_3$	能被 $3$ 整除，但不能被 $2$ 整除	$3,9,15$

只要一个子数组含有 $S_6$ 元素，其乘积一定能被 $6$ 整除。不含 $S_6$ 时，则需要同时出现 $S_2$ 与 $S_3$ 元素。

构造方案

江月诗只需将卡片按以下四组的顺序重新排列：

$$\boxed{[S_6]+[S_2]+[S_1]+[S_3]}.$$

各组内部的顺序不影响结果，可以保留读入顺序。

直观上，把 $S_6$ 集中放在一端，避免它们分散影响更多区间；把 $S_2$ 与 $S_3$ 分开放，中间用不会贡献因子 $2$ 或 $3$ 的 $S_1$ 隔开。

下面通过计数上界证明这个构造确实最优，而不仅是直觉上合理。

证明：对“不满足条件”的子数组计数

设

$$T(z)=\frac{z(z+1)}2$$

表示长度为 $z$ 的数组的非空连续子数组总数。

记 $|S_6|=k$、$|S_2|=p$、$|S_3|=q$，以及 $m=n-k$。定义

$$g(a)=T(n)-f(a),$$

即乘积不能被 $6$ 整除的子数组数量。最小化 $f(a)$ 等价于最大化 $g(a)$。

第一步：给任意排列的 $g(a)$ 建立上界。

一个计入 $g(a)$ 的子数组不可能含有 $S_6$ 元素，因此其左右端点必须都来自其余 $m$ 个位置。从这 $m$ 个位置中选择左、右端点，按实际位置满足左端点不晚于右端点，总共只有 $T(m)$ 种选择。

这些端点选择不一定都有效：区间内部可能出现 $S_6$，也可能同时出现因子 $2$、$3$。因此，$T(m)$ 只是候选数量的上界。

其中，只要两个端点分别选自 $S_2$ 与 $S_3$，区间乘积就一定能被 $6$ 整除。这样的端点组合恰好有 $pq$ 个：每选一个 $S_2$ 位置和一个 $S_3$ 位置，就唯一确定一个区间，无论哪个位置在前。

所以对任意排列，都有

$$g(a)\le T(m)-pq,$$

从而

$$f(a)\ge T(n)-T(m)+pq.$$

第二步：证明构造达到这个界。

在构造 $[S_6]+[S_2]+[S_1]+[S_3]$ 中，不包含 $S_6$ 的部分是一个长度为 $m$ 的连续后缀。

这个后缀共有 $T(m)$ 个子数组。其中，乘积能被 $6$ 整除的子数组，必须左端点位于 $S_2$、右端点位于 $S_3$，恰好有 $pq$ 个。其他子数组全部计入 $g(a)$。

因此，此构造满足

$$g(a)=T(m)-pq,$$

恰好达到任意排列都不能超过的上界。所以它使 $f(a)$ 达到最小值，构造正确。

C++示例代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using ulll = unsigned __int128;

const int N = 1e6 + 10;

void solve(){
    int n;
    cin >> n;

    vector<vector<int>> a(4);
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        if(x % 6 == 0) a[0].push_back(x);
        else if(x % 2 == 0) a[1].push_back(x);
        else if(x % 3 == 0) a[3].push_back(x);
        else a[2].push_back(x);
    }

    int cnt = 0;
    for(auto& it1 : a){
        for(int it2 : it1){
            cout << it2 << (++cnt == n ? '\n' : ' ');
        }
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}

F - 第 67 个异或问题

关键观察：两个未被删除元素的异或值不会改变

设江月诗当前数组中两个元素的值为 $u,v$。如果某次操作选择的值是 $x$，且这两个元素都没有被删除，那么它们的新值分别为 $u\oplus x$ 与 $v\oplus x$。

根据异或的结合律、交换律以及 $x\oplus x=0$，有

$$(u\oplus x)\oplus(v\oplus x) =u\oplus v\oplus x\oplus x =u\oplus v.$$

因此，只要两个元素都还在数组中，它们当前值的异或，就始终等于它们在原数组中的值的异或。

这里把元素看作有固定身份的对象：即使数组下标随删除发生变化，也能追踪到它原来的位置。

把整个操作过程转化为选择两个原数组位置

在最后一次操作之前，数组中恰好剩下两个元素。设它们原来位于位置 $p,q$，当前值分别为 $u,v$。

最后一次操作无论删除哪个元素，最终留下的值都是

$$u\oplus v=a_p\oplus a_q.$$

所以，任意合法操作序列的最终结果，都一定是原数组中两个不同位置的元素的异或值。

反过来，任意选择两个不同的原数组位置 $p,q$，先按任意顺序删除其余 $n-2$ 个元素，最后再删除这两个元素中的一个，就可以得到 $a_p\oplus a_q$。当 $n=2$ 时，直接进行最后一次操作即可。

因此，问题严格等价于求

$$\boxed{\max_{1\le p<q\le n}(a_p\oplus a_q)}.$$

这里要求位置不同，但不要求数值不同。

C++示例代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using ulll = unsigned __int128;

const int N = 1e6 + 10;

void solve(){
    int n;
    cin >> n;

    vector<int> a(n);
    for(auto& it : a) cin >> it;

    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            ans = max(ans, a[i] ^ a[j]);
        }
    }
    cout << ans << endl;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}

G - 回文 mex

关键观察：最优子数组一定包含 $0$

江月诗可以只取任意一个 $0$，得到的单元素数组是回文，且其 $\operatorname{mex}=1$。因此答案至少为 $1$。

不包含 $0$ 的子数组，其 $\operatorname{mex}=0$，不可能比上述方案更优。所以只需要考虑包含 $0$ 的回文子数组。

题目又保证 $0$ 恰好出现两次。设这两个 $0$ 的下标为 $p,q$，其中 $p<q$。下面统一使用从 $0$ 开始的下标，与代码一致。

为什么只需要三个候选中心

情况一：回文子数组中只有一个 $0$。

在回文中，除奇数长度回文的中心外，每个位置都对应一个值相同的镜像位置。若唯一的 $0$ 不在中心，就必须有另一个 $0$ 与它配对，产生矛盾。

因此，唯一的 $0$ 必须是中心，候选中心只能是 $p$ 或 $q$。

情况二：回文子数组中包含两个 $0$。

这两个 $0$ 必须关于中心对称。否则，其中一个 $0$ 还需要第三个 $0$ 作为镜像，违背整个数组中 $0$ 只有两次的条件。

所以中心必须为

$$\frac{p+q}{2}.$$

由此，所有可能最优的回文子数组，其中心都属于

$$\boxed{p,\ q,\ \frac{p+q}{2}}.$$

统一处理奇数和偶数长度回文

用一对初始指针 $(l,r)$ 表示中心：当 $l=r$ 时表示以某个元素为中心；当 $r=l+1$ 时表示以两个相邻元素之间为中心。

三个候选的起始指针为

$$(p,p),\qquad(q,q),\qquad \left(\left\lfloor\frac{p+q}{2}\right\rfloor, \left\lceil\frac{p+q}{2}\right\rceil\right).$$

第三对指针在代码中写作

(lef + rig) / 2
(lef + rig + 1) / 2

因为下标非负，整数除法正好实现所需的向下取整。当 $p+q$ 为偶数时，两式相同；为奇数时，两式相差 $1$。

从中心向外扩展

对每个候选中心，建立一个出现标记数组 seen。当左右指针都未越界，且对应元素相等时，将两个端点的值标记为出现，然后令左指针减一、右指针加一。

遇到不相等或越界后停止，得到该中心能够扩展出的最长回文区间。随后从 $0$ 开始扫描出现标记，找到第一个没有出现的整数，就是其 $\operatorname{mex}$。

为什么只检查该中心的最长回文，而不检查所有较短的回文？因为扩展只会增加元素，不会删除已出现的元素，故 $\operatorname{mex}$ 不会减小。最长回文的 $\operatorname{mex}$ 一定不小于同中心任何较短回文的 $\operatorname{mex}$。

C++示例代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using ulll = unsigned __int128;

const int N = 1e6 + 10;

void solve(){
    int n;
    cin >> n;

    int len = 2 * n;
    vector<int> arr(len), zero;
    for(int i = 0; i < len; i++){
        cin >> arr[i];
        if(arr[i] == 0) zero.push_back(i);
    }

    auto calc = [&](int lef, int rig){
        vector<int> seen(n + 1, 0);
        while(lef >= 0 && rig < len && arr[lef] == arr[rig]){
            seen[arr[lef]] = 1;
            seen[arr[rig]] = 1;
            lef--;
            rig++;
        }

        int mex = 0;
        while(mex < n && seen[mex]) mex++;
        return mex;
    };

    int lef = zero[0], rig = zero[1];
    int ans = max(calc(lef, lef), calc(rig, rig));
    ans = max(ans, calc((lef + rig) / 2, (lef + rig + 1) / 2));
    cout << ans << endl;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}