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

神好清，而心扰之

题目怎么说，我们就怎么做。我给个只学过条件判断的做法。有些同学会在 $2233$ 这样的两个对子的数据点挂掉。

#include <bits/stdc++.h>
using namespace std;
char temp;
int a, b, c, d;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> temp;
    a = temp - '0';
    cin >> temp;
    b = temp - '0';
    cin >> temp;
    c = temp - '0';
    cin >> temp;
    d = temp - '0';

    int ans = a + b + c + d;

    if (a == b && b == c && c == d)
        ans += b * b * b * b;
    else if (a == b && b == c || b == c && c == d)
        ans += b * b * b;
    else if (a == b && c == d)
        ans += a * a + c * c;
    else if (a == b || b == c)
        ans += b * b;
    else if (c == d)
        ans += c * c;

    if (a == 8 || a == 6)
        ans *= 2;
    if (b == 8 || b == 6)
        ans *= 2;
    if (c == 8 || c == 6)
        ans *= 2;
    if (d == 8 || d == 6)
        ans *= 2;

    cout << ans;
    return 0;
}

心好静，而欲牵之

诈骗题。由这题大家也能感受到并查集用了路径压缩和按秩合并之后，在信息学竞赛中几乎可以当作是 $O(1)$ 用了。

• $\text{akm}(0,0)=1$
• $\text{akm}(1,1)=3$
• $\text{akm}(2,2)=7$
• $\text{akm}(3,3)=61$
• $\text{akm}(4,2)=2^{65536}-3$
• $\text{akm}(4,4)=2^{2^{2^{2^{2^{2^2}}}}}-3$ 远超 ${10}^{18}$，所以答案只有 $0,1,2,3$ 四种。

很多同学这题没注意输入输出优化挂掉。很容易忽视掉非常多行输出时的 endl 会刷新缓冲区导致超时。

#include <bits/stdc++.h>
using namespace std;
int f[] = {1, 3, 7, 61};
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        long long n;
        cin >> n;
        if (1 <= n && n < 3)
            cout << 0 << "\n";
        else if (3 <= n && n < 7)
            cout << 1 << "\n";
        else if (7 <= n && n < 61)
            cout << 2 << "\n";
        else if (61 <= n)
            cout << 3 << "\n";
    }
    return 0;
}

遣其欲，而心自静

显然只有两种情况：$p_1\times p_2$ 或者 $p_1^3$（$p_1,p_2$ 为质数）。所以可以先打个质数表（用埃氏筛就够了），然后枚举 $p_1$ 算算有多少个 $p_2$ 满足 $p_1\times p_2\le n$（二分或者双指针都可以）。

当然如果你记得唯一分解定理，那么也可以直接快速求出来每个数的因子个数，搭配欧拉筛甚至能做到 $O(n)$ 处理出来 $1\sim n$ 每个数的因子个数，就更简单了。

#include <bits/stdc++.h>
using namespace std;
int n;
bool f[10000000 + 5];
vector<int> p;
int main()
{
    cin >> n;
    f[0] = f[1] = true;
    for (int i = 2; i <= n; i++)
    {
        if (!f[i])
        {
            p.push_back(i);
            for (int j = i + i; j <= n; j += i)
                f[j] = true;
        }
    }
    // p1*p2 <= n
    int ans = 0;
    for (int i = 0; i < p.size(); i++)
    {
        // 最后一个小于等于 n/p[1] 的数
        int pos = upper_bound(p.begin(), p.end(), n / p[i]) - p.begin() - 1;
        if (pos <= i)
            break;
        ans += pos - i;
    }
    // p1 * p1 * p1
    for (int i = 0; i < p.size(); i++)
        if (p[i] * p[i] * p[i] > n)
        {
            ans += i;
            break;
        }
    cout << ans;
    return 0;
}

澄其心，而神自清

10 分

每个词都没有含义，直接输出原文的值即可。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1'000'000'000 + 7;
int n, m;
string seq[100005];
map<string, vector<string>> e;
int cal(string &s)
{
    int a = s[0];
    int b = s[1];
    int c = s[2];
    int d = s[3];
    return a + b + c + d;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> seq[i];
    for (int i = 1; i <= m; i++)
    {
        string s, t;
        int num;
        cin >> s;
        cin >> num;
        while (num--)
        {
            cin >> t;
            e[s].push_back(t);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += cal(seq[i]);
        ans %= MOD;
    }
    cout << ans;
    return 0;
}

30 分

其实可以先把字符串对应到一个 $26$ 进制整数再处理（如果不是定长的字符串就需要 $27$ 进制）。但反正不超时，我给一个 map<string, vector<string>> 的代码。注意这样写的话查 e["xxxx"] 就自带一个 $\log$ 了。

30 分只有一层含义，直接有含义就做一层就好了。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1'000'000'000 + 7;
int n, m;
string seq[100005];
map<string, vector<string>> e;
int cal(string &s)
{
    int a = s[0];
    int b = s[1];
    int c = s[2];
    int d = s[3];
    return a + b + c + d;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> seq[i];
    for (int i = 1; i <= m; i++)
    {
        string s, t;
        int num;
        cin >> s;
        cin >> num;
        while (num--)
        {
            cin >> t;
            e[s].push_back(t);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (e.find(seq[i]) == e.end())
        {
            ans += cal(seq[i]);
            ans %= MOD;
        }
        else
        {
            for (auto x : e[seq[i]])
            {
                ans += cal(x);
                ans %= MOD;
            }
        }
    }
    cout << ans;
    return 0;
}

60 分

虽然有多层含义，但是最终文章也不长，所以直接暴力递归算就好了。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1'000'000'000 + 7;
int n, m;
string seq[100005];
map<string, vector<string>> e;
int cal(string &s)
{
    // 没有额外含义
    if (e.find(s) == e.end())
    {
        int res = 0;
        for (char x : s)
            res += (int)x;
        return res;
    }
    // 算出来每个含义的值，求和
    int res = 0;
    for (string &x : e[s])
    {
        res += cal(x);
        res %= MOD;
    }
    return res;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> seq[i];
    for (int i = 1; i <= m; i++)
    {
        string s, t;
        int num;
        cin >> s;
        cin >> num;
        while (num--)
        {
            cin >> t;
            e[s].push_back(t);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += cal(seq[i]);
        ans %= MOD;
    }
    cout << ans;
    return 0;
}

100 分

显然每次算某个词的时候，最终展开求出来的值是一样的，记忆化加上就好了。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1'000'000'000 + 7;
int n, m;
string seq[100005];
map<string, vector<string>> e;
map<string, int> rnk;
int cal(string &s)
{
    if (rnk.find(s) != rnk.end())
        return rnk[s];
    // 没有额外含义
    if (e.find(s) == e.end())
    {
        int res = 0;
        for (char x : s)
            res += (int)x;
        return rnk[s] = res;
    }
    // 算出来每个含义的值，求和
    int res = 0;
    for (string &x : e[s])
    {
        res += cal(x);
        res %= MOD;
    }
    return rnk[s] = res;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> seq[i];
    for (int i = 1; i <= m; i++)
    {
        string s, t;
        int num;
        cin >> s;
        cin >> num;
        while (num--)
        {
            cin >> t;
            e[s].push_back(t);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += cal(seq[i]);
        ans %= MOD;
    }
    cout << ans;
    return 0;
}