题目大意 给定一个只包含字符 a 和 b 的字符串，通过删除字符（可以不删除）将其转化为满足以下条件的最长字符串： 字符串可以分为三段。 第一段和第三段仅包含 a。 第二段仅包含 b。 每一段都可以为空。 解决思路 可以使用动态规划解决，$dp_{i,j}$ 表示前 $i$ 个字符，第 $j$ 段时，最长美丽字符串的长度，其中 $j\in{0,1,2}$。 可以考虑逐个考虑字符串 $s$ 的每一位： 如果 $s_i$ 是 a，那么： $dp[i][0]=dp[i-1][0]+1$，即第一段延长； $dp[i][1]=dp[i-1][1]$，即第二段不变； $dp[i][2]=\max(dp[i-1][1],dp[i-1][2])+1$，即第三段开始或延长。 如果 $s_i$ 是 b，那么： $dp[i][0]=dp[i-1][0]$，即第一段不变； $dp[i][1]=\max(dp[i-1][0],dp[i-1][1])+1$，即第二段开始或延长； $dp[i][2]=dp[i-1][2]$，即第三段不变。 则最终答案是 $\max(dp[n][0],\max(dp[n][1],dp[n][2]))$，其中，$n$ 为字符串 $s$ 的长度。 代码 #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define int long long #define tem template #define sizet size_t #define il inline #define uni union #define endl "\n" const int INF=0xfffffff; using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; int dp[5005][3]; signed main() { char a; a=getchar(); dp[0][0]=dp[0][2]=(a=='a')?1:0;//初始化 dp[0][1]=1-dp[0][0]; string s; cin>>s; for(int i=0;i<s.size();i++) { if(s[i]=='a')//状态转移 { dp[i+1][0]=dp[i][0]+1; dp[i+1][1]=dp[i][1]; dp[i+1][2]=max(dp[i][1],dp[i][2])+1; } else { dp[i+1][0]=dp[i][0]; dp[i+1][1]=max(dp[i][0],dp[i][1])+1; dp[i+1][2]=dp[i][2]; } } cout<<max(dp[s.size()][0],max(dp[s.size()][1],dp[s.size()][2]))<<endl; return 0; } 时间复杂度 $O(|s|)$，其中 $|s|$ 是字符串 $s$ 的长度。 空间复杂度 $O(|s|)$。

在放代码之前，先介绍一个库—— pbds（Policy-Based Data Structures），这是一个 GNU C++ STL 的扩展库，提供了增强版数据结构，包括优先队列，平衡树。 在 pbds 库中，有一个容器，叫 tree，是一种平衡二叉搜索树，可以支持按排名访问元素。 tree 容器 定义 template< typename Key, // 元素类型 typename Mapped, // 映射值类型 (相当于 map 的映射值)，模拟 set 时无需该项，设为 null_type即可 typename Cmp_Fn, // 比较函数，例如 less<Key> 等，也可以使用自定义比较函数 typename Tag, // 树类型 rb_tree_tag（红黑树，默认是这个） / splay_tree_tag template<typename Const_Node_Iterator, typename Node_Iterator, typename Cmp_Fn_, typename Allocator_>class Node_Update // 节点更新策略，例如 tree_order_statistics_node_update >class tree; 使用前提 需要包含<ext/pb_ds/assoc_container.hpp>，<ext/pb_ds/tree_policy.hpp> 头文件（注意，万能头文件中一般不含这两个头文件）。 使用 find_by_order 或 order_of_key 函数时，必须使用 tree_order_statistics_node_update 策略。 默认去重，重复元素需用 pair 处理。 核心功能/函数 功能函数说明返回值/类型时间复杂度 *插入元素insert(x)插入元素 x（唯一）voidO(log n)删除元素erase(x)删除值等于 x 的元素voidO(log n)查找元素find(x)返回迭代器iteratorO(log n)查找第 k 小find_by_order(k)返回第 k 小元素，0-indexiteratorO(log n)查询排名order_of_key(x)返回严格小于 x 的元素数量intO(log n)大小size()当前元素个数intO(1)是否为空empty()检查是否为空boolO(1)清空clear()删除所有元素voidO(n) *：时间复杂度是在 rb_tree_tag 的基础上计算的。 『题解』P1168中位数 题目大意 题目等价于：动态维护前i个元素的有序序列，快速取第k小元素。 中位数的下标 $\displaystyle k=\frac{i}{2}$ (1-indexed)。 输入 $N \le 1 0^{5}$，元素范围 $0 \le A_{i}\le 1 0^{9}$。 代码实现 #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define int long long using namespace std; using namespace __gnu_pbds;//使用 __gnu_pbds 命名空间 tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>s;//定义一棵平衡树 signed main() { int n; cin>>n; for (int i=1;i<=n;i++) { int x; cin>>x; s.insert({x,i});//将每一个值插入树中，i 避免重复 if(i%2==1) //如果是奇数项 { cout<<s.find_by_order(i/2)->first<<"\n";//输出排名为 i/2 的项的值，即前 1~i 位的中位数 } } return 0; } 时间复杂度 $\mathcal{O}(n \log n)$。

问题描述 将一个后缀表达式（逆波兰表示法）转换成另一种形式，使得使用队列进行计算的结果与使用栈计算原表达式的结果相同。 思路 构建表达式树：从左到右读取输入的后缀表达式，构建一个二叉表达式树。 bfs 遍历：对构建好的表达式树进行广度优先搜索。 反转结果：将遍历的结果反转，就得到了最终答案。 BFS 反转分析 1. 初始状态 表达式树根节点为 A，其他节点按层次排列。 2. BFS 第一层 第一步，访问根节点 A。将 A 的值添加到结果字符串中，并将 A 的子节点 B 和 C 加入队列。 3. BFS 第二层 接下来访问 A 的子节点 B 和 C。将 B 和 C 的值添加到结果字符串中，并将它们的子节 D、E、F 和 G 加入队列。 4. BFS 第三层 最后访问 B 和 C 的子节点 D、E、F 和 G。将它们的值添加到结果字符串中。由于这些节点没有子节点，跳出递归。 5. 最终结果 BFS 遍历的结果字符串为：ABCDEFG。 将这个结果反转后，得到最终答案：GFEDCBA。 这个反转后的字符串就是我们需要求的，使用队列计算时与原后缀表达式使用栈计算结果相同的新表达式。 代码实现 #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define int long long using namespace std; using namespace __gnu_pbds; struct Node { char value; Node *left,*right; Node(char v):value(v),left(nullptr),right(nullptr){} }; Node* build(const string& expr)//建树 { stack<Node*>st; for (char c:expr) { Node* node=new Node(c); if(isupper(c)) { node->right=st.top();st.pop(); node->left=st.top();st.pop(); } st.push(node); } return st.top(); } string bfs(Node* root)//bfs 遍历搜索 { string ans; queue<Node*>q; q.push(root); while(!q.empty()) { Node* node=q.front();q.pop(); ans+=node->value; if(node->left) q.push(node->left); if(node->right) q.push(node->right); } return ans; } signed main() { int T; cin>>T; while(T--) { string expr;//表达式 cin>>expr; Node* root=build(expr); string ans=bfs(root); reverse(ans.begin(),ans.end());//翻转 cout<<ans<<endl; } return 0; } 时间复杂度 构建表达式树和层序遍历的时间复杂度都是 $O(n)$，其中 $n$ 是表达式的长度。

这题一看数据范围 $n\leq 10^{18}$ 就知道暴力会超时，所以这题一定有规律可循。 找规律：（以下 1 代表 true，0 代表 false） 题意： 当一个人为 $1$ 时，后面两个人只能为 $01$ 或 $10$。 当一个人为 $0$ 时，后面两个人只能为 $00$ 或 $11$​。 第一位为 1 接 01 字符串变为 $101$，第二位为 $0$，且 $0$ 之后一定为 $00$ 或者 $11$，且第三位为 $1$，所以第四位一定为 $1$，字符串变 为：$1011$。 依此规律向下推，依次为 $10110$，$101101$，$1011011$，$10110110$。 可见一直出现 $101$，即当 $n$ 整除 $3$ 时，每三位中都出现一次假，总共有 $\frac{n}{3}$ 个假，答案加上 $\frac{n}{3}$。 接 10 依次推理，为 $110$，$1101$，$11011$，$110110$，$1101101$，$11011011$​。 可见一直出现 $110$，即当 $n$ 整除 $3$ 时，每三位中都出现一次假，总共有 $\frac{n}{3}$ 个假，答案再加上 $\frac{n}{3}$。 第一位为 0 接 11 也不难得到 $011$，$0110$，$01101$，$011011$，$0110110$，$01101101$​。 可见一直出现 $011$，即当 $n$ 整除 $3$ 时，每三位中都出现一次假，总共有 $\frac{n}{3}$ 个假，答案再加上 $\frac{n}{3}$。 接 00 分别得到 $000$，$0000$，$00000$，$000000$，$0000000$，$00000000$。 无论 $n$ 为几，都出现 $n$ 次假，答案加上 $n$。 总结 当 $n$ 整除 $3$ 时，答案为$$\frac{n}{3}+\frac{n}{3}+\frac{n}{3}+n=2\times n$$当 $n$ 不整除 $3$ 时，答案就为 $n$，即 $n$ 个假相接。 代码： c++ #include <bits/stdc++.h> #define int long long using namespace std; inline void solve() { int n; cin>>n; cout<<(!(n%3)?(n*2):n)<<endl; } signed main() { int t; cin>>t; while(t--)solve(); return 0; } 介于是 Python 组的题目，也放一下 Python 代码 Python t=int(input()) for _ in range(t): n=int(input()) if n%3==0: print(n*2) else: print(n)

题目大意 给定从 $1$ 到 $n$ 编号的牌，初始按 $1$ 在顶部、$n$ 在底部的顺序排列。进行了 $k$ 次操作，操作类型包括： 移除顶部的牌； 移除底部的牌； 移除顶部或底部的任意一张牌。 需判断每张牌的状态：被移除（输出 -）、保留（输出 +）或状态不确定（输出 ?）。 思路 通过三个变量统计新的顶部位置 $ctop$，新的底部位置 $cback$ 以及未知移除的个数 $uk$。 之后遍历 $1\sim n$，分如下几种情况： 情况一：如果操作次数 $k$ 大于等于总数 $n$​，则说明已经没有牌存在了，直接输出 -。\ 情况二：如果当前位置不在顶位置加上未知移除数以及底位置减去未知移除数的范围中，则说明即使未知移除全为同一个操作也无法移除当前位置，输出 +。 情况三：如果当前位置不在顶位置以及底位置之间，则一定被移除了，输出 -。 情况四：剩余情况即为不确定，输出 ?。 代码实现 #include<bits/stdc++.h> #define int long long using namespace std; inline void solve() { int n,k,ctop=0,cback=0,uk=0;string s; cin>>n>>k>>s; cback=n;//初始化底位置 for(char c:s) { if(c=='0')//更新顶位置 { ctop++; } else if(c=='1')//更新底位置 { cback--; } else//更新未知位置 { uk++; } } for(int i=1;i<=n;i++) { if(k>=n)cout<<"-";//情况1 else if(i>ctop+uk&&i<cback-uk+1)cout<<"+";//情况2 else if(i<=ctop||i>=cback+1)cout<<"-";//情况3 else cout<<"?";//情况4 } puts(""); } signed main() { int t; cin>>t;//别忘了 t 组样例 while(t--) { solve(); } return 0; } 复杂度 时间复杂度为 $\mathcal{O}(t(k+n))$。

前言 珂朵莉树Old Driver Tree (ODT) 是一种十分暴力的数据结构。珂朵莉树是一场 CF 比赛中提出的数据结构，因那道题题面（CF896C）关于珂朵莉而得名。 珂朵莉树适用于以下的情况：维护一个序列，有区间赋值操作，数据随机。下面是珂朵莉树板子题： 维护一个序列，需要支持以下操作 1. 将 $[l,r]$ 区间所有数加上 $x$ 2. 将 $[l,r]$ 区间所有数改成 $x$ 3. 求 $[l,r]$ 区间第 $k$ 小 4. 求 $[l,r]$ 区间每个数字的 $x$ 次方的和模 $y$ 的值 (即 $\left(\sum_{i=l}^{r} a_{i}^{x}\right) \bmod y$) – CF896C Willem, Chtholly and Seniorious 支持的操作还可以有很多，只要暴力能做珂朵莉树一般都可以做。 珂朵莉树的思想是维护一堆区间，合并相同值的区间，这样区间总数就可以减少。 珂朵莉树非常依赖区间赋值操作，如果区间赋值操作很少或者区间赋值的区间都较短，那么珂朵莉树和暴力就没什么区别了。 显然，要卡珂朵莉树非常容易。但对于数据完全随机的情况，珂朵莉树就可以跑得飞快。有很多题可以用珂朵莉树水过，甚至比正解还快。 思路 珂朵莉树维护了很多区间。 一个区间表示一段相同的数。一个区间 $(l,r,num)$ 表示从左端点 $l$ 到右端点 $r$，中间的数字全部为 $num$。 例如 $1,2,3,3,3,4,4,5$ 可以用 $5$ 个区间来表示：$(1,1,1)(2,2,2)(3,5,3)(6,7,4)(8,8,5)$。 区间赋值的时候，我们可以删去一些区间并用一个大区间代替它们，区间数量就少了很多。 而查询只需要找出相应的区间，然后暴力统计即可。 如果某次操作的边界在某个区间的中心，那么将这个区间断开即可。 我们用 set 维护区间左端点位置的值，使区间始终保持有序。 区间结构体定义 struct node { long long l,r; mutable long long num; bool operator<(const node y) const { return l<y.l; } }; Split Split 操作用来将一个区间断开。 set<node>::iterator split(long long x) { node tmp={x}; set<node>::iterator it=s.lower_bound(tmp); if(it!=s.end()&&it->l==x) { return it; } it--; long long l=it->l,r=it->r,num=it->num; s.erase(it); tmp={l,x-1,num}; s.insert(tmp); tmp={x,r,num}; return s.insert(tmp).first; } 区间赋值操作 (Assign) 删除该区间所覆盖的所有小区间，并插入一个大区间来代替它们。 void assign(long long l,long long r,long long x) { set<node>::iterator R=split(r+1); set<node>::iterator L=split(l); s.erase(L,R); node tmp={l,r,x}; s.insert(tmp); } 查询操作 就是暴力，找出相应区间并暴力统计 区间和 long long query_sum(long long l,long long r) { set<node>::iterator R=split(r+1),L=split(l); long long ans=0; while (L!=R) { ans+=L->num*(L->r-L->l+1); //遍历求和 ans%=y; L++; } return ans; } 区间 x 次方和 和求和一样，只是改成快速幂 long long query_pow_sum(long long l,long long…