本文为论文 Magic mirror in my hand, which is the best in the land?An Experimental Evaluation of Index Selection Algorithms 的阅读笔记。 1 引言 🟠 索引对于高效处理数据库工作负载来说很重要，针对索引选择提出的方案有很多，主要的难点是： 解空间是巨大的：随索引数量、列、类型增加 索引间相互作用 很难在部署运行前量化索引对工作负载的影响 🟡 本文描述和分析了 8 种基于不同概念的索引选择算法，并沿着不同的维度进行比较，如解决方案质量、运行时长、多列支持、解决方案粒度和复杂性。 🟢 虚拟索引（hypothetical indexes） 为了避免执行查询、创建索引，一些数据库系统支持虚拟索引，通过它来估计成本。 2 索引选择算法 索引选择算法的里程碑时间轴如下： 2.1 Drop 这种方法依次删除候选索引，直到不能进一步降低成本为止。成本是由数据的特征决定的，而不是由查询优化器决定的。不支持多列索引的选择 2.2 AutoAdmin 该迭代算法通过在每次迭代中增加索引宽度来识别多列索引。首先从每个查询 $j=1,…Q$ 确定候选索引 $S_j$ ，再将所有查询的候选并集作为第二步的输入，确定最佳索引配置时考虑所有查询。 2.3 (Anytime) DTA 首先确定每个查询的候选索引，然后根据原始贪婪枚举确定整个工作负载的索引配置。 2.4 DB2Advis ① 确定候选索引：对每个查询 j ，在列上创建假设索引。然后，向优化器询问查询 j 的最佳计划，在结果计划中使用的假设索引被添加到索引候选集。 ② I 中的所有候选索引都按照它们的逐空间效益比降序排序。下面，如果索引对w1的比值更高，则组合索引对w1和w2，直到达到存储预算。 ③ 将先前计算的解决方案集与不属于的索引集交换，看成本是否降低。 2.5 Relaxation ① 为每个查询获取最佳索引配置。

⏰总用时：89/240 🎯总分：73/150 题号 时间 结果 满分 难度 备注 1 3 ✅ 3 🌕 2 3 ✅ 5 🌕 🔹 在Excel中直接用日期格式拉出答案 3 10 ✅ 9 🌕 🔸 直接用next_permutation(a,a+10) 来枚举 4 15 ✅ 11 🌕 🔹 注意 printf、scanf 中 %*s 的用法 5 1 ✅ 15 🌕 🔸 注意此题 dfs 的用法 6 15 ✅ 17 🌕 🔹 dfs 7 10 ❌ 21 🌓 🔸 全排列+特殊去重🔸 去重旋转：判断 t 是否是 s+s 的子串🔸 在字符串中寻找子串：s.

⏰总用时：146/240 🎯总分：66/150 题号 时间 结果 满分 难度 备注 1 3 ✅ 3 🌕 2 3 ✅ 5 🌕 3 40 ❌ 11 🌓 🔸 直接用 next_permutation(a,a+10) 来枚举所有可能 4 5 ✅ 9 🌕 5 10 ✅ 13 🌓 🔸 消除末尾连续的 1 ： x&(x+1) 6 35 ✅ 15 🌕 🔹 dfs 7 30 ❌ 19 🌓 🔸 先枚举，再用dfs判断连通性🔸 压缩：用一维数组存储2×3矩阵 8 10 ✅ 21 🌕 🔹 暴力枚举 9 5 ❌ 25 🌓 🔸 问题转化为求【最长回文子序列】🔸 动态规划、带备忘录 10 5 ❌ 29 1 【填空】网友年龄 题目 某君新认识一网友。 当问及年龄时，他的网友说： “我的年龄是个 2 位数，我比儿子大 27 岁, 如果把我的年龄的两位数字交换位置，刚好就是我儿子的年龄”

⏰总用时：170/240 🎯总分：32.5/150 题号 时间 结果 满分 难度 备注 1 45 ✅ 5 🌓 🔸 dfs🔸 注意考虑回路的情况 2 15 ❌ 11 🌓 🔹 考虑空盘子的跳法🔹 数据结构、bfs🔹 注意 set 容器的用法 3 5 ❌ 13 🌑 🔸 Burnside引理 4 5 ❌ 17 🌓 🔹 考虑分割线的走法🔹 【dfs】从对称中心开始遍历 5 5 ✅ 7 🌕 6 10 ✅ 9 🌕 7 25 ❌ 19 🌓 🔸 dfs 8 5 ❌ 21 🌓 🔹 动态规划：要判断的包子数设置一个上限🔹 所有包子数最大公因数不为1，则凑不出来的有无数个 9 30 50% 23 🌓 🔸 二分 10 25 ❌ 25 1 【填空】迷宫 题目 X 星球的一处迷宫游乐场建在某个小山坡上。它是由 10×10 相互连通的小房间组成的。房间的地板上写着一个很大的字母。我们假设玩家是面朝上坡的方向站立，则：

⏰总用时：245/240 🎯总分：59.1/150 题号 时间 结果 满分 难度 备注 1 5 ❌ 5 🌕 🔸 计算完一定要带入样例检验，漏加了 1 ❗❗❗ 2 15 ✅ 7 🌕 3 40 ✅ 9 🌕 4 10 ✅ 13 🌕 5 5 ✅ 11 🌕 6 60 ✅ 17 🌕 🔹 注意 scanf，printf 格式化输入输出的使用 7 25 ❌ 19 🌑 🔸 三维差分数组🔸 二分法查找🔸 压缩数组🔸 memcpy()用法 8 25 10% 21 🌓 🔹 【dfs】每次遍历一整块岛屿，并标记其是否能幸存🔹 用%c时小心读入空行等🔹 注意代码中变量类型的错误 9 10 ❌ 23 🌓 🔸 暴力 10 50 ❌ 25 1 【填空】分数 题目 1/1+1/2+1/4+1/8+……

1 创建queue 1 queue<int> q; 2 常用操作 front() 返回 queue 中第一个元素的引用。 back() 返回 queue 中最后一个元素的引用 push(T&& obj) 以移动的方式在 queue 的尾部添加元素。 pop() 删除 queue 中的第一个元素。 empty() 如果 queue 中没有元素的话，返回 true。 size() 返回 queue 中元素的个数。

⏰总用时：170/240 🎯总分：39/150 题号 时间 结果 满分 难度 备注 1 5 ✅ 5 🌕 2 5 ✅ 5 🌕 3 5 ✅ 10 🌕 4 20 ❌ 10 🌓 🔹 用 BFS、queue 遍历🔹 输入地图时用 char 而不是 int 5 35 ❌ 10 🌓 🔸 快速计算 $a^b(mod p)$🔸 快速计算 $a*b(mod p)$ 6 20 20% 15 🌓 🔹 二叉树🔹 先算出每个节点所在层数，再根据层数算总和，这样不会超时 7 40 40% 20 🌓 🔸 模拟🔸 用 map 容器，以外卖店的视角存储订单信息🔸 可以通过的，要注意易错的细节❗❗❗ 8 30 40% 20 🌓 🔹 并查集（不过没用） 9 10 ❌ 25 🌑 🔸 状压dp🔸 fill()：初始化数组，填充内容可不为0 10 25 1 【填空】平方和 题目 小明对数位中含有 2、0、1、9 的数字很感兴趣，在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。

⏰总用时：125/240 🎯总分：14.5/150 题号 时间 结果 满分 难度 备注 1 5 ✅ 5 🌕 2 5 ❌ 5 🌓 🔹 博弈论：只能转移到必胜态的，均为必败态。可以转移到必败态的，均为必胜态🔹 c++中计算字符串中某字符个数：count(s.begin(),s.end(),‘o’)🔹 DFS：深搜的时候保存已有结果🔹 二维数组可直接压缩为一维数组🔹 遍历不连续数组，可把要遍历的索引存储在一个数组中 3 5 30% 10 🌕 🔸 先观察所求式子能否化简，注意超时问题🔸 注意题目所给数据范围，答案应该用 long long型 4 30 40% 10 🌓 🔹 巧妙构造数组可以简化题目🔹 若 a ^ b=x，则 a ^ x=b， b ^ x=a。🔹 可以用 map 来映射一组数和他们的索引🔹 直接把异或表达式放 if 语句或输出语句中会出错 5 5 ❌ 10 🌑 🔸 【分数取模】、【快速幂】🔸 注意找递推关系🔸 加快输入速度：ios::sync_with_stdio(false); cin.

⏰总用时：177/ 🎯总分：0/150 题号 时间 结果 满分 难度 备注 1 20 ❌ 5 🌕 🔸【计算一个整数各位上的数字】：当 i/10!=0 时，不断取出 i%10 。 2 7 ❌ 5 🌕 🔹 确定一条直线要考虑斜率和截距 3 40 ❌ 10 🌓 🔸 整数问题常用【取模】 4 35 ❌ 10 🌕 🔹 二维数组太大容易引起报错：program received signal sigsegv, segmentation fault. （本题中用 int g[2022][2022]; 就报错了QAQ） 5 45 ❌ 10 🌑 🔸 状压dp🔸 移位操作较多，容易出错 6 25 ❌ 15 🌓 🔹 用迭代器循环时不能修改 set 内元素 7 5 ❌ 20 🌓 🔸 【博弈论】重点是判断必胜 8 20 9 25 10 25 1 【填空】卡片 题目 小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个，就保存起来，卡片就不能用来拼其它数了。小蓝想知道自己能从 1 拼到多少。

1 简介 🟠 pair 容器将 2 个普通元素 first 和 second（C++ 基本数据类型、结构体、类自定的类型等）创建成一个新元素<first, second>。 🔵 使用需加上头文件：#include <utility> 2 创建map容器 1️⃣ 调用 pair 容器类的默认构造函数。 1 pair <string, int> pair1; 2️⃣ 在创建 pair 容器的同时，进行初始化。 1 pair <string, int> pair2("语文",90); 3️⃣ 利用先前已创建好的 pair 容器和拷贝构造函数，再创建一个新的 pair 容器。 1 pair <string, int> pair3(pair2); 3 常见用法 3.1 手动为 pair 对象赋值 1 2 pair1.first = "数学"; pair1.second = "100"; 3.

🔴 【动态规划三要素】重叠子问题、最优子结构、状态转移方程 🟢 【思维框架】明确 base case → 明确「状态」→ 明确「选择」 → 定义 dp 数组/函数的含义。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 # ⾃顶向下递归的动态规划 def dp(状态1, 状态2, ...): for 选择 in 所有可能的选择: # 此时的状态已经因为做了选择⽽改变 result = 求最值(result, dp(状态1, 状态2, ...)) return result # ⾃底向上迭代的动态规划 # 初始化 base case dp[0][0][...] = base case # 进⾏状态转移 for 状态1 in 状态1的所有取值： for 状态2 in 状态2的所有取值： for .

1 题目 实现一个计算器，功能如下： 1、输入一个字符串，可以包含 + - * /、数字、括号以及空格，你的算法返回运算结果。 2、要符合运算法则，括号的优先级最高，先乘除后加减。 3、除号是整数除法，无论正负都向 0 取整（5/2=2，-5/2=-2）。 4、可以假定输入的算式⼀定合法，且计算过程不会出现整型溢出，不会出现除数为 0 的意外情况。 2 解析 2.1 字符串转整数 1 2 3 4 5 6 // 把字符串s转为整数n int n = 0; for (int i = 0; i < s.size(); i++) { char c = s[i]; n = 10 * n + (c - '0'); } ❗❗❗ 注意 (c - ‘0’) 的括号不能省略，否则可能造成整型溢出。 2.2 处理加减法 🟠 先给第⼀个数字加⼀个默认符号 +，变成 +1-12+3。