前排提醒：
就只有A~D题。
题目大意就不放啦，可以点链接去看题目。
思路我就写我写时候的思路，希望能对你有帮助qwq
A题：Chess For Three
Q：什么情况是不可能出现的？
A：总得分为奇数的情况是不可能出现的，因为要得分，只能一个人加两分，或者两个人每个人加一分，不可能出现奇数的情况。
Q：怎么使得平局次数最多呢？
A：当然，如果得分全都是由平局得来的话次数肯定最多。
题目给了一个信息，a是单调不减的。
我们有三种搭配方式， a1 - a2 a1 - a3 a2 - a3
所以去进行搭配的只是a1和a2，
a3特别大的时候，答案是a1+a2
这个特别大我们可以推出来是 a3 > a1 + a2
这就成为了我们分类讨论的依据
而 a3 <= a1 + a2的时候，
a3 - a1 <= a2
可以考虑它们的奇偶性，a3 - a1和 a2 差 2的倍数 （0， 1， 2 ...)
也就是说 a1 可以使得 a2和a3配成相等
如 3 4 5
ans = 3 + （0， 3，3） = 3 + 3 = 6
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define int long long
#define endl '\n'
//#define LOCAL
inline void solve() {
int a[3], sum = 0;
for (int i = 0; i < 3; i ++ ) cin >> a[i], sum += a[i];
if (sum & 1) return cout << -1 << endl, void();
if (a[2] - a[1] > a[0]) {
cout << a[0] + a[1] << endl;
}else {
cout << sum / 2 << endl;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
int tt; tt = 1;
cin >> tt;
while (tt -- ) solve();
return 0;
}B题：Cat, Fox and the Lonely Array
Q：怎么去找最小的K啊？
A：题目要求我们去找最小的K，那么一定可以有更大的K满足题意的对吧。
Q：有道理，所以小于最小的K不满足题意，大于最小的K满足题意？
A：是这样的，这样你就想出来了二分这种解法了对吧？我来给你更严谨点
左边是k = 5的情况，右边是k = 6的情况
x x x x x x x x x x x
x x x x x x x x x x x
右边上面那段是由左边上下两端或起来的，右边下面是由另外两段或起来的。
而左边每段或起来的值相等，就推出来了右边每段或起来的值相等。
Q：嗷，我知道了，那怎么求出来一段区间的或值呢？
A：这题可以窗口，也可以暴力上ST表，ST表更清楚些
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
#define int long long
#define endl '\n'
//#define LOCAL
const int N = 1e5 + 9;
int a[N], st[N][20], lg2[N];
inline void build(int n) {
for (int i = 1; i <= n; i ++ ) st[i][0] = a[i];
for (int j = 1; (1 << j) <= n; j ++ ) {
for (int i = 1; i + (1 << (j - 1)) <= n; i ++ ) {
st[i][j] = st[i][j - 1] | st[i + (1 << (j - 1))][j - 1];
}
}
}
inline int query(int l, int r) {
int s = lg2[r - l + 1];
return st[l][s] | st[r - (1 << s) + 1][s];
}
inline void solve() {
int n; cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
build(n);
int l = 0, r = n + 1;
while (l + 1 != r) {
int mid = (l + r) >> 1;
int cur = query(1, mid);
bool ok = true;
for (int i = 2; i + mid - 1 <= n; i ++ ) {
if (query(i, i + mid - 1) != cur) {
ok = false;
break;
}
}
if (ok) r = mid;
else l = mid;
}
cout << r << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
for (int i = 2; i < N; i ++ ) lg2[i] = lg2[i >> 1] + 1;
int tt; tt = 1;
cin >> tt;
while (tt -- ) solve();
return 0;
}
C题：Cat, Fox and Double Maximum
Q：题目我看懂了，该怎么构造呢？
A：n是偶数对吧？
Q：是的。
A：那最理想构造出几个？
Q：(n - 2) / 2个，中间隔一个就有一个局部最大。
A：就这么构造
Q：你的意思是，要让一些成为局部最大的点的点配上最大，另一些配上最小？
1 2 3 4 5 6
我们让2，4成为局部最大，就配6 5
其他配4 3 2 1，所以是4 6 3 5 2 1？
也可以是3，5成为局部最大，配6 5
其他配4 3 2 1，成4 3 6 2 5 1？
两种情况一定能出一个(n - 2) / 2？这么做的理由是什么？
A：我猜对了，就花了8min。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int, int> PII;
//#define LOCAL
inline void solve() {
int n; cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++ ) cin >> a[i];
vector<PII> b, c;
for (int i = 1; i <= n; i ++ ) {
if (i % 2 == 0 && i != n) {
b.push_back({a[i], i});
}else {
c.push_back({a[i], i});
}
}
sort(b.begin(), b.end());
int cur = n;
vector<int> res(n + 1);
for (int i = 0; i < b.size(); i ++ ) {
res[b[i].second] = cur --;
}
sort(c.begin(), c.end());
for (int i = 0; i < c.size(); i ++ ) {
res[c[i].second] = cur --;
}
vector<int> temp(n + 1);
for (int i = 1; i <= n; i ++ ) {
temp[i] = res[i] + a[i];
}
int cnt = 0;
for (int i = 2; i < n; i ++ ) {
if (temp[i] > temp[i - 1] && temp[i] > temp[i + 1]) cnt += 1;
}
if (cnt == (n - 2) / 2) {
for (int i = 1; i <= n; i ++ ) cout << res[i] << ' ';
cout << endl;
return;
}
b.clear(), c.clear();
for (int i = 1; i <= n; i ++ ) {
if (i & 1 && i != 1) {
b.push_back({a[i], i});
}else {
c.push_back({a[i], i});
}
}
sort(b.begin(), b.end());
cur = n;
res.clear();
for (int i = 0; i < b.size(); i ++ ) {
res[b[i].second] = cur --;
}
sort(c.begin(), c.end());
for (int i = 0; i < c.size(); i ++ ) {
res[c[i].second] = cur --;
}
for (int i = 1; i <= n; i ++ ) cout << res[i] << ' ';
cout << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
int tt; tt = 1;
cin >> tt;
while (tt -- ) solve();
return 0;
}D题： Cat, Fox and Maximum Array Split
Q：如果已经知道a数组了，这个构造也是很麻烦啊。
A：所以是交互题
Q：该怎么做呢？
A：题目给的最大次数是2 * n，所以它是想让你去遍历n，也就是a数组。我们先去考虑这个数组中的最大值，每次可以ask（1，i * n），当返回值是n的时候，i就是数组中的最大值，这样的操作次数最大是n
接着我们可以考虑最大值所在区间的长度，长度最大是 n / k （下取整）
Q：为什么长度最大是 n / k ？
A：你这样想，按题目意思，如果区间中最大值越大，那么我们要配成一样的话是不是长度要越小？
Q：是的，没毛病
A：如果就只有一段有最大值，那么其他段的长度都要比其长度大一点，这样就使得其小于 n / k了，但是全有最大值的话，就可以是 n / k了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
//#define LOCAL
int ask(int l, int w) {
cout << "? " << l << " " << w << endl;
int r; cin >> r;
return r;
}
inline void solve() {
int n, k; cin >> n >> k;
int maxv;
for (int i = 1; i <= n; i ++ ) {
int r = ask(1, n * i);
if (r == n) {
maxv = i;
break;
}
}
for (int i = n / k; i >= 1; i -- ) {
int head = 1, cnt = 1;
bool flag = true;
while (cnt <= k && head <= n) {
int r = ask(head, maxv * i);
if (r == n + 1) {
flag = false;
break;
}
head = r + 1;
cnt += 1;
}
if (flag && cnt == k + 1 && head == n + 1) {
cout << "! " << i * maxv << endl;
cin >> n;
return;
}
}
cout << "! " << -1 << endl;
cin >> n;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
int tt; tt = 1;
cin >> tt;
while (tt -- ) solve();
return 0;
}写在最后：
