GDUT 2020 年 ACM 第一次月赛 - 题解(全)

时间 10 月 18 日 13:00-17:00,面向 GDUT 2020 级新生。

过题情况参考:只计算新生,10 题过题 8 题或更多 6 人,5 题或更多 20 人,4 题或更多 35 人。

下面只提供关键代码供理解思路。笔者认为这套题非常适合 SCNU 2019 级的同学完成(大雾)。

如果你希望亲自完成这些题目请务必不要提前阅读题解,否则只会给你“这些题很简单”的错觉。

比赛链接 // 忽略链接中打错的标题

http://gdutcode.sinaapp.com/contest.php?cid=1124

题目已经上传到了 SCNUOJ

https://oj.socoding.cn/contest/view?id=13

A. 骗红包

(AC 提交共 20 份)

如果 n=1 ,显然先手 zf 胜。

如果 n>1 ,只要 n/2n-1 有一个是先手输,zf 就可以走这一步让 zn 输。

a[1] = 1;
for (int i = 2; i <= 1000; i++)
{
    if (a[i - 1] && a[i / 2]) a[i] = 0;
    else a[i] = 1;
}

B. Dio 的面包工坊

(AC 提交共 34 份)

结合平方差公式就可以知道,每个小面包的爱心值应该尽可能均等,那么枚举小面包个数即可。

ll ans = -1;
for (ll i = 1; i <= n; i++)
{
    ll a = n / i;
    ll b = n % i;
    ans = max(ans, qpow(a, i - b) * qpow(a + 1, b));
}

C. tmk 一衣带水

(AC 提交共 203 份)

签到题,直接输出即可。

cout << "tmknb!" << endl;

D. 三角切

(AC 提交共 61 份)

作业题,下面示例为判断锐角三角形。

sort(a, a + 3);
if (a[0] * a[0] + a[1] * a[1] > a[2] * a[2])
{
    cout << "Acute" << endl;
}

E. 素数判定

(AC 提交共 132 份)

模版题,下面是其中一种做法。

bool isprime(ll p)
{
    if (p == 2 || p == 3)
        return 1;
    if (p < 2 || (p % 6 != 1 && p % 6 != 5))
        return 0;
    for (T i = 5; i * i <= p; i = i + 6)
        if (p % i == 0 || p % (i + 2) == 0)
            return 0;
    return 1;
}

F. K 阶 Mex 数列

(AC 提交共 10 份)

直接按照题意模拟,能很快注意到 a_i=i \ \% \ (k+1)

cout << n % (k + 1) << endl;

G. 秧歌 Star 不要上补习班

(AC 提交共 30 份)

一种做法是二维前缀和,去年 SCNUSE 蓝桥杯热身赛防 AK 考过?

// 前缀和
for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + a[i][j];
    }
}
// 查询
cout << dp[x2][y2] + dp[x1 - 1][y1 - 1] - dp[x1 - 1][y2] - dp[x2][y1 - 1] << endl;

另一种做法是考虑到生物体系数量很少,使用下面的读入和存储方式,查询时直接暴力累加即可。

for (i = 1; i <= k; i++)
{
     cin >> x[i] >> y[i] >> v[i];
}

H. 一道难题

(AC 提交共 3 份)

考虑以下动态规划转移方程。

\left\{\begin{matrix} dp_i=dp_{i-1} \times 2 \ (i \leq m) \\ dp_i=dp_{i-1} \times 2 -dp_{i-m-1} \ (i > m) \end{matrix}\right.
dp[0] = 1;
for (int i = 1; i <= m; i++)
{
    dp[i] = (dp[i - 1] * 2) % MOD;
}
for (int i = m + 1; i <= n; i++)
{
    dp[i] = ((dp[i - 1] * 2) % MOD - (dp[i - m - 1]) % MOD) % MOD;
    dp[i] = (dp[i] + MOD) % MOD;
}

I. 超消函数

(AC 提交共 11 份)

实则是计算每个数的最大因数,查询时输出 fac[n]-1 即可。

for (int i = 1; i < MAXN; i++)
{
    bool flag = 0;
    for (int j = 2; j * j <= i; j++)
    {
        if (i % j == 0)
        {
            fac[i] = i / j;
            flag = 1;
            break;
        }
    }
    if (flag == 0) fac[i] = 1;
}
for (int i = 1; i < MAXN; i++)
{
    fac[i] += fac[i - 1];
}

J. 最大公因数排序

(AC 提交共 10 份)

两数交换始终借助 min 作中间者即可。

cout << "Yes" << endl;
4赞

:hear_no_evil::hear_no_evil::hear_no_evil: :cold_sweat:

粤 ICP 备 2020080455 号