Kendieer

题解题解 | 小白月赛 Round 128

题解

/ 注册

题解 | 小白月赛 Round 128

19 浏览 0 回复 2026-01-30

Kendieer

+关注

https://ac.nowcoder.com/acm/contest/127265/F

参考代码放在最后面。

思路

A.模糊匹配

按照题意直接替换后比较即可。

B.只留专一数

由于幂运算不会影响质因数个数，所以我们可以将操作视作删除 $a_j$ ，所以只需找到原数组是否存在质因数个数 $\le 1$ 的数即可。

C.左右左右左左右，左右左左右

考虑贪心，每步保证最优，即只需满足 $|a_0\cdot\texttt{pc}(i,1)-a_1\cdot\texttt{pc}(i,0)|$ 最小化即可。

所以可以枚举下一步插入 $0$ 或者 $1$ 进行枚举，取最优即可。

D.进退的艺术

由于序列顺序不会影响结果，所以可以进行排序，然后考虑贡献组成即可：（设当前为 $i$ 索引）

满足 $a_i+a_j\le m$ ，我们可以用二分找出 $\le m-a_i$ 的数量，然后加上对应数量的 $a_i$ 即可。
否则，我们需要得出所有满足条件 $a_j$ 的和，然后减去即可。

上面两步都可以通过排序后容易得出，二分出对应位置，得出其对应后缀和

特别需要讨论的是： $i=j$ 时，需要考虑两种情况下分别处理。

时间复杂度为 $O(n\log n)$

E.扫雷难度调节

首先考虑什么情况下数字数量是最大化的。

当一个雷周围八格都是非雷时，数字数量是最大化的。

所以

000000\cdots \\ 010010\cdots \\ 000000\cdots

是最优的，此时只需考虑 $n=3x+1$ 和 $m=3y+1$ 的情况即可。（因为没有足够的空间容纳下一个 $3\times 3$ 模块中的 $1$ 。）

于是考虑把剩余部分也填充雷，即 $0100100\cdots$ 。

如果数字多了，直接改成 $1$ 即可。

F.徽章计数

记 $cnt_i$ 表示 $a_j = i$ 的数量。

特判无解情况：

$cnt_i$ 无法被 $i$ 整除。
徽章种类不足，即 $\sum \frac{cnt_i}{i} \gt m$ 。

考虑贡献拆分，拆分成从 $m$ 种徽章中选 $k$ 种徽章的方案数和选 $k$ 种特定徽章下分配的数量。

前者很好算，直接 $A(m,k)$ 即可。

后者我们需要对于每一个 $i$ 计算 $cnt_i$ 个小朋友分配 $\frac{cnt_i}{i}$ 种徽章下不同的方案数，由于前者已经全排列了颜色情况，所以对应需要除去 $\frac{cnt_i}{i}!$ 用于去重，所以公式为 $\frac{cnt_i!}{i!^{\frac{cnt_i}{i}}\cdot \frac{cnt_i}{i}!}$

时间复杂度度为 $O(n)$ 到 $O(n\log n)$ 。

代码

A.模糊匹配

void solve(){
    int n;
    cin >> n;
    string a,b;
    cin >> a >> b;
    for (auto &ch : a){
        if (ch == 'I' || ch == 'l' || ch == '1') ch = 'I';
        if (ch == 'O' || ch == '0') ch = '0';
    }
    for (auto &ch : b){
        if (ch == 'I' || ch == 'l' || ch == '1') ch = 'I';
        if (ch == 'O' || ch == '0') ch = '0';
    }
    cout << (a == b ? "YES\n" : "NO\n");
}

B.只留专一数

namespace Prime{
    std::vector<int> cnt;
    std::vector<bool> np;
    constexpr int N = 1e3+7;
    void Eratosthenes(){
        for (int i = 2;i < N;i ++){
            if (np[i]) continue;
            for (int j = i<<1;j < N;j += i) {
                np[j] = 1;
                cnt[j]++;
            }
        }
    }
    void init(){
        np.resize(N);
        cnt.resize(N);
        np[0] = np[1] = 1;
        cnt[0] = cnt[1] = 0;
        Eratosthenes();
    }
}
using Prime::cnt;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n+1);
    for (int i = 1;i <= n;i++) cin >> a[i];
    bool flag = 0;
    for (int i = 1;i <= n;i++) {
        if (cnt[a[i]] <= 1) flag = 1;
    }
    cout << (flag ? "YES\n" : "NO\n");
}

C.左右左右左左右，左右左左右

using i64 = long long;
void solve(){
    i64 n,a,b;
    cin >> n >> a >> b;
    p64 cnt = {0,0};
    for (int i = 1;i <= n;i++){
        i64 x = cnt[0] * b,y = cnt[1] * a;
        if (abs(x+b-y) <= abs(y+a-x)) cout << "0",cnt[0]++;
        else cout << "1",cnt[1]++;
    }
    cout << '\n';
}

D.进退的艺术

using i64 = long long;
using p64 = array<i64,2>;
void solve(){
    int n,m;
    cin >> n >> m;
    vector<p64> a(n+1);
    vector<i64> c(n+1);
    for (int i = 1;i <= n;i++){
        a[i][1] = i;
        cin >> a[i][0];
    }
    sort(a.begin()+1,a.end());
    vector<i64> b(n+1),suf(n+2);
    for (int i = 1;i <= n;i++) b[i] = a[i][0];
    for (int i = n;i > 0;i--) suf[i] += suf[i+1] + b[i];
    for (int i = 1;i <= n;i++){
        int j = upper_bound(b.begin()+1,b.end(),m-b[i]) - b.begin();
        if (i < j) {
            c[i] -= suf[j];
            c[i] += i64(j-2) * b[i];
        } else {
            c[i] -= suf[j] - b[i];
            c[i] += i64(j-1) * b[i];
        }
    }
    for (int i = 1;i <= n;i++) {
        a[i][0] = c[i];
    }
    sort(a.begin()+1,a.end(),[](p64 x,p64 y)->bool {
        return x[1] < y[1];
    });
    for (int i = 1;i <= n;i++) {
        cout << a[i][0] << " \n"[i==n];
    }
}

E.扫雷难度调节

void solve(){
    int n,m,k;
    cin >> n >> m >> k;
    vector<vector<bool>> vis(n+1,vector<bool>(m+1));
    bool flag = 1;
    int cnt = n*m;
    for (int i = 2;i <= n;i += 3){
        for (int j = 2;j <= m;j += 3){
            vis[i][j] = 1;
            cnt--;
        }
    }
    if (n % 3 == 1){
        for (int j = 2;j <= m;j += 3){
            vis[n][j] = 1;
            cnt--;
        }
    }
    if (m % 3 == 1){
        for (int i = 2;i <= n;i += 3){
            vis[i][m] = 1;
            cnt--;
        }
    }
    if (n%3 == 1 && m%3 == 1){
        cnt--;
        vis[n][m] = 1;
    }
    if (cnt < k) flag = 0;
    else {
        for (int i = 1;i <= n;i++){
            for (int j = 1;j <= m;j++){
                if (vis[i][j]) continue;
                if (cnt > k) {
                    cnt--;
                    vis[i][j] = 1;
                }
            }
        }
    }
    if (flag){
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= m;j++){
                cout << vis[i][j];
            }
            cout << "\n";
        }
    } else {
        cout << -1 << "\n";
    }
}

F.徽章计数

void solve(){
    int n,m;
    cin >> n >> m;
    vector<int> cnt(n+1),a(n+1),tot(n+1);
    int req = 0;
    Z ans = 1;
    for (int i = 1;i <= n;i++){
        cin >> a[i];
        cnt[a[i]]++;
        tot[a[i]]++;
        if (cnt[a[i]] == a[i]) {
            cnt[a[i]] = 0;
            req ++;
        }
    }
    for (int i = 1;i <= n;i++) {
        if (cnt[i] > 0) {
            cout << 0 << "\n";
            return;
        }
    }
    if (req > m){
        cout << 0 << "\n";
        return;
    }
    for (int i = 0;i < req;i++) ans *= m-i;
    for (int i = 1;i <= n;i++){
        if (tot[i] == 0) continue;
        int col = tot[i] / i;
        Z res = comb.A(tot[i],tot[i]);
        for (int j = 1;j <= col;j++){
            res *= comb.inv[i];
        }
        res /= comb.A(col,col);
        ans *= res;
    }
    cout << ans << "\n";
}

模版

取模类与组合数

template <long long MOD>
struct ModInt{
    long long val = 0;
    ModInt(long long x = 0):val(norm(x)){}
    long long operator()(){ return val; }
    constexpr ModInt operator-() const {
        return ModInt(MOD - val);
    }
    constexpr ModInt operator~() const {
        assert(val != 0);
        return Pow(val,MOD-2);
    }
    constexpr ModInt& operator+=(ModInt x){
        return val += x(),val = norm(val),*this;
    }
    constexpr ModInt& operator-=(ModInt x){
        return val -= x(),val = norm(val),*this;
    }
    constexpr ModInt& operator*=(ModInt x){
        return val *= x(),val = norm(val),*this;
    }
    constexpr ModInt& operator/=(ModInt x){
        return val *= (~x)(),val = norm(val),*this;
    }
    constexpr ModInt& operator^=(long long y){
        return val = Pow(*this,y)(),*this;
    }
    constexpr ModInt& operator++(){
        return val ++,val = norm(val),*this;
    }
    constexpr ModInt operator++(int){
        ModInt v = *this;
        return val ++,val = norm(val),v;
    }
    constexpr ModInt& operator--(){
        return val --,val = norm(val),*this;
    }
    constexpr ModInt operator--(int){
        ModInt v = *this;
        return val --,val = norm(val),v;
    }
    constexpr friend ModInt operator+(ModInt x, ModInt y){
        return x += y;
    }
    constexpr friend ModInt operator-(ModInt x, ModInt y){
        return x -= y;
    }
    constexpr friend ModInt operator*(ModInt x, ModInt y){
        return x *= y;
    }
    constexpr friend ModInt operator/(ModInt x, ModInt y){
        return x /= y;
    }
    constexpr friend ModInt operator^(ModInt x, long long y){
        return x ^= y;
    }
    constexpr friend std::ostream& operator<<(std::ostream& os,ModInt x){
        return os << x();
    }
    constexpr friend std::istream& operator>>(std::istream& is,ModInt &x){
        is >> x.val, x.val = norm(x.val);
        return is;
    }
    constexpr static long long norm(long long x){
        return x < 0 ? (x % MOD + MOD) % MOD : x % MOD;
    }
    constexpr static ModInt Pow(ModInt x,long long y){
        ModInt ans = 1;
        for (;y; y >>= 1,x *= x)
            if (y & 1) ans *= x;
        return ans;
    }
};
 
template <long long MOD>
struct Combination{
    int siz = 0;
    using Z = ModInt<MOD>;
    std::vector<Z> fact,inv;
    Combination():siz(1),fact(1,1),inv(1,1){}
    void expend(int size){
        if (siz >= size) return;
        fact.resize(size),inv.resize(size);
        for (int i = siz;i < size;i++) fact[i] = fact[i-1] * i;
        inv[size-1] = 1 / fact[size-1];
        for (int i = size - 2;i >= siz;i--) inv[i] = inv[i+1] * (i+1);
        siz = size;
    }
    void check(int size){
        if (siz >= size) return;
        int n = siz;
        while(n < size) n <<= 1;
        n = std::min<unsigned int>(n,MOD);
        expend(n);
    }
    Z A(int n,int m){
        if (n < 0 || m < 0 || n < m) return 0;
        check(n+1);
        return fact[n]*fact[n-m];
    }
    Z C(int n,int m){
        if (n < 0 || m < 0 || n < m) return 0;
        if (n < MOD && m < MOD) {
            check(n+1);
            return fact[n] * inv[m] * inv[n - m];
        } else return C(n/MOD,m/MOD)*C(n%MOD,m%MOD);
    }
};
 
Combination<i64(1e9+7)> comb;
 
using Z = ModInt<i64(1e9+7)>;

主程序

#include<bits/stdc++.h>
#if __has_include("tool/local.hpp")
#include "tool/local.hpp"
#include "grader.hpp"
#else
#define Testcases(T) while(T--) solve();
    #ifndef ONLINE_JUDGE
    #define listen(...) freopen("data.in","r",stdin),freopen("data.out","w",stdout);
    #else
    #define listen(...)
    #endif
#endif
using namespace std;
// Base type
using ll = long long;
using ld = long double;
using i64 = long long;
using f128 = long double;
using u64 = unsigned long long;
using p32 = std::array<int,2>;
using p64 = std::array<i64,2>;

// mt19937_64 rnd(time(0));

void solve(){
}

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr),std::cout.tie(nullptr);
    listen(_TIMER,_FILE,_CHECKER);
    int T = 1;
    std::cin >> T;
    Testcases(T);
    return 0;
}

/*
 | Code By Kendieer
 | Model Updated : 2025/12/09
 | Code With VSCode
*/

C++ 数学计数组合数学

举报

收藏

赞 2

评论加载中...