LOJ

[Problem Link](https://loj.ac/p/3629) 有一个长为 $n$ 的未知序列，给定 $m$ 个限制，每个限制形如给定 $i,j,k,x$，要求 $a_i,a_j,a_k$ 的中位数为 $x$。构造一个符合条件的序列或输出无解。 $n,m\le 10^5$。 首先这是一个 ......

[link](https://loj.ac/p/6160) 思维+容斥计数。 首先的转化比较妙，二分图转化为 $n\times n$ 的网格图染色。 > 与网络流的转化方向相反，值得注意。 然后发现两种颜色（红、蓝）如果独立染色，同一个格子可能会重复染色。 考虑容斥，式子很好列，直接容斥即可。 $$ ......

经典问题，环形均分纸牌 设每个人的糖果数量为$a[1]$~$a[n]$ 设$b[i]$表示第$i$个人传递给第$i+1$个人的糖果数量（正负有意义），其中$b[n]$表示第$n$个人传递给第$1$个人的糖果数量 根据题意不难列出$n$个方程，看似$n$个未知数，只有唯一解，但其实只有$n-1$个方程 ......

惊奇地发现我的赛时做法也可以通过转化一下计算式优化到 $O(n+m)$。或许也算是一种另解？ 首先，我们考虑把后手的决策视为图上的一个自环或一条边。对于每条边，你要对其选择其连接的一个点，且使得其满足两两不同。 对先手的决策，则意味着对这个点 / 边的额外代价，包括 * 无额外代价。（$|S\cap ......

2023.7.3 [Problem Link](https://loj.ac/p/6669) 交互库有一棵 $n$ 个点的二叉树，你每次可以询问两个点之间的距离，猜出这棵二叉树。$n\le 3000$，询问次数上限 $30000$。 首先给你距离一定是先把每个点的深度问出来，确定一个大致的考虑顺序。 ......

注意到相邻两数的向下取整的差值不可能大于 $1$，也就是： $$ \lfloor \frac x k\rfloor-\lfloor \frac {x-1} k\rfloor \leq 1 $$ 稍微推广一下，我们得到： $$ x-1-\lfloor \frac {x-1} k\rfloor \leq... ......

首先不难想到一个贪心，就是先填出一个全黑的行，然后再用其填黑列。 而且在其中“填出一个全黑的行步数”我们应该最小化。 那么如何最小化“填出一个全黑的行步数”呢？我们发现关键所在是白点，我们可以进行操作填黑它。 我们设对应的操作为 $(x,y)$,白点为 $(a,y)$,则 $(x,a)$ 为黑。 ......

链接：[#10121. 「一本通 4.2 例 3」与众不同](https://loj.ac/p/10121) # summarization 给出一个长度为 $n$ 数列 $a$ 和若干个询问，询问某一段区间内最长的「完美序列」的长度。（「完美序列」：一段连续的序列满足序列中的数互不相同） # so ......

## loj6728 U 群把妹王 The most important part is the PIE coefficient. with out loss of generality, consider the case of 1 dimension. denote $p:n$ $p\in$ p ......

# 题目 [点这里](https://loj.ac/p/3406)看题目。 给定一张包含 $n$ 个顶点和 $m$ 条边的 **无向连通图**，Tom 和 Jerry 在图上进行了 $q$ 次追逐游戏。 在第 $i$ 次游戏中，Tom 一开始位于顶点 $a_i$，而 Jerry 一开始位于顶点 $b ......

做到这题，发现自己对$SAM$的一些性质还不知道，特此记录。 题目要求01字符串区间内前缀的最长公共后缀 由SAM parent tree性质可知，2个前缀的最长公共后缀就是它们在parent tree上lca的len值 如何去感性理解 我们知道，在parent tree上每个节点都代表了一个end ......

## 题目大意 有 $n$ 个物品，第 $i$ 个费用为 $w_i$ ，价值为 $v_i$ ，对于 $k\in[1,m]$ 求费用为 $m$ 时能获得的最大价值。 $1\leq n\leq 10^6,1\leq m\leq 5\times 10^4,1\leq w_i\leq 300,1\leq v ......

设当前询问的串为 $s_i$ 记为 $t$。考虑 $r$ 右移，维护每个 $l$ 对应的 $g(l,r)$ 和 $\max_{l}\frac{g(l,r)}{r-l+1}$ 即可。 最基本的观察是：当 $r$ 右移后，考虑 $t_{1..r}$ 在 AC 自动机上匹配到的点 $p$，那么对于 $p$ ......

# 题目 [点这里](https://loj.ac/p/3405)看题目。 有一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$。初始时，$\forall 1\le i\le n,a_i=1$。 接下来进行 $d$ 轮操作。每一轮操作会以 $\frac{a_i}{\sum_{j=1} ......

模拟赛考的题，但是模拟赛没有打，哈哈，摆烂。 考场上想到大致做法了，没继续推，去打 GP of Tokyo 了。 首先发现操作都在查询前面，所以我们只需要预处理出答案即可。 我们先记 $b_i$ 表示对 $i$ 进行的操作的总和，那么容易写出 $a_i$ 的式子： $$ a_i = \sum_{j ......

# 教主的魔法 ## 题目描述 教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给 XMYZ 信息组每个英雄看。于是 $N$ 个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为 $1, 2, \ldots, N$。 每个人的身高一开始都是不超过 $1000$ 的正整数。教主的魔法每次 ......

# 题目 [点这里](https://loj.ac/p/2462)看题目。 小 A 有一棵 $N$ 个点的带边权的树，树的每个节点有重量 $w_i$ 和价值 $v_i$。 现在小 A 要从中选出若干个节点形成一个集合 $S$，满足这些节点重量之和 $\leq M$ 并且构成一个连通块。小 A 是一个 ......

题目链接 题意 给定整数 $n(1\le n\le 10^{25})$，求 $n$ 以内 Powerful Number 的个数，以及它们的和。 题解 Part 1 如果 $x$ 是一个 Powerful Number，那么它一定可以表示成 $a^2b^3$ 的形式。 我们限制 $b$ 不含（大于 ......

有意思的题，做这题的时候也发现了不少有趣的东西~~虽然不会做~~。 考场上没有看出来建图。事实上本题复杂的性质基本决定它需要一步图论转化，而互不相同也是一个经典限制。可以得到如下建图转化：对于集合 $T_i$ 的两个数，在它们之间建立无向边，用定向表示选择，则我们需要给边定向使得每个点的入度不超过 ......

#6029. 「雅礼集训 2017 Day1」市场 题目描述 数据范围1e5 题解 对于这种数据貌似可以快速缩小的题目，我们可以用势能分析来证明其某暴力或者什么做法的复杂度。 设某节点的势能函数是点内数的极差，每次除一个数极差一定会减半，总共会被除 $\log$ 次。 然而有特殊情况，如果考虑下取整 ......

怎么全天下就我没见过？被薄纱了/ll 还是考虑从朴素的 DP 入手优化。不难发现对于固定的 $i$，相邻的 $dp_{i,j}$ 的差要么是 $0$ 要么是 $1$，也就是说从压位的考虑角度可能很有前途。因此我们转而维护 $dp_{i,j}$ 的差分数组 $v_{i,j}=dp_{i,j}-dp_{ ......

题面传送门 为啥大家都会这个科技？ 首先我们有一个比较愚蠢的dp：设 $f_{i,j}$ 表示第一个序列到第 $i$ 位，第二个序列到第 $j$ 位，最长公共子序列的长度。这样做是 $O(n^2)$ 的。 如果你做过 dp 套 dp 你应该可以发现 $f_{i,j}$ 行差分是只有 $01$ 的，我 ......

考虑归并排序，问题即如何合并两个序列$A,B$ 不妨假设$|A|>|B|$，将$A$按下标奇偶性划分为$A_{0}$和$A_{1}$ 将$A_{0}$与$B$归并，得到序列$C$ 对于$A_{1}$中的元素，仅需与（$C$中）$A_{0}$中相邻两数间的$B$中元素比较 比较次数为$|B|$，用莫队 ......

考虑归并排序，难点在于怎样合并两个有序序列。 我们假设要合并两个有序序列 $A,B$，不妨假设 $|A|>|B|$，考虑以下过程： 将 $|A|$ 中的元素按下标奇偶性分成两个序列 $A_0,A_1$。 递归合并 $A_0$ 与 $B$。 将 $A_1$ 中的元素插入 $A_0$ 与 $B$ 得到的 ......