Back to Blog

牛客周赛 Round 121题解

这道题就是一道简单的签到题，我们就让幽幽子吃，每吃1吨答案加a，若吃的超过b吨了答案减c 这道题就是简单的贪心题，每次吃的都先让昨天的食物吃。吃完了再吃今天的食物。这道题我是用状态压缩写的，$1 << 26$然后判断是否只有3个元素。然后如果有的话相乘就行。答案加上。是全排列。这道题就是贪心问题，如果今天一定...

Type 题解

Created Dec 08, 2025, 17:00:00 / Updated Dec 08, 2025, 17:00:00

Views — / Comments — / Words 284

牛客周赛 Round 121题解

幽幽子想吃东西

这道题就是一道简单的签到题，我们就让幽幽子吃，每吃1吨答案加a，若吃的超过b吨了答案减c

void solve() {
    int a, b, c, n;
    read(a, b, c, n);
    int ans = a * n + (n <= b ? -c : 0);
    cout << ans << endl;
}

米斯蒂娅不想被吃掉

这道题就是简单的贪心题，每次吃的都先让昨天的食物吃。吃完了再吃今天的食物。

void solve() {
    read(n, x);
    for (int i = 1; i <= n; i++)
        read(w[i]);
    int last = 0;
    for (int i = 1; i <= n; i++) {
        int ans = w[i];
        if (last + ans < x) {
            cout << "No" << endl;
            return;
        }
        last = max(0, min(last + ans - x, ans));
    }
    cout << "Yes" << endl;
}

三妖精say subsequence ！！！

这道题我是用状态压缩写的， $1 << 26$ 然后判断是否只有3个元素。然后如果有的话相乘就行。答案加上。是全排列。

void solve() {
    cin >> n;
    cin >> str;
    for (int i = 0; i < str.size(); i++) {
        cnt[str[i] - 'a']++;
    }
    i64 ans = 0;
    for (int i = 7; i < (1 << 26); i++) {
        if (bitset<32>(i).count() != 3)
            continue;
        i64 sum = 1;
        for (int j = 0; j < 26; j++)
            if (i >> j & 1)
                sum *= cnt[j];
        sum *= 6;
        ans = (ans + sum) % MOD;
    }
    cout << ans << endl;
}

恋恋的01串大冒险

这道题就是贪心问题，如果今天一定要消失了。那么进行一次操作。把 $0$ 变成 $1$ ，一直累计。最后如果操作数没用完，就用一个循环输出 $n$

void solve() {
    cin >> n >> k >> str;
    int ret = 0;
    int l = 0, cnt = 0;
    for (int r = 0; r < n; r++) {
        if (str[r] == '0')
            cnt++;
        else
            cnt = 0;
        if (cnt == k) {
            cout << r << ' ';
            ret++;
            cnt = 0;
        }
    }
    for (int i = ret; i <= n; i++)
        cout << n << ' ';
}

永远亭的小游戏（续）

线性基：当线性基为简化阶梯型时，对于其能覆盖的数，必然存在唯一的、每个基元素最多用一次的异或表示 —— 这个表示就是该数的唯一编码。核心是利用线性基的阶梯型结构，通过 “逐位消去” 实现唯一编码，且满足 “只用一次” 的要求。

用线性基表示就行

int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
int cnt = 25;
int core[MAXT];
void init() {
    for (int i = 1; i <= MAXT; i++) {
        if (!core[i]) {
            for (int j = 1; j * j * i <= MAXT; j++)
                core[j * j * i] = i;
        }
    }
}
struct XorBasis {
private:
    vector<i64> b;
    int n;

    vector<int> right_most;
    int right_most_zero;

    bool zero;
    vector<i64> basis;

public:
    // 初始化
    XorBasis() {
        this->n = 64;
        b.resize(this->n + 1, 0);
        right_most.resize(this->n + 1, 0);
        right_most_zero = zero = false;
    }
    bool insert(i64 x) {
        for (int i = n - 1; i >= 0; i--)
            if (x >> i & 1LL) {
                if (b[i] == 0) {
                    b[i] = x;
                    return true;
                }
                x ^= b[i];
            }
        this->zero = true;
        return false;
    }
};

int calc(int x) {
    int mask = 0;
    for (int i = 0; i < 25; i++) {
        int p = primes[i];
        int cnt = 0, tmp = x;
        while (tmp % p == 0) {
            tmp /= p;
            cnt++;
        }
        if (cnt % 2 == 1)
            mask |= (1 << i);
    }
    return mask;
}

void solve() {
    init();
    read(n, q);
    
    for (int i = 1; i <= n; i++)
        read(w[i]), w[i] = calc(core[w[i]]);

    int l, r;
    while (q -- ) {
        read(l, r);
        bool flag = false;
        XorBasis xr;
        for (int i = l; i <= r; i++) {
            if (!xr.insert(w[i])) {
                flag = true;
                break;
            }
        }
        puts(flag ? "Yes" : "No");
    }
}

Comments

Notes, questions, and follow-ups are welcome here.

Comments are temporarily unavailable because WALINE_SERVER_URL or PUBLIC_WALINE_SERVER_URL is not configured.