2023 暑假集训模拟赛 Day 3

CareyBlog / 2023-07-26 / 原文

比赛题目共 \(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)\)