SCNUOJ (DOMjudge) 试机赛题解

既然是试机赛那就随便出了。自认为这套题对新生还是很友好的,当然这套题跟正式校赛难度无关哈…

acm.socoding.cn/public/change-contest/6

A. Easy Counting Problem

等式左右两边平方, i+j+2 \sqrt {ij}=k ,发现要使 k 为整数,必需要令 i \cdot j 为完全平方数,所以我们就枚举完全平方数,然后再枚举这些完全平方数的因数。

Code
#include <bits/stdc++.h>
using namespace std;
int n, ans;
int main()
{
    cin >> n;
    for (int i = 1; i * i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            if (i * i % j == 0)
            {
                ans += 2;
            }
        }
        ans--;
    }
    cout << ans << endl;
    return 0;
}

B. Easy Construction Problem

签到,直接输出左端点(或者输出右端点)。

Code
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int l, r;
        cin >> l >> r;
        cout << l << endl;
    }
    return 0;
}

C. Hard Combinatorial Problem

还是这道题,做了蓝桥杯国赛训练的同学应该被 1 \leq n,m \leq 3 \times 10^6 的原题整懵了,就削了范围。

D. Medium Query Problem

题目都直接告诉你抄完板子就完事了… 下面两个板子是将某个数加上 k ,这题是设置为 v

即使不会改板子,我先把 a_i 给查询出来,然后把问题变成将某个数加上 v-a_i 还是一回事。

https://www.luogu.com.cn/problem/P3374

https://www.luogu.com.cn/problem/P3372

E. Medium Game Theory Problem

找规律,发现当糖果数是 2^n 的时候输出 NO ,否则输出 YES

如果不是 2^n ,先手可直接拿等同于当前糖果数二进制最低位的数量的糖果数。
由于后手拿的糖果数量不能多于先手,意味着后手无论如何取都不会让糖果数二进制 1 的数量变少。

如果是 2^n ,由于先手无法直接取完,取完第一次后糖果数二进制 1 的数量至少为 1
此时后手可以拿等同于当前糖果数二进制最低位的数量的糖果数,那就回到了前面的情况,从而取得胜利。

判断是不是 2^n 的代码实现也可使用 __builtin_popcount(int x)__builtin_popcountll(long long x) 或者任意你喜欢的方式。

Code
#include <bits/stdc++.h>
using namespace std;

long long lowbit(long long x)
{
    return x & (-x);
}

int main()
{
    long long n;
    cin >> n;
    if (lowbit(n) == n)
    {
        cout << "NO" << endl;
        return 0;
    }
    cout << "YES" << endl;
    return 0;
}

F. Easy String Problem

贪心。要修改一个字符,显然直接修改比先移除(再增补)更快。故对于前 min(l_a,l_b) 个字符用此方式即可。如果还有 l_a \neq l_b ,接下来增补较短的字符串或者移除较长的字符串多出来的部分就可以了。

Code
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, m, ans = 0;
    cin >> n >> m;
    string a, b;
    cin >> a >> b;

    if (n < m)
    {
        swap(n, m);
        swap(a, b);
    }

    for (int i = 0; i < m; i++)
    {
        if (a[i] != b[i])
        {
            ans++;
        }
    }
    ans += n - m;
    cout << ans << endl;
    return 0;
}

G. Medium Graph Problem

注意到从一个点出发,沿着出边一路 DFS 下去,一定会走到一个环,此时就可以结束统计。

为了避免超时,可记忆化答案,用 cnt_u 表示从 u 出发的最长简单路径的结点数量。那么假设我某次 DFS 到一个曾经访问过的节点 v ,直接返回 cnt_v+1 就行了,不用继续 DFS。特别地,如果 cnt_v 还没被更新过,说明发现了一个没访问过的环。考虑到我在选取其它结点作为起点 DFS 时可能会从不同的地方再次进入这个环,应该把这个环上的所有结点的 cnt 值统一(从环上任意一点出发 cnt 的值都应该是环上结点的数量),这样才能保证粗体字部分的正确性。

Code
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;

int G[MAXN], cnt[MAXN];
bool vis[MAXN];
int max_cnt_node;

int dfs(int x)
{
    vis[x] = 1;
    if (vis[G[x]] != 0)
    {
        cnt[x] = cnt[G[x]] + 1;
        if (cnt[G[x]] == 0)
        {
            max_cnt_node = G[x];
        }
        return cnt[x];
    }
    return cnt[x] = dfs(G[x]) + 1;
}

void update(int u, int v)
{
    cnt[u] = cnt[v];
    if (G[u] != v)
    {
        update(G[u], v);
    }
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> G[i];
    }
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == 0)
        {
            max_cnt_node = -1;
            dfs(i);
            if (max_cnt_node != -1)
            {
                update(max_cnt_node, max_cnt_node);
            }
        }
    }
    sort(cnt + 1, cnt + n + 1);
    cout << cnt[n] << endl;
    return 0;
}
1赞
粤 ICP 备 2020080455 号