在放代码之前，先介绍一个库—— pbds（Policy-Based Data Structures），这是一个 GNU C++ STL 的扩展库，提供了增强版数据结构，包括优先队列，平衡树。 在 pbds 库中，有一个容器，叫 tree，是一种平衡二叉搜索树，可以支持按排名访问元素。 tree 容器 定义 template< typename…

问题描述 将一个后缀表达式（逆波兰表示法）转换成另一种形式，使得使用队列进行计算的结果与使用栈计算原表达式的结果相同。 思路 构建表达式树：从左到右读取输入的后缀表达式，构建一个二叉表达式树。 bfs 遍历：对构建好的表达式树进行广度优先搜索。 反转结果：将遍历的结果反转，就得到了最终答案。 BFS 反转分析 1. 初始状态 表达式树根节点为 A，…

这题一看数据范围 $n\leq 10^{18}$ 就知道暴力会超时，所以这题一定有规律可循。 找规律：（以下 1 代表 true，0 代表 false） 题意： 当一个人为 $1$ 时，后面两个人只能为 $01$ 或 $10$。 当一个人为 $0$ 时，后面两个人只能为 $00$ 或 $11$​。 第一位为 1 接 01 字符串变为 $101$，第…

题目大意 给定从 $1$ 到 $n$ 编号的牌，初始按 $1$ 在顶部、$n$ 在底部的顺序排列。进行了 $k$ 次操作，操作类型包括： 移除顶部的牌； 移除底部的牌； 移除顶部或底部的任意一张牌。 需判断每张牌的状态：被移除（输出 -）、保留（输出 +）或状态不确定（输出 ?）。 思路 通过三个变量统计新的顶部位置 $ctop$，新的底部位置 $…

前言 珂朵莉树Old Driver Tree (ODT) 是一种十分暴力的数据结构。珂朵莉树是一场 CF 比赛中提出的数据结构，因那道题题面（CF896C）关于珂朵莉而得名。 珂朵莉树适用于以下的情况：维护一个序列，有区间赋值操作，数据随机。下面是珂朵莉树板子题： 维护一个序列，需要支持以下操作 1. 将 $[l,r]$ 区间所有数加上 …