比赛题目共 \(2\) 套，其中初赛题 \(1\) 套，复赛 \(2\) 题。
比赛时间: \(10:50 - 12:00 a.m\)。
Part 0x01 过程-Process
\(8:30\,a.m.\) 做初赛题目；
\(10:40\,a.m.\) 拿到题目；
\(10:41\,a.m.\) 先写 \(\text{T1}\)，发现有点像分类讨论；
\(10:50\,a.m.\) 发现 \(\text{T1}\) 不需要那么麻烦，直接取 \(\text{max}\) 即可；
\(11:00\,a.m.\) 把 \(\text{T1}\) 写完了，估计能过，但加了一些暴力写法，防止掉分。
\(11:01\,a.m.\) 看 \(\text{T2}\)，并写了个暴力。
\(12:00\,a.m.\) \(\text{T2}\) 排序 \(+\) 去重卡过大样例。
总分 \(= 100pts + 65pts = 165pts\)。
Part 0x02 初赛注意事项-Theory
- \(∨\) 代表或运算，即
|| - \(∧\) 代表与运算，即
&& - \(?\) 代表非运算，即
! - 文件型病毒传染的主要对象是
EXE和COM文件 - Linux下可执行文件没有后缀名
- 田忌赛马思想：
- 对手必胜，就用最小的马输给对手
- 对手必败，就用最小的马赢对手
- 我方必胜，就用最小的马赢对手
- 我方必败，就用最小的马输给对手
- 对拍 \(=\) 造数据程序 \(+\) 暴力程序 \(+\) 你的正解
- 如果不用补码思想，把 \(n\) 位二进制最高位当符号位，其他位正常储存，那么表示数字范围为 \([-2^n+1, 2^n-1]\)，同时会引发 \(0 \neq -0\) 的 \(\text{BUG}\)
- 在 \(n\) 位补码中，数字范围为 \([-2^n, 2^n-1]\)，同时 \(0 = -0\) ，加减法无需特判，同时也可以根据最高位判断是否是负数。
- 浮点数由尾数和阶码构成。
- 只给出前序遍历与后序遍历的情况下无法确认二叉树。
- 计算机四种存储器：硬盘、\(\text{RAM}\)、\(\text{Cache}\)、寄存器，速度逐渐变快，可用空间逐渐变小
- 二叉搜索树的每个节点内有数字，满足左子树都小于自己，右子树都大于自己
- \(n\) 个物品中有一件次品，已知这件次品轻一些，使用天平分三份称量；
- 组合数学从不同角度出发均可得到答案.
- \(100\) 以内的质数有 \(25\) 个
- 欧拉筛保证每个数只会被自己的最小质因子筛到一次，所以是 \(O(n)\) 的
- 每过一年星期数 \(+1\)，闰年 \(+2\)
- 一行组合数加起来是 2 的次幂，也即 \(C(n, 0) + ... + C(n, n) = 2^n\)
- 判断 \(\text{T}\) 是否是 \(\text{S}\) 的子序列，可以直接 \(O(|S|)\) 的硬匹配，也可以预处理好 \(S\) 的
Pos[i][j]数组后 \(O(|T|)\) 地匹配
Part 0x03 复赛题目-Problem
T1 选择乘积
其实不需要分类讨论，直接把可能成为答案的乘积取 max 即可。
为了防止掉分，可以适当的在正解中写暴力。
\(\mathfrak{Code\,Here}\)
// g++ "choose.cpp" -Wall -std=c++14 -o "choose"
// ./"choose"
#include <bits/stdc++.h>
using namespace std;
int main()
{
freopen("choose.in", "r", stdin);
freopen("choose.out", "w", stdout);
long long a, b, c, d;
scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
if(a >= 0 && c >= 0) //对于前 50% 的数据
{
printf("%lld", b * d);
}
else if(abs(a) <= 100 && abs(b) <= 100 && abs(c) <= 100 && abs(d) <= 100) //对于前 80% 的数据
{
long long ans = -114514;
for(long long i = a; i <= b; i++)
{
for(long long j = c; j <= d; j++)
{
ans = max(ans, i * j);
}
}
printf("%lld\n", ans);
}
else //正解
{
printf("%lld\n", max(max(a * c, a * d), max(b * c, b * d)));
}
return 0;
}
时间复杂度 \(O(1)\)
T2 公约数
暴力
考场做法，首先我们意识到，「擦去之后填⼊新的」只是⼀个幌⼦，本质上是要求擦掉一个数之后其他所有数的最大公因数。设删去第 \(i\) 个数后其他所有数的最大公因数为 \(m\)，那么只要填⼊ \(m\) 的倍数就能保证公约数最大了。
问题转变为：怎么求删去第 \(i\) 个数后的最大公因数是多少，模拟即可，排序 \(+\) 去重后可通过大样例。
掉了5分，原因：\(n = 1\) 时，可以吧第一个数擦掉，改成题目要求的最大值（\(10^9\)）
\(\mathfrak{Code\,Here\,(65pts)}\)
// g++ "gcd.cpp" -Wall -std=c++14 -o "gcd"
// ./"gcd"
#include <bits/stdc++.h>
using namespace std;
int a[100010];
int vis[100010];
int n;
int gcd(int a, int b)
{
if(b == 0)
{
return a;
}
return gcd(b, a % b);
}
int getgcd(int x)
{
int cnt = 0;
for(int i = 1; i <= n; i++)
{
if(i != x)
{
cnt = gcd(cnt, a[i]);
}
}
return cnt;
}
int main()
{
freopen("gcd.in", "r", stdin);
freopen("gcd.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
sort(a + 1, a + n + 1);
n = unique(a + 1, a + n + 1) - a - 1;
if(a[1] == 1) //对于另外 20% 的数据
{
printf("%d", getgcd(1));
}
else if(n <= 10000) //对于前 50% 的数据
{
int ans = 0;
for(int i = 1; i <= n; i++)
{
ans = max(ans, getgcd(i));
}
printf("%d", ans);
}
else
{
printf("1");
}
return 0;
}
时间复杂度 \(O(n^2)\)
正经做法
设 \(pre_i = \gcd(a_1, a_2, ···, a_i)\), 有 \(pre_i = \gcd(pre_{i-1}, a_i)\)
设 \(suf_i = \gcd(a_n, a_{n-1}, ···, a_i)\), 有 \(suf_i = \gcd(suf_{i+1}, a_i)\)
明显删去第 \(i\) 个数后的最大公因数是 \(\gcd(pre_{i-1}, suf_{i+1})\)
\(\mathfrak{Code\,Here}\)
// g++ "gcd.cpp" -Wall -std=c++14 -o "gcd"
// ./"gcd"
#include <bits/stdc++.h>
using namespace std;
int a[100010], pre[100010], suf[100010];
int main()
{
freopen("gcd.cpp", "r", stdin);
freopen("gcd.out", "w", stdout);
int n;
scanf("%d", &n);
if(n != 1)
{
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
pre[i] = __gcd(a[i], pre[i-1]);
}
for(int i = n; i >= 1; i--)
{
suf[i] = __gcd(a[i], suf[i+1]);
}
int ans = -114514;
for(int i = 1; i <= n; i++)
{
ans = max(ans, __gcd(pre[i-1], suf[i+1]));
}
printf("%d\n", ans);
}
else
{
printf("1000000000\n");
}
return 0;
}
时间复杂度 \(O(n)\)
Part 0x04 总结-Summary
- 不要死磕，不要死磕，不要死磕（重要的事情说三遍）
- 注意代码细节
- 存图应使用邻接表
- 当数据小的时候，可以使用
打表解决问题 - 考试注意文件名以及一定要测过了样例，没测样例基本 0 分
- 可以自己尝试造数据，需要使用
srand(time(0))和rand()函数 - 得到 \([l, r]\) 内的一个整数:
rand() % (r - l + 1) + l - 可以多写个暴力来跑自己造出来的数据
- 值域过大时不宜用桶，\(10^8\) 个 \(int = 380MB\)
- 做题时思路略显粗糙，要加强对于知识点的练习和写模板
- \(\gcd\) 具有「可重复贡献性质」，区间 \(\gcd\) 和区间最大值一样需要使用 \(\text{ST}\) 表
- \(\gcd\) 本质上是对指数取 \(\min\)