## 2026 MIT Integration Qualifier Tests 笔者太菜了，只会做资格赛的题，等我哪天上了大学再去进行积分大学习吧。 ### T1 > $$ > \int_{-\pi}^{\pi} \sin^{2025}(x) \cos^{2026}(x) \, \mathrm{d}x > $$ 注意到…

在讨论《求题单》回复：

您太强了，给您递茶/cha

在讨论《动态开点线段树的建树能 O(n) 吗》回复：

？你动态开点的节点数就是 $O(n\log n)$ 的，怎么 $O(n)$？

写在前面：感谢 noip 出题人黄紫黑黑给老子送退役了。 # Day -INF 摆烂，打云斗集训。 中途参加了个济南 CCPC，被 K 区分掉了，铁。 中途参加了个 YCPC，赛时 rk3，赛后毙掉了 rk1 和 rk2，成为 rk1，得到高达 27 元的奖金加上一个小 U 盘。 然后吃三次盒饭 60 块钱给我的奖金送…

noip 模拟赛 T2，场上写了 5.1k，恐怖如斯。 嘱以题解以记之。 ## 思路 先抛出一个问题，怎么快速判断两个可重集合是否相同？ 一个简单的思路，就是把一个可重集 $S$ 映射到一个数 $x$ 上，然后直接判断两个映射后的 $x$ 是否相同即可，这是哈希思想。 如果此时还想要进行合并可重集的操作怎么办？这就要求…

这题，难在哪里？ ## 思路 先考虑这个问题的弱化，如果不要求强连通，仅要求其构成若干个环，怎么做？ 问题等价于修改几个位置，能够使得 $A_i$ 两两不同，最小化其代价。我们不关心我们把 $A_i$ 修改成了什么，我们只关心修改哪些，所以贪心思路很显然，对于多个相同 $A$ 的位置 $i$，选择保留 $C_i$ 最大…

头一次见把解题过程写在题面里的题目。 ## 思路 破环为链后倍长，考虑对于每个位置作为开头进行计算。 然后你发现对于一个 $k$，你直接预处理 `J`、`O`、`I` 的前缀出现次数，就能够把一个 $k$ 级序列归约到一个 $k-1$ 级别序列的问题上。 设 $f_{i,k}$ 表示从第 $i$ 个位置开始构成一个 $…

好题，出到集训里了，写个题解。 怎么大家的 dp 状态都是三维空间 $O(n^3)$ 的啊，这里给一个空间 $O(n^2)$ 的做法。 ## 思路 我们记**取第 1 张卡牌的操作为操作 $A$**，**取第 3 张卡牌的操作为操作 $B$**。我们能够注意到，对于连续进行的操作 $B$，通过其取出来的卡片一定是连续的…

出到集训里了，写个题解。 ## 思路 感觉 dp 很没有前途啊，所以还是考虑枚举吧。 设我们当前枚举的连续的 `0` 的长度为 $k$，则我们需要从原来的串中找到由连续 $k$ 个 `0` 和一个 `1` 构成的子序列，显然贪心的找即可，因为剩下的部分更多一定是不劣的，这样我们就有了一个 $O(n^2)$ 的暴力。 那…

在文章《题解：P10747 [SEERC 2020] Neo-Robin Hood》发表评论：

您太强了，给您递茶/cha

在讨论《关于基于比较的排序》回复：

@[Register_int](luogu://user/406941) 感谢

在讨论《关于基于比较的排序》回复：

@[lailai0916](luogu://user/455474) 欧感谢，此帖结

基于比较的排序的比较次数下界是 $n\ln n$ 的，有没有大手子能证明一下？ 给个相关链接也行。

在模拟赛的时候用了一个自我感觉是紫的观察过了一道绿，不甘心。发现这题也可以用这个观察，而且这题是紫，于是就将其做掉，嘱以题解以记之。 ## 思路 我们考虑把山画出图来：  蓝色的横线是水位线，不…

在文章《题解：P11757 [COTS 2014] 城市建设 / GRAD》发表评论：

您太强了，给您递茶

给一个完全不需要吉司机线段树的单 $\log$ 做法。 ## 思路 我们定义一个区间是**好的**当且仅当该区间中所有的**路灯当前或者曾经某时都是正常的。** 假设区间 $[l,r]$ 是好的（满足 $l r$，则必然存在某个时刻满足 $[pre_{r'}+1,r']$ 中路灯都是好的，所以 $pre_r'$ 必然…

# Day 1 ## T1 > 给定长度为 $n$ 的两个数列 $\{a_n\},\{b_n\}$，你可以花费 $1$ 的代价从两个数列中取出一个数，该操作可以做任意多次。 > > 假设最终你一共取了 $k$ 个数，其中从 $\{a_n\}$ 中取的数的和为 $A$，从 $\{b_n\}$ 中取的数的和为 $B$，求：…

在讨论《RE》回复：

@[Yuzzzu](luogu://user/510311) 你怎么这么卷

比较巧妙的数数题。 ## 思路 一般的有限制类数列计数都是从两种方向考虑，一种是从左往右逐一确定值，另一种是从小到大逐一确定位置。对于这道题来说，我们考虑第二种计数方式。 先假设 $A$ 中元素没有重复的，并令其递增。设 $f_i$ 表示将 $A$ 的前 $i$ 小重排后得到的满足条件的数列有多少个。考虑把 $A_i$…

显然是可以双指针的。 考虑左侧取得一个极长的串满足 $[0,l]$ 中没有重复的数，在该情况下从右侧取得一个与 $[0,l]$ 中没有重复的数且 $[r,n-1]$ 中也没有重复的数。 令 $l$ 逐渐减小，并逐渐更新 $r$，记录下当前情况下的最优 $[l,r]$ 即可，时间复杂度线性。 ```cpp #includ…

假设你要找一个区间加上 $d>0$，则**这个区间一定是数列的后缀。** 证明是简单的，因为假设某个位置 $i$ 位于最终的答案中且 $i$ 属于被操作的那个区间，则后面的数显然越大越好。 于是我们可以直接枚举所加的后缀是什么，假设是 $[i,n]$，则我们只需要考虑位置 $i$ 在这个后缀中的最长上升子序列，并加上该…

**“我常常追忆过去。”** 考完 csp 就觉得完蛋了，出了考场就跟做了一场梦似的。 这个赛季其实本来准备直接文化课的，但是 n 过来找，说是 noip 没考直接放弃太可惜了，还是建议冲一下 noip 高分，我也没怎么想就答应了。 然后上半学期就是兼着文化课和竞赛，两手抓，真是抓啥啥不好。月考发挥不完全，S直接完全不…

好题，质量很高。 ## 思路 首先是一些不成熟的想法，考虑对于一个城市 $i$ 来说，我们用 $L_i$ 表示**其左边距离其最近的一个有直达 $i$ 车站车次的城市编号**（即满足没有操作一覆盖 $[L_i,i]$），同理我们也可以定义出 $R_i$ 表示**其右边距离其最近的一个有直达 $i$ 车站车次的城市编号*…

简单计数，感觉没有蓝。 ## 思路 由于 $d_{b_i}\le d_{b_{i+1}}$，所以 $b_1$ 的深度一定最浅，但是考虑到如果存在 $b_i$ 满足 $d_{b_1} #include #include #define ll long long using namespace std; const ll…

简单题。 ## 思路 感觉与廊桥分配很相似啊。 首先把所有区间的左端点从小到大排序，然后依次考虑对每个线段进行染色。不难发现，如果我们知道当前线段能够被染成多少种颜色，则乘法原理连乘起来就是答案。 于是变成了个非常典的区间覆盖问题，即有多少个区间覆盖了当前区间的左端点，只需要把对应区间的右端点丢进优先队列里去维护即可，…