挖土机 CSP-J 模拟赛 ~ 第五场

达标率比拼

这题似乎有同学因为使用了 y1 作为全局变量挂掉了。

大家可以看看 首次参赛手册 最下面的“其他常见的代码错误”。

j0 j1 jn y0 y1 yn 在 <cmath> 中有定义，是贝塞尔函数的解。不要在全局变量用这些变量名。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a1, a2, a3, a4;
    int x1, x2, x3, x4;
    int b1, b2, b3, b4;
    int y1, y2, y3, y4;
    cin >> a1 >> a2 >> a3 >> a4;
    cin >> x1 >> x2 >> x3 >> x4;
    cin >> b1 >> b2 >> b3 >> b4;
    cin >> y1 >> y2 >> y3 >> y4;
    int a = a1 + a2 + a3 + a4;
    int x = x1 + x2 + x3 + x4;
    int b = b1 + b2 + b3 + b4;
    int y = y1 + y2 + y3 + y4;
    if (x * b > y * a)
        cout << "A";
    else if (x * b < y * a)
        cout << "B";
    else
        cout << "33DAI";
    return 0;
}

区间开方和

90 分就不多说了。满分除了做法本身之外还有两个问题：

• 一个是要用 __int128 或者高精度。这题最后 $10$ 主要就是为了科普一下 __int128 的用法。__int128 是 128 位二进制数，也就是能存得下 long long * long long，运算速度会稍微的慢一丢丢，然后不能直接用 cin/cout 读写。一般会直接读进来一个 long long 然后赋值过去，或者逐个读字符类似快读的方法拼凑。输出时可以像我下面代码一样递归一位位转成可以输出的类型输出即可。
• 另一个是直接用 sqrt 的精度不够，一定要注意 sqrt 默认参数和返回值都是 double 类型，对 int 以上的数据范围开方时精度很大概率不够。当然这题也不能手写二分，时间复杂度会不够，我看有一位同学就是用了 __int128 但是每个算术平方根都是用二分求的出的问题。

那满分怎么做呢？暴力枚举 1e14 肯定超呀。其实我们会发现算术平方根只有 1e8 种，可以反向求解每个算术平方根对应的数有几个来计算即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
void outInt128(__int128 x)
{
    int num = x % 10;
    if (x / 10 > 0)
        outInt128(x / 10);
    cout << num;
}
signed main()
{
    int l, r;
    cin >> l >> r;
    __int128 sum = 0;
    for (int i = 1; i <= 10000000; i++)
    {
        __int128 L = i * i;
        __int128 R = (i + 1) * (i + 1) - 1;
        if (R < l)
            continue;
        if (L > r)
            break;
        if (R > r)
            R = r;
        if (L < l)
            L = l;
        sum += i * (R - L + 1);
    }
    outInt128(sum);
    return 0;
}

多少种得分

部分分给了很多爆搜的分，满分就是个分组背包的小变种，没啥好说的。

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> e[105];
bool f[105][10000 + 5];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int num, x;
        cin >> num;
        for (int j = 1; j <= num; j++)
        {
            cin >> x;
            e[i].push_back(x);
        }
    }
    f[0][0] = true;
    for (int i = 1; i <= n; i++)
        for (int v = 10000; v >= 0; v--)
            for (int j = 0; j < e[i].size(); j++)
            {
                int now = e[i][j];
                if (v >= now)
                    f[i][v] = f[i][v] | f[i - 1][v - now];
            }
    int ans = 0;
    for (int i = 0; i <= 10000; i++)
        if (f[n][i])
            ans++;
    cout << ans;
    return 0;
}

拉多少个群

想想好久没出麻烦一点的构造题了，其实这题想清楚后就很简单。

• 子任务 1：就两个人，可以拉 $10$ 个群，直接第一个群有两个人你，然后两个人分别自己待一个单人群就好了。
• 子任务 2：每个群都能放进去所有人，能拉 $n+1$ 个群。通过第一个子任务的经验，显然发现可以直接先拉 $n$ 个单人群就搞定了后两个规则。然后还有一个群直接拉一个所有人的群就好了。
• 子任务 3：每个群两个人，那直接任意两个人之间拉一个群就好了。
• 子任务 4：因为 $m$ 这个限制，显然第一个人需要 $\frac{n-1}{m-1}$ 个群才能和其他人建立联系，所以 $k$ 的数据范围就给了那么宽松的范围（其实本来准备给 $n\times \lceil \frac{n-1}{m-1}\rceil$ 然后写错了）。显然只要每个人都和所有没有同群的人拉个群就好了。

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int tot;
vector<int> e[105];
set<int> ee[105]; // ee[1] 存 1 和哪些人已经在一个群了
int main()
{
    freopen("group.in", "r", stdin);
    freopen("group.out", "w", stdout);
    cin >> n >> m >> k;
    // 子任务 1
    if (n == 2)
    {
        cout << "3\n";
        cout << "2 1 2\n";
        cout << "1 1\n";
        cout << "1 2\n";
        return 0;
    }
    // 子任务 2
    if (m == n)
    {
        cout << n + 1 << "\n";
        cout << n << " ";
        for (int i = 1; i <= n; i++)
            cout << i << " ";
        cout << "\n";
        for (int i = 1; i <= n; i++)
            cout << "1 " << i << "\n";
        return 0;
    }
    // 子任务 3
    if (m == 2)
    {
        cout << n * (n - 1) / 2 << "\n";
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                cout << "2 " << i << " " << j << "\n";
        return 0;
    }
    // 子任务 4
    for (int i = 1; i <= n; i++)
    {
        tot++;
        ee[i].insert(i);
        e[tot].push_back(i);
        for (int j = 1; j <= n; j++)
        {
            if (ee[i].count(j))
                continue;
            if (e[tot].size() < m)
            {
                for (int k = 0; k < e[tot].size(); k++)
                {
                    ee[j].insert(e[tot][k]);
                    ee[e[tot][k]].insert(j);
                }
                e[tot].push_back(j);
            }
            else
            {
                tot++;
                e[tot].push_back(i);
                e[tot].push_back(j);
                ee[i].insert(j);
                ee[j].insert(i);
            }
        }
    }
    cout << tot << "\n";
    for (int i = 1; i <= tot; i++)
    {
        cout << e[i].size() << " ";
        for (int j = 0; j < e[i].size(); j++)
            cout << e[i][j] << " ";
        cout << "\n";
    }
    return 0;
}