CF1105E - Helping Hiasat

可以发现,在两个 1 操作之间的人中最多满足一个。我们可以两两连边,这样问题就转换为最大独立集问题,按照套路此时我们作补图,将最大独立集转换为求补图最大团

最大团的常用算法是 Bron Kerbosch ,我们甚至不需要很强的优化剪枝就可以过掉这题。

CF1043F - Make It One

考虑加入一个数如果不能使公因数减少,则可以不放。计算可得答案必定 $\leq 7$。又发现不能直接对存在性进行容斥,容斥方案数即可。

($cnt_i$ 表示以 $i$ 为因数的数的个数,$f_i$ 表示选 $ans$ 个数使得公因数为 $i$ 的方案数。)

AT2064 - Many Easy Problems

容斥可得:

$$
ans_k = n {n \choose k} - \sum\limits_{u=1}^n ({n - siz_u\choose k} + \sum\limits_{v \in son_u} {siz_v \choose k})
$$

NTT 一波即可。

数据范围容易想到利用矩阵进行计算。

考虑 $f(k) = (A, B)$ ,其中 $A$ 表示恰好等于 $k$ 的路径条数, $B$ 表示小于等于 $k$ 的路径条数。则可以这样转移: $(A, B) \times (C, D) = (A \times C, B + A \times D)$ 。

需要注意的是,对长度为 $L$ 的路径对答案的贡献可以表示为一个二次多项式(即 $f(L) = L ^ 2$),转移时不能直接计算,而需要记录一次项和常数项系数。注意多项式乘法时需要乘上组合数。

大于 $\max(c_i c_j)$ 的 $ v = \gcd(c_i) \ (i \in [1, n])$ 的倍数都可以被取到。
先做关于 $v$ 的循环卷积,然后背包一下把中间相差的部分补上即可。
由于要求对 $10^9+7$ 取模,所以需要 MTT。

考虑 Min-Max 容斥,$\min(S)$ 表示至少一个从 $s$ 走到至少一个属于集合 $S$ 的点的期望时间。

用 $f(i, S)$ 表示集合 $S$ 下 $i$ 到任意 $u \in S$ 的期望时间,则 $\min(S) = f(s, S)$。

$$
f(i, S) =
\begin{cases}
0 &(i \in S) \\
\frac{\sum_{i \to j} f(j, S)}{d_i} + 1 &(i \notin S)
\end{cases}
$$

可通过高斯消元求出,但复杂度过大不能接受。
考虑把原式化为 $f(i) = k_i \times f(father_i) + b_i$ 的形式,推导过程略。
对于每个查询状压处理 $\max(S)$ 不现实,需要处理出子集卷积即可 AC 。

与上一题类似,我们可以考虑生成函数。但是由于本题是 $\mod m$ 意义下的乘法,所以我们可以把原来的乘法转换为与 $m$ 的原根的对数的加法。再用上题目类似的思路即可。

定义生成函数 $f$ :

$$
f(x) = \sum\limits_{i=0}^{\varphi(m)} tag(i) \times x^i
$$

其中 $tag(i) = 1$ 当且仅当存在 $x \in S$ 使得 $\log_g x = i$ 。

最后答案为:

$$
[x^k]f^n(x)
$$

考虑到原问题等价于以下行列式的值:

$$
第 i 行的 l_i 到 r_i 的值为 1 ,其他为 0 。
$$

我们采用高斯消元,复杂度 $O(n ^ 3)$ ,可以获得 70 pts.

考虑优化,由于 $1$ 的位置是连续的区间,采用左偏树维护每个左端点的右端点最小值即可。

注意行列式中交换两列,行列式的值取相反数;如果不能消成单位矩阵,则行列式的值为 $0$ 。

BZOJ5404 - party

和其他题解不太一样,这里没有用线段树……

首先肯定会在 LCA 处集合,通过树剖 + bitset 维护出可选的集合。然后利用 Hall 定理进行完美匹配统计答案。可以发现直接树剖 + 暴力跳是 $O(n ^ 2)$ 的,所以限制树链的长度至多为 $S$ ,则复杂度为:$O(n + qcS\times\frac{m}{32} + qc \times \frac{n}{S} + q \times 2^c \times \frac{m}{32})$ ,取 $S = \sqrt n$ 。

然后跑的飞快 233333.

BZOJ5405 - platform

首先,我们需要知道如何利用后缀数组对一个指定的字符串计算字典序 Rank 。我们以 abaab 为例:

1
2
3
4
5
6
7
8
9
10
 a    a    b
11 10 9
a b
x 8
a b a a b
x x 7 6 5
b
4
b a a b
x 3 2 1

按照顺序进行编号,因为本质相同的字符串不重复计算次数,所以每一行的前 $height_i$ 个不计入个数,所以我们也有了一个很自然的 $O(n ^ 2)$ 做法。

接下来我们考虑正解,可以发现,每次可以看做对上面的字典序 Rank 数组进行了依次递减的区间覆盖,可以使用线段树维护。同时我们可以发现,这个 Rank 是递减的,而前缀和是递增的,所以我们可以二分出相等的那个位置。

首先 $c$ 没什么卵用,我们直接把他乘到属性里。

可以发现这里的 $d$ 是两个属性值减一减的绝对值,所以我们要考虑怎么维护这个绝对值。

我们先考虑 $K = 1$ 的情况,先把这些生物按照 $d$ 的大小排个序,那么后一个减前一个的值一定就是非负的,也就等于绝对值,直接扫一遍就好了。

接下来考虑 $K \not = 1$ 的时候的前 $K - 1$ 位,根据幼儿园学过的知识我们可以知道:

$$a - b \leq |a -b|$$

由于我们要求绝对值的和的最大值,所以我们只要枚举每个属性的正负把他们一起取最大值即可。

那么第 $K $ 位怎么办呢?我们可是要加上绝对值的相反数啊。没关系,采用之前 $K = 1$ 的时候的方法,减一减扫过去,就能保证你去到的值非负啦。

考虑离线做法,每个物品存在的时间一定是一段连续的区间。建一棵线段树按时间分治,乱搞一下。

考虑在线做法:有一个部分分是只会在一端进行插入删除操作,那么我们开个栈,插入元素就加进去,删除就弹出。复杂度 $ O ( n m ) $ ;既然我们需要在两端操作,那么我们只要维护两个这样的栈即可,查询时把两边的 dp 数组合并。暴力合并是 $ O ( m ^ 2 ) $ 的,会 TLE ,所以我们把一个数组放在线段树上,枚举另一个数组的每一个数,做一下区间查询即可。同时有个问题即有可能在前端删除从后端插入的元素,这种时候我们暴力重构两个栈,各放一半的元素,就能保证复杂度。最后总时间复杂度 $ O (n \log n \times m \log m) $ ,可以通过此题。

由于笔者在做题时把合并的 $ O (m ^ 2) $ 算成了 $ O ( m ) $ 所以去写了在线做法,还好想出了线段树才捡回一条命 233。

按题意可知,考虑每个节点会给左孩子带来一个 $(-\infty, a_i )$ 的限制,会给右孩子带来一个 $(a_i, +\infty)$ 的限制。 定义限制 $(-\infty, a_i)$ 的限制取反为 $(a_i, +\infty)$ ,反之亦然。

考虑把原树进行树链剖分。每个节点存放自己给重儿子带来的限制,用支持单点修改、区间取反、区间查询的线段树维护区间限制的并集。由于每个节点往上跳只会经过 $\log n$ 条重链,重链内部直接从线段树上查询,两条重链之间的转移把转折点对重儿子的限制取反即可。总复杂度为 $O(n \log ^ 2 n)$,可以通过此题。

20181211 - NOI模拟赛

T1、T3 的思路基本都成型但是由于自己傻逼最后一个都没调出来。

LCM

考虑一个数最多被分解为一个大于 $\sqrt {\max a_i}$ 的质数和一些小于 $\sqrt {\max a_i} $ 的质数的乘积。考虑小于的部分,最多有 4320 种状态,我们可以用一种简单背包的方法统计出每一种值的个数。对于大于的部分,相当于我们给上一步统计的个数的时候给个数加上一个权值。通过一些简单的处理避免超过 $\sqrt { \max a_i }$ 的质数被重复计算。理论复杂度 $O(n \times 4320 \times (\log n + \log 4320))$ 。

Xor

不知道为什么出题人要把题意搞的这么迷。我们直接把边权异或到两个端点上,计算割的价值就是一边的点的权值的异或和。考虑贪心,把点按照权值从大到小排序,利用线性基维护会不会产生 $0$ ,不会就加上价值,否则减掉即可。

Lis

考虑把从左到右的最长上升子序列转变为从右到左的最长下降子序列,这样每次操作最多影响十棵树。树套树(树状数组套权值线段树)维护一个后缀高度大于指定值的 dp 值的最大值,每次暴力重算那十棵树即可。复杂度 $O(n \log^2 n \times 10)$ 。需要注意的是需要动态开的节点个数可能会很多,一定要开够。

根据小学我们就学过的一个简单公式,如果 $x = \prod p_i ^ { a_i } $ 那么 $x$ 因子个数为 $\prod a_i + 1$ 。因此我们需要维护查询的区间内每一个质数的和。

考虑把原来的数分解,这一步我们只需要预处理出小于 $ \sqrt { \max {a_i} }$ 的质数即可。然后对于每个数 $ a_i $ 依次判断小于 $ a_i $ 的质数。复杂度 $ O( \frac {n \sqrt{\max{a_i}}} {\log n} )$ ,实际情况下表现非常优越。或者采用 Pollard-Rho 算法优化为 $ n \times \sum { a_i^{ 1 / 4 } }$ ,但实现会较为复杂而且没有必要。

接下来考虑分解出的质数如何处理,如果直接放在一起去莫队的话复杂度是 $ O(n \sqrt n \log n) $ ,如果常数不优秀的话会 TLE 。我们考虑一个优化方式,对于大小在前 $\sqrt n$ 个的范围内的质数,预处理出个数,前缀和统计,不参与莫队,其余分解出的质数参与莫队,可以证明,每一个数需要参与莫队的数的个数是 $O(1)$ 级别的。这样的话复杂度降为 $n \sqrt n$ ,事实上我们可以把范围由 $\sqrt n$ 调整为 $100$ ~ $200$ 左右以获得一个较小的常数,跑到目前效率 rank 1。

20181208 - NOI模拟赛

最近准备学科营,平时考的模拟赛准备总结记录一下。这些题解会被分类到 Contest 目录下,可能只会讲笔者会的部分或笔者觉得有用的部分,思路可能会讲完整也可能不会,代码可能会放也可能不会,但题面和题意肯定是不会有的。大概就是这样(

Forest

考虑到每个节点出去只有一个父亲,所以要把修改都集中到自己和自己的父亲上去(而不是遍历自己的孩子)。为了方便维护,我们把原来的 $C_i$ 拆成

$$
C_i = E_{a_i} + (B_i - D_i \times E_i + E_i + \sum E_{ P_j } [ j 是 i 的孩子])
$$

通过简单的 trick 把括号内的东西(假设叫 $F_i$ )放到 $i$ 节点上维护,可以使得 1 、 2 操作的复杂度变为 $O(1)$ ,但 3 操作需要遍历所有节点,复杂度是 $O(n)$ 。考虑优化,把每个节点都开个 multiset (或可删堆),用来存自己的每个孩子的 $F_i$ ,当自己的 $E_i$ 改变时利用自己的 multiset 去更新答案,同时当自己的 $F_i$ 改变时更新父亲的 multiset ,并利用父亲的 multiset 更新答案

Bear

20 分简单爆枚,40 分简单状压。100 分以对角线进行插头 dp ,还没写过。

Juice

考场上用一个乱搞做法 AC 了这题(也依赖于 IOI 赛制)。先枚举答案,对于每个答案进行 check ,方法如下。

先根据答案计算出分出的每个桶的大小 $S$,把给定的每个 $a_i$ 丢进 multiset 里。每次取出一个最小的 $A$,如果 $A > S$ ,那么就把 $A - S$ 丢回去;如果 $A < S$ ,那么就在 set.lower_bound(A) 到 –set.end() 的范围内随机一个迭代器配对。利用合适的随机种子和合适的调参,成功 Accepted。

首先我们把原来的距离数组 $p$ 差分为数组 $a$。原题可以等同为在 $a$ 数组中选择 $k$ 个不相邻的数使得总和最小。

假设我们已经选择了 $a_i$ ,那么 $a_{i-1}$ 和 $a_{i+1}$ 要么同时选择,要么同时没有被选择。同时,如果我们同时选择,需要的花费即 $V_{a_{i+1}} + V_{a_{i-1}} - V_{a_i}$ 。我们维护一个堆和双向链表,每次从小根堆选择堆顶,把 $a_i$、 $a_{i-1}$ 和 $a_{i+1}$ 同时删除,再新建一个价值为 $V_{a_{i+1}} + V_{a_{i-1}} - V_{a_i}$ 的节点,扔到堆里,重复 $k$ 次就能得到答案。

CF706E - Working routine

题意:

给你个 $1000 \times 1000$ 的矩阵,每次交换任意两个不重合的子矩阵,求最后的结果

如果你是一位数据结构学傻的选手(像我),那么第一感觉肯定是用平衡树做,复杂度 $O(m \times n \log n)$ ,不过不幸的是,由于常数巨大,最后得分甚至可能不如暴力的 memcpy

如果你是一个不会高级数据结构的普及选手你说不定就能想到链表。维护一个矩形的链表,然后每次交换就分别把两块矩阵取出再拼接上去。

给定一个序列,要求兹滋: 区间加数、区间除以数、区间求和、区间求最小值。

其他都很简单,关键在于怎么解决区间除法。

一开始很容易想到之前的 “花神游历各国” ,但是这题并不能这样做(有区间加数),感觉线段树不可做想分块然而分块照样没法解决除法的问题。

正解则是将除法转换为减法,如果当前区间的最大值和最小值与除以除数的数的差值相同,那么把除数变成减数。

复杂度为 $O(n \log^2 n)$ 据称可以用势能分析,但是本蒟蒻太菜了不会,因此略过 QAQ。

已知每个数最多能被开方而减小的次数是有限的,当当前的数是 $0$ 或 $1$ 时就没有必要操作。

所以我们可以用线段树维护区间最大值,如果当前的最大值已经等于 $0$ 或 $1$ ,就无需操作,否则逐个修改。

复杂度 $O(n \sqrt {10^9} \log n)$ ,可过。

区间取模操作同理。

理论上来说资瓷区间开方 / 取模和单点修改,算是优美的暴力吧。


多倍经验(数据范围和要求略有不同):

  1. BZOJ3211 - 花神游历各国
  2. 洛谷4145 - 上帝造题的七分钟2 / 花神游历各国
  3. SPOJ2713 - GSS4 - Can you answer these queries IV
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×