A – Table Tennis Training
思博题，考虑两端和奇偶性即可。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n, A, B, ans = 0x7fffffffffffffff;
scanf("%lld%lld%lld", &n, &A, &B);
ans = min(A - 1, n - B) + 1 + ((B - A - 1) >> 1);
if (!((A^B) & 1))
ans = min(ans, (B - A) >> 1);
printf("%lld\n", ans);
return 0;
}
B – Voting Judges
首先要意识到这个问题是可二分的，因为如果答案更大可行、那么小答案也可行。接下来考虑写一个 check。首先要判掉单独加上都无法入围的情况，然后算比 \(a_{mid}\) 小的那些 \(a_i\) 可以提供的票数。最后算这个票数是否能使之入围即可。
// B.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 200;
int n, m, V, P, ai[MAX_N];
bool check(int mid)
{
if (ai[mid] + m < ai[P])
return false;
long long acc = 0;
for (int i = P; i <= n; i++)
if (i != mid && ai[i] < ai[mid] + m)
acc += min(m, ai[mid] + m - ai[i]);
return acc >= 1LL * (V - 1) * m;
}
int main()
{
scanf("%d%d%d%d", &n, &m, &V, &P);
for (int i = 1; i <= n; i++)
scanf("%d", &ai[i]);
sort(ai + 1, ai + 1 + n), reverse(ai + 1, ai + 1 + n);
V = max(1, V - P + 1);
int l = P, r = n, res = P;
while (l <= r)
{
int mid = (l + r) >> 1;
if (check(mid))
res = mid, l = mid + 1;
else
r = mid - 1;
}
printf("%d\n", res);
return 0;
}
C – Domino Quality
首先可以找出 \(3\) 的、单元数为 \(2\) 的那个情况，这个情况直接输出即可；另外，我们能自己搞出来 \(4 \to 7\) 的、单元数为 \(3\) 的情况，之后如果 \(n > 7\)，则表示成 \(n = 4x + y, y > 3\)，然后拼在对角线上即可。
// C.cpp
#include <bits/stdc++.h>
using namespace std;
int n;
char buffer[1010][1010];
const char m3[3][4] =
{"aa.",
"..a",
"..a"};
const char m4[4][5] =
{"aabc",
"ddbc",
"bcaa",
"bcdd"};
const char m5[5][6] =
{"aabba",
"bcc.a",
"b..cb",
"a..cb",
"abbaa"};
const char m6[6][7] =
{"aabc..",
"ddbc..",
"..aabc",
"..ddbc",
"bc..aa",
"bc..dd"};
const char m7[7][8] =
{"aabbcc.",
"dd.dd.a",
"..d..da",
"..d..db",
"dd.dd.b",
"..d..dc",
"..d..dc"};
void writeBuffer(int id, int x, int y)
{
for (int i = 0; i < id; i++)
{
const char *str;
switch (id)
{
case 3:
str = m3[i];
break;
case 4:
str = m4[i];
break;
case 5:
str = m5[i];
break;
case 6:
str = m6[i];
break;
case 7:
str = m7[i];
break;
}
for (int j = 0; str[j]; j++)
buffer[x + i][y + j] = str[j];
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
buffer[i][j] = '.';
if (n <= 2)
puts("-1"), exit(0);
if (n <= 7)
writeBuffer(n, 0, 0);
else
{
int base = 0;
writeBuffer(n % 4 + 4, base, base), base += n % 4 + 4;
while (base < n)
writeBuffer(4, base, base), base += 4;
}
for (int i = 0; i < n; i++)
printf("%s\n", buffer[i]);
return 0;
}
D – Problem Scores
这应该是本次最有意思的题目了，之前 lcx 的某个教练群里发过。
其实就是要满足其 \(k + 1\) 前缀和严格大于其 \(k\) 后缀和，写出来即：
\[ \sum_{i = 1}^{k + 1} a_i > \sum_{i = n – k + 1}^n a_i \]
一共会有 \(n\) 个这样的限制条件，我们尝试寻找性质来缩减之。首先，对于 \(k > \lfloor \frac{n}{2} \rfloor\) 的情况，存在前缀和后缀中间重叠的部分，这个可以直接移项消掉，转化成 \(k \leq \lfloor \frac{n}{2} \rfloor\) 的情况。
再考虑利用 \(a_i \leq a_{i + 1}\) 的性质，则发现当 \(k = \lfloor \frac{n}{2} \rfloor\) 时满足，\(k \leq \lfloor \frac{n}{2} \rfloor\) 的情况可以被充分满足。
那么我们现在只需要保证 \(\sum_{i = 1}^{k + 1} a_i > \sum_{i = n – k + 1}^n a_i, k = \lfloor \frac{n}{2} \rfloor\) 即可。
现在我们对这个序列进行差分，使得 \(a_k = 1 + \sum_{i = 1}^k \Delta_i\)。首先显然有 \(\Delta \geq 0\)。其次，带回式子时，发现前缀和可以被拆解为 \(\sum \Delta_i c_i\)，其中这个 \(c_i\) 很好算。考虑带入：
\[ \sum_{i = 1}^{k + 1} 1 + \sum_{j = 1}^i \Delta_j > \sum_{i = n – k + 1}^n 1 + \sum_{j = 1}^i \Delta_j \\ 1 + \sum_{i = 1}^{k + 1} \sum_{j = 1}^i \Delta_j > \sum_{i = n – k + 1}^n \sum_{j = 1}^i \Delta_j \\ \sum_{i = 1}^{k + 1} \sum_{j = 1}^i \Delta_j \geq \sum_{i = n – k + 1}^n \sum_{j = 1}^i \Delta_j \\ \sum_{j = 1}^n \Delta_j \sum_{i = 1}^{k + 1} [j \leq i] \geq \sum_{j = 1}^n \Delta_j \sum_{i = n – k + 1}^n [j \leq i] \\ \sum_{j = 1}^{k + 1} \Delta_j (k + 2 – j) \geq \sum_{j = 1}^n \Delta_j (n – \max(j, n – k + 1) + 1) \]
得到：
\[ (k + 1) \Delta_1 + \sum_{j = 2}^{k + 1} \Delta_j (k + 2 – j) \geq k\Delta_1 + \sum_{j = 2}^n \Delta_j (n – \max(j, n – k + 1) + 1) \\ \Delta_1 \geq \sum_{j = 2}^n \Delta_j (n – \max(j, n – k + 1) + 1) – \sum_{j = 2}^{k + 1} \Delta_j (k + 2 – j) \\ \Delta_1 \geq \sum_{j = 2}^n \Delta_j (n – \max(j, n – k + 1) + 1) – \sum_{j = 2}^n \Delta_j \max(0, k + 2 – j) \\ \Delta_1 \geq \sum_{j = 2}^n \Delta_j (n + 1 – (\max(j, n – k + 1) + \max(0, k + 2 – j))) \\ \Delta_1 \geq \sum_{j = 2}^n \Delta_j (n + 1 – \max(j, k + 2, n – k + 1, n + 3 – j)) \\ \Delta_1 \geq \sum_{j = 2}^n \Delta_j (n + 1 + \min(-j, – k – 2, – n + k – 1, – n – 3 + j)) \\ \Delta_1 \geq \sum_{j = 2}^n \Delta_j \min(n – j + 1, n – k – 1, k, j – 2) \\ \]
提醒一下，\(k = \lfloor \frac{n}{2} \rfloor\)：
区间是离散的，所以最后 \(\min(n – j + 1, n – k – 1, k, j – 2) = \min(j – 2, n – j + 1)\)。最后整个不等式形如：
\[ \Delta_1 \geq [\Delta_2, \Delta_3, \dots \Delta_n] \cdot [0, 1, 2, 3, \dots 3, 2, 1] \]
考虑设：
\[ a = \Delta_2 + \Delta_3 + \Delta_4 + \dots + \Delta_n \\ b = [\Delta_2, \Delta_3, \dots \Delta_n] \cdot [0, 1, 2, 3, \dots 3, 2, 1] \]
发现 \(\Delta_1 \leq n – 1 – a, \Delta_1 \geq b \)，那么，\(\Delta_1\) 的选择方式有 \(\max(0, n – 1 – (a + b))\) 种。\(a + b = [\Delta_2, \Delta_3, \dots \Delta_n] \cdot [1, 2, 3, 4, \dots 4, 3, 2]\)，所以我们用 \(DP\) 算下和为 \(j = a + b\) 的 \(\Delta_i\) 序列的方案数，然后用方案数乘上一个 \(\max(0, n – 1 – (a + b))\) 即为答案。
// D.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5050;
int n, mod, dp[MAX_N], coeff[MAX_N];
int main()
{
scanf("%d%d", &n, &mod), dp[0] = 1;
for (int i = 1; i < n; i++)
for (int j = min(n - i + 1, i), k = j; j < n; j++)
dp[j] = (0LL + dp[j] + dp[j - k]) % mod;
int ans = 0;
for (int i = 0; i < n; i++)
ans = (0LL + ans + 1LL * dp[i] * (n - i) % mod) % mod;
printf("%d\n", ans);
return 0;
}