题目链接

CF

题意简述

给你一个长为 $n$ 的数列，对于 $1\le k\le n$ 的所有整数 $k$，求出这个问题的答案：将数列划分成若干连续段，每段内最多有 $k$ 个 不同 的数，至少要划分成几段？

$n\le 10^5$ 。

题目链接

CF

题意简述

给你一个正整数序列，多次询问给定区间内每个数之积的欧拉函数 ($\varphi$)，对 $10^9+7$ 取模。

数列长度、询问个数不超过 $2\cdot 10^5$，数的大小不超过 $10^6$ 。

题目链接

CF

题意简述

给你一个序列，在线地支持两个操作：

1. 将一个区间循环移位。

2. 查询一个区间中某个数出现的次数。

序列长度、查询个数都不超过 $10^5$，时限 $\texttt{4s}$ 。

题目链接

CF

题意简述

定义一个“偶环”为边数为偶数的回路（回路又被称作“边简单环”，即不经过重复边且首尾点相同的途径）。

给你一张不含“偶环”的无向图。称一个区间是“好的”，当且仅当编号在这个区间中的点的导出子图是一张二分图。

多组询问，每次询问一个给定区间有多少个子区间是“好的”。

点数、边数、询问数均不超过 $3\cdot 10^5$ 。

题目链接

CF

题意简述

给你一棵树，每个点的颜色为一个区间内的整数，一种染色方案的权值是所有同色无序点对的距离之和，求所有不同染色方案的权值之和。

点数、颜色数均不超过 $10^5$ 。

本文讲的是自己搭建的 UOJ 如何解决无限 waiting，而不是 https://uoj.ac 如何解决无限 waiting（后者大概要联系 vfk..反正我是没遇到过）。

题目链接

UOJ

洛谷

题意简述

给你一棵树，$i$ 号点有 $p_i$、$q_i$ 和 $l_i$ 三个属性，每条边有给定的长度。

从一个点出发可以到达其祖先中与其距离不超过 $l_i$ 的点，费用为 $p_i\cdot dis+q_i$，求每个点到根的最小费用。

点数不超过 $2\cdot 10^5$ 。

怀着伤感的心情写下这段文字，然后开始一段新的征程。

标题来自 三月のライオン Chapter.64 銀の羽根 ：

答案只在漆黑的水底。

越是前进，下一个答案就只能在更深的地方找到。

以前越是潜入，就能获得答案。

比起恐怖，欲望更胜一筹。

但是成为职业棋手 6 年后，如今变得完全不能前进。

即便带着要撕碎全身的想法去潜入，但是却空手而回，已经是很常见的事了。

比起 「也许能找到」，「反正又不一定能找到」这个念头胜利的时候，就只能进行有限的努力了。

但是，桐山和二海堂无视了那样的我。

理所当然一样无论多少次都跳入其中。根本就不正常。

他们即便屡次空手而归，也会制定对策继续挑战。

丝毫不介意痛苦，无论多少次都投身其中。

只留下，被恐惧压倒的我。

大多数人所使用的费用流算法，即每次求出残量网络中 $s$ 到 $t$ 关于费用的最短路进行增广（将 Dinic 最大流算法中的 BFS 改为 SPFA），是伪多项式复杂度的，最坏情况下复杂度为 $O(nmf)$，其中 $f$ 为最大流。已知有一种在点数为 $n$，边数为 $O(n^2)$，值域为 $O(2^{n/2})$ 时将其用时卡成关于 $n$ 的指数级复杂度的构造方法。

本文将介绍一种复杂度为进行 $O(m\log U)$ 次（$U$ 表示边的最大容量）无负权边单源最短路（使用 priority_queue 实现 Dijkstra 算法，总复杂度即为 $O(m^2\log U\log m)$）的弱多项式复杂度算法。

其实这个算法并不是很复杂（只是相关资料比较少，会对学习造成一定困难，这也是我写这篇博客的原因），最小费用最大流的模板也只需要 $2.5KB$，并不比常见的伪多项式复杂度算法长很多。