【SEOI2024】官方题解
【SEOI2024】官方题解
摘要
作为市二编程社举办的第一场公开比赛，主题为数据的处理与分析，赛题主要围绕基本算法以及数据结构展开。难度被设计呈两级分化趋势，\(A\)题与\(B\)题及其简单，\(DEF\)题则在省选难度，毫无疑问\(DEF\)赛时无人拿分，可能是因为时间不足，也有可能是因为选手第一次接受到专业的信息试题，在\(SEOI2025\)我们会对选手进行赛前的简单培训，让选手能够提前熟悉比赛环境从而对难度有更好的适应。
【SEOI2024 A】二元运算器
这题没什么好说的，但是\(Python\)读入会由于行末换行符而多读入一个字符，导致直接进入\(math\ error\)分支或者直接\(RE\)，几乎所有\(Python\)选手都因为这点没有拿到第一题的分数。
参考代码：
#include <bits/stdc++.h>
#define I return
#define Love 0
#define Coding ;
using namespace std;
int main() {
char opt;
cin >> opt;
int num1, num2;
cin >> num1 >> num2;
if (opt == '+') cout << num1 + num2;
if (opt == '-') cout << num1 - num2;
if (opt == '*') cout << num1 * num2;
if (opt == '^') cout << (int) pow(num1, num2);
if (opt == '%') {
if (num2 == 0) printf("math error");
else cout << num1 % num2;
}
if (opt == '/') {
if (num2 == 0) printf("math error");
else cout << (int) round(num1 * 1.0 / num2);
}
I Love Coding
}
【SEOI2024 B】Grievous
这题是唯一不是我出的题，一开始被排除在题单外，因为这题\(Python\)根本无法使用素数筛，而开小数据会被其他编程语言\(O(n\sqrt n)\)暴力秒掉，而对于\(Python\)而言如果想卡掉这个根号，几乎是不可能的，即使把百万级的数塞进数组就以及无法在最高时限\(5s\)中完成了。在赛前的几个小时，胡同学把这题
加了进来，我紧急把后面大样例删掉了，但这个决定最终被证明是明智的，至少让两支队伍\(A\)掉拿到了\(100\)分，不至于全员爆零。
参考代码：
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 1e8 + 10, M = 2e2 + 10;
int isNotPrime[N];
int Prime[N], cnt, a[N];
int main() {
int n;
scanf("%d", &n);
int maxm = -1;
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]), maxm = max(a[i], maxm);
for (int i = 2; i <= maxm; ++i) {
if (!isNotPrime[i]) {
Prime[++cnt] = i;
}
for (int j = 1; j <= cnt; ++j) {
if (Prime[j] * i > maxm)
break;
isNotPrime[Prime[j] * i] = 1;
if (i % Prime[j] == 0)
break;
}
}
int ans = 0;
for (int i = 1; i <= n; ++i)
if (!isNotPrime[a[i]] && a[i] != 1)
++ans;
printf("%d", ans);
return 0;
}
【SEOI2024 C】修改向量
本次比赛阴间的开始，没有人进行过尝试，所有提交的人都输出了\(-1\)或\(2\)骗了\(5\sim15\)分。
我们记\(\delta = A\cdot B\)，如果\(\delta = 0\)显然无需进行修改操作，而对于\(\delta \neq 0\)，我们对\(B_i\)进行修改时会对\(\delta\)产生\(|\Delta B\cdot A_i|\)的增减，而单次修改增减的最大值即为\(|b\cdot A_i|\)，其中\(b\)为常数，提出得\(\Delta _{max}=|b|\cdot |A_i|\)，我们为了最小化修改次数，显然每次因选择最大的\(|A_i|\)，于是将\(A\)序列按\(|A|\)大小排序，每次取最大的\(|A|\)，能够使\(\delta =0\)时，该次数即为最小操作次数。时间复杂度\(O(n\log_{2}n)\)，在于排序。
参考代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
int A[N], B[N];
bool cmp(int a, int b) { return a > b; }
signed main() {
int flag = 0;
int n, m;
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%lld", &A[i]);
for (int i = 1; i <= n; ++i) scanf("%lld", &B[i]);
int tmp = 0;
for (int i = 1; i <= n; ++i) tmp += A[i] * B[i];
if (tmp == 0) {
puts("0");
return 0;
}
tmp = abs(tmp);
for (int i = 1; i <= n; ++i) A[i] = abs(A[i]);
sort(A + 1, A + n + 1, cmp);
for (int i = 1; i <= n; ++i) {
if (m * A[i] >= tmp) {
printf("%lld", i);
flag = i;
break;
} else tmp -= m * A[i];
}
if (!flag) puts("-1");
return 0;
}
【SEOI2024 D】意大利面序列
这题极其考验选手对时间复杂度的优化，对于暴力，显然存在\(O(n^3)\)的算法，枚举左右端点\(O(n^2)\)，计算左右端点最大值\(O(n)\)。对于最大值的计算我们可以通过\(ST\)表通过\(O(nlog_{2}n)\)，的预处理达到\(O(1)\)查询，总时间复杂度\(O(n^2)\)，\(ST\)表写的代码比标算长，赛时有一个人写出来了，但是没编译通过很遗憾。
接下来考虑正解，我们发现\(O(n^3)\)和\(ST\)表优化得到的\(O(n^2)\)瓶颈皆在于\(O(n^2)\)的枚举左右端点的，我们对于同一类型的划分寻找相似性，不难发现如果左右端点一处被固定下来的话，一端的最大值也恒定了，此时滑动另一端点，对结果产生影响的只有另一端点在不同位置的最大值。
于是我们尝试构造数列
即前缀\(max\)和，于后缀\(max\)，由于确定右端点后右端点贡献恒定为从右端点到序列尾部的最大值，我们只需要对左端点之前每次分割位置得到的最大值做前缀和，最后两者相乘就能得到最终答案。
通过大样例的拟合，我们很容易发现第二问的数学期望逼近\(k^2\)，具体数学证明欢迎大家来编程社讨论。
参考代码：
#include <bits/stdc++.h>
#define int long long
const int N = 2e7 + 10;
int a[N], f[N], g[N];
using namespace std;
signed main() {
int type;
scanf("%lld", &type);
if (type) {
int k;
scanf("%lld", &k);
printf("%lld\n", 1ll * k * k);
return 0;
}
int n;
scanf("%lld", &n);
int num = (1 + n - 2) * (n - 2) / 2;
for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
f[1] = a[1];
for (int i = 2; i <= n; ++i) f[i] = max(f[i - 1], a[i]);
for (int i = 1; i <= n; ++i) f[i] += f[i - 1];
g[n] = a[n];
for (int i = n - 1; i >= 1; --i) g[i] = max(g[i + 1], a[i]);
int sum = 0;
for (int i = 2; i <= n - 1; ++i) sum += 1ll * f[i - 1] * g[i + 1];
printf("%.9f", sum * 1.0 / num);
return 0;
}
【SEOI2024 E】旅途的华章
非常有意思的一道思维题，