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

33DAI2024年12月24日大约 3 分钟

瞒天过海

简单替换，这边给一个类似于“位运算遍历二进制每一位”的遍历十进制每一位的小技巧。直接数位分解当然没什么问题。直接读一个字符串自然也更没什么问题了。

#include <bits/stdc++.h>
using namespace std;
string t = "olz34sb78q";
int a;
int main()
{
    freopen("man.in", "r", stdin);
    freopen("man.out", "w", stdout);
    cin >> a;
    bool zero = true;
    for (int i = 1000000000; i >= 1; i /= 10)
    {
        int now = a / i % 10;
        if (now > 0 || !zero)
        {
            cout << t[a / i % 10];
            zero = false;
        }
    }
    return 0;
}

围魏救赵

其实就是贪心先用 $a_{i}$ 大的去消耗 $m$ 就好。但细节有点多，可以多想想再写。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, k;
int a[1005];
int b[1005];
signed main()
{
    freopen("wei.in", "r", stdin);
    freopen("wei.out", "w", stdout);
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++)
        cin >> a[i];
    for (int i = 1; i <= k; i++)
        cin >> b[i];
    for (int i = 1; i <= k; i++)
        for (int j = i + 1; j <= k; j++)
            if (a[j] > a[i])
            {
                swap(a[i], a[j]);
                swap(b[i], b[j]);
            }
    for (int i = 1; i <= k; i++)
    {
        // cout << a[i] << " " << b[i] << "\n";
        if (a[i] == 1 || m == 0 || n == 0)
            break;
        // 尽可能消耗 n, num 为能消耗多少 n
        int num = min(b[i], (m + (a[i] - 1)) / a[i]);
        n = max(0LL, n - num);
        m = max(0LL, m - num * a[i]);
    }
    if (n > m)
        cout << n - m;
    else
        cout << "No";
    return 0;
}

借刀杀人

题目来源：https://www.luogu.com.cn/problem/CF900B

显然就是模拟看每一位，遇到循环了还没找到就停。但是需要注意，可以手算一下除法什么时候出现循环节，容易发现是当余数出现过了，或者说当前被除数已经出现过了就循环了。

或者直接暴力做 $b + 5$ 次，因为余数最多就 $b$ 种可能，直接多做几次可以保证没错也不用想那么多。

#include <bits/stdc++.h>
using namespace std;
int a, b, c, now;
bool f[100000 + 5];
int main()
{
    freopen("jie.in", "r", stdin);
    freopen("jie.out", "w", stdout);
    cin >> a >> b >> c;
    int cnt = 1;
    while (!f[a])
    {
        f[a] = true;
        a = a * 10;
        now = a / b;
        if (now == c)
        {
            cout << cnt;
            return 0;
        }
        a = a % b;
        cnt++;
    }
    cout << 0;
    return 0;
}

以逸待劳

最暴力的做法显然是直接枚举所有选择方案，再来一个个用户检查是否符合条件，时间复杂度 $O (n^{4} m)$ 。能拿不少分。

此时我们可以简单想想什么情况下是不行的。对于每个人来说，就是所有他做过的题只能出现一个，反向想想，也就是他做过的题之间任意两个都是冲突的。可以直接 $O (m n^{2})$ 预处理出冲突数组（描述任意两道题是否冲突）。这样 $O (n^{4})$ 枚举后就只要 $4^{2}$ 检查是否有冲突。总体来说就是道数据范围题，不是很难。

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1000 + 5][88 + 5];
bool b[88 + 5][88 + 5];
int cnt, ans[4 + 5];
void dfs(int now, int st)
{
    if (now == 5)
    {
        for (int i = 1; i <= 4; i++)
            for (int j = i + 1; j <= 4; j++)
                if (b[ans[i]][ans[j]])
                    return;
        // for (int i = 1; i <= 4; i++)
        //     cout << ans[i] << " ";
        // cout << "\n";
        cnt++;
        return;
    }
    for (int i = st; i <= n; i++)
    {
        ans[now] = i;
        dfs(now + 1, i + 1);
    }
}
int main()
{
    freopen("yi.in", "r", stdin);
    freopen("yi.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
        for (int j = 1; j <= n; j++)
            for (int k = j + 1; k <= n; k++)
                if (a[i][j] && a[i][k])
                    b[j][k] = b[k][j] = 1;
    }
    cnt = 0;
    dfs(1, 1);
    cout << cnt;
    return 0;
}