C++java算法
2023 年第十四届蓝桥杯省赛 C/C++ 大学 B 组真题及题解
2023 年第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组的真题与题解。涵盖日期统计、01 串熵、冶炼金属、飞机降落、接龙数列、岛屿个数、子串简写、整数删除等八道题目。提供 C++ 和 Java 两种语言的参考代码，涉及暴力搜索、动态规划、二分查找、优先队列、双向链表等核心算法知识点。旨在帮助参赛者复习备考，掌握竞赛常见题型与解题思路。
2023 年第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组的真题与题解。涵盖日期统计、01 串熵、冶炼金属、飞机降落、接龙数列、岛屿个数、子串简写、整数删除等八道题目。提供 C++ 和 Java 两种语言的参考代码，涉及暴力搜索、动态规划、二分查找、优先队列、双向链表等核心算法知识点。旨在帮助参赛者复习备考，掌握竞赛常见题型与解题思路。
二分查找主要位于 <algorithm> 头文件中。常用的有 lower_bound、upper_bound。
查找第一个大于等于的元素
auto it = lower_bound(vec.begin(), vec.end(), num);
int place = it - vec.begin();
查找最后一个大于的元素
auto it = upper_bound(vec.begin(), vec.end(), num);
int place = it - vec.begin();
cout << *it << " " << (it - vec.begin()) << endl;
判断目标值，是否存在
bool t = binary_search(vec.begin(), vec.end(), num);
C++ 中，emplace 是 C++11 引入的，用于在容器中构建元素，避免复制/移动操作，提高效率。
container.emplace(args...);
push: 先构造对象，可能会传递。 emplace：传参、直接构造。 （具体用法的话，就是原本 push 怎么用，emplace 就代替成 push。 如：push_back--emplace_back） （push--emplace）
std::vector<std::pair<int, int>> vec; // 传统 push_back
vec.push_back(std::make_pair(1, 2));
vec.push_back({3, 4}); // C++11 后可简化
// 使用 emplace_back
vec.emplace_back(5, 6); // 直接构造 pair，更高效
emplace 的容器：
vector、deque、listmap、set、unordered_map、unordered_setpriority_queue（底层容器支持即可）emplace 的容器：
queue、stack 等适配器（接口限制）。在 C++ 里，log() 函数一般是指 <cmath> 头文件里用于进行对数运算的函数。下面会详细介绍 log() 函数的具体用法。
log() 函数原型<cmath> 头文件里定义了几个不同版本的 log() 函数，常用的有：
// 计算自然对数（以 e 为底）
double log(double x);
float log(float x);
long double log(long double x);
这些函数接收一个浮点数参数 x，并返回 x 的自然对数（以自然常数 e 为底）。
需要使用换底公式：log_b(x) = ln(x) / ln(b)。
除了 log() 函数，<cmath> 头文件还提供了其他对数相关的函数：（C++11 及之后适用）
log10: 以 10 为底的对数log2: 以 2 为底的对数问题描述
小蓝现在有一个长度为 100 的数组，数组中的每个元素的值都在 0 到 9 的范围之内。数组中的元素从左至右如下所示：
现在他想要从这个数组中寻找一些满足以下条件的子序列：子序列的长度为 8；这个子序列可以按照下标顺序组成一个 yyyymmdd 格式的日期，并且要求这个日期是 2023 年中的某一天的日期，例如 20230902，20231223。yyyy 表示年份，mm 表示月份，dd 表示天数，当月份或者天数的长度只有一位时需要一个前导零补充。
请你帮小蓝计算下按上述条件一共能找到多少个不同的 2023 年的日期。对于相同的日期你只需要统计一次即可。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
/* 其实本题非常简单，因为它体现了蓝桥杯可以 暴力（dfs）的点： 首先，以 2023 开头是固定的，你可以在前方，先把这个给枝剪掉 然后再剩下 mmdd 这四位中爆搜（dfs，当然多层 for 循环也行）就行，把所有可能给列举出来 切记，一定要防止日期重复，这点很细节。 */
#include <iostream>
#include <vector>
using namespace std;
vector<int> vec{ // 年份剔除，已经存储完毕
3, 8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5,
6, 1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3
};
vector<vector<bool>> ymd(13, vector<bool>(32, false)); // 已经非常确定了
void {
(mm==||mm==||mm==||mm==||mm==||mm==||mm==){
(<dd&&dd<=) ymd[mm][dd]=;
} (mm==){
(<dd&&dd<=) ymd[mm][dd]=;
} (mm==||mm==||mm==||mm==){
(<dd&&dd<=) ymd[mm][dd]=;
}
}
{
(cur==){
mm = (str.(,));
dd = (str.(,));
(mm,dd);
;
}
( i=pla; i<vec.(); ++i){
(cur,i,str+ (vec[i]));
}
}
{
(,,);
sum = ;
( i=; i<ymd.(); ++i){
( j=; j<; ++j){
(ymd[i][j]) sum++;
}
}
cout<<sum<<endl;
;
}
import java.util.ArrayList;
import java.util.List;
public class Main {
// 年份剔除，已经存储完毕
static List<Integer> vec = List.of(
3, 8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5,
6, 1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3
);
// 已经非常确定了
static boolean[][] ymd = new boolean[13][32];
// 检查日期是否合法并标记
static void t {
(mm == || mm == || mm == || mm == || mm == || mm == || mm == ) {
( < dd && dd <= ) {
ymd[mm][dd] = ;
}
} (mm == ) {
( < dd && dd <= ) {
ymd[mm][dd] = ;
}
} (mm == || mm == || mm == || mm == ) {
( < dd && dd <= ) {
ymd[mm][dd] = ;
}
}
}
{
(cur == ) {
Integer.parseInt(str.substring(, ));
Integer.parseInt(str.substring(, ));
t(mm, dd);
;
}
( pla + ; i < vec.size(); ++i) {
dfs(cur + , i, str + vec.get(i));
}
}
{
dfs(, , );
;
( ; i < ymd.length; ++i) {
( ; j < ; ++j) {
(ymd[i][j]) {
sum++;
}
}
}
System.out.println(sum);
}
}
// 只要你不 chu，认真读题，仔细观察，还是能做本题的
/* 但是前提条件之一是，你要知道 log 的用法 =底数; C++ 中，log 默认是 ln(..) ，要做到 log(真数，指数的底数)，这一步， 需要用换底公式：=ln(真数)/ln(指数的底数) 这涉及到，数学中的指数式 与 对数的转换 细节：log(float/double) 内部只能传递这两种类型，传出也是，否则也会被隐式转换 / / 本题的式子，都给的这么明显了，怎么可能还搞不出来？ H(S)= 首先是负号、然后观察 100，一个 1，两个 0。看出什么没？ 当然是后面的对应顺序呀。共 3 个（1 个 1 1/3) (2 个 0 2/3）还有个数。 '0 出现次数比 1 少' 根据题意：所以 0 的个数一定 1~23333333/2，之间的某个数字。 */
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int N = 23333333;
for(int i=1; i<=N/2; ++i){
int n0 = i; // 0 的个数;
int n1 = N-i; // 1 的个数;
double sum = 0;
sum-=(double)n0/N*log((double)n0/N)/ log(2)*n0;
sum-=(double)n1/N*log((double)n1/N)/ log(2)*n1;
if(fabs(sum-11625907.5798)<1e-4){
cout<<n0<<endl;
break;
}
}
return 0;
}
import java.lang.Math;
public class Main {
public static void main(String[] args) {
int N = 23333333;
for (int i = 1; i <= N / 2; ++i) {
int n0 = i; // 0 的个数
int n1 = N - i; // 1 的个数
double sum = 0;
sum -= (double) n0 / N * Math.log((double) n0 / N) / Math.log(2) * n0;
sum -= (double) n1 / N * Math.log((double) n1 / N) / Math.log(2) * n1;
if (Math.abs(sum - 11625907.5798) < 1e-4) {
System.out.println(n0);
break;
}
}
}
}
问题描述
小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 V 时，无法继续冶炼。
现在给出了 N 条冶炼记录，每条记录中包含两个整数 A 和 B，这表示本次投入了 A 个普通金属 O，最终冶炼出了 B 个特殊金属 X。每条记录都是独立的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。
根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。
输入格式
第一行一个整数 N，表示冶炼记录的数目。
接下来输入 N 行，每行两个整数 A、B，含义如题目所述。
输出格式
输出两个整数，分别表示 V 可能的最小值和最大值，中间用空格分开。
样例说明
当 V=20 时，有：⌊75/20⌋=3，⌊53/20⌋=2，⌊59/20⌋=2，可以看到符合所有冶炼记录。
当 V=25 时，有：⌊75/25⌋=3，⌊53/25⌋=2，⌊59/25⌋=2，可以看到符合所有冶炼记录。
且再也找不到比 20 更小或者比 25 更大的符合条件的 V 值了。
// 本题为贪心算法 - 从局部推至整体、 // 我看网上，其他人用了很多复杂的方法，什么差分呐... // 好像用不到耶，只需要，推逼一下极限就行 /* 听好喽，这几部很关键。 什么是转化率消耗的最小值？极限就是你刚好能转化 B+1 块， 但因为是推理出来的极限，实际上是不存在的，也就是差一点点。所以要再结果上在 +1 块 （例：75/4=18，18+1=19，19 就是此时的极限） 同样什么是转化率消耗的最大值？你的所有金属 A，刚好转哈为 B 块。A/B */
#include <iostream>
#define ll long long
using namespace std;
const ll maxl = 0x3f3f3f3f3f3f3f3f; // 伪最大值
int main() {
int t;
cin>>t;
int maxV=maxl,minV=0; // 涉及一个极端情况。
int A,B;
while(t--){
cin>>A>>B;
minV=max((A/(B+1)+1),minV); // 最小值
maxV=min((A/B),maxV); // 最大值
}
cout<<minV<<" "<<maxV;
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long maxV = Long.MAX_VALUE; // 初始化为最大可能值
long minV = 0; // 初始化为最小可能值
int t = scanner.nextInt();
for (int i = 0; i < t; i++) {
long A = scanner.nextLong();
long B = scanner.nextLong();
// 计算当前测试用例的最小和最大值
long currentMin = (A / (B + 1)) + 1;
long currentMax = A / B;
// 更新全局的最小和最大值
if (currentMin > minV) {
minV = currentMin;
}
if (currentMax < maxV) {
maxV = currentMax;
}
}
System.out.println(minV + " " + maxV);
}
}
问题描述
N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间，即它最早可以于 Ti 时刻开始降落，最晚可以于 Ti+Di 时刻开始降落。降落过程需要 Li 个单位时间。
一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。
请你判断 N 架飞机是否可以全部安全降落。
输入格式
输入包含多组数据。
第一行包含一个整数 T，代表测试数据的组数。
对于每组数据，第一行包含一个整数 N。
以下 N 行，每行包含三个整数：Ti，Di 和 Li。
输出格式
对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。
// 我当时写的时候，一直轮询检测超时。我还以为是太暴力了 (┬┬﹏┬┬)，结果...是蓝桥杯官网出问题了，提交不了，可恶。 // 人家都给你飞机了，而且最多不会超过 10 架 // 题都给到这种程度了，还犹豫什么？？？直接爆搜，把所有情况给枚举出来。（最多 10！） // 所以说好听点，本题本质上就是一道组合题目 /* 你要先创建一个数组 used[N]，这台飞机你遍历过没 然后在爆搜期间，维持一个 cnt(原 count、简写)，去记录到底停了几架飞机 ---以上，这些只是方便缕清思路的一环，接下来才是关键--- 咱假设 cur_start 是你的最晚开始落下时间、cur_last 其他飞机能开始落下的时间。 cur_start=Ti+Di 是你的最晚开始落下时间、 而 cur_last=Ti+Di+Li 才是你最晚落下后，并且能让其他飞机降落的时间。 也就是 cur_last = cur_start+Li; 但是认真读过题的都知道！ 开始降落的时间，不一定非要是 Ti+Di, 他取决于 2 点：
此刻 if(other_last>Ti) cur_last = other_last; if(other_last<Ti) cur_last = Ti; （确切的是，画个图就知道了） OK，知道这些了，你确定你还会做不出来吗？ 爆搜开始 */
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e1+5;
int t,n;
vector<bool> used(N,false); // 是否已经降落
vector<vector<int>> res(N,vector<int>(3,0));
int flag = false;
void dfs(int cur ,int tim){ // n
if(cur==n){ // 成功的条件
flag=true;
return;
}
for(int i=0; i<n; ++i){ // 标准回溯
if(!used[i] && tim<=(res[i][0]+res[i][1])){ // tim>vec[i][1] 超过了最晚截止时间
used[i]=true;
// cout<<i<<" "<<used[i]<<" "<<tim<<" "<<res[i][0]<<" "<<res[i][1]<<endl;
int cur_start = max(res[i][0],tim);
dfs(cur+1,cur_start+res[i][2]);
used[i]=false;
}
}
}
{
cin>>t;
(t--){
( i=; i<n; ++i) used[i]=;
cin>>n;
( i=; i<n; ++i){
cin>>res[i][]>>res[i][]>>res[i][];
}
(,);
(flag) cout<<<<endl;
cout<<<<endl;
flag = ;
}
;
}
import java.util.Scanner;
import java.util.ArrayList;
public class Main {
static final int N = 105;
static int t, n;
static boolean[] used = new boolean[N];
static int[][] res = new int[N][3];
static boolean flag = false;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
t = scanner.nextInt();
while (t-- > 0) {
for (int i = 0; i < N; i++) {
used[i] = false;
}
n = scanner.nextInt();
for (int i = 0; i < n; i++) {
res[i][0] = scanner.nextInt();
res[i][1] = scanner.nextInt();
res[i][2] = scanner.nextInt();
}
flag = ;
dfs(, );
(flag) {
System.out.println();
} {
System.out.println();
}
}
scanner.close();
}
{
(cur == n) {
flag = ;
;
}
( ; i < n; i++) {
(!used[i] && tim <= (res[i][] + res[i][])) {
used[i] = ;
Math.max(res[i][], tim);
dfs(cur + , cur_start + res[i][]);
used[i] = ;
}
}
}
}
问题描述
对于一个长度为 K 的整数数列：A1,A2,…,AK，我们称之为接龙数列当且仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2≤i≤K)。例如 12,23,35,56,61,11 是接龙数列；12,23,34,56 不是接龙数列，因为 56 的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。
现在给定一个长度为 N 的数列 A1,A2,…,AN，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,…,AN。
输出格式
一个整数代表答案。
// 有很多，特殊的案例的，11 12 13 35 // 额，字典 dp 这玩意... 我真的还是第一次听说耶， // 挺值得思考的，为什么我在第一次做本题的时候，咋就没有往动态规划上想 // 他们都是这样解释字典 dp 的：利用（哈希表）来储存和管理状态的优化方式 // 简而言之，就是通过，键值对储存最优解，适用于不连续的场景，或范围较大的场景 /* 好啦、知道啥是字典序了，就来解决一下本题 --> 肯定很多人，在一开始，直接想到贪心、局部最优 推导 全局最优。 于是就吓唬乱删一通。 举个例子：11 12 13 35； 你能乱删吗？ 删 13、35 -> 你就会得到 11 12 删 12 -> 你就会得到 11 13 15 那？该怎么做？难道是将所有的可能，都给枚举出来删一遍？ 额、包超时的。 这个时候，你仔细观察就会发现一个很有趣的现象。 毕竟题目就叫做接龙了。 不论你删谁，都跟你的上一个以本首字母，为结尾的字母的状态有关。 这不就是 动态规划，能推导的前提吗？ 原顺序 13 35 34 45 56 __34-45 举个列子：13- -56 （56 你接在谁后面？ --35 这个时候，35 经过判断，会接在 56 后边 所以，这个时候维护一个 dp[0~9] 之后，dp[i] 的含义就是，以 i 为起始位置的串的长度 递归公式 dp[last]=max(dp[start]+1,dp[last]); */
#include <iostream>
using namespace std;
int main() {
int dp[10]={0};
int n;
cin>>n;
for(int i=0; i<n; ++i){
string str;
cin>>str;
int i1 = str[0]-'0';
int i2 = str[str.size()-1]-'0';
dp[i2] = max(dp[i1]+1,dp[i2]);
}
int maxn=0;
for(int i=0; i<10; ++i) maxn=max(maxn,dp[i]);
cout<<n-maxn<<endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] dp = new int[10]; // 初始化动态规划数组
int n = scanner.nextInt();
for (int i = 0; i < n; i++) {
String str = scanner.next();
int i1 = str.charAt(0) - '0'; // 首字符转数字
int i2 = str.charAt(str.length() - 1) - '0'; // 尾字符转数字
// 更新动态规划状态
if (dp[i1] + 1 > dp[i2]) {
dp[i2] = dp[i1] + 1;
}
}
int maxn = 0;
for (int num : dp) {
if (num > maxn) {
maxn = num;
}
}
System.out.println(n - maxn);
}
}
问题描述
小蓝得到了一副大小为 M×N 的格子地图，可以将其视作一个只包含字符 '0'（代表海水）和 '1'（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 '1' 相连接而形成。
在岛屿 A 所占据的格子中，如果可以从中选出 k 个不同的格子，使得他们的坐标能够组成一个这样的排列：(x0,y0),(x1,y1),…,(xk−1,yk−1)，其中 (xi+1modk,yi+1modk) 是由 (xi,yi)( 通过上/下/左/右移动一次得来的 (0≤i≤k−1)，此时这 k 个格子就构成了一个'环'。如果另一个岛屿 B 所占据的格子全部位于这个'环'内部，此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子岛屿，C 又是 B 的子岛屿，那 C 也是 A 的子岛屿。
请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。
// 注：在上网了解一下，emplace 的作用。 // 搜索一下，fill 的作用
// 可恶啊，预处理数组大小开小了。(┬┬﹏┬┬) // 本题是一道典型的搜索类型题目，不论你是用 dfs、还是用 bfs，还是俩个结合着用，不论如何这都是非常酷的。 // 我非常确定，肯定有些人，一上来就直接被 (x0,y0) (x1,y1)...(xi+1modk,yi+1modk) 给整成小迷糊 // 这样会导致失去很多细节 // 仔细审题，最好在纸上，画出来 // 就像本题、通过 上/下/左/右 移动得来的，才算围成环，画图时，就会发现左上呢？右下呢？...等等等 /* 作为一道经典的板子题（套路题） 做这类型的题目，一般就是现在外层围一圈海 简而言之，就是在最外围，多铺垫一层'0'; 本题最大的左右就是，在左上角，（0，0）的位置，首先将所有外海染色， 为啥 (⊙_⊙)？要染色呢，因为没有染色的，必然有两种情况 1、是岛屿 2、是内海 这时，思路就清晰了，只要岛屿在内海中，他就是子岛屿，不用计数，但是也要染色，方便继续搜索。 */ // 拓展一下，就是 emplace 家族的用法。（emplace_back、emplace） // 优点是能直接在容器内，构建元素，避免不必要的拷贝，提高性能 // vector 用 emplace_back(); list、map 等，可用 emplace // 使用方法与 insert、push 类似。不过是传入构造元素所需参数。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 1e2+5;
int T,m,n; // 组 行 列
vector<vector<int>> arr(N,vector<int>(N,0));
struct node{
int x; // 行
int y; // 列
node(int cx,int cy):x(cx),y(cy){}
};
// 一共 8 个方向
int fa1[]={0,0,1,-1,1,1,-1,-1};
int fa2[]={1,-1,0,0,-1,1,-1,1};
queue<node> q;
void bfs(){ // 广搜，用于起始时将外海染色，这个用深搜不太行，因为没法地毯式染色
while(!q.empty()){
x = q.().x, y = q.().y;
q.();
(arr[x][y]!=) ;
(x<||x>m||y<||y>n) ;
arr[x][y]=;
( i=; i<; ++i){
(x+fa1[i]<||x+fa1[i]>m||y+fa2[i]<||y+fa2[i]>n) ;
q.(x+fa1[i], y+fa2[i]);
}
}
}
{
(arr[x][y]!=) ;
(x<||x>m||y<||y>n) ;
arr[x][y]=;
( i=; i<; ++i){
( x+fa1[i], y+fa2[i] );
}
}
{
cin>>T;
(T--){
( i=; i<N; i++)
( j=; j<N; ++j)
arr[i][j]=;
cin>>m>>n;
( i=; i<=m; ++i){
string str;
cin>>str;
( j=; j<=n; ++j)
arr[i][j] = str[j]-;
}
q.(,);
();
sum=;
( i=; i<=m; ++i){
( j=; j<=n; ++j){
(arr[i][j]!=||arr[i][j]!=) ;
sum++;
(i,j);
}
}
cout<<sum<<endl;
}
;
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static final int N = 102;
static int T, m, n;
static int[][] arr = new int[N][N];
static int[] fa1 = {0, 0, 1, -1, 1, 1, -1, -1};
static int[] fa2 = {1, -1, 0, 0, -1, 1, -1, 1};
static Queue<node> q = new LinkedList<>();
static class node {
int x;
int y;
node(int cx, int cy) {
x = cx;
y = cy;
}
}
public static void main(String[] args) {
Scanner scanner = (System.in);
T = scanner.nextInt();
(T-- > ) {
( ; i < N; i++) {
( ; j < N; j++) {
arr[i][j] = ;
}
}
m = scanner.nextInt();
n = scanner.nextInt();
( ; i <= m; i++) {
scanner.next();
( ; j <= n; j++) {
arr[i][j] = str.charAt(j - ) - ;
}
}
q.add( (, ));
bfs();
;
( ; i <= m; i++) {
( ; j <= n; j++) {
(arr[i][j] != || arr[i + ][j] != ) {
;
}
sum++;
dfs(i, j);
}
}
System.out.println(sum);
}
scanner.close();
}
{
(!q.isEmpty()) {
q.peek().x;
q.peek().y;
q.remove();
(arr[x][y] != ) {
;
}
(x < || x > m + || y < || y > n + ) {
;
}
arr[x][y] = ;
( ; i < ; i++) {
(x + fa1[i] < || x + fa1[i] > m + || y + fa2[i] < || y + fa2[i] > n + ) {
;
}
q.add( (x + fa1[i], y + fa2[i]));
}
}
}
{
(arr[x][y] != ) {
;
}
(x < || x > m + || y < || y > n + ) {
;
}
arr[x][y] = ;
( ; i < ; i++) {
dfs(x + fa1[i], y + fa2[i]);
}
}
}
问题描述
程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internation-alization 简写成 i18n，Kubernetes（注意连字符不是字符串的一部分）简写成 K8s, Lanqiao 简写成 L5o 等。
在本题中，我们规定长度大于等于 K 的字符串都可以采用这种简写方法（长度小于 K 的字符串不配使用这种简写）。
给定一个字符串 S 和两个字符 c1 和 c2，请你计算 S 有多少个以 c1 开头 c2 结尾的子串可以采用这种简写？
在遍历第二遍，从 k-1 开始，当遇到 b 时，直接 arr(下标-k+1)，求这个位置，有几个能匹配成 a--b;然后累加。 没喽 */
#include <iostream>
#include <vector>
#define ll long long
using namespace std;
const ll N = 5e5+5;
int main() {
int k;
cin>>k;
string str;
char c1,c2;
cin>>str;
cin>>c1>>c2;
vector<ll> vec(N,0);
if(str[0]==c1) vec[0]++;
ll sum=0;
for(int i=1; i<str.size(); ++i){
if(str[i]==c1) vec[i]=vec[i-1]+1;
else vec[i]=vec[i-1];
}
for(int i=k-1; i<str.size(); ++i){
if(str[i]==c2) sum+=vec[i-(k-1)];
}
cout<<sum<<endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取间隔长度 k
int k = scanner.nextInt();
// 读取字符串
String str = scanner.next();
// 读取两个字符 c1 和 c2
char c1 = scanner.next().charAt(0);
char c2 = scanner.next().charAt(0);
scanner.close();
long[] vec = new long[str.length()]; // 初始化前缀和数组的第一个元素
if (str.charAt(0) == c1) {
vec[0] = 1;
}
// 计算前缀和数组
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == c1) {
vec[i] = vec[i - 1] + 1;
} else {
vec[i] = vec[i - 1];
}
}
long ;
( k - ; i < str.length(); i++) {
(str.charAt(i) == c2) {
sum += vec[i - (k - )];
}
}
System.out.println(sum);
}
}
问题描述
给定一个长度为 NN 的整数数列：A1,A2,…,AN。你要重复以下操作 K 次：
每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。
输出 K 次操作后的序列。
OK 了，其他的，想必大家就清楚了 切接，priority_queue 默认大堆顶 */
#include <iostream>
#include <vector>
#include <queue>
#define ll long long
const ll N = 1e6+5;
ll n,k;
using namespace std;
vector<ll> pre(N, 0);
vector<ll> ne(N, 0);
vector<ll> sum(N,0);
vector<ll> a(N,0);
// 重载
struct cmp{
// !!!
bool operator() (const pair<ll,ll>& p1, const pair<ll,ll>& p2){
if(p1.first == p2.first) return p1.second > p2.second; // 值相同选下标小的
return p1.first > p2.first;
}
};
int main() // 天呐，这些都是什么东西 · {
cin>>n>>k;
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,cmp> p;
ne[]=;
( i=; i<=n; ++i){
ll val;
cin>>val;
p.(val,i);
}
(k--){
ll val = p.().first;
ll y = p.().second;
(sum[y]){
val += sum[y];
p.();
p.(val,y);
sum[y]=;
val = p.().first;
y = p.().second;
}
sum[pre[y]]+=val;
sum[ne[y]]+=val;
pre[ne[y]]=pre[y];
ne[pre[y]]=ne[y];
p.();
}
(!p.()){
a[p.().second]=p.().first;
p.();
}
( i=; i<=n; i++)
(a[i]+sum[i])
cout<<a[i]+sum[i]<<;
;
}
import java.util.PriorityQueue;
import java.util.Scanner;
// 自定义比较器，用于优先队列
class PairComparator implements java.util.Comparator<Pair> {
@Override
public int compare(Pair p1, Pair p2) {
if (p1.val == p2.val) {
return Long.compare(p1.index, p2.index);
}
return Long.compare(p1.val, p2.val);
}
}
// 定义 Pair 类，用于存储值和索引
class Pair {
long val;
long index;
Pair(long val, long index) {
this.val = val;
this.index = index;
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long n = scanner.nextLong();
long k = scanner.nextLong();
long[] pre = new long[(int) (n + 2)];
long[] ne = new long[() (n + )];
[] sum = [() (n + )];
[] a = [() (n + )];
PriorityQueue<Pair> p = <>( ());
ne[] = ;
( ; i <= n; i++) {
scanner.nextLong();
p.offer( (val, i));
pre[i] = i - ;
ne[i] = i + ;
}
( ; i < k; i++) {
p.poll();
top.val;
top.index;
(sum[() y] != ) {
val += sum[() y];
sum[() y] = ;
p.offer( (val, y));
top = p.poll();
val = top.val;
y = top.index;
}
sum[() pre[() y]] += val;
sum[() ne[() y]] += val;
pre[() ne[() y]] = pre[() y];
ne[() pre[() y]] = ne[() y];
}
(!p.isEmpty()) {
p.poll();
a[() pair.index] = pair.val;
}
;
( ; i <= n; i++) {
(a[i] + sum[i] != ) {
(!first) {
System.out.print();
}
System.out.print(a[i] + sum[i]);
first = ;
}
}
System.out.println();
scanner.close();
}
}
后面的两道题，咱时间有限，就先跳过啦。 要学会做减法。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online