144练习赛题解_牛客博客

A

这个问题非常巧妙，它看起来像是一个博弈论问题，但实际上是一个寻找不变量的代数问题。结论的得出，关键在于对操作 $a×b+a+b$

进行一次漂亮的代数变形。

这个表达式看起来很眼熟，它非常像 $(a+1)(b+1)$ 的展开式。 $(a+1)(b+1)=a×b+a×1+1×b+1×1=ab+a+b+1$

对比一下题目给的操作 $ab+a+b$ ,我们发现： $ab+a+b=(a+1)(b+1)−1$

那假设 $c$ 是新产生的数，得出 $c=ab+a+b$

那如果用 $c$ 和其他的数进行操作得到 $d =(c+1)(x+1)=(ab+a+b+1)(x+1)=(a+1)(b+1)(x+1)$

所以，操作的顺序是不重要的，最后的结果是一定的 $(a_1+1)(a_2+1)...(a_n+1)-1 = 2∗\frac{3}{2}∗\frac{4}{3}....\frac{n+1}{n}−1=n+1−1=n$

但是由于是在 $A$ 题，所以通过枚举前3个数即可大胆猜结论。

STD

#include <bits/stdc++.h>

using i64 = long long;

void DAOQI() {
    int n;
    std::cin >> n;
    std::cout << n << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    std::cin >> T;
    while (T--) DAOQI();
    return 0;
}

B

思路

结论：连续的 $79$ 个数必定有一个合法的，暴力找就可以了证明：把 $79$ 个数分为两段，前 $40$ 个数、后 $39$ 个数前 $40$ 个数里，至少有 $4$ 个数尾数是 0（因为每 10 个数就会有一个以0结尾的），所以一定可以找到一个十位 $\leq 6$ 的数，设为 $y$ , 那么 $y,y+1,y+2...y+9,y+19,y+29,y+39$ 这13个数的数位和是连续的所以一定能找到一个13的倍数 (y的十位≤6，所以没发生过进百位)

#include <bits/stdc++.h>

using i64 = long long;

void DAOQI() {
    int l, r;
    std::cin >> l >> r;
    int ans = 0;
    for (int i = l; i <= r; i++) {
        int t = i, sum = 0;
        while (t) {
            sum += t % 10;
            t /= 10;
        }
        if (sum % 13 == 0) {
            ans++;
        }
        if (ans == 2) {
            std::cout << i << "\n";
            return;
        }
    }
    std::cout << -1 << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    std::cin >> T;
    while (T--) DAOQI();
    return 0;
}

C

问题等价于 $a_i+a_j=b_p+b_q$

把 $1$ 到 $n+m$ 做分组循环，相邻同组的数聚在一起分类讨论。

两段

$\{a_1,a_2...a_n\} \{b_1,b_2...b_m\}$ 第一段的数都小于第二段的数，各拿两个出来一定不相等，无解

三段

$\{a_1,a_2...a_i\} \{b_1,b_2...b_m\}\{a_{i+1}...a_n\}$

这个时候只需要取 $a_i,b_1,b_m,a_{i+1}$ 这四个数，正好符合

四段1

$\{a_1,a_2...a_{n-1}\} \{b_1\}\{a_n\}\{b_2...b_m\}$

显然缺少 $b_1$ 或 $a_n$ 就退化成两段，无解;二者必选后，前后两段各取一个 $a_i、b_j$ ，会出现 $b_1>a_i且 b_j>a_n$ ，故无解。

四段2

$\{a_1,a_2...a_{i}\} \{b_1...b_j\}\{a_{i+1}...a_n\}\{b_{j+1}...b_m\}$

若第二段至少有两个数:取 $a_i，b_1，b_j，a_{j+1}$ 正好符合。

若第三段至少有两个数:取 $b_j，a_{i+1}，a_n，b_{j+1}$ 正好符合

至少五段

$\{a_1,a_2...a_{i}\} \{b_1...b_p\}\{a_{i+1}...a_j\}\{b_{p+1}...b_q\}\{a_{j+1}...\}\{...\}...$

至少五段不必关心各段具体数量，取 $a_i，b_1，b_q，a_{j+1}$ 即可，正好符合。

class Seg:
    def __init__(self, l, r):
        self.l = l
        self.r = r


n, m = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()

A = []
for x in arr:
    if not A or A[-1].r + 1 < x:
        A.append(Seg(x, x))
    else:
        A[-1].r = x

B = []
tot = n + m
prev = 0
for s in A:
    if s.l > prev + 1:
        B.append(Seg(prev + 1, s.l - 1))
    prev = s.r
if prev < tot:
    B.append(Seg(prev + 1, tot))

seg = sorted(A + B, key=lambda s: s.l)

k = len(seg)

if k == 2:
    print(-1)
elif k == 3:
    print(seg[0].r, seg[1].l, seg[1].r, seg[2].l)
elif k == 4:
    if seg[1].l == seg[1].r and seg[2].l == seg[2].r:
        print(-1)
    elif seg[1].l != seg[1].r:
        print(seg[0].r, seg[1].l, seg[1].r, seg[2].l)
    else:
        print(seg[1].r, seg[2].l, seg[2].r, seg[3].l)
else:
    print(seg[0].r, seg[1].l, seg[3].r, seg[4].l)

D

有 $O(n)和O(nlogU)，U=∑cnt两种做法，O(nlogU)其实是比较易于理解的$

#include <bits/stdc++.h>

using i64 = long long;


void DAOQI() {
    std::string s;
    std::cin >> s;
    std::vector<int> cnt(26);
    for (int i = 0; i < 26; i++) {
        std::cin >> cnt[i];
    }
    int l = 0, r = accumulate(cnt.begin(), cnt.end(), 0) + 1;

    auto check = [&](int n) {//使用给定的字符能否构造出n个字典序严格大于s的字符串
        std::vector<int> ct = cnt;
        for (char c: s) {
            int i = c - 'a';
            for (int j = i + 1; j < 26; ++j) {//遍历到了新的字符i，先把严格大于i的填下去
                n -= ct[j];
                ct[j] = 0;
            }
            if (n <= 0) { //严格大于都够了，直接提前返回
                return true;
            }
            if (ct[i] < n) { //严格大于不够的，就要用i填满，i不够就无解了
                return false;
            }
            ct[i] -= n;
        }
        return accumulate(ct.begin(), ct.end(), 0) >= n;//现在还剩n个完全等于s的，顺便再末尾填个什么字符就可以字典序严格大于s了
    };
    while (l + 1 != r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }

    std::cout << l << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    //std::cin >> T;
    while (T--) DAOQI();
    return 0;
}

o(n)

代码分两步：

前缀贡献：统计所有以比 s[0] 大的字符开头的字符串数量。
后缀贡献：在以 s[0] 开头的字符串中，统计字典序严格大于 s 的字符串数量。

详细解释

Step 1：前缀贡献

int ans = 0;
for (int i = s[0] - 'a' + 1; i < 26; i++) {
    ans += cnt[i];
}

所有新字符串以比 s[0] 大的字符开头（即首字符大于 s[0]）。
这些字符串一定字典序严格大于 s（无论后面字符如何）。
因此直接累加这些字符的剩余数量。

Step 2：后缀贡献

2.1 预处理：找到 `s` 的“最长的递减前缀”

for (int i = 0; i < s.size() - 1; i++) {
        if (s[i] < s[i + 1]) {
            s = s.substr(0, i + 1);
            for (int j = 0; i <= s[i] - 'a'; j++) {//这些字符无用
                cnt[j] = 0;
            }
            break;
        }
    }

那为什么那些前面的字符是无用的呢。

假设我们向构造一个比 dcb 更大的字符，那我们一个方法就是把最后的 b 换为更大的一个字符，所以所有小于 b 的都删去即可

🔍 2.2 计算以 `s[0]` 开头的贡献

int sup = 0;
    for (int i = 0; i <= s[0] - 'a'; i++) {
        if (cnt[i] >= sup * ori[i]) {
            sup += (cnt[i] - sup * ori[i]) / (ori[i] + 1);
        } else {
            sup = cnt[i] / ori[i];
        }
    }

现在，我们以 s[0] 开头（如 d），构造字典序严格大于 s 的字符串。
这些字符串形如 d...，后面字符必须大于 s 的剩余部分。
这里用 贪心 + 数学计算：
- sup 表示最多能构造多少个这样的字符串。
- 对于每个字符 i，计算其剩余数量能支持多少个 s 的副本。
- 公式推导：
  - 每构造一个字符串，消耗 ori[i] 个字符 i。
  - 剩余 cnt[i] - sup * ori[i] 个字符，可额外支持 (cnt[i] - sup * ori[i]) / (ori[i] + 1) 个字符串。

为什么是要除 $ori[i]+1$ 呢？

假设是 edcc,如果cnt['d']>=sup * ori['d']那就说明这个 'd '字符还有剩余，还可以分配，那为了分配之后大于 edcc,我们要将多余’d字符,分到原来的 ‘c ’ 上，即 edd.每一个都多分派一个，就是除 ori[i]+1

#include<bits/stdc++.h>

using i64 = long long;

void DAOQI() {
    std::string s;
    std::cin >> s;
    std::vector<int> cnt(26);
    for (int i = 0; i < 26; i++) {
        std::cin >> cnt[i];
    }
    int ans = 0;
    for (int i = s[0] - 'a' + 1; i < 26; i++) {
        ans += cnt[i];
    }

    for (int i = 0; i < s.size() - 1; i++) {
        if (s[i] < s[i + 1]) {
            s = s.substr(0, i + 1);
            for (int j = 0; j <= s[i] - 'a'; j++) {
                cnt[j] = 0;
            }
            break;
        }
    }

    std::vector<int> ori(26);
    for (auto &i: s) {
        ori[i - 'a']++;
    }

    int sup = 0;
    for (int i = 0; i <= s[0] - 'a'; i++) {
        if (cnt[i] >= sup * ori[i]) {
            sup += (cnt[i] - sup * ori[i]) / (ori[i] + 1);
        } else {
            sup = cnt[i] / ori[i];
        }
    }
    ans += sup;
    std::cout << ans << '\n';

}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T = 1;
    //std::cin >> T;
    while (T--) DAOQI();
    return 0;
}

E

本题要求查询一个递归生成的超长字符串的特定位置的字符。由于字符串长度指数增长，模拟生成是不可行的，我们必须通过分析其递归结构来进行数学求解。

算法思想

整体思路是分治 + 递归。我们利用字符串的自相似性，将查询一个大问题 (m, k)（查询第 m 秒的第 k 个字符）转化为查询一个小问题 (m-1, k')。

1. 预处理与长度计算

首先，我们需要知道每一秒字符串的长度。设 $L_i$ 为第 $i$ 秒字符串的长度。根据生成规则，o/O 会被替换为长度为8的字符串，而 nowcoder ***有2个o，6个其他字符。 $s_{i-1}$ 中 o/O 的数量为 $2^{i-1}$ 。可以推导出长度的递推公式： $L_i = L_{i-1} + 7 \times 2^{i-1}$ ，其中 $L_0=1$ 。解得通项公式为 $L_i = 7 \cdot 2^i - 6$ 。我们预处理出 $L_i$ 的值并存入数组 l 中，由于 $k$ 最大为 $10^{18}$ ， $L_{60}$ 已经远超这个范围，所以数组大小开到60左右即可。

2. 关键性质剪枝

通过观察可以发现一个重要的性质：第 $m$ 秒的字符串 $s_m$ 的前 $m$ 个字符是一个由 n 和 N 交替组成的序列，奇数位为 n，偶数位为 N。因此，如果查询的 $k \le m$ ，我们可以直接根据 $k$ 的奇偶性 $O(1)$ 得出答案，无需进行复杂的递归。

3. 问题降阶与递归求解

当 $k > m$ 时，我们需要进入递归求解。

首先，当 $m$ 很大时， $s_m$ 的前缀 nNnN... 对字符串的宏观结构没有影响。我们可以将问题简化：查询 $s_m$ 的第 $k$ 个字符，等价于找到一个足够小的 $i$ （比如 $i \approx 60$ ），使得 $s_m$ 的结构可以看作是 (m-i) 个 n/N 前缀，后面跟着一个完整的 $s_i$ 字符串。此时，查询 $s_m$ 的第 $k$ 个字符就变成了查询 $s_i$ 的第 $k-(m-i)$ 个字符。这样我们就把一个超大的 $m$ 降阶到了一个可控的范围（例如 $i \le 60$ ）。

接下来是核心的递归函数 cal(m, k, c)，它负责查询第 m 秒字符串的第 k 个字符。参数 c 是一个大小写翻转标志位。 $s_m$ 的结构可以看作是由 nowcoder/NOWCODER 扩展而来，其骨架是 n o w c o d e r。我们遍历这个骨架：

遇到 n, w, c, d, e, r 这些“定值”字符，它们只占1个位置。如果 $k$ 正好落在这个位置，我们就找到了答案。
遇到 o 这个“变值”字符，它代表了一个完整的、由 $s_{m-1}$ 扩展而来的子串，其长度为 $L_{m-1}$ 。如果 $k$ 落在这个子串的范围内，我们就递归地调用 cal(m-1, k', c') 来查询这个子串。
- 新的查询位置 $k'$ 是 $k$ 在子串中的相对位置。
- 新的翻转标志位 $c'$ 需要翻转一次 (c^1)，因为 o 和 O 的大小写在奇偶秒是交替的，进入下一层递归相当于处理了一次 o/O 的替换。

最后，根据递归返回的基准字符 ch 和最终的翻转标志位 c，确定输出字符的大小写。同时，还要考虑初始查询的 m 和降阶后的 i 的奇偶性是否相同，如果不同，需要对最终的大小写翻转标志位再进行一次调整。

s="nowcoder"
l=[0]+[(7<<i)-6 for i in range(1,30)] 
#l[i]表示第i秒的字符串的长度
#l[29]足够覆盖k<=1e9的情况

def cal(m,k,c):
    """
    返回：第 m 秒串的第 k 个字符，以及大小写翻转位(c)：0 表示保持，1 表示取反
    做法：按结构分解
      F(m) = 'n' + F(m-1) + 'w' + 'c' + F(m-1) + 'd' + 'e' + 'r'
    其中遇到 'o' 对应的是整段 F(m-1)，其他字符都是单个字母
    c 在每次跨入一段 F(m-1) 时 ^1（因为 o/O 的大小写在奇偶秒交替）
    """
    if m==1:
        return s[k-1],c
    tot=0
    for i in "nowcode":
        if i=="o":
            if tot+l[m-1]>=k:
                return cal(m-1,k-tot,c^1)
            tot+=l[m-1]
        else:
            if tot+1>=k:
                return i,c
            tot+=1
    return "r",c

q=int(input())
for _ in range(q):
    m,k=map(int,input().split())
    # 关键性质：第 m 秒的前 m 个字符一定是 n/N 交替，从 'n' 开始
    # 因而若 k ≤ m，可直接用奇偶决定大小写
    if m>=k:    
        print("n" if k%2==1 else "N")
    else:
        # 否则把问题“降阶”到某个较小的 i（≤29）
        # 去掉前面的 m-i 个交替前缀后
        # 在 F(i) 中查第 k-(m-i) 个字符即可。
        for i in range(1,30): 
            if (m-i)+l[i]>=k:         # 找到能覆盖第 k 位的最小 i
                ch,c=cal(i,k-(m-i),0) # 在 F(i) 里查位置
                if i%2!=m%2:          # i和m奇偶性不同，整体奇偶性就要反转一下
                    c^=1
                print(ch.upper() if c==1 else ch)
                break

F

把所有的限制 $(l,r,c)，(r,c)$ 相同的放一组，每组只保留最严格的限制，即l最大的

$dp_0[i][j]$ 表示前 $i$ 个班级，恰好 $j$ 个班级非空，且第 $i$ 个班级为空的方案数 $dp_1[i][j]$ 表示前 $i$ 个班级，恰好 $j$ 个班级非空，且第 $i$ 个班级非空的方案数

维护一个 $mx_1$ 和 $mx_0$ ，分别表示两种数当前最严格的限制

转移 $dp_1[i][j]=dp_0[mx_0][j-(i-mx_0)]+dp_0[mx_0+1][j-(i-mx_0)+1]...dp_0[i-2][j-2]+dp_0[i-1][j-1]$ 即从上一个末尾为空的地方转移过来，后面这一段全部非空，是一个斜向的前缀和

$dp_0[i][j]=dp_1[mx1][j]+dp_1[mx1+1][j]+...dp_1[i-2][j]+dp_1[i-1][j]$ 即从上一个末尾非空的地方转移过来，后面这一段全部为空，用正常的前缀和做

做完这个dp后， $dp_0[n][i]+dp_1[n][i]$ 就表示恰好 $i$ 个教室非空的方案数然后还剩一个子问题，转化成 $m$ 个不同的小球，放入 $i$ 个互不相同的盒子，每个盒子至少放一个小球的方案数，用容斥或者再dp完成即可

void DAOQI() {
    Comb<i64> comb;
    i64 m, n, k;
    std::cin >> m >> n >> k;
    std::vector d(2, std::vector(n + 1, 0ll));
    std::vector<std::array<i64, 3>> arr;
    for (int i = 1; i <= k; i++) {
        i64 c, l, r;
        std::cin >> l >> r >> c;
        d[c][r] = std::max(d[c][r], l);
        arr.push_back({l, r, c});
    }
    std::vector dp0(n + 1, std::vector(n + 1, Z{}));
    auto dp1 = dp0, p0 = dp0, p1 = dp0;
    dp0[0][0] = dp1[0][0] = p0[0][0] = p1[0][0] = 1;
    std::array<i64, 2> mx = {0, 0};

    for (int i = 1; i <= n; i++) {
        mx[0] = std::max(mx[0], d[0][i]);
        mx[1] = std::max(mx[1], d[1][i]);
        for (int j = 0; j <= i; j++) {
            dp0[i][j] = p1[i - 1][j] - (mx[1] - 1 >= 0 ? p1[mx[1] - 1][j] : 0);
            i64 dis = i - (mx[0] - 1);
            dp1[i][j] = (j == 0 ? 0 : p0[i - 1][j - 1]) - (mx[0] - 1 >= 0 && j - dis >= 0 ? p0[mx[0] - 1][j - dis] : 0);
            p0[i][j] = (j == 0 ? 0 : p0[i - 1][j - 1]) + dp0[i][j];
            p1[i][j] = p1[i - 1][j] + dp1[i][j];
        }
    }
    //容斥 n个互不相同的小球，放入k个互不相同的盒子，盒子不空的方案数
    std::vector<Z> pw(n + 1, Z(1));
    for (int i = 1; i <= n; i++) {
        pw[i] = power(Z(i), m);
    }
    auto calc = [&](i64 n, i64 k) {
        Z res = 0;
        for (int i = 0; i <= k; i++) {
            if ((k - i) & 1) {
                res -= comb.binom(k, i) * pw[i];
            } else {
                res += comb.binom(k, i) * pw[i];
            }
        }
        return res;
    };
    Z res = 0;
    for (int i = 1; i <= n; i++) {
        res += calc(m, i) * (dp1[n][i] + dp0[n][i]);
    }
    std::cout << res << "\n";
}

144练习赛题解

A

STD

B

思路

C

D