今天好像没什么可以讲的。 今天主要是讲关于线段树的题目。但是题目内容目前还在做，而且主要做的是洛谷和vjudge的题目，所以信友队上没什么提交。 话说老师手把手带我们写一堆题目。难度…就是有点爆表。 具体看下面的图片$\downarrow$ 再加上今天做的事比较多，总共就没多少时间做题了。

洛谷上本文的链接 思路本题的情况大致分为两种： 有人不是种子选手 都是种子选手 有人不是种子选手的情况比较简单，因为都是随机抽签，所以最小的相遇的可能性就是 1。 否则需要计算两人的批次后计算最小相遇轮数。步骤： 确定批次。批次为满足条件 $2^{l-1}<x\le 2^l$ 的最小 $l$。 最小相遇轮数为 $8-\max(a,b)+1$。其中 $a,b$ 为两人的批次。 最后直接

今天主要讲了啥都不是（杂题）其实是模考。 但是全班这个断网的模考，对惨的就是我。由于集训带了一个台式机，所以没法搬到考试的地方，就只能用备用的电脑。 题目T1这题还是比较简单（其实是纯签到题）。唯一可能错的原因就是把输出的内容抄错了。 代码就是输入每个数，判断是否为0，如果不为0，就去过的地方加一。最后判断去过的地方的数量，输出对应的内容即可。 T2这题的正解其实就是暴力枚举。 但是考试的时候不知

洛谷同文链接 题意给你 $n$ 根青菜，$m$ 个机器人，机器人洗菜用 $a$ 的时间，做菜用 $b$ 的时间。求多久之后菜能做好。 思路使用一个小根堆调度。确保每次出队的都是最早空闲的机器人。 然后先让机器人完成所有物品的清洗，对于每个机器人，完成清洗任务后再次进入队列，作为空闲机器人等待下一次使用。 当所有的菜都洗碗之后，让空闲的机器人从处理洗菜任务变成开始处理水煮任务。水煮任务的处理逻辑同以

搜索优化今天又去上大班课，然后又把我热死了。 为什么要优化在比赛中，搜索一般用于取得部分分，而且大部分时候无法通过都是因为超时。 但是，搜索还是很多高级算法的基础。所以，搜索还是很重要的。 三种优化剪枝遇到一些显然不合法/不是最优解的答案时直接返回。 当然，剪枝的缺点（？）就是很难分析剪枝后的算法的时间复杂度，所以也很难预测分数。所以，剪枝其实和卡常一样，也是比较适合在骗分的时候使用。

题目T1采用预计算$+$哈希映射的策略，提前处理可能的平方数，再通过查询快速返回结果： 预计算阶段：生成数据范围内的平方数，统计其各位数字的出现次数，并考虑添加不同数量的0后的数字组成，存储到映射中（确保记录最小的平方数）。 查询阶段：对于输入数字，统计其数字组成，直接到映射中查找是否存在匹配的记录，返回对应的最小平方数或-1。 查询： 处理输入：对于每个测试用例，读取数字n，统计其各位数字

树状数组lowbit正整数$x$的二进制写法里最右边（也就是最后）那个1被称为$x$的$\text{lowbit}$ $\text{lowbit}(x)$是能整数$x$的2的最高次方 计算方法：$x\text{&}-x$（最简洁） 123int lowbit(int x){ return x&(-x);} 对于正整数$x,-x$的编码是把$x$的编码

题目T1图的表示：每个节点有两个可能的 “出口”（用$endss[i][0]$和$endss[i][1]$表示），分别对应两种方向标记（如$R$和非$R$，通过change函数映射为0和1）。每个出口存储连接的目标节点和对应的反向标记（确保边的双向性）。 连通分量遍历：用 DFS 遍历所有未访问的节点，探索其所在的连通分量，记录分量中的节点总数（re1）和边总数（re2）。由于每条边被双向记录（如

线段树概念二叉树二叉树满足条件： 有根树 每个节点的孩子不超过两个 孩子有左右之分 满二叉树是指所有层都是完整的二叉树，即如果二叉树有$n$层，那么就有$2^n-1$个节点。 完全二叉树是指除了最下一层的节点是从左往右排列且可能不满之外，其他部分是一棵满二叉树。 完全二叉数或满二叉树中，设一个节点的编号为$n$，则其左儿子编号为$2n$，右儿子编号是$2n+1$。 T1 静态RMQ这题是模板题

今天照例还是模考。 时间线我发现写时间线要考试的时候自己记录，容易忘也很烦，以后模考的话时间线就不写了吧。 题目T1当遇到一道题目，如果有两个思路，一个简单但是正确性不确定，另一个较难但是确定正确，就可以通过写对拍等方式验证猜想。 思路是给一个数组中的每个元素分配一个“分数”，然后计算所有分数的总和。分数的分配规则基于元素与其相邻元素的大小关系： 较大的元素应该获得较高的分数 相等的元素应该获得