您现在的位置是:首页 >技术杂谈 >第十四届蓝桥杯大赛软件赛省赛(C/C++ 大学B组)网站首页技术杂谈

第十四届蓝桥杯大赛软件赛省赛(C/C++ 大学B组)

肖有量 2023-05-10 22:30:04
简介第十四届蓝桥杯大赛软件赛省赛(C/C++ 大学B组)


要来力


试题 A: 日期统计

本题总分: 5 5 5


【问题描述】

  小蓝现在有一个长度为 100 100 100 的数组,数组中的每个元素的值都在 0 0 0 9 9 9 的范围之内。数组中的元素从左至右如下所示:
   5 5 5 6 6 6 8 8 8 6 6 6 9 9 9 1 1 1 6 6 6 1 1 1 2 2 2 4 4 4 9 9 9 1 1 1 9 9 9 8 8 8 2 2 2 3 3 3 6 6 6 4 4 4 7 7 7 7 7 7 5 5 5 9 9 9 5 5 5 0 0 0 3 3 3 8 8 8 7 7 7 5 5 5 8 8 8 1 1 1 5 5 5 8 8 8 6 6 6 1 1 1 8 8 8 3 3 3 0 0 0 3 3 3 7 7 7 9 9 9 2 2 2 7 7 7 0 0 0 5 5 5 8 8 8 8 8 8 5 5 5 7 7 7 0 0 0 9 9 9 9 9 9 1 1 1 9 9 9 4 4 4 4 4 4 6 6 6 8 8 8 6 6 6 3 3 3 3 3 3 8 8 8 5 5 5 1 1 1 6 6 6 3 3 3 4 4 4 6 6 6 7 7 7 0 0 0 7 7 7 8 8 8 2 2 2 7 7 7 6 6 6 8 8 8 9 9 9 5 5 5 6 6 6 5 5 5 6 6 6 1 1 1 4 4 4 0 0 0 1 1 1 0 0 0 0 0 0 9 9 9 4 4 4 8 8 8 0 0 0 9 9 9 1 1 1 2 2 2 8 8 8 5 5 5 0 0 0 2 2 2 5 5 5 3 3 3 3 3 3
  现在他想要从这个数组中寻找一些满足以下条件的子序列:
  1. 子序列的长度为 8 8 8
  2. 这个子序列可以按照下标顺序组成一个 y y y y m m d d m yyyymmdd yyyymmdd 格式的日期,并且要求这个日期是 2023 2023 2023 年中的某一天的日期,例如 20230902 20230902 20230902 20231223 20231223 20231223 y y y y m yyyy yyyy 表示年份, m m m mm mm 表示月份, d d m dd dd 表示天数,当月份或者天数的长度只有一位时需要一个前导零补充。
  请你帮小蓝计算下按上述条件一共能找到多少个不同的 2023 2023 2023 年的日期。对于相同的日期你只需要统计一次即可。

【答案提交】

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


235


  枚举长度为 8 8 8的子序列复杂度直接炸裂,不过考虑到日期前缀为 2023 2023 2023且唯一,因为找到 2023 2023 2023第一次出现的位置截断后枚举长度为 4 4 4的子序列与 2023 2023 2023年的合法日期取交集即可。

#include <bits/stdc++.h>

char *A = "5686916124919823647759503875815861830379270588570991944686338516346707827689565614010094809128502533";

char *prefix = "2023";

int n = 100, m = 0, ds[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

std::set<int> subs[4], target;

std::vector<int> ans;

int main() {
    for (int k = 0; k < 4 && m < n; ++m)
        if (prefix[k] == A[m]) ++k;
    for (; m < n; ++m) {
        for (int i = 2; i >= 0; --i)
            for (int sb : subs[i])
                subs[i + 1].insert(sb * 10 + A[m] - '0');
        subs[0].insert(A[m] - '0');
    }
    for (int m = 1; m <= 12; ++m)
        for (int d = 1; d <= ds[m]; ++d)
            target.insert(m * 100 + d);
    std::set_intersection(target.begin(), target.end(), subs[3].begin(), subs[3].end(), std::back_inserter(ans));
    printf("%d", ans.size());
}

试题 B: 01 串的熵

本题总分: 5 5 5


【问题描述】

  对于一个长度为 n n n 01 01 01 S = x 1 x 2 x 3 ⋯ x n S = x_1x_2x_3cdots x_n S=x1x2x3xn,香农信息熵的定义为 H ( S ) = − ∑ i n p ( x i ) log ⁡ 2 ( p ( x i ) ) H(S)=-sum_{i}^{n}p(x_i)log_2(p(x_i)) H(S)=inp(xi)log2(p(xi)),其中 p ( 0 ) , p ( 1 ) p(0), p(1) p(0),p(1) 表示在这个 01 01 01 串中 0 0 0 1 1 1 出现的占比。比如,对于 S = 100 S = 100 S=100 来说,信息熵 H ( S ) = − 1 3 log ⁡ 2 ( 1 3 ) − 2 3 log ⁡ 2 ( 2 3 ) − 2 3 log ⁡ 2 ( 2 3 ) = 1.3083 H(S)=-frac 13log_2(frac 13)-frac 23log_2(frac 23)-frac 23log_2(frac 23)=1.3083 H(S)=31log2(31)32log2(32)32log2(32)=1.3083。对于一个长度为 23333333 23333333 23333333 01 01 01 串,如果其信息熵为 11625907.5798 11625907.5798 11625907.5798,且 0 0 0 出现次数比 1 1 1 少,那么这个 01 01 01 串中 0 0 0 出现了多少次?

【答案提交】

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


11027421


对于一个长度为 a + b a + b a+b 0 0 0出现 a a a次的 01 01 01 S S S H ( S ) = − a a a + b log ⁡ 2 ( a a + b ) − b b a + b log ⁡ 2 ( b a + b ) H(S)=-afrac a{a+b}log_2(frac a{a+b})-bfrac b{a+b}log_2(frac b{a+b}) H(S)=aa+balog2(a+ba)ba+bblog2(a+bb),嗯算就完了。

#include <stdio.h>
#include <math.h>

int n = 23333333;

double target = 11625907.5798;

int main() {
    for (double i = 0, j = n; i <= n; i += 1, j -= 1)
        if (abs(i * (- i / n * log2(i / n)) + j * (- j / n * log2(j / n)) - target) < 1e-4) {
            printf("%.0lf", i);
            return 0;
        }
}

试题 C: 冶炼金属

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


【问题描述】

  小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个称作转换率的属性 V V V V V V 是一个正整数,这意味着消耗 V V V 个普通金属 O O O 恰好可以冶炼出一个特殊金属 X X X,当普通金属 O O O 的数目不足 V V V 时,无法继续冶炼。
  现在给出了 N N N 条冶炼记录,每条记录中包含两个整数 A A A B B B,这表示本次投入了 A A A 个普通金属 O O O,最终冶炼出了 B B B 个特殊金属 X X X。每条记录都是独立的,这意味着上一次没消耗完的普通金属 O O O 不会累加到下一次的冶炼当中。
  根据这 N N N 条冶炼记录,请你推测出转换率 V V V 的最小值和最大值分别可能是多少,题目保证评测数据不存在无解的情况。

【输入格式】

  第一行一个整数 N N N,表示冶炼记录的数目。
  接下来输入 N N N 行,每行两个整数 A 、 B A、B AB,含义如题目所述。

【输出格式】

  输出两个整数,分别表示 V V V 可能的最小值和最大值,中间用空格分开。

【样例输入】

3
75 3
53 2
59 2

【样例输出】

20 25

【样例说明】

  当 V = 20 V = 20 V=20 时,有: ⌊ 75 20 ⌋ = 3 , ⌊ 53 20 ⌋ = 2 , ⌊ 59 20 ⌋ = 2 lfloorfrac{75}{20} floor=3,lfloorfrac{53}{20} floor=2,lfloorfrac{59}{20} floor=2 2075=3,2053=2,2059=2,可以看到符合所有冶炼记录。
  当 V = 25 V = 25 V=25 时,有: ⌊ 75 25 ⌋ = 3 , ⌊ 53 25 ⌋ = 2 , ⌊ 59 25 ⌋ = 2 lfloorfrac{75}{25} floor=3,lfloorfrac{53}{25} floor=2,lfloorfrac{59}{25} floor=2 2575=3,2553=2,2559=2,可以看到符合所有冶炼记录。
  且再也找不到比 20 20 20 更小或者比 25 25 25 更大的符合条件的 V V V 值了。

【评测用例规模与约定】

  对于 30 % 30\% 30% 的评测用例, 1 ≤ N ≤ 1 0 2 1 ≤ N ≤ 10^2 1N102
  对于 60 % 60\% 60% 的评测用例, 1 ≤ N ≤ 1 0 3 1 ≤ N ≤ 10^3 1N103
  对于 100 % 100\% 100% 的评测用例, 1 ≤ N ≤ 1 0 4 , 1 ≤ B ≤ A ≤ 1 0 9 1 ≤ N ≤ 10^4,1 ≤ B ≤ A ≤ 10^9 1N1041BA109


V i m a x V_i^{max} Vimax为满足 ⌊ A i V i ⌋ = B i leftlfloorcfrac{A_i}{V_i} ight floor=B_i ViAi=Bi的最大值, V i m i n V_i^{min} Vimin为满足 ⌊ A i V i ⌋ = B i leftlfloorcfrac{A_i}{V_i} ight floor=B_i ViAi=Bi的最小值,则最大的 V V V min ⁡ { V i m a x } min{V_i^{max}} min{Vimax},因为取最大值可能会使 ⌊ A i V i ⌋ > B i leftlfloorcfrac{A_i}{V_i} ight floor>B_i ViAi>Bi成立,同理最小的 V V V max ⁡ { V i m a x } max{V_i^{max}} max{Vimax}
对于 A A A B B B我们取 ⌊ A B ⌋ leftlfloorcfrac{A}{B} ight floor BA V m a x V^{max} Vmax,当 A = V B A=VB A=VB V V V的取值唯一,显然成立,否则 ⌈ A B ⌉ = V m a x + 1 leftlceilcfrac{A}{B} ight ceil = V^{max} + 1 BA=Vmax+1,当取 V m a x + 1 V^{max} + 1 Vmax+1 V V V时带入 ⌊ A V ⌋ = ⌊ B ( V − 1 ) + A ′ V ⌋ < B leftlfloorcfrac{A}{V} ight floor =leftlfloorcfrac{B(V - 1)+A'}{V} ight floor<B VA=VB(V1)+A<B,故 V m a x V^{max} Vmax最大。
考虑到 ⌊ A V ⌋ leftlfloorcfrac{A}{V} ight floor VA为单调减函数,我们取 A , B + 1 A,B+1 A,B+1的最大值加 1 1 1,显然最小。

#include <stdio.h>
#include <algorithm>

int n, a, b, max = 0x3f3f3f3f, min = 0;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &a, &b);
        max = std::min(max, a / b);
        min = std::max(min, a / (b + 1) + 1);
    }
    printf("%d %d", min, max);
}

试题 D: 飞机降落

时间限制: 2.0 s 2.0mathrm s 2.0s 内存限制: 256.0 M B 256.0mathrm{MB} 256.0MB 本题总分: 10 10 10


【问题描述】

   N N N 架飞机准备降落到某个只有一条跑道的机场。其中第 i i i 架飞机在 T i T_i Ti 时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 D i D_i Di 个单位时间,即它最早可以于 T i T_i Ti 时刻开始降落,最晚可以于 T i + D i T_i + D_i Ti+Di 时刻开始降落。降落过程需要 L i L_i Li个单位时间。
  一架飞机降落完毕时,另一架飞机可以立即在同一时刻开始降落,但是不能在前一架飞机完成降落前开始降落。
  请你判断 N N N 架飞机是否可以全部安全降落。

【输入格式】

  输入包含多组数据。
  第一行包含一个整数 T T T,代表测试数据的组数。
  对于每组数据,第一行包含一个整数 N N N
  以下 N N N 行,每行包含三个整数: T i T_i Ti D i D_i Di L i L_i Li

【输出格式】

  对于每组数据,输出 Y E S m YES YES 或者 N O m NO NO,代表是否可以全部安全降落。

【样例输入】

2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20

【样例输出】

YES
NO

【样例说明】

  对于第一组数据,可以安排第 3 3 3 架飞机于 0 0 0 时刻开始降落, 20 20 20 时刻完成降落。安排第 2 2 2 架飞机于 20 20 20 时刻开始降落, 30 30 30 时刻完成降落。安排第 1 1 1 架飞机于 30 30 30 时刻开始降落, 40 40 40 时刻完成降落。
  对于第二组数据,无论如何安排,都会有飞机不能及时降落。

【评测用例规模与约定】

  对于 30 % 30\% 30% 的数据, N ≤ 2 N ≤ 2 N2
  对于 100 % 100\% 100% 的数据, 1 ≤ T ≤ 10 , 1 ≤ N ≤ 10 , 0 ≤ T i , D i , L i ≤ 1 0 5 1 ≤ T ≤ 10,1 ≤ N ≤ 10,0 ≤ T_i, D_i, L_i ≤ 10^5 1T101N100Ti,Di,Li105


感觉暴搜会被卡常,所以选用记忆化搜索,用二进制表示第 i i i位为 1 1 1表示第 i i i量飞机降落,记 d p s t a t u s dp_{status} dpstatus s t a t u s status status表示的降落状态的最早完成时间, − 1 -1 1表示不可达, inf ⁡ inf inf表示未访问,时间复杂度为 O ( ∑ i = 1 T ( N i C N N + ( N i − 1 ) C N N − 1 + ⋯ + C N 1 ) ) = O ( T N 2 N − 1 ) O(sum_{i=1}^T(N_iC_N^N+(N_i-1)C_N^{N-1}+cdots+C_{N}^1)) =O(TN2^{N-1}) O(i=1T(NiCNN+(Ni1)CNN1++CN1))=O(TN2N1)

#include <stdio.h>
#include <algorithm>

int T, n, t[1 << 10], d[1 << 10], l[1 << 10], dp[1 << 10], inf = 0x3f3f3f3f;

int dfs(int status, int depth) {
    if (dp[status] != inf) return dp[status];
    if (depth == n) return dp[status] = t[status] + l[status];
    for (int i = status; i; ) {
        int p = i & -i;
        int q = dfs(status - p, depth + 1);
        if (q != -1 && q <= t[p] + d[p])
            dp[status] = std::min(dp[status], std::max(t[p], q) + l[p]);
        i -= p;
    }
    if (dp[status] == inf) dp[status] = -1;
    return dp[status];
}

void run() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d %d %d", &t[1 << i], &d[1 << i], &l[1 << i]);
    int full = (1 << n) - 1;
    for (int i = 0; i <= full; ++i) dp[i] = inf;
    dfs(full, 1);
    printf(dp[full] >= 0 ? "YES
" : "NO
");
}

int main() {
    scanf("%d", &T);
    while (T--) run();
}

试题 E: 接龙数列

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


【问题描述】

  对于一个长度为 K K K 的整数数列: A 1 , A 2 , ⋯   , A K A_1, A_2, cdots, A_K A1,A2,,AK,我们称之为接龙数列当且仅当 A i A_i Ai 的首位数字恰好等于 A i − 1 A_{i−1} Ai1 的末位数字 ( 2 ≤ i ≤ K ) (2 ≤ i ≤ K) (2iK)
  例如 12 , 23 , 35 , 56 , 61 , 11 12, 23, 35, 56, 61, 11 12,23,35,56,61,11 是接龙数列; 12 , 23 , 34 , 56 12, 23, 34, 56 12,23,34,56 不是接龙数列,因为 56 56 56 的首位数字不等于 34 34 34 的末位数字。所有长度为 1 1 1 的整数数列都是接龙数列。
  现在给定一个长度为 N N N 的数列 A 1 , A 2 , ⋯   , A N A_1, A_2, cdots, A_N A1,A2,,AN,请你计算最少从中删除多少个数,可以使剩下的序列是接龙序列?

【输入格式】

  第一行包含一个整数 N N N
  第二行包含 N N N 个整数 A 1 , A 2 , ⋯   , A N A_1, A_2, cdots, A_N A1,A2,,AN

【输出格式】

  一个整数代表答案。

【样例输入】

5
11 121 22 12 2023

【样例输出】

1

【样例说明】

  删除 22 22 22,剩余 11 , 121 , 12 , 2023 11, 121, 12, 2023 11,121,12,2023 是接龙数列。

【评测用例规模与约定】

  对于 20 % 20\% 20% 的数据, 1 ≤ N ≤ 20 1 ≤ N ≤ 20 1N20
  对于 50 % 50\% 50% 的数据, 1 ≤ N ≤ 10000 1 ≤ N ≤ 10000 1N10000
  对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 1 0 5 , 1 ≤ A i ≤ 1 0 9 1 ≤ N ≤ 10^5,1 ≤ A_i ≤ 10^9 1N1051Ai109。所有 A i A_i Ai 保证不包含前导 0 0 0


  令 d p i , d dp_{i,d} dpi,d [ 1 , i ] [1,i] [1,i]范围内构成的最长接龙序列以 d d d结尾的长度,则有状态转移方程 d p i , d = max ⁡ ( d p i − 1 , d , d p i − 1 , b i ) dp_{i,d}=max(dp_{i-1,d}, dp_{i-1,b_i}) dpi,d=max(dpi1,d,dpi1,bi),其中 b i b_i bi A i A_i Ai的首位数字,然后滚动数组优化下,根据序理论,答案为 N − max ⁡ { d p d } N-max{dp_d} Nmax{dpd}

#include <stdio.h>
#include <string.h>
#include <algorithm>

int n, ans, dp['9' + 1];

char a[18];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%s", &a);
        int last = a[strlen(a) - 1];
        dp[last] = std::max(dp[last], dp[a[0]] + 1);
    }
    for (int i = '1'; i <= '9'; ++i)
        ans = std::max(ans, dp[i]);
    printf("%d", n - ans);
}

试题 F: 岛屿个数

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


【问题描述】

  小蓝得到了一副大小为 M × N M × N M×N 的格子地图,可以将其视作一个只包含字符 ‘ 0 ’ ‘0’ ‘0’(代表海水)和 ‘ 1 ’ ‘1’ ‘1’(代表陆地)的二维数组,地图之外可以视作全部是海水,每个岛屿由在上 / / / / / / / / /右四个方向上相邻的 ‘ 1 ’ ‘1’ ‘1’ 相连接而形成。
  在岛屿 A m A A 所占据的格子中,如果可以从中选出 k k k 个不同的格子,使得他们的坐标能够组成一个这样的排列: ( x 0 , y 0 ) , ( x 1 , y 1 ) , . . . , ( x k − 1 , y k − 1 ) (x0, y0),(x_1, y_1), . . . ,(x_{k−1}, y_{k−1}) (x0,y0),(x1,y1),...,(xk1,yk1),其中 ( x ( i + 1 ) % k , y ( i + 1 ) % k ) (x_{(i+1)\%k}, y_{(i+1)\%k}) (x(i+1)%k,y(i+1)%k) 是由 ( x i , y i ) (x_i, y_i) (xi,yi) 通过上 / / / / / / / / /右移动一次得来的 ( 0 ≤ i ≤ k − 1 ) (0 ≤ i ≤ k − 1) (0ik1),此时这 k k k 个格子就构成了一个 “环”。如果另一个岛屿 B m B B 所占据的格子全部位于这个 “环” 内部,此时我们将岛屿 B m B B 视作是岛屿 A m A A 的子岛屿。若 B m B B A m A A 的子岛屿, C m C C 又是 B m B B 的子岛屿,那 C m C C 也是 A m A A 的子岛屿。
  请问这个地图上共有多少个岛屿?在进行统计时不需要统计子岛屿的数目。

【输入格式】

  第一行一个整数 T T T,表示有 T T T 组测试数据。
  接下来输入 T T T 组数据。对于每组数据,第一行包含两个用空格分隔的整数 M 、 N M、N MN 表示地图大小;接下来输入 M M M 行,每行包含 N N N 个字符,字符只可能是 ‘ 0 ’ ‘0’ ‘0’ ‘ 1 ’ ‘1’ ‘1’

【输出格式】

  对于每组数据,输出一行,包含一个整数表示答案。

【样例输入】

2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111

【样例输出】

1
3

【样例说明】

  对于第一组数据,包含两个岛屿,下面用不同的数字进行了区分:
01111 01111 01111
11001 11001 11001
10201 10201 10201
10001 10001 10001
11111 11111 11111
  岛屿 2 2 2 在岛屿 1 1 1 的 “环” 内部,所以岛屿 2 2 2 是岛屿 1 1 1 的子岛屿,答案为 1 1 1
  对于第二组数据,包含三个岛屿,下面用不同的数字进行了区分:
111111 111111 111111
100001 100001 100001
020301 020301 020301
100001 100001 100001
111111 111111 111111
  注意岛屿 3 3 3 并不是岛屿 1 1 1 或者岛屿 2 2 2 的子岛屿,因为岛屿 1 1 1 和岛屿 2 2 2 中均没有“环”。

【评测用例规模与约定】

  对于 30 % 30\% 30% 的评测用例, 1 ≤ M , N ≤ 10 1 ≤ M, N ≤ 10 1M,N10
  对于 100 % 100\% 100% 的评测用例, 1 ≤ T ≤ 10 , 1 ≤ M , N ≤ 50 1 ≤ T ≤ 10,1 ≤ M, N ≤ 50 1T101M,N50


bfs,先将公海标记出来,然后碰到内海直接当成陆地,注意海洋有八个方向可以扩散。

#include <stdio.h>

char map[66][66], inf = 0x7f;

int T, n, m, offset[]{ -1, 0, 0, 1, 1, 0, 0, -1, -1, -1, -1, 1, 1, 1, 1, -1 };

int h, t, X[2333], Y[2333];

void bfs(int x, int y, int a, int r) {
    X[0] = x, Y[0] = y, map[x][y] = inf;
    for (h = 0, t = 1; h != t;) {
        x = X[h], y = Y[h], ++h;
        for (int i = 0; i < r;) {
            int k = x + offset[i++], g = y + offset[i++];
            if (k < 0 || k >= n || y < 0 || y >= m) continue;
            if (map[k][g] <= a) {
                X[t] = k, Y[t] = g, ++t;
                map[k][g] = inf;
            }
        }
    }
}

void run() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf("%s", map[i]);
    for (int i = 0; i < n; ++i) {
        if (map[i][0] == '0') bfs(i, 0, '0', 16);
        if (map[i][m - 1] == '0') bfs(i, m - 1, '0', 16);
    }
    for (int i = 0; i < m; ++i) {
        if (map[0][i] == '0') bfs(0, i, '0', 16);
        if (map[n - 1][i] == '0') bfs(n - 1, i, '0', 16);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (map[i][j] == '1'){
                bfs(i, j, '1', 8);
                ++ans;
            }
    printf("%d
", ans);
}

int main() {
    scanf("%d", &T);
    while (T--) run();
}

试题 G: 子串简写

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


【问题描述】

  程序猿圈子里正在流行一种很新的简写方法:对于一个字符串,只保留首尾字符,将首尾字符之间的所有字符用这部分的长度代替。例如 i n t e r n a t i o n m internation internation- a l i z a t i o n m alization alization 简写成 i 18 n m i18n i18n K u b e r n e t e s m Kubernetes Kubernetes (注意连字符不是字符串的一部分)简写成 K 8 s m K8s K8s L a n q i a o m Lanqiao Lanqiao 简写成 L 5 o m L5o L5o 等。
  在本题中,我们规定长度大于等于 K K K 的字符串都可以采用这种简写方法(长度小于 K K K 的字符串不配使用这种简写)。
  给定一个字符串 S S S 和两个字符 c 1 c_1 c1 c 2 c_2 c2,请你计算 S S S 有多少个以 c 1 c_1 c1 开头 c 2 c_2 c2 结尾的子串可以采用这种简写?

【输入格式】

  第一行包含一个整数 K K K
  第二行包含一个字符串 S S S 和两个字符 c 1 c_1 c1 c 2 c_2 c2

【输出格式】

  一个整数代表答案。

【样例输入】

4
abababdb a b

【样例输出】

6

【样例说明】

  符合条件的子串如下所示,中括号内是该子串:
[ a b a b ] a b d b m [abab]abdb [abab]abdb
[ a b a b a b ] d b m [ababab]db [ababab]db
[ a b a b a b d b ] m [abababdb] [abababdb]
a b [ a b a b ] d b m ab[abab]db ab[abab]db
a b [ a b a b d b ] m ab[ababdb] ab[ababdb]
a b a b [ a b d b ] m abab[abdb] abab[abdb]

【评测用例规模与约定】

  对于 20 % 20\% 20% 的数据, 2 ≤ K ≤ ∣ S ∣ ≤ 10000 2 ≤ K ≤ |S | ≤ 10000 2KS10000
  对于 100 % 100\% 100% 的数据, 2 ≤ K ≤ ∣ S ∣ ≤ 5 × 1 0 5 2 ≤ K ≤ |S | ≤ 5 × 10^5 2KS5×105 S S S 只包含小写字母。 c 1 c_1 c1 c 2 c_2 c2 都是小写字母。
   ∣ S ∣ |S | S 代表字符串 S S S 的长度。


  几乎裸一维dp,不是这题凭什么值20分啊。

#include <stdio.h>

char s[500023], &c1 = s[500010], &c2 = s[500020];

int i, k, dp[500010];

long long ans = 0;

int main() {
    scanf("%d
%s %s %s", &k, s + 1, &c1, &c2);
    for (i = 1; s[i]; ++i) {
        if (s[i] == c1) dp[i] = 1;
        dp[i] += dp[i - 1];
    }
    while (--i >= k)
        if (s[i] == c2)
            ans += dp[i - k + 1];
    printf("%lld", ans);
}

睡觉了


试题 H: 整数删除

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


【问题描述】

  给定一个长度为 N N N 的整数数列: A 1 , A 2 , ⋯   , A N A_1, A_2, cdots, A_N A1,A2,,AN。你要重复以下操作 K K K 次:
  每次选择数列中最小的整数(如果最小值不止一个,选择最靠前的),将其删除。并把与它相邻的整数加上被删除的数值。
  输出 K K K 次操作后的序列。

【输入格式】

  第一行包含两个整数 N N N K K K
  第二行包含 N N N 个整数, A 1 , A 2 , A 3 , ⋯   , A N A_1, A_2, A_3, cdots, A_N A1,A2,A3,,AN

【输出格式】

  输出 N − K N − K NK 个整数,中间用一个空格隔开,代表 K K K 次操作后的序列。

【样例输入】

5 3
1 4 2 8 7

【样例输出】

17 7

【样例说明】

  数列变化如下,中括号里的数是当次操作中被选择的数:
[ 1 ]   4   2   8   7 [1] 4 2 8 7 [1] 4 2 8 7
5   [ 2 ]   8   7 5 [2] 8 7 5 [2] 8 7
[ 7 ]   10   7 [7] 10 7 [7] 10 7
17   7 17 7 17 7

【评测用例规模与约定】

  对于 20 % 20\% 20% 的数据, 1 ≤ K < N ≤ 10000 1 ≤ K < N ≤ 10000 1K<N10000
  对于 100 % 100\% 100% 的数据, 1 ≤ K < N ≤ 5 × 1 0 5 , 0 ≤ A i ≤ 1 0 8 1 ≤ K < N ≤ 5 × 10^5,0 ≤ A_i ≤ 10^8 1K<N5×1050Ai108


试题  I: 景区导游

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


【问题描述】

  某景区一共有 N N N 个景点,编号 1 1 1 N N N。景点之间共有 N − 1 N − 1 N1 条双向的摆渡车线路相连,形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行,需要花费一定的时间。
  小明是这个景区的资深导游,他每天都要按固定顺序带客人游览其中 K K K 个景点: A 1 , A 2 , ⋯   , A K A_1, A_2, cdots, A_K A1,A2,,AK。今天由于时间原因,小明决定跳过其中一个景点,只带游客按顺序游览其中 K − 1 K − 1 K1 个景点。具体来说,如果小明选择跳过 A i A_i Ai,那么他会按顺序带游客游览 A 1 , A 2 , ⋯   , A i − 1 , A i + 1 , ⋯   , A K , ( 1 ≤ i ≤ K ) A_1, A_2, cdots, A_{i−1}, A_{i+1}, cdots, A_K, (1 ≤ i ≤ K) A1,A2,,Ai1,Ai+1,,AK,(1iK)
  请你对任意一个 A i A_i Ai,计算如果跳过这个景点,小明需要花费多少时间在景点之间的摆渡车上?

【输入格式】

  第一行包含 2 2 2 个整数 N N N K K K
  以下 N − 1 N − 1 N1 行,每行包含 3 3 3 个整数 u , v u, v u,v t t t,代表景点 u u u v v v 之间有摆渡车线路,花费 t t t 个单位时间。
  最后一行包含 K K K 个整数 A 1 , A 2 , ⋯   , A K A_1, A_2, cdots, A_K A1,A2,,AK 代表原定游览线路。

【输出格式】

  输出 K K K 个整数,其中第 i i i 个代表跳过 A i A_i Ai 之后,花费在摆渡车上的时间。

【样例输入】

6 4
1 2 1
1 3 1
3 4 2
3 5 2
4 6 3
2 6 5 1

【样例输出】

10 7 13 14

【样例说明】

  原路线是 2 → 6 → 5 → 1 2 → 6 → 5 → 1 2651
  当跳过 2 2 2 时,路线是 6 → 5 → 1 6 → 5 → 1 651,其中 6 → 5 6 → 5 65 花费时间 3 + 2 + 2 = 7 3 + 2 + 2 = 7 3+2+2=7 5 → 1 5 → 1 51 花费时间 2 + 1 = 3 2 + 1 = 3 2+1=3,总时间花费 10 10 10
  当跳过 6 6 6 时,路线是 2 → 5 → 1 2 → 5 → 1 251,其中 2 → 5 2 → 5 25 花费时间 1 + 1 + 2 = 4 1 + 1 + 2 = 4 1+1+2=4 5 → 1 5 → 1 51 花费时间 2 + 1 = 3 2 + 1 = 3 2+1=3,总时间花费 7 7 7
  当跳过 5 5 5 时,路线是 2 → 6 → 1 2 → 6 → 1 261,其中 2 → 6 2 → 6 26 花费时间 1 + 1 + 2 + 3 = 7 1 + 1 + 2 + 3 = 7 1+1+2+3=7 6 → 1 6 → 1 61 花费时间 3 + 2 + 1 = 6 3 + 2 + 1 = 6 3+2+1=6,总时间花费 13 13 13
  当跳过 1 1 1 时,路线时 2 → 6 → 5 2 → 6 → 5 265,其中 2 → 6 2 → 6 26 花费时间 1 + 1 + 2 + 3 = 7 1 + 1 + 2 + 3 = 7 1+1+2+3=7 6 → 5 6 → 5 65 花费时间 3 + 2 + 2 = 7 3 + 2 + 2 = 7 3+2+2=7,总时间花费 14 14 14

【评测用例规模与约定】

  对于 20 % 20\% 20% 的数据, 2 ≤ K ≤ N ≤ 1 0 2 2 ≤ K ≤ N ≤ 10^2 2KN102
  对于 40 % 40\% 40% 的数据, 2 ≤ K ≤ N ≤ 1 0 4 2 ≤ K ≤ N ≤ 10^4 2KN104
  对于 100 % 100\% 100% 的数据, 2 ≤ K ≤ N ≤ 1 0 5 , 1 ≤ u , v , A i ≤ N , 1 ≤ t ≤ 1 0 5 2 ≤ K ≤ N ≤ 10^5,1 ≤ u, v, A_i ≤ N,1 ≤ t ≤ 10^5 2KN1051u,v,AiN1t105。保证 A i A_i Ai 两两不同。


试题 J: 魔法阵

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


【问题描述】

  给定一棵由 n n n 个结点组成的树以及 m m m 个不重复的无序数对 ( a 1 , b 1 ) , ( a 2 , b 2 ) , ⋯   , ( a m , b m ) (a_1, b_1), (a_2, b_2), cdots, (a_m, b_m) (a1,b1),(a2,b2),,(am,bm),其中 a i a_i ai 互不相同, b i b_i bi 互不相同, a i , b j ( 1 ≤ i , j ≤ m ) a_i , b_j(1 ≤ i, j ≤ m) ai,bj(1i,jm)
  小明想知道是否能够选择一条树上的边砍断,使得对于每个 ( a i , b i ) (a_i, b_i) (ai,bi) 满足 a i a_i ai b i b_i bi 不连通,如果可以则输出应该断掉的边的编号(编号按输入顺序从 1 1 1 开始),否则输出 − 1 -1 1

【输入格式】

  输入共 n + m n + m n+m 行,第一行为两个正整数 n , m n,m nm
  后面 n − 1 n − 1 n1 行,每行两个正整数 x i , y i x_i,y_i xiyi 表示第 i i i 条边的两个端点。
  后面 m m m 行,每行两个正整数 a i , b i a_i,b_i aibi

【输出格式】

  一行一个整数,表示答案,如有多个答案,输出编号最大的一个。

【样例输入】

6 2
1 2
2 3
4 3
2 5
6 5
3 6
4 5

【样例输出】

4

【样例说明】

  断开第 2 2 2 条边后形成两个连通块: { 3 , 4 } , { 1 , 2 , 5 , 6 } {3, 4},{1, 2, 5, 6} {3,4}{1,2,5,6},满足 3 3 3 6 6 6 不连通, 4 4 4 5 5 5 不连通。
  断开第 4 4 4 条边后形成两个连通块: { 1 , 2 , 3 , 4 } , { 5 , 6 } {1, 2, 3, 4},{5, 6} {1,2,3,4}{5,6},同样满足 3 3 3 6 6 6 不连通, 4 4 4 5 5 5 不连通。
   4 4 4 编号更大,因此答案为 4 4 4

【评测用例规模与约定】

  对于 30 % 30\% 30% 的数据,保证 1 < n ≤ 1000 1 < n ≤ 1000 1<n1000
  对于 100 % 100\% 100% 的数据,保证 1 < n ≤ 1 0 5 , 1 ≤ m ≤ n 2 1 < n ≤ 10^5,1 ≤ m ≤ frac n2 1<n1051m2n


风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。