2023 暑假集训模拟赛 Day 2

CareyBlog / 2023-07-25 / 原文

比赛题目共2套，其中初赛题1套，复赛2题。

比赛时间: \(10:50 - 12:00 a.m\)

Part 0x01 过程-Process

\(8:40\,a.m.\) 做初赛题目；

\(10:40\,a.m.\) 拿到题目；

\(10:51\,a.m.\) 先写 \(\text{T2}\)，发现是初赛考过的题目，但时限变小；

\(11:20\,a.m.\) 在 \(\text{T2}\) 上花了太久，没调出来，赶紧写 \(\text{T1}\)；

\(11:35\,a.m.\) 终于把 \(\text{T1}\) 写完了，估计能过。

\(11:36\,a.m.\) 接着看 \(\text{T2}\)，突然发现理解错题目了，但是样例 \(2\) 没过……

\(12:00\,a.m.\) \(\text{T2}\) 发现了一些问题，但是样例 \(2\) 还是没过。

总分 \(= 100pts + 30pts = 130pts\)。

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\) ，加减法无需特判，同时也可以根据最高位判断是否是负数。
浮点数由尾数和阶码构成。
只给出前序遍历与后序遍历的情况下无法确认二叉树。

Part 0x03 复赛题目-Problem

T1 最大乘积

题链

暴力枚举 \(i\)，使用前缀和优化求和过程即可，

\(\mathfrak{Code\,Here}\)

// g++ "times.cpp" -Wall -std=c++14 -o "times"
// ./"times"

#include <bits/stdc++.h>

using namespace std;

long long a[100010], pre[100010];
vector <long long> ans;
long long Max = -1919810;

long long query(long long L, long long R)
{
    return pre[R] - pre[L-1];
}

int main()
{
    freopen("times.in", "r", stdin);
    freopen("times.out", "w", stdout);

    long long n, l, r;

    scanf("%lld %lld %lld", &n, &l, &r);

    for(long long i = 1; i <= n; i++)
    {
        scanf("%lld", &a[i]);

        pre[i] = pre[i-1] + a[i];
    }

    for(long long i = 1; i <= n; i++)
    {
        Max = max(Max, query(max(i-l, 1ll), i) * query(i, min(n, i+r)));
    }

    for(long long i = 1; i <= n; i++)
    {
        if(query(max(i-l, 1ll), i) * query(i, min(n, i+r)) == Max)
        {
            printf("%lld ", i);
        }
    }

    return 0;
}

时间复杂度 \(O(n)\)

T2 和谐数对

题链

暴力

考场做法，模拟即可。

\(\mathfrak{Code\,Here\,(60pts)}\)

// g++ "number.cpp" -Wall -std=c++14 -o "number"
// ./"number"

#include <bits/stdc++.h>

int getlast(int x)
{
    return x / pow(10, (int)log10(x));
}

bool check(int i, int j)
{
    return (i % 10 == getlast(j)) && (getlast(i) == j % 10);
}

int calc(int n)
{
    int ans = 0;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(check(i, j) == true)
            {
                ans++;
//                printf("(%d %d)\n", i, j);
            }
        }
    }

    return ans;
}

int main()
{
    int n;

    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);

    scanf("%d", &n);
    printf("%d", calc(n));

    return 0;
}

时间复杂度 \(O(n^2)\)

正经做法

设 \(dp_{i, j}\) 为数字中以 \(i\) 开头并且以 \(j\) 结尾的数的个数，明显有：

\[answer = \sum_{i = 0}^{9}\sum_{j = 0}^{9} dp_{i,j} × dp_{j,i} \]

\(\mathfrak{Code\,Here}\)

// g++ "number.cpp" -Wall -std=c++14 -o "number"
// ./"number"

#include <bits/stdc++.h>

long long dp[20][20];

long long getlast(long long x)
{
    return x / pow(10, (long long)log10(x));
}

long long calc(long long n)
{
    for(long long i = 1; i <= n; i++)
    {
        dp[i % 10][getlast(i)] ++;
    }

    long long ans = 0;

    for(long long i = 0; i <= 9; i++)
    {
        for(long long j = 0; j <= 9; j++)
        {
            ans += dp[i][j] * dp[j][i];
        }
    }

    return ans;
}

int main()
{
    long long n;

    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);

    scanf("%lld", &n);
    printf("%lld", calc(n));

    return 0;
}

时间复杂度 \(O(n)\)