Back to Blog

牛客小白月赛125题解

这场比赛是数学场吧。一场下来，没几个题是没有数学公式的。而且没有考的算法。都是最基本的，看的就是基本盘坚不坚定。 这道题就是给一个式子求解$a^b = x$求$a$, $b$的大小，我们一眼就可以看出当$b = 1$时 $a = x$,得出答案，因为$x^1=x$ 题目大意呢就是求$\leq x$的数至少有$k$...

Type 题解

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

Views — / Comments — / Words 404

牛客小白月赛125题解

这场比赛是数学场吧。一场下来，没几个题是没有数学公式的。而且没有考的算法。都是最基本的，看的就是基本盘坚不坚定。

幂运算

这道题就是给一个式子求解$a^b = x$求$a$, $b$的大小，我们一眼就可以看出当$b = 1$时 $a = x$,得出答案，因为$x^1=x$

void solve() {
    read(x);
    cout << x << ' ' << 1 << endl;
}

琪露诺的 K 维偏序

题目大意呢就是求$\leq x$的数至少有$k$个直接用二分写了

void solve() {
    int q;
    read(n, q);
    for (int i = 0; i < n; i++)
        read(w[i]);
    sort(w, w + n);
    while (q --) {
        read(k, x);
        int rank = lower_bound(w, w + n, x) - w;
        puts(rank >= k ? "Yes" : "No");
    }
}

合成大企鹅

给一个数学式子，将数组中$a$,$b$变成$\sqrt{a*b}$，让$\sqrt{a*b}$最大，我们可以贪心的思考如何让$\sqrt{a*b}$最大呢。根据$a + b \geq 2 * \sqrt{a*b}$即当$a = b$时，式子成立。我们让$a$, $b$尽可能的近。从小开始遍历就行了。用优先队列写。让$a$,$b$的尽可能的差值小

void solve() {
    read(n);
    priority_queue<double, vector<double>, greater<>> pq;
    for (int i = 0; i < n; i++)
        read(w[i]), pq.push(w[i]);
    while (pq.size() != 1) {
        double x = pq.top();
        pq.pop();
        double y = pq.top();
        pq.pop();
        double res = sqrt(x * y);
        pq.push(res);
    }
    printf("%.12lf", pq.top());
}

⑨运算(Easy Version)、⑨运算(Hard Version)

这道题，我是半蒙半写，写出来的。我怕爆long long，用的python暴力写的题。没什么含金量。赛后看看题解是什么。

我先说说是如何暴力的。我们可以知道有两种操作：

• 一种是对该整数加 9，即$x \leftarrow x + 9$
• 另一种是对该整数乘 9，即$x \leftarrow x * 9$，有限制最多只能用一次

第二种操作就是第一种操作多次使用。假设这个数是$x$

------
x + 9 * n = 999...999
------
(x + 9 * n) * 9 + m * 9 = 999...999

这两种操作展开看

------
n = (999...999 - x) / 9 # 答案是n
------
9 * n + m = 111...111   # 答案是n + 1 + m      +1是*9这个操作

我们只需要构造$999...999$然后暴力的看看上面哪一个的答案小就行。这就是我的暴力题解

def solve():
    global arr
    x = ii()
    ln = len(str(x))
    while True:
        base = 10 ** ln - 1
        ans = inf
        if x == base:
            print(0)
            return
        base -= x
        if base % 9 == 0:
            ans = base // 9
        base += x
        if base % 9 == 0:
            base //= 9
            base -= x
            if base >= 0:
                m = base // 9
                n = base % 9
                ans = fmin(ans, m + n + 1)
        if ans != inf:
            print(ans)
            return
        ln += 1

琪露诺的排列构造

这道题是构造题。我场上思考了好长时间。构造有三个限制

• 构造一个长度为 n的排列 $p$
• 对于任意的$i \in[1,n]$，都有$p_i \neq i$
• 对于任意的$1 \leq i < j \leq n$，都有$p_i + i \neq p_j + j$

我们可以知道对于$\leq 2$的无解。

我发现这个规律(其实就是打表)：

arr:  	 2 3 4 5 .... n      1
i:       1 2 3 4 .... n - 1  n
arr + i: 3 5 7 9 .... 2n - 1 n + 1

对于$n$是奇数的时候成立,$n$是偶数的时候不成立。这是我们就要找如何使偶数时成立

其实我们可以发现$arr[i] + i$是奇数，并且是单调递增的（除了$1$），而$1 + n$是根据$n$的值变化的。

当$n$是偶数时$1 + n$会与前面的一个数重合这时，如果我们将$1$和前面的偶数($j$)换一下位置，这样$1 + j - 1$是偶数，$j + n$是偶数。并且让$1 + j - 1 \neq j + n$就行，这样就构造出来了。我选的是前面的$4$这个数,这样的话。就需要特判一下$n = 4$的时候了。其他就根据前面的构造就行了

void solve() {
    read(n);
    if (n == 1 || n == 2) {
        cout << -1 << endl;
        return;
    }
    if (n == 4) {
        cout << 3 << ' ' << 1 << ' ' << 4 << ' ' << 2 << endl;
        return;
    }
    vector<int> p(n);
    iota(p.begin(), p.end(), 2);
    p[n - 1] = 1;
    if (n & 1) {
        for (int x: p)
            cout << x << ' ';
        cout << endl;
        return;
    }
    swap(p[2], p.back());
    for (int x: p)
        cout << x << ' ';
    cout << endl;
}

琪露诺的连续取模求和

这道题我写的有点复杂。先看看题目的数学公式吧:

形式化地说，对于给定两个整数区间 $[l, r]$和$[p, q]$。你需要计算以下式子的结果：$\sum^{r}_{i = r}(i \mod (q) \mod (q - 1)\mod (q - 2)\cdots \mod (p))$

简单来说，计算结果为：对区间$[l,r]$每一个整数 $i$，依次对从 $q$ 到 $p$ 内所有整数取模后求和

我想的是分类讨论：

• 当$l<q$时
• 当$r > p$时
  • $l<q$
  • $l\ge q$

这两种讨论。

我们可以发现

• 当$i< q$可以直接相加
• 当$q \leq i \leq p$时为$0$
• 当$i > p$时将$i \%= p$然后从1、2中看是那种情况

int l, r, p, q;
i64 calc(i64 a, i64 b) {
    if (a > b)
        return 0;
    return (a + b) * (b - a + 1) / 2;
}

i64 bushi(int x, int q) {
    if (x < q)
        return 0;
    x = x - q;
    int base = x / q;
    int res = x % q;
    i64 ans = calc(1, p - 1) * base;
    ans += calc(1, min(res, p - 1));
    return ans;
}
void solve() {
    read(l, r, p, q);
    if (p <= l && r <= q)
        return cout << 0 << endl, void();
    i64 ans = 0;
    if (l < p) {
        ans += calc(l, min(p - 1, r));
    }
    if (r > q) {
        // q + 1 ~ r -> 0 ~ q - 1
        ans += bushi(r, q) - bushi(l - 1, q);
    }
    cout << ans << endl;
}

— 商业转载请联系站长获得授权，非商业转载请注明本文出处及文章链接，您可以自由地在任何媒体以任何形式复制和分发作品，也可以修改和创作，但是分发衍生作品时必须采用相同的许可协议。本文采用 CC BY-NC-SA 4.0 - 非商业性使用 - 相同方式共享 4.0 国际 进行许可。

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.