2024蓝桥杯省赛保奖突击班-单调栈、模拟、简单dp_练习题解

  • 开发
  • 30

P1449 后缀表达式

题目链接: P1449
参考思路：

如果遇到的字符是数字，则将连续的数字转成整数，并把操作数后面的"."过滤掉；如果遇到是字符是运算符，则取出操作数栈栈顶的两个元素进行计算，并把结果压回去；如果是“@”，程序结束，输出栈顶（栈底）元素。

C++参考代码
#include <bits/stdc++.h>
using namespace std;
int n, m,i,j,k, a[1010];
string s;
int getint(){//从字符串中获取一个操作数
    int n=0;
    while(s[i]>='0'&& s[i]<='9'){
        n = n * 10 + s[i++]- 48;
    }
    i++; //s[i]= ·过滤操作数后面的“.”return n;
    return n;
}
void cal(){
    //取出两个操作数根据运算符进行计算
    if(s[i] == '+')a[n-1] += a[n];
    else if(s[i] == '-')a[n-1] -= a[n];
    else if(s[i] == '*')a[n-1] *= a[n];
    else if(s[i] == '/')a[n-1] /= a[n];
    n--, i++;//操作数少一个，字符串后移一位
}
int main(){
    cin>>s;
    while(s[i] != '@'){
        if(s[i]< 48)cal();//遇到运算符则计算
        else a[++n]= getint();//读取操作数
    }
    cout<<a[1];
    return 0;
}
java参考代码
import java.util.Scanner;

public class Main {
    static int n = 0, i = 0; // 定义静态变量n和i
    static int[] a = new int[1010]; // 定义一个静态整数数组a，长度为1010
    static String s; // 定义静态字符串s

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        s = scanner.nextLine(); // 从标准输入读取一行字符串

        while (i < s.length() && s.charAt(i) != '@') { // 循环直到字符串结束或遇到'@'
            if (s.charAt(i) < '0') { // 如果字符不是数字，则是运算符
                calculate(); // 调用calculate方法进行计算
            } else { // 如果字符是数字
                a[++n] = getInt(); // 调用getInt方法获取整数并存储在数组a中
            }
        }
        System.out.println(a[1]); // 输出数组a的第一个元素
        scanner.close(); // 关闭Scanner对象
    }

    static int getInt() { // 从字符串中获取一个整数的方法
        int num = 0; // 定义并初始化变量num
        while (i < s.length() && s.charAt(i) >= '0' && s.charAt(i) <= '9') { // 循环直到非数字字符
            num = num * 10 + (s.charAt(i++) - '0'); // 将字符转换为数字并累加到num
        }
        if (i < s.length() && s.charAt(i) == '.') { // 如果数字后面跟着一个点'.'
            i++; // 跳过这个点
        }
        return num; // 返回获取到的整数
    }

    static void calculate() { // 根据运算符进行计算的方法
        switch (s.charAt(i)) { // 根据当前字符选择运算符
            case '+':
                a[n - 1] += a[n]; // 加法运算
                break;
            case '-':
                a[n - 1] -= a[n]; // 减法运算
                break;
            case '*':
                a[n - 1] *= a[n]; // 乘法运算
                break;
            case '/':
                a[n - 1] /= a[n]; // 除法运算
                break;
        }
        n--; // 用掉一个操作数
        i++; // 字符串指针后移一位
    }
}
python参考代码
def getint(s, i):
    n = 0
    while i < len(s) and '0' <= s[i] <= '9':
        n = n * 10 + int(s[i])
        i += 1
    i += 1  # 跳过数字后面的句点
    return n, i

def cal(stack, operator):
    b = stack.pop()
    a = stack.pop()
    if operator == '+':
        stack.append(a + b)
    elif operator == '-':
        stack.append(a - b)
    elif operator == '*':
        stack.append(a * b)
    elif operator == '/':
        stack.append(a // b)  # 使用整数除法

def main():
    s = input()
    i = 0
    stack = []
    while i < len(s) and s[i] != '@':
        if '0' <= s[i] <= '9':
            number, i = getint(s, i)
            stack.append(number)
        else:
            cal(stack, s[i])
            i += 1
    print(stack[0])

if __name__ == '__main__':
    main()

P1540机器翻译

题目链接: P1540
参考思路：

由于本题数据范围较小，我们可以采用指针的方法来解决。

首先，我们创建两个数组。一个数组 a 用于存储标记。在读入单词 x 时，若当前数组 a 中的第 x 位的标记为 1，则表示该单词在内存中；若标记为 0，则表示该单词不在内存中。这样做可以一步判断读入的单词当前是否在内存中，而不必从头到尾搜索。此外，在存入单词时，只需将数组 a 中的第 x 位的标记从 0 改为 1；在删除内存中的单词 x 时，只需将数组 a 的第 x 位的标记从 1 改为 0。这样一来，我们可以在一步到位，大大降低时间复杂度，提高程序效率。这是本题的关键之一，需要仔细体会和理解。

接着，我们创建另一个数组 b，用于存储内存中的单词，并按读入顺序存入。例如，b[1] 中存储的单词 x 是在时间1存入的。需要注意的是，如果当前读入的单词 x 已经在内存中（即 a[x]==1），则不必存入数组 b 中；只有遇到内存中没有的新单词才需要存入。

然后，我们需要引入两个指针。一个是 l，指向当前内存中最先存入的单词，例如 b[l] 是当前内存中第一个存入的单词。另一个是 r，指向当前内存中最后一个存入的单词，例如 b[r] 是当前内存中最后一个存入的单词。因此，数组 b 的第 l 位到第 r 位存储的就是当前内存中的单词。

当遇到新单词时（即 a[x]==0），情况有两种：

  1. 如果内存未被用完（即 r<=m），则指针 r 向右移一位，在 b[r] 中存入新单词，并将数组 a 中单词 x 的标记改为 1。
  2. 如果内存已满（即 r>m），则先删除当前内存中最先存入的单词 b[l]。删除操作不需要太复杂，只需将指针 l 向右移一位，然后再修改数组 a 中 b[l] 位置的标记即可。最后别忘了在 b[r] 中存入新单词 x。
c++参考代码
#include <bits/stdc++.h>
using namespace std;
int n,m,x,ans,l,r,a[1005],b[1005];
int main(){
	cin>>m>>n;
    l=0;r=0;//初始化两个指针
    for (int i=1;i<=n;i++){
        cin>>x;//边读入边做
        if (a[x]==0) {
        	ans++;
            r++;b[r]=x;a[x]=1;//因为每次遇到新单词都要做这些操作，不如搬到判断语句外做，这样程序更简洁
            if (r>m) {
            	l++;
            	a[b[l]]=0;
            }
        }
    }
    cout<<ans;
    return 0;
}
java参考代码
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt(); // 窗口或缓存的最大大小
        int n = scanner.nextInt(); // 总输入数
        int[] a = new int[1005]; // 用于检查项目是否在缓存中
        int[] b = new int[1005]; // 用于存储缓存中的项目（类似队列）
        int l = 0, r = 0, ans = 0; // l 和 r 是缓存窗口的指针，ans 是唯一项目的计数

        for (int i = 1; i <= n; i++) {
            int x = scanner.nextInt(); // 输入项目
            if (a[x] == 0) { // 如果项目尚未在缓存中
                ans++; // 增加唯一计数
                r++;
                b[r] = x; // 将项目添加到缓存中
                a[x] = 1; // 将项目标记为在缓存中
                if (r > m) { // 如果缓存超过其大小
                    l++;
                    a[b[l]] = 0; // 从缓存中移除最旧的项目
                }
            }
        }
        System.out.println(ans); // 输出唯一项目的计数
        scanner.close();
    }
}
python参考代码
m, n = map(int, input().split())  # 同时读取 m 和 n
inputs = list(map(int, input().split()))  # 读取整行输入并转换为整数列表

a = [0] * 1005  # 初始化数组 a
b = [0] * 1005  # 初始化数组 b
ans = 0
l = 0
r = 0

for x in inputs:  # 直接迭代处理输入的整数列表
    if a[x] == 0:
        ans += 1
        r += 1
        b[r] = x
        a[x] = 1
        if r > m:
            l += 1
            a[b[l]] = 0

print(ans)

P9290 Decryption

题目链接: p9290
参考思路：

考虑到"最小"和"最大"对于序列的限制，我们可以采用单调栈来优化数组的维护。对于这道题目，我们需要使用两个栈进行维护：一个是严格单调递减的栈（记作 stk1[n]），另一个是单调递增的栈（记作 stk2[n]）（关于为何使用这两种单调栈的问题建议配合后面的 AC 代码食用）。

其次，这道题还需要利用动态规划（DP）来求解。我们定义一个一维数组 dp[n]，对于任意一个数组下标 i，dp[i] 表示到 i 坐标处，分割出来的序列全为合法序列的最小分割次数。

然后我们来构思状态转移方程，试想，如果当前坐标 i 后（注意是 i 坐标后，否则状态转移会出问题）需要进行分割以构成合法序列，上一次开始分割的坐标 j 需要尽可能地小才能保证转移出的结果是最小的。

有了这样的想法，这时候就应该与前面提到的单调栈来配合了。由于这道题对数组内的顺序有严格要求，因此在使用单调栈时，栈中存储的不是数组变量的值，而是数组变量的下标。

c++参考代码
#include<bits/stdc++.h>
using namespace std;
int n,a[300005],dp[300005],top1,top2,stk1[300005],stk2[300005];
//stk1：严格单调递减栈 stk2：单调递增栈
int main()
{
	cin>>n;
	for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
	for(int i = 1; i <= n; i++)
	{
		while(top1 && a[stk1[top1]] <= a[i]) top1--;
		stk1[++top1] = i;
		while(top2 && a[stk2[top2]] > a[i]) top2--;
		stk2[++top2] = i;
		//维护两个单调栈 
		dp[i] = dp[*lower_bound(stk2 + 1,stk2 + top2 + 1,stk1[top1 - 1]) - 1] + 1;
		 
	}
	cout<<dp[n];
	return 0;
}
java参考代码
//注意！java版本500ms左右过不去
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n + 1];
        int[] mn = new int[n + 1];
        int[] mx = new int[n + 1];
        Deque<Integer> mns = new ArrayDeque<>();
        Deque<Integer> mxs = new ArrayDeque<>();

        mns.addLast(0); // Initialize with 0 to handle base case
        mxs.addLast(0);

        for (int i = 1; i <= n; i++) {
            a[i] = scanner.nextInt();
            while (!mns.isEmpty() && a[i] < a[mns.peekLast()]) {
                mns.removeLast();
            }
            while (!mxs.isEmpty() && a[i] >= a[mxs.peekLast()]) {
                mxs.removeLast();
            }
            mn[i] = mns.isEmpty() ? 0 : mns.peekLast(); // Check if empty before accessing
            mx[i] = mxs.isEmpty() ? 0 : mxs.peekLast(); // Check if empty before accessing
            mns.addLast(i);
            mxs.addLast(i);
        }

        int res = 0;
        for (int i = n; i > 0; ) {
            int j = i;
            // Ensure that mn[j] is a valid index
            while (mx[i] < mn[j] && mn[j] > 0) {
                j = mn[j];
            }
            i = j - 1;
            res++;
        }

        System.out.println(res);
        scanner.close();
    }
}
python参考代码
此题 Python不合适 正式比赛不会出现这种情况。

P1725 琪露诺

题目链接: P1725
参考思路：

假设f[i]表示跳到第 i 个格子的最优值。

初始状态为f[0]=0，表示在原点的价值为0。

状态转移方程为：
f [ i ] = max ⁡ j ∈ [ i − r , i − l ] { f [ j ] + a [ i ] } f[i] =\max_{j\in[i-r,i-l]}\{f[j]+a[i]\} f[i]=j∈[i−r,i−l]max​{f[j]+a[i]}
最终状态为 max(f[n+1],…,f[n+l])，因为琪露诺最终跳到的区间范围是 [n+1,n+l]。

为了优化这一过程，我们观察到 f[i] 的取值只能由决策区间[i−r,i−l] 转移而来，而 a[i] 是定值，因此我们只需考虑决策区间 [i−r,i−l] 对 f[i] 的影响。

根据动态规划的转移方程，我们需要求决策的最大值。因此，我们可以采用一种数据结构来维护决策的最优值。

考虑到每个f[i] 对应一个决策区间，而区间移动的长度是固定的，这启发我们联想到滑动窗口这个概念。我们可以通过动态维护区间的最大值，从而省去一维枚举决策的时间。

维护区间最值可以使用优先队列或者单调队列两种方式。

首先，考虑优先队列的做法。对于堆中的元素，我们需要使用一个 vis[i] 数组来表示是否在队列中，并检查维护的区间是否超出了决策区间，直到删除堆顶元素使其符合条件为止。

每次移动的操作时间复杂度为 O(logn)，因此总时间复杂度为 O(nlogn)。

c++参考代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+50;
int n,l,r,a[N],f[N],vis[N],ans=-1e9,use[N];//use[i]标记f[i]是否合法
priority_queue< pair<int,int> > q;
int main(){
	cin>>n>>l>>r;
	for(int i = 1; i <= 2 * n; i++) f[i]=-1e9;
	for(int i = 0; i <= n; i++) cin>>a[i];
	for(int i = l; i <= r; i++) use[i]=1;
	for(int i = 0; i <= n; i++){
		if(i<l) {q.push(make_pair(-1e9,0));f[i+l]=a[i+l];continue;}
		int y=q.top().second; 
		if(i-r+l-1>=0) vis[i-r+l-1]=1;
		while(vis[y]||!use[y]) { q.pop(); if(q.empty()) break; y=q.top().second;} //删除堆顶不合法的决策
		q.push(make_pair(f[i],i));
		f[i+l]=q.top().first+a[i+l];
		if(use[i]) use[i+l]=1;
	}
	for(int i = n + 1; i <= n + l; i++) if(use[i]) ans=max(ans,f[i]);
	cout<<ans;
	return 0;
}
java参考代码
import java.util.*;

public class Main {
    static final int N = 300050; 
    static int[] a = new int[N];
    static int[] f = new int[N];
    static boolean[] vis = new boolean[N];
    static boolean[] use = new boolean[N];
    static int ans = Integer.MIN_VALUE; // 相当于 C++ 中的 -1e9

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int l = sc.nextInt();
        int r = sc.nextInt();
        Arrays.fill(f, Integer.MIN_VALUE); // 使用 -1e9 初始化 f[]

        for (int i = 0; i <= n; i++) {
            a[i] = sc.nextInt();
        }
        for (int i = l; i <= r; i++) {
            use[i] = true;
        }

        PriorityQueue<Pair> q = new PriorityQueue<>((x, y) -> y.first - x.first); // 基于第一个元素的最大堆
        for (int i = 0; i <= n; i++) {
            if (i < l) {
                q.offer(new Pair(Integer.MIN_VALUE, 0)); // 入队 -1e9,0
                f[i + l] = a[i + l];
                continue;
            }
            int y = q.peek().second;
            if (i - r + l - 1 >= 0) {
                vis[i - r + l - 1] = true;
            }
            while (vis[y] || !use[y]) {
                q.poll();
                if (q.isEmpty()) break;
                y = q.peek().second;
            }
            q.offer(new Pair(f[i], i));
            f[i + l] = q.peek().first + a[i + l];
            if (use[i]) use[i + l] = true;
        }
        for (int i = n + 1; i <= n + l; i++) {
            if (use[i]) ans = Math.max(ans, f[i]);
        }
        System.out.println(ans);
        sc.close();
    }

    static class Pair {
        int first;
        int second;

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }
}
python参考代码
此题 Python不合适 正式比赛不会出现这种情况。
阅读全部

相关推荐

  1. 2024蓝桥杯省赛保奖突击班-单调栈、模拟、简单dp_练习题解

    2024-04-09 10:42:02       31 阅读

  2. 2024蓝桥杯省赛保奖突击班-Day1-二分查找_笔记_练习题解

    2024-04-09 10:42:02       39 阅读

  3. 2024蓝桥杯省赛保奖突击班-Day2-前缀和、差分、尺取_笔记_练习题解

    2024-04-09 10:42:02       35 阅读

  4. 【备战蓝桥杯】2024蓝桥杯赛前突击省一：图论模版篇

    2024-04-09 10:42:02       43 阅读

  9. 2023蓝桥杯省赛真题分糖果 |枚举+DFS

    2024-04-09 10:42:02       54 阅读

  10. [蓝桥杯 2023省模拟题]判断蓝桥

    2024-04-09 10:42:02       57 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-09 10:42:02       94 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-09 10:42:02       100 阅读

  9. 在Django里面运行非项目文件

    2024-04-09 10:42:02       82 阅读

  19. Python语言-面向对象

    2024-04-09 10:42:02       91 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-04-09 10:42:02       85 阅读

热门阅读

  2. 突破编程_C++_网络编程（TCPIP 四层模型（传输层））

    2024-04-09 10:42:02       28 阅读

  3. Docker搭建CodiMD

    2024-04-09 10:42:02       36 阅读

  8. Golang 为什么要使用接口

    2024-04-09 10:42:02       41 阅读

  10. Mysql的四种索引实现方式

    2024-04-09 10:42:02       36 阅读

  12. 【C++】STL--list

    2024-04-09 10:42:02       39 阅读

  19. MYSQL数据库故障排除与优化

    2024-04-09 10:42:02       38 阅读

  24. Puzzle Solving using Reasoning of Large Language Models: A Survey

    2024-04-09 10:42:02       35 阅读

  25. 第7章 事务

    2024-04-09 10:42:02       36 阅读

  30. 业务逻辑之业务安全

    2024-04-09 10:42:02       36 阅读