讨论/题目交流/🐱 第 20 场夜喵双周赛/
🐱 第 20 场夜喵双周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 根据数字二进制下 1 的数目排序
4 分 - 每隔 n 个顾客打折
5 分 - 包含所有三种字符的子字符串数目
6 分 - 有效的快递序列数目

展开讨论

Biweekly Contest 20 Unofficial Editorial

这场比赛共计耗时34分27秒,排名39,全部一次AC,但距离CF红名dalao JOHNKRAM还有差距(主要C题卡了一会儿没有想到二分,加上前期测试大排长队)。

题解本身是0:00发的,但是前面发了其他内容好像时间没改。

做题顺序是ABDC。

TLDR

A. STL题
B. 简单模拟
C. 二分
D. 数学推理

Problem A

直接调用库函数sort就可以了。这里我使用了lambda expression

同时GCC还有一个不错的标准扩展__builtin_popcount,用起来这题就只有两行了。顺便说一句,它还有对应的__builtin_popcountll

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), [](int a, int b) {
            if (__builtin_popcount(a) == __builtin_popcount(b))
                return a < b;
            else 
                return __builtin_popcount(a) < __builtin_popcount(b);
        });
        return arr;
    }
};

Problem B

这题应该看英文题面,翻译似乎有一点问题。

然后就是快乐的大模拟,没有思维难度。可以用std::map来减小代码难度。

class Cashier {
public:
    int n, d;
    map <int, int> p;
    int cnt;
    Cashier(int _n, int discount, vector<int>& products, vector<int>& prices) {
        n = _n;
        d = discount;
        for (int i = 0; i < products.size(); i++) p[products[i]] = prices[i];
        cnt = 0;
    }
    
    double getBill(vector<int> product, vector<int> amount) {
        double ans = 0;
        for (int i = 0; i < product.size(); i++) ans += amount[i] * p[product[i]];
        cnt++;
        if (cnt == n) {
            cnt = 0;
            ans = ans - (d * ans) / 100;
        }
        return ans;
    }
};

Problem C

五万级的数据范围理论上O(n2)O(n^2)加上各种卡常是可以过去的,但是非常不稳,所以我写了一个O(nlogn)O(n\log n)的解法。

对于每种字母维护出现次数的前缀和序列。接着从头遍历到尾,对每个位置二分答案。check时判断是否在这一段内三个字母的出现次数都至少为11

个人习惯写左闭右开的二分。下面的实现总是会漏掉一个,我也不知道什么原因。

总的时间复杂度是O(nlogn)O(n \log n)

class Solution {
public:
    int pref[3][50010];
    bool check(int p, int x, int orig) {
        for (int i = 0; i < 3; i++) {if (pref[i][x] - pref[i][p - 1] < 1) return false;}
        return true;
    }
    int numberOfSubstrings(string s) {
        int ans = 0;
        s = "$" + s;    //习惯从1开始,避免前缀和第一项的特判
        memset(pref, 0, sizeof(pref));
        int n = s.length() - 1;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < 3; j++) {
                pref[j][i] = pref[j][i - 1] + (s[i] - 'a' == j);
            }
        for (int i = 1; i <= n; i++) {
            int L = i + 1, R = n + 1;
            while (L + 1 < R) {
                int mid = (L + R) >> 1;
                if (check(i, mid, s[i] - 'a')) {
                    R = mid;
                }
                else L = mid;
            }
            ans += n - L;
        }
        return ans + 1;
    }
};

Problem D

典型的公式题。数据范围可以出到10710^7都没有问题的。

证明的思路是把它看成一个字符串,长度为2n2n,每个字符都出现且恰好出现22次,问题是有多少个不同的这样的串(因为字符是一样的所以同一个字符之间的排列顺序无关紧要)。这样就把问题转变成了求一个每个元素都出现22次并且有nn个元素的可重集的排列数目,这是可以用**多项式展开(multinomial theorem)**做的。

实现的时候,注意到题目很友善地用p=109+7p=10^9+7这个质数作为模数,因此它对于任意数都有乘法逆元,且整数aa在模pp意义下的逆元就是ap2a^{p-2}

公式本身是(2n)!2n\dfrac{(2n)!}{2^n},实现的时候把除号改成乘逆元就可以了。

总的时间复杂度是O(n)O(n),来源于求阶乘。

const int MOD = 1e9 + 7;
class Solution {
typedef long long LL;
LL qpow(LL a, LL b, LL p = MOD) {
    LL ans = 1;
	for (; b; b >>= 1) {
		if (b & 1) ans = ans * a % p;
		a = a * a % p;
	}
	return ans;
}
LL fact(int x) {
    LL ans = 1;
    for (int i = 1; i <= x; i++) ans = ans * i % MOD;
    return ans;
}
LL getInv(LL x) {
	return qpow(x, MOD - 2);    //求逆元
}
public:
    int countOrders(int n) {
        return (int)((long long)(fact(2 * n) * getInv(qpow(2, n))) % MOD);
    }
};
3
展开全部 22 讨论