2025.1.17——1200

2025.1.17——1200

---

Q1. 1200

Jellyfish has $n$ green apples with values $a_1,a_2,\dots ,a_n$ and Gellyfish has $m$ green apples with values $b_1,b_2,\dots ,b_m$.

They will play a game with $k$ rounds. For $i=1,2,\dots ,k$ in this order, they will perform the following actions:

• If $i$ is odd, Jellyfish can choose to swap one of her apples with one of Gellyfish’s apples or do nothing.
• If $i$ is even, Gellyfish can choose to swap one of his apples with one of Jellyfish’s apples or do nothing.

Both players want to maximize the sum of the values of their apples.

Since you are one of the smartest people in the world, Jellyfish wants you to tell her the final sum of the value of her apples after all $k$ rounds of the game. Assume that both Jellyfish and Gellyfish play optimally to maximize the sum of values of their apples.
Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 2000$). The description of the test cases follows.

The first line of each test case contains three integers, $n$, $m$ and $k$ ($1\le n,m\le 50$, $1\le k\le 10^9$) — the number of green apples Jellyfish has, the number of green apples Gellyfish has and the number of rounds of the game respectively.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — the values of Jellyfish’s green apples.

The third line of each test case contains $m$ integers $b_1,b_2,\dots ,b_m$ ($1\le b_i\le 10^9$) — the values of Gellyfish’s green apples.

Do note that the sum of $n$ and $m$ over all test cases are both not bounded.

---

Q2. 1200

Andrey is just starting to come up with problems, and it’s difficult for him. That’s why he came up with a strange problem about permutations${}^{†}$ and asks you to solve it. Can you do it?

Let’s call the cost of a permutation $p$ of length $n$ the value of the expression:

$({\sum }_{i=1}^n{p}_i\cdot i)-({\max }_{j=1}^n{p}_j\cdot j)$.

Find the maximum cost among all permutations of length $n$.

${}^{†}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 30$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains a single integer $n$ ($2\le n\le 250$) — the length of the permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $500$.

---

Q3. 1200

Monocarp is going to make a purchase with cost of exactly $m$ burles.

He has two types of coins, in the following quantities:

• coins worth $1$ burle: $a_1$ regular coins and infinitely many fancy coins;
• coins worth $k$ burles: $a_k$ regular coins and infinitely many fancy coins.

Monocarp wants to make his purchase in such a way that there’s no change — the total worth of provided coins is exactly $m$. He can use both regular and fancy coins. However, he wants to spend as little fancy coins as possible.

What’s the smallest total number of fancy coins he can use to make a purchase?
Input

The first line contains a single integer $t$ ($1\le t\le 3\cdot 10^4$) — the number of testcases.

The only line of each testcase contains four integers $m,k,a_1$ and $a_k$ ($1\le m\le 10^8$; $2\le k\le 10^8$; $0\le a_1,a_k\le 10^8$) — the cost of the purchase, the worth of the second type of coin and the amounts of regular coins of both types, respectively.

---

Q4. 1300

Cats are attracted to pspspsps, but Evirir, being a dignified dragon, is only attracted to pspspsps with oddly specific requirements…

Given a string $s=s_1{s}_2\dots s_n$ of length $n$ consisting of characters p, s, and . (dot), determine whether a permutation${}^{\text{∗}}$ $p$ of length $n$ exists, such that for all integers $i$ ($1\le i\le n$):

• If $s_i$ is p, then $[p_1,p_2,\dots ,p_i]$ forms a permutation (of length $i$);
• If $s_i$ is s, then $[p_i,p_{i+1},\dots ,p_n]$ forms a permutation (of length $n-i+1$);
• If $s_i$ is ., then there is no additional restriction.

${}^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le 500$), the length of $s$.

The second line of each test case contains a string $s$ of length $n$ that consists of the characters p, s, and …

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.

---

Q5. 1300

You are given an array $a$ of $n$ integers, and $q$ queries.

Each query is represented by two integers $l$ and $r$ ($1\le l\le r\le n$). Your task is to find, for each query, two indices $i$ and $j$ (or determine that they do not exist) such that:

• $l\le i\le r$;
• $l\le j\le r$;
• $a_i\ne a_j$.

In other words, for each query, you need to find a pair of different elements among $a_l,a_{l+1},\dots ,a_r$, or report that such a pair does not exist.
Input

The first line of the input contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($2\le n\le 2\cdot 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^6$) — the elements of the array $a$.

The third line of each test case contains a single integer $q$ ($1\le q\le 2\cdot 10^5$) — the number of queries.

The next $q$ lines contain two integers each, $l$ and $r$ (KaTeX parse error: Expected 'EOF', got '&' at position 9: 1 \le l &̲lt; r \le n) — the boundaries of the query.

It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $2\cdot 10^5$. Similarly, it is guaranteed that the sum of the values of $q$ across all test cases does not exceed $2\cdot 10^5$.

---

------------------------思考------------------------

• 贪心博弈+guess+数学+发现结论+思维

---

A1

1. 贪心博弈：发现策略为将自己最小与其最大交换/不操作。

---

A2

1. 神秘题：严谨证明太难，只能靠手玩/天马行空/打表/guess。

---

A3

1. 有趣的数学题：贪心再数学，考虑回退。
2. 另解可对函数二分

---

A4

1. 观察各种情况发现结论。

---

A5

1. 巧妙的思维，维护少许东西就可以作出回答。
2. 原题区间询问可看作（充分必要）： $[l,r)$ 中是否存在与 $a[r]$ 不相同的数。

---

------------------------代码------------------------

A1

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(10);int T = 1;cin >> T;while (T--)_();return 0;
}void _()
{int n, m, k;cin >> n >> m >> k;int res = 0;vector<int> a{(int)1e10, 0};vector<int> b = a;for (int i = 0; i < n; i++){int x;cin >> x;res += x;a[0] = min(a[0], x);a[1] = max(a[1], x);}for (int i = 0; i < m; i++){int x;cin >> x;b[0] = min(b[0], x);b[1] = max(b[1], x);}res -= a[0] + a[1];if (a[0] < b[1])swap(a[0], b[1]);sort(a.begin(), a.end());sort(b.begin(), b.end());if ((k ^ 1) & 1){// bug(k);if (b[0] < a[1])swap(b[0], a[1]);}res += a[0] + a[1];cout << res << endl;
}

---

A2

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(10);int T = 1;cin >> T;while (T--)_();return 0;
}void _()
{int n;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i++)a[i] = i;auto get = [&](){int res = 0, mx = 0;for (int i = 1; i <= n; i++)res += a[i] * i, mx = max(mx, a[i] * i);return res - mx;};int res = get();for (int i = n - 1; i; i--){for (int j = i; j < n; j++)swap(a[j], a[j + 1]);res = max(res, get());// for (int i = 1; i <= n; i++)//     cout << a[i] << " ";// cout << endl;}cout << res << endl;
}

---

A3

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(10);int T = 1;cin >> T;while (T--)_();return 0;
}void _()
{int m, k, a1, ak;cin >> m >> k >> a1 >> ak;int res = 0;int m1 = m, m2 = 0;if (ak)m1 = max(0ll, m - k * min(ak, m / k));if (m1)m2 = max(0ll, m1 - a1);if (m2){res = m2 / k + m2 % k;if (m1 / k - m2 / k)res = min(res, m2 / k + 1);}cout << res << endl;
}
// void _()
// {
//     int m, k, a1, ak;
//     cin >> m >> k >> a1 >> ak;
//     int res = 0;
//     if (ak)
//         m = max(0ll, m - ak * min(k, (m + ak - 1) / ak));
//     if (m)
//         m = max(0ll, m - a1);
//     if (m)
//     {
//         res = m / k + m % k;
//         if ((m / k + 1) * k <= m)
//             res = min(res, m / k + 1);
//     }
//     cout << res << endl;
// }

---

A4

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // attention: interactive/debug
#define el cout << endl
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
#define bugv(VEC)           \cout << "bug:# ";       \for (auto val : VEC)    \cout << val << ' '; \el;void _();
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(10);int T = 1;cin >> T;while (T--)_();return 0;
}void _()
{int n;cin >> n;string s;cin >> s;s.front() = s.front() == '.' ? 's' : s.front();s.back() = s.back() == '.' ? 'p' : s.back();bool f = 0;map<char, int> cnt;for (auto v : s)cnt[v]++;if (!cnt['p'] || !cnt['s'])f = 1;if (cnt['p'] == 1 && s.back() == 'p')f = 1;if (cnt['s'] == 1 && s.front() == 's')f = 1;cout << (f ? "YES" : "NO");el;
}

---

A5

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // attention: interactive/debug
#define el cout << endl
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
#define bugv(VEC)           \cout << "bug:# ";       \for (auto val : VEC)    \cout << val << ' '; \el;void _();
signed main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cout << fixed << setprecision(10);int T = 1;cin >> T;while (T--)_();return 0;
}void _()
{int n;cin >> n;vector<int> a(n + 1), f(n + 1, -1);for (int i = 1; i <= n; i++){cin >> a[i];f[i] = a[i] == a[i - 1] ? f[i - 1] : i - 1;}int q;cin >> q;while (q--){int l, r;cin >> l >> r;int resl = -1, resr = -1;if (f[r] >= l)resl = f[r], resr = r;cout << resl << ' ' << resr;el;}el;
}

---