第三场

2025“钉耙编程”中国大学生算法设计春季联赛（3）¶

1001¶

明天补。

看了好久的。。幸好有题解且能看别人代码帮助我理解。

Lucas定理: https://oi-wiki.org/math/number-theory/lucas/ $$ \tbinom{x}{y}\equiv\tbinom{\lfloor x/p\rfloor}{\lfloor y/p\rfloor}\tbinom{x\%p}{y\%p}\mod p $$ 题目要求出满足以下条件的方案数 $$ \prod_{i=1}^{n} \binom{a_i}{b_i} \mod 2 = 1 $$ 所以我们需要每个 $\binom {a_i}{b_i}=1$ ，即 $a_i$ 和 $b_i$ 的二进制的每一位的组合数都为 $1$ ，也就是 $a_i$ 取 $0$ 的位， $b_i$ 不能为 $1$ ，其他的都可以。

但是有 $b_i\le Li$ 的条件，就很烦。

如果 $Li>=a_i$ 显然所有方案都能满足。

否则我们看 $a_i$ 和 $L_i$ 的二进制位

若 $L_i$ 的这一位为 $1$ ，$a_i$ 的这一位也为 $1$ 那么可以让 $a_i$ 的这一位为 $0$ ，后面则可以自由的选择所有方案。

若 $L_i$ 的这一位为 $1$ ，$a_i$ 的这一位为 $0$ 那么我们可以取得后面的所有数字，就可以直接跳出循环了。

为什么可以跳出循环呢？因为我们实际上，枚举到每一个位，我们加的方案数都是，$b_i$ 的前面的位和 $L_i$ 的前面是一模一样的，而这一位等于 $0$ ，就可以满足 $b_i\le L_i$ 的条件。而后面的位就可以随便取了。若 $a_i$ 的这一位等于 $0$ ，则我们之后不能保证前面全部相等了，所以需要退出循环。

但是由于每次我们都设置一位等于 $0$ ，若我们遇到的所有 $L_i$ 为 $1$ 的位， $a_i$ 也为 $1$ ，则实际上会少考虑 $b_i=L_i$ 的方案，所以需要给方案数 +$1$ 。

最终答案即为每一个 $b_i$ 的方案数的乘积。

constexpr int mod = 998244353;

void ChatGptDeepSeek()
{
    /*
    101
    101

    2+1
    */
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    ll ans = 1;
    for (int i = 1; i <= n; i++)
    {
        int L;
        cin >> L;
        if (L >= a[i])
        {
            int x = 0;
            for (int j = 30; j >= 0; j--)
                x += (a[i] >> j & 1);
            ans = ans * (1 << x) % mod;
            continue;
        }
        int cnt = 0, ok = 1;
        for (int j = 30; j >= 0; j--)
        {
            int x = a[i] >> j & 1;
            int y = L >> j & 1;
            if (y)
            {
                int bit = 0;
                for (int k = j - 1; k >= 0; k--)
                    bit += (a[i] >> k & 1);
                cnt = (cnt + (1 << bit)) % mod;
                if (x == 0)
                {
                    ok = 0;
                    break;
                }
            }
        }
        if (ok)
            cnt++;
        ans = ans * cnt % mod;
    }
    cout << ans << '\n';
}

1003¶

看题解还没太看明白。。原来这么妙的。。

统计对于每一个公司，不满足的能力的数量，若全部满足，则是可以下一次面试的公司。把所有的不满足的能力的公司，放进 $m$ 维的优先队列，当我们每次能力更新时，去检查对应的能力是否满足。

using pii = pair<int, int>;
using ll = long long;

void ChatGptDeepSeek()
{
    int n, m;
    cin >> n >> m;
    vector<ll> a(m + 1);
    for (int i = 1; i <= m; i++)
        cin >> a[i];
    vector<vector<int>> c(n + 1, vector<int>(m + 1)), w(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            cin >> c[i][j];
        for (int j = 1; j <= m; j++)
            cin >> w[i][j];
    }
    vector<priority_queue<pii, vector<pii>, greater<>>> pq(m + 1);
    queue<int> q;
    vector<int> cnt(n + 1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (c[i][j] > a[j])
            {
                pq[j].push({c[i][j], i});
                cnt[i]++;
            }
        }
        if (!cnt[i])
            q.push(i);
    }
    int ans = 0;
    while (!q.empty())
    {
        ans++;
        int k = q.front();
        q.pop();
        for (int i = 1; i <= m; i++)
        {
            a[i] += w[k][i];
            while (!pq[i].empty() && a[i] >= pq[i].top().first)
            {
                auto [_, j] = pq[i].top();
                pq[i].pop();
                cnt[j]--;
                if (!cnt[j])
                    q.push(j);
            }
        }
    }
    cout << (ans == n ? "YES\n" : "NO\n");
}

怎么说呢？我本来还在想，他是怎么用到优先队列，怎么更新能力值的。。。非常的牛。

1005¶

由于城市间是互相可以到达的，所以只需要求联通块的数量。

可以用 DFS 或并查集。

constexpr int N = 3e5 + 10;
int f[N + 1];

int find(int x)
{
    // cerr << x << " " << f[x] << '\n';
    return f[x] == x ? x : f[x] = find(f[x]);
}

void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        f[i] = i;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        // cerr << i << "\n";
        if (i - a[i] >= 1) {
            // cerr << i - a[i] << " " << find(i - a[i]) << '\n';

            f[find(i)] = find(i - a[i]);
            // f[i] = f[find(f[i - a[i]])];
        }
        if (i + a[i] <= n) {
            // cerr << i + a[i] << " " << find(i + a[i]) << '\n';
            f[find(i + a[i])] = find(f[i]);
            // f[i] = f[find(f[i + a[i]])];
        }

        // for (int j = 1; j <= n; j++)
        //     cerr << f[j] << " \n"[j == n];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (find(f[i]) == i)
            ans++;
        // cerr << f[i] << '\n';
    }
    cout << ans - 1 << '\n';
}

1010¶

$\mid x_0-x_1\mid+\mid y_0-y_1\mid=max(x_0-x_1+y_0-y_1,$

$x_1-x_0+y_0-y_1,x_0-x_1+y_1-y_0,x_1-x_0+y_1-y_0)$

所以到 $x_0,y_0$ 曼哈顿距离最大的点，一定是使得对应的 $x_1+y_1$ 或 $x_1-y_1$ 更大/更小。

void ChatGptDeepSeek()
{
    int n, m;
    cin >> n >> m;
    vector<int> x(n), y(n);
    vector<int> a(4);
    a[1] = a[3] = 2e9;
    a[0] = a[2] = -2e9;
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> y[i];
        a[0] = max(a[0], x[i] + y[i]);
        a[1] = min(a[1], x[i] + y[i]);
        a[2] = max(a[2], x[i] - y[i]);
        a[3] = min(a[3], x[i] - y[i]);
    }
    long long ans = 4e9;
    for (int i = 0; i < m; i++)
    {
        int X, Y;
        cin >> X >> Y;
        long long c = X + Y, d = X - Y;
        long long now = max({c - a[1], a[0] - c, a[2] - d, d - a[3]});
        ans = min(ans, now);
    }
    cout << ans << '\n';
}