第十二届蓝桥杯大赛软件赛决赛（C/C++ 大学C组）

蓝桥杯 2021年国赛真题
^{C/C++ 大学C组}

试题 A: 整数范围
试题 B: 带宽
试题 C: 纯质数
试题 D: 完全日期
试题 E: 最小权值
试题 F: 大写
试题 G: 123
试题 H: 异或变换
试题 I: 巧克力
试题 J: 二进制问题

蓝桥杯个人赛软件类历届真题及其解析

更新中。

试题 A: 整数范围

本题总分： 5 5 5 分

【问题描述】

用 8 8 8 位二进制（一个字节）来表示一个非负整数，表示的最小值是 0 0 0，则一般能表示的最大值是多少？

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

255

#include 

int main() {
    printf("%d", 0xff);
}

¿ ¿ ¿

试题 B: 带宽

本题总分： 5 5 5 分

【问题描述】

小蓝家的网络带宽是 200 200 200 M b p s mathrm{Mbps} Mbps，请问，使用小蓝家的网络理论上每秒钟最多可以从网上下载多少 M B mathrm{MB} MB 的内容。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

25

#include 

int main() {
    printf("%d", 200 / 8);
}

p s mathrm{ps} ps 意为 p e r s e c o n d mathrm{per second} per second， 1 B = 8 b 1mathrm{B} = 8mathrm{b} 1B=8b。

试题 C: 纯质数

本题总分： 10 10 10 分

【问题描述】

如果一个正整数只有 1 1 1 和它本身两个约数，则称为一个质数（又称素数）。

前几个质数是：：： 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , ⋯ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37,cdots 2,3,5,7,11,13,17,19,23,29,31,37,⋯。

如果一个质数的所有十进制数位都是质数，我们称它为纯质数。例如：：： 2 , 3 , 5 , 7 , 23 , 37 2, 3, 5, 7, 23, 37 2,3,5,7,23,37 都是纯质数，而 11 , 13 , 17 , 19 , 29 , 31 11, 13, 17, 19, 29, 31 11,13,17,19,29,31 不是纯质数。当然 1 , 4 , 35 1, 4, 35 1,4,35 也不是纯质数。

请问，在 1 1 1 到 20210605 20210605 20210605 中，有多少个纯质数？

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

1903

#include 

const int N = 20210605;

int ans, composite[N + 1];

int check(int n) {
    if (n < 10) return n == 2 || n == 3 || n == 5 || n == 7;
    do
        if (!check(n % 10)) return 0;
    while (n /= 10);
    return 1;
}

int main() {
    for (int i = 2; i <= N; ++i)
        if (!composite[i]) {
            for (int j = i + i; j <= N; j += i) composite[j] = 1;
            if (check(i)) ++ans;
        }
    printf("%d", ans);
}

埃拉托色尼筛选法。

试题 D: 完全日期

本题总分： 10 10 10 分

【问题描述】

如果一个日期中年月日的各位数字之和是完全平方数，则称为一个完全日期。

例如：：： 2021 2021 2021 年 6 6 6 月 5 5 5 日的各位数字之和为 2 + 0 + 2 + 1 + 6 + 5 = 16 2 + 0 + 2 + 1 + 6 + 5 = 16 2+0+2+1+6+5=16，而 16 16 16 是一个完全平方数，它是 4 4 4 的平方。所以 2021 2021 2021 年 6 6 6 月 5 5 5 日是一个完全日期。

例如：：： 2021 2021 2021 年 6 6 6 月 23 23 23 日的各位数字之和为 2 + 0 + 2 + 1 + 6 + 2 + 3 = 16 2 + 0 + 2 + 1 + 6 + 2 + 3 = 16 2+0+2+1+6+2+3=16，是一个完全平方数。所以 2021 2021 2021 年 6 6 6 月 23 23 23 日也是一个完全日期。

请问，从 2001 2001 2001 年 1 1 1 月 1 1 1 日到 2021 2021 2021 年 12 12 12 月 31 31 31 日中，一共有多少个完全日期？

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

977

#include 

int ans, days[]{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int is_leap(int year) { return !(year % 100 ? year % 4 : year % 400); }

int calc(int n) {
    int res = 0;
    do
        res += n % 10;
    while (n /= 10);
    return res;
}

int check(int n) {
    switch (n) {
        case 1:
        case 4:
        case 9:
        case 16:
        case 25:
        case 36: return 1;
    }
    return 0;
}

int main() {
    for (int year = 2001; year <= 2021; ++year)
        for (int month = 1; month <= 12; ++month) {
            if (is_leap(year)) days[2] = 29;
            for (int day = 1; day <= days[month]; ++day)
                if (check(calc(year) + calc(month) + calc(day))) ++ans;
            days[2] = 28;
        }
    printf("%d", ans);
}

签到 × 4 times 4 × 4。

试题 E: 最小权值

本题总分： 15 15 15 分

【问题描述】

对于一棵有根二叉树 T T T，小蓝定义这棵树中结点的权值 W ( T ) W(T) W(T) 如下：：：

空子树的权值为 0 0 0。

如果一个结点 v v v 有左子树 L L L，右子树 R R R，分别有 C ( L ) C(L) C(L) 和 C ( R ) C(R) C(R) 个结点，则 W ( v ) = 1 + 2 W ( L ) + 3 W ( R ) + ( C ( L ) ) 2 C ( R ) W(v) = 1 + 2W(L) + 3W(R) + (C(L))^2C(R) W(v)=1+2W(L)+3W(R)+(C(L))2C(R)。

树的权值定义为树的根结点的权值。

小蓝想知道，对于一棵有 2021 2021 2021 个结点的二叉树，树的权值最小可能是多少？

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

2653631372

动态规划

#include 

#define min(a, b) (a < b ? a : b)

const int N = 2021;

long long dp[N + 1];

int main() {
    for (int i = 1; i <= N; ++i) {
        dp[i] = 0x3f3f3f3f3f3f3f3f;
        for (int l = 0; l < i; ++l)
            dp[i] = min(dp[i], 1 + 2 * dp[l] + 3 * dp[i - l - 1] + l * l * (i - l - 1));
    }
    printf("%lld", dp[N]);
}

设 f i f_i fi 为 C ( T ) = i C(T) = i C(T)=i 的有根二叉树 T T T 的最小权值，显然 f i f_i fi 无后效性，故考虑动态规划，有转移方程：：： f i = min ⁡ ( 1 + 2 f l + 3 f r + l 2 r ) , i = l + r + 1 , l , r ∈ N f_i = min(1 + 2f_l + 3 f_r + l^2r),quad i = l + r + 1,quad l,r in mathbb N fi=min(1+2fl+3fr+l2r),i=l+r+1,l,r∈N 初始时 f 0 = 0 f_0 = 0 f0=0，答案为 f 2021 f_{2021} f2021。

试题 F: 大写

时间限制: 1.0 s 1.0mathrm s 1.0s 内存限制: 256.0 M B 256.0mathrm{MB} 256.0MB 本题总分： 15 15 15 分

【问题描述】

给定一个只包含大写字母和小写字母的字符串，请将其中所有的小写字母转换成大写字母后将字符串输出。

【输入格式】

输入一行包含一个字符串。

【输出格式】

输出转换成大写后的字符串。

【样例输入】

LanQiao

【样例输出】

LANQIAO

【评测用例规模与约定】

对于所有评测用例，字符串的长度不超过 100 100 100。

#include 

#define upper(a) a >= 'a' && a <= 'z' ? a - 0x20 : a

int main() {
    for (int a; ~(a = getchar());) putchar(upper(a));
}

签到 × 6 times 6 × 6，几个常用的 A S C I I mathrm{ASCII} ASCII 码需要记住，

像 0 0 0 对应 0 x 30 0mathrm x30 0x30； A mathrm A A 对应 0 x 41 0mathrm x41 0x41； a mathrm a a 对应 0 x 61 0mathrm x61 0x61，

且数字字母字符在 A S C I I mathrm{ASCII} ASCII 码表中是自然连续的。

试题 G: 123

时间限制: 1.0 s 1.0mathrm s 1.0s 内存限制: 256.0 M B 256.0mathrm{MB} 256.0MB 本题总分： 20 20 20 分

【问题描述】

小蓝发现了一个有趣的数列，这个数列的前几项如下：：：

1 , 1 , 2 , 1 , 2 , 3 , 1 , 2 , 3 , 4 , ⋯ 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, cdots 1,1,2,1,2,3,1,2,3,4,⋯

小蓝发现，这个数列前 1 1 1 项是整数 1 1 1，接下来 2 2 2 项是整数 1 1 1 至 2 2 2，接下来 3 3 3 项是整数 1 1 1 至 3 3 3，接下来 4 4 4 项是整数 1 1 1 至 4 4 4，依次类推。

小蓝想知道，这个数列中，连续一段的和是多少。

【输入格式】

输入的第一行包含一个整数 T T T，表示询问的个数。

接下来 T T T 行，每行包含一组询问，其中第 i i i 行包含两个整数 l i l_i li 和 r i r_i ri，表示询问数列中第 l i l_i li 个数到第 r i r_i ri 个数的和。

【输出格式】

输出 T T T 行，每行包含一个整数表示对应询问的答案。

【样例输入】

【样例输出】

1
4
8

【评测用例规模与约定】

对于 10 % 10% 10% 的评测用例， 1 ≤ T ≤ 30 , 1 ≤ l i ≤ r i ≤ 100 1 ≤ T ≤ 30, 1 ≤ l_i ≤ r_i ≤ 100 1≤T≤30,1≤li≤ri≤100。
对于 20 % 20% 20% 的评测用例， 1 ≤ T ≤ 100 , 1 ≤ l i ≤ r i ≤ 1000 1 ≤ T ≤ 100, 1 ≤ l_i ≤ r_i ≤ 1000 1≤T≤100,1≤li≤ri≤1000。
对于 40 % 40% 40% 的评测用例， 1 ≤ T ≤ 1000 , 1 ≤ l i ≤ r i ≤ 1 0 6 1 ≤ T ≤ 1000, 1 ≤ l_i ≤ r_i ≤ 10^6 1≤T≤1000,1≤li≤ri≤106。
对于 70 % 70% 70% 的评测用例， 1 ≤ T ≤ 10000 , 1 ≤ l i ≤ r i ≤ 1 0 9 1 ≤ T ≤ 10000, 1 ≤ l_i ≤ r_i ≤ 10^9 1≤T≤10000,1≤li≤ri≤109。
对于 80 % 80% 80% 的评测用例， 1 ≤ T ≤ 1000 , 1 ≤ l i ≤ r i ≤ 1 0 12 1 ≤ T ≤ 1000, 1 ≤ l_i ≤ r_i ≤ 10^{12} 1≤T≤1000,1≤li≤ri≤1012。
对于 90 % 90% 90% 的评测用例， 1 ≤ T ≤ 10000 , 1 ≤ l i ≤ r i ≤ 1 0 12 1 ≤ T ≤ 10000, 1 ≤ l_i ≤ r_i ≤ 10^{12} 1≤T≤10000,1≤li≤ri≤1012。
对于所有评测用例， 1 ≤ T ≤ 100000 , 1 ≤ l i ≤ r i ≤ 1 0 12 1 ≤ T ≤ 100000, 1 ≤ l_i ≤ r_i ≤ 10^{12} 1≤T≤100000,1≤li≤ri≤1012。

容斥原理

令该数列为 A A A，显然对于每个回答 ∑ i = l r a i sum_{i=l}^ra_i ∑i=lrai 可变化为 ∑ i = 1 r a i − ∑ i = 1 l − 1 a i sum_{i=1}^ra_i - sum_{i=1}^{l-1}a_i ∑i=1rai−∑i=1l−1ai，同时构造数列 S S S， ∑ i = 1 k s i = ∑ i = 1 k ( k + 1 ) / 2 a i sum_{i=1}^ks_i = sum_{i=1}^{k(k + 1)/2} a_i ∑i=1ksi=∑i=1k(k+1)/2ai，并定义 l ′ l' l′ 满足 l = l ′ ( l ′ + 1 ) / 2 l = l'(l' + 1) / 2 l=l′(l′+1)/2，容易将回答再变化为 ∑ i = 1 r ′ s i − ∑ i = 1 l ′ − ξ s i sum_{i=1}^{r'}s_i - sum_{i=1}^{l'-xi}s_i ∑i=1r′si−∑i=1l′−ξsi，不过 l ′ 、 r ′ l'、r' l′、r′ 都可能不为正整数，但容易发现 s k = a k ( k − 1 ) / 2 + 1 + a k ( k − 1 ) / 2 + 2 + ⋯ + a k ( k + 1 ) / 2 s_k = a_{k(k-1)/2+1} + a_{k(k-1)/2+2} + cdots +a_{k(k+1)/2} sk=ak(k−1)/2+1+ak(k−1)/2+2+⋯+ak(k+1)/2，因此在此基础上添加一点点细节，将 A A A 的前缀和变化为：：： c a l c i = ∑ j = 1 i a j = ∑ j = 1 ⌊ i ′ ⌋ s i + ∑ j = 1 i − ⌊ i ′ ⌋ a j , mathrm{calc}_i = sum_{j=1}^ia_j = sum_{j=1}^{lfloor i'rfloor}s_i + sum_{j=1}^{i-lfloor i'rfloor}a_j, calci=j=1∑iaj=j=1∑⌊i′⌋si+j=1∑i−⌊i′⌋aj, 最终，答案为：：： a n s l , r = c a l c r − c a l c l − 1 . mathrm{ans}_{l,r}=mathrm{calc}_r - mathrm{calc}_{l-1}. ansl,r=calcr−calcl−1.

#include 
#include 
#include 

const int N = sqrt(2e12) + 9;

typedef long long ll;

ll A[N], S[N], l, r;

ll calc(ll n) {
    ll *K = std::upper_bound(A, A + N, n) - 1;
    return S[K - A] + A[n - *K];
}

int T;

int main() {
    for (int i = 0; i < N; ++i)
        A[i] = A[i - 1] + i,
        S[i] = S[i - 1] + A[i];
    for (scanf("%d", &T); T--;) {
        scanf("%lld %lld", &l, &r);
        printf("%lldn", calc(r) - calc(l - 1));
    }
}

试题 H: 异或变换

时间限制: 1.0 s 1.0mathrm s 1.0s 内存限制: 256.0 M B 256.0mathrm{MB} 256.0MB 本题总分： 20 20 20 分

【问题描述】

小蓝有一个 01 01 01 串 s = s 1 s 2 s 3 ⋅ ⋅ ⋅ s n s = s_{1} s_{2} s_{3} · · · s_{n} s=s1s2s3⋅⋅⋅sn。

以后每个时刻，小蓝要对这个 01 01 01 串进行一次变换。每次变换的规则相同。

对于 01 01 01 串 s = s 1 s 2 s 3 ⋅ ⋅ ⋅ s n s = s_{1} s_{2} s_{3} · · · s_{n} s=s1s2s3⋅⋅⋅sn，变换后的 01 01 01 串 s ′ = s 1 ′ s 2 ′ s 3 ′ ⋯ s n ′ s' = s'_{1}s'_{2}s'_{3} cdots s'_{n} s′=s1′s2′s3′⋯sn′ 为：：：

s 1 ′ = s 1 s'_{1} = s_{1} s1′=s1;
s i ′ = s i − 1 ⊕ s i s'_{i} = s_{i−1} ⊕ s_{i} si′=si−1⊕si。

其中 a ⊕ b a ⊕ b a⊕b 表示两个二进制的异或，当 a a a 和 b b b 相同时结果为 0 0 0，当 a 和 b不同时结果为 1 1 1。

请问，经过 t t t 次变换后的 01 01 01 串是什么？

【输入格式】

输入的第一行包含两个整数 n , t n, t n,t，分别表示 01 01 01 串的长度和变换的次数。

第二行包含一个长度为 n n n 的 01 01 01 串。

【输出格式】

输出一行包含一个 01 01 01 串，为变换后的串。

【样例输入】

5 3
10110

【样例输出】

【样例说明】
初始时为 10110 10110 10110，变换 1 1 1 次后变为 11101 11101 11101，变换 2 2 2 次后变为 10011 10011 10011，变换 3 3 3 次后变为 11010 11010 11010。

【评测用例规模与约定】

对于 40 % 40% 40% 的评测用例， 1 ≤ n ≤ 100 , 1 ≤ t ≤ 1000 1 ≤ n ≤ 100, 1 ≤ t ≤ 1000 1≤n≤100,1≤t≤1000。
对于 80 % 80% 80% 的评测用例， 1 ≤ n ≤ 1000 , 1 ≤ t ≤ 1 0 9 1 ≤ n ≤ 1000, 1 ≤ t ≤ 10^{9} 1≤n≤1000,1≤t≤109。
对于所有评测用例， 1 ≤ n ≤ 10000 , 1 ≤ t ≤ 1 0 18 1 ≤ n ≤ 10000, 1 ≤ t ≤ 10^{18} 1≤n≤10000,1≤t≤1018。

二项式定理

我们将 01 01 01 串 s s s 视为 n n n 维向量，第 i i i 个分量为 s i s_i si，容易想到通过模 2 2 2 矩阵乘法，对 s s s 进行 t t t 次变化，更具体地说：：：

s = ( s 1 , s 2 , ⋯ , s n ) T , s=(s_1,s_2,cdots,s_n)^T, s=(s1,s2,⋯,sn)T,

则变换后的 01 01 01 串 s ′ s' s′ 可以表示为：：：

s ′ = s A n × n , A n × n = ( 1 1 0 ⋯ 0 0 0 1 1 ⋯ 0 0 0 0 1 ⋯ 0 0 ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ 0 0 0 ⋯ 1 1 0 0 0 ⋯ 0 1 ) ( m o d 2 ) s'=sA_{ntimes n},A_{ntimes n}=begin{pmatrix} 1 & 1 & 0 & cdots & 0 & 0\ 0 & 1 & 1 & cdots & 0 & 0\ 0 & 0 & 1 & cdots & 0 & 0\ vdots & vdots & vdots & ddots & vdots & vdots\ 0 & 0 & 0 & cdots &1 & 1\ 0 & 0 & 0 & cdots &0 & 1 end{pmatrix}pmod 2 s′=sAn×n,An×n=⎝⎜⎜⎜⎜⎜⎜⎜⎛100⋮00110⋮00011⋮00⋯⋯⋯⋱⋯⋯000⋮10000⋮11⎠⎟⎟⎟⎟⎟⎟⎟⎞(mod2)

最终答案为 s A t sA^t sAt，不过 n n n 最大为 1 e 4 1e4 1e4，即使是在快速幂加速的情况下， O ( n 3 log ⁡ t ) O(n^3log t) O(n3logt) 的复杂度显然无法通过所有测试用例，不过矩阵 A A A 很“工整”，我们将 A A A 拆分为 E E E 与 B B B 之和，即：：：

A = E + B = ( 1 0 0 ⋯ 0 0 0 1 0 ⋯ 0 0 0 0 1 ⋯ 0 0 ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ 0 0 0 ⋯ 1 0 0 0 0 ⋯ 0 1 ) + ( 0 1 0 ⋯ 0 0 0 0 1 ⋯ 0 0 0 0 0 ⋯ 0 0 ⋮ ⋮ ⋮ ⋱ ⋮ ⋮ 0 0 0 ⋯ 0 1 0 0 0 ⋯ 0 0 ) A = E + B = begin{pmatrix} 1 & 0 & 0 & cdots & 0 & 0\ 0 & 1 & 0 & cdots & 0 & 0\ 0 & 0 & 1 & cdots & 0 & 0\ vdots & vdots & vdots & ddots & vdots & vdots\ 0 & 0 & 0 & cdots &1 & 0\ 0 & 0 & 0 & cdots &0 & 1 end{pmatrix} +begin{pmatrix} 0 & 1 & 0 & cdots & 0 & 0\ 0 & 0 & 1 & cdots & 0 & 0\ 0 & 0 & 0 & cdots & 0 & 0\ vdots & vdots & vdots & ddots & vdots & vdots\ 0 & 0 & 0 & cdots &0 & 1\ 0 & 0 & 0 & cdots &0 & 0 end{pmatrix} A=E+B=⎝⎜⎜⎜⎜⎜⎜⎜⎛100⋮00010⋮00001⋮00⋯⋯⋯⋱⋯⋯000⋮10000⋮01⎠⎟⎟⎟⎟⎟⎟⎟⎞+⎝⎜⎜⎜⎜⎜⎜⎜⎛000⋮00100⋮00010⋮00⋯⋯⋯⋱⋯⋯000⋮00000⋮10⎠⎟⎟⎟⎟⎟⎟⎟⎞

E E E、 B B B 可交换，即 E B = B E EB = BE EB=BE，对二项式 A t = ( E + B ) t A^t = (E + B)^t At=(E+B)t 展开有 A t = ∑ i = 0 n C n i E n − i B i = ∑ i = 0 n C n i B i A^t=displaystyle{sum_{i=0}^nC_{n}^iE^{n-i}B^i = sum_{i=0}^nC_{n}^iB^i} At=i=0∑nCniEn−iBi=i=0∑nCniBi，

而 B n × n = ( b i j ) n × n B_{ntimes n} = (b_{ij})_{ntimes n} Bn×n=(bij)n×n， b i j = { 1 i = j − 1 0 o t h e r w i s e , b_{ij}=begin{cases}1 &i=j-1\0&otherwiseend{cases}, bij={10i=j−1otherwise,

根据矩阵乘法的定义， ( c i j ) n × m = ( a i j ) n × k ( b i j ) k × m (c_{ij})_{ntimes m}=(a_{ij})_{ntimes k}(b_{ij})_{ktimes m} (cij)n×m=(aij)n×k(bij)k×m， c i j = ∑ g = 1 k a i g b g j c_{ij} = sum_{g=1}^ka_{ig}b_{gj} cij=∑g=1kaigbgj，则 g g g 确定时， ( d i j ) = B 2 (d_{ij}) = B^2 (dij)=B2， i = j − 2 i = j - 2 i=j−2 时 d i j d_{ij} dij 才非零，类似的我们可以得到结论：：： B n = ( b i j ) , b i j = { 1 i = j − n 0 o t h e r w i s e , B^n = (b_{ij}),quad b_{ij}=begin{cases}1 &i=j-n\0&otherwiseend{cases}, Bn=(bij),bij={10i=j−notherwise, 容易找到 A n A^n An 的通项公式：：： A n = ( a i j ) , a i j { 0 i < j C n j − i o t h e r w i s e A^n = (a_{ij}),quad a_{ij}begin{cases}0 &i0Cnj−ii

证明：：：

首先 [ a = [a= [a= 偶数 ] ⇔ [ 2 ∣ a ] ] Leftrightarrow [2 mid a] ]⇔[2∣a]，

而 C n m = n ! m ! ( n − m ) ! C_n^m = cfrac{n!}{m!(n-m)!} Cnm=m!(n−m)!n!，令 a 、 b 、 c a、b、c a、b、c 分别为 n ! 、 m ! 、 ( n − m ) ! n!、m!、(n-m)! n!、m!、(n−m)! 中因子 2 2 2 的个数，则 [ a = [a= [a= 偶数 ] ⇔ [ a = b + c ] ] Leftrightarrow[a = b + c] ]⇔[a=b+c]，

笔者在十三届省赛求阶乘中给出过一种计算某个阶乘给定因子个数的公式，即有 a = ∑ i = 1 ⌊ log ⁡ 2 n ⌋ ⌊ n 2 i ⌋ a = displaystyle{sum_{i=1}^{lfloorlog_2 nrfloor}leftlfloorfrac n{2^i}rightrfloor} a=i=1∑⌊log2n⌋⌊2in⌋，

若 n & m = m n & m = m n & m=m 成立，则 ⌊ n 2 k ⌋ = ⌊ m 2 k ⌋ + ⌊ n − m 2 k ⌋ displaystyle{leftlfloorfrac n{2^k}rightrfloor = leftlfloorfrac m{2^k}rightrfloor + leftlfloorfrac {n - m}{2^k}rightrfloor} ⌊2kn⌋=⌊2km⌋+⌊2kn−m⌋ 恒成立，同时 a = b + c a = b + c a=b+c 成立， C n m C_n^m Cnm 为奇数。

若 n & m = m n & m = m n & m=m 不成立，则 m + ( n − m ) m + (n - m) m+(n−m) 在某一二进制位上会出现进位，设该数位为 k k k，则有 n m o d 2 k < m m o d 2 k + ( n − m ) m o d 2 k n mathrm{mod} 2^k < m mathrm{mod} 2^k + (n - m) mathrm{mod} 2^k n mod 2k ⌊ m 2 k ⌋ + ⌊ n − m 2 k ⌋ displaystyle{leftlfloorfrac n{2^k}rightrfloor > leftlfloorfrac m{2^k}rightrfloor + leftlfloorfrac {n - m}{2^k}rightrfloor} ⌊2kn⌋>⌊2km⌋+⌊2kn−m⌋，故而 a > b + c a > b + c a>b+c 成立， C n m C_n^m Cnm 为偶数。

#include 

#define min(a, b) (a < b ? a : b)

char buf[10009];

long long t;

int n;

int main() {
    scanf("%d %lld %s", &n, &t, buf);
    for (int i = n - 1; i; --i)
        for (int j = min(i, t); j; --j)
            if ((t & j) == j && buf[i - j] == '1') buf[i] ^= 1;
    printf("%s", buf);
}

试题 I: 巧克力

时间限制: 1.0 s 1.0mathrm s 1.0s 内存限制: 256.0 M B 256.0mathrm{MB} 256.0MB 本题总分： 25 25 25 分

【问题描述】

小蓝很喜欢吃巧克力，他每天都要吃一块巧克力。

一天小蓝到超市想买一些巧克力。超市的货架上有很多种巧克力，每种巧克力有自己的价格、数量和剩余的保质期天数，小蓝只吃没过保质期的巧克力，请问小蓝最少花多少钱能买到让自己吃 x 天的巧克力。

【输入格式】

输入的第一行包含两个整数 x , n x, n x,n，分别表示需要吃巧克力的天数和巧克力的种类数。

接下来 n n n 行描述货架上的巧克力，其中第 i i i 行包含三个整数 a i , b i , c i a_i, b_i, c_i ai,bi,ci，表示第 i i i 种巧克力的单价为 a i a_i ai，保质期还剩 b i b_i bi 天（从现在开始的 b i b_i bi 可以吃），数量为 c i c_i ci。

【输出格式】

输出一个整数表示小蓝的最小花费。如果不存在让小蓝吃 x x x 天的购买方案，输出 − 1 -1 −1。

【样例输入】

【样例输出】

【样例说明】
一种最佳的方案是第 1 1 1 种买 5 5 5 块，第 2 2 2 种买 2 2 2 块，第 3 3 3 种买 3 3 3 块。前 5 5 5 天吃第 1 1 1 种，第 6 、 7 6、7 6、7 天吃第 2 2 2 种，第 8 8 8 至 10 10 10 天吃第 3 3 3 种。

【评测用例规模与约定】

对于 30 % 30% 30% 的评测用例， n , x ≤ 1000 n, x ≤ 1000 n,x≤1000。
对于所有评测用例， 1 ≤ n , x ≤ 100000 ， 1 ≤ a i , b i , c i ≤ 1 0 9 1 ≤ n, x ≤ 100000，1 ≤ a_i, b_i, c_i ≤ 10^9 1≤n,x≤100000，1≤ai,bi,ci≤109。

贪心

#include 
#include 

#define min(a, b) (a < b ? a : b)

const int N = 100001;

int n, x, buf, linked[N];

long long ans;

struct node {
    int a, b, c;
} choco[N];

inline bool cmp(node &n1, node &n2) { return n1.a < n2.a; }

int find(int x) { return x == linked[x] ? x : (linked[x] = find(linked[x])); }

int main() {
    scanf("%d %d", &x, &n);
    for (int i = 0; i < n; ++i)
        scanf("%d %d %d", &choco[i].a, &choco[i].b, &choco[i].c);
    for (int i = 1; i <= x; ++i) linked[i] = i;
    std::sort(choco, choco + n, cmp);
    for (int i = 0; i < n; ++i) {
        if (choco[i].b > x) choco[i].b = x;
        while (buf = find(choco[i].b)) {
            if (!choco[i].c--) break;
            linked[buf] = buf - 1;
            ans += choco[i].a;
        }
    }
    for (int i = 1; i <= x; ++i)
        if (i == linked[x]) ans = -1;
    printf("%lld", ans);
}

试题 J: 二进制问题

时间限制: 1.0 s 1.0mathrm s 1.0s 内存限制: 256.0 M B 256.0mathrm{MB} 256.0MB 本题总分： 25 25 25 分

【问题描述】

小蓝最近在学习二进制。他想知道 1 1 1 到 N N N 中有多少个数满足其二进制表示中恰好有 K K K 个 1 1 1。你能帮助他吗？

【输入格式】

输入一行包含两个整数 N N N 和 K K K。

【输出格式】

输出一个整数表示答案。

【样例输入】

7 2

【样例输出】

【评测用例规模与约定】

对于 30 % 30% 30% 的评测用例， 1 ≤ N ≤ 1 0 6 , 1 ≤ K ≤ 10 1 ≤ N ≤ 10^6, 1 ≤ K ≤ 10 1≤N≤106,1≤K≤10。
对于 60 % 60% 60% 的评测用例， 1 ≤ N ≤ 2 × 1 0 9 , 1 ≤ K ≤ 30 1 ≤ N ≤ 2 × 10^9, 1 ≤ K ≤ 30 1≤N≤2×109,1≤K≤30。
对于所有评测用例， 1 ≤ N ≤ 1 0 18 , 1 ≤ K ≤ 50 1 ≤ N ≤ 10^{18}, 1 ≤ K ≤ 50 1≤N≤1018,1≤K≤50。

要下课了，润

第十二届蓝桥杯大赛软件赛决赛（C/C++ 大学C组）

C/C++/C#相关栏目本月热门文章