「CEOI2019」游乐园 题解首先看到这个是一个数图的题目。这里有一个转化，考虑翻转边本质上就是对这个图进行一个定向，容易想到翻转的边和自己定向的 $DAG$ 是一一对应的。 所以我们考虑给定一个无向图，对于每一条边进行定向，求定向后是 $DAG$ 的图的贡献。 然后我们考虑对于一个 $DAG$ 我们把所有的边都翻转了肯定也还是一个 $DAG$。 所以对于每一个合法的方案都有一个可以和其进行配对的图，其贡献之和是 $m$。所以每一张图的贡献可以当做 $\dfrac{m}{2}$ 来计算。 发现 $n \le 18$ 使用状压 $Dp$。设 $f(S)$ 表示只选用了 $S$ 中的点，构成合法图的方案数，之后考虑转移是通过枚举一个集合进行转移。对于 $S$ 通过 $S’$ 转移到 $T$，我们必须要保证 $S’$ 内部是没有边的，才可以让我们进行定向。然后对于 $S’$ 其贡献又会被计算多次，也就是对于其每一个子集其都会被计算一次贡献，当然转移肯定不能使空集，所以总共被计算的次数是 $2^{|S|} - 1$。直接进行容斥就好了。 至于容斥系数，我们直接考虑只有一个点转移就是 $1$， ...

P3293 [SCOI2016]美味 一道好的二分题目。 对于常规的来说肯定是考虑在 $Trie$ 树上找一个最优的点。 但是我们发现这里是 $b_i \ \text{xor}\ (a_j + x)$ 对于 $b, x$ 都是固定的，但是异或却没有分配律，所以就会难搞一点。 我们考虑二分一下答案，和平时的二分答案不一样，我们不能快速地判定可行性，但是我们可以判定对于一位是否可行。 也就是说我们对于每一位分别进行考虑，不妨当前可以得到的前面几位的答案是 $ans$。如果这一位是 $0$，是第 $j$ 位，那么我们就尽量要得到 $1$，所以我们会得到一个合法的选择区间，也就是 $[ans, ans + 2^j - 1]$，如果说这里面有数，那么我们这一位就可以得到 $1$。另一种情况同理。 这样我们就可以转换成查询一个区间中是否有数，直接可持久化线段树就好了。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616 ...

P3758 [TJOI2017]可乐 首先考虑一个 $Dp$。会想到 $f(t, i, j)$ 表示在时刻 $t$ 走到位置 $(i, j)$ 的方案数。但是因为我们是从 $1$ 开始走。那么完全可以设 $f(t, i)$ 表示从 $1 \to i$ 在时刻 $t$ 的方案数。转移的话就枚举之后可以走到的位置进行转移。 然后处理一下爆炸的情况，可以建立一个新的节点，之后进行转移，然后每个点只能进入不能出来。 我们发现本质上我们的 $t$ 意味着死亡时间最晚是 $t$ 所以之前的状态需要继承。然后要对于新建的节点再来一个自环，进行转移。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#include <bits/stdc++.h>using namespace std;#def ...

P5283 [十二省联考2019]异或粽子 首先把题目转换一下，可以得到以下题面： 有一个长度为 $n$ 的序列 $a$，求两两异或的前 $K$ 大值。 本质和 CF241B Friends 一样。 $Tricks:$ 补全三角形矩阵，答案 $\div 2$。 考虑建立可持久化 $Trie$。之后考虑两种情况。 如果 $K$ 和 $n$ 是同阶的，我们可以得到一个 $K \log K$ 的算法。 我们维护一个大根堆，常规维护一下第 $K$ 小。之后考虑每一个位置的贡献。我们不妨考虑每一个位置作为右边位置的贡献。那么就是求左边异或第 $K$ 小。 对于每一个位置都这样做。可以保证有答案。 当取出一个元素的时候，更新答案，然后使用当前元素计算比其小 $1$ 个 $rank$ 的答案，放入堆。 可以得到复杂度是 $O((n + k) \log (nk))$。 $n$ 是插入的复杂度， $k$ 是堆的复杂度。 如果 $n$ 比较小，然后 $k$ 是 $n^2$ 级别的呢？ 我们考虑对于所有的数都插入到 $Trie$ 里面。 发现如果可以得到第 $K$ 大的值，那么计算比其小的值可 ...

CF295D Greg and Caves 首先说一下这题很值得做。 $Update \times n\ on \ 2021.6.30$。 首先题目我们就直接分成两个三角形来写。 之后发现，其实上一行的具体位置不用知道，因为我们枚举当前的长度是必须 $\ge$ 上一次的长度的，然后其所有可能的位置也是很好算的。 我们就开始 $Dp$，设 $f(i,j)$ 表示从上到下计算到第 $i$ 行，当前行的长度 $\le j$ 的方案数。 很显然，我们考虑每一次找一个长度为 $j$ 的方案数。 $$f(i,j) = \sum_{c = 2} ^ m f(i - 1, c) \times (j - c + 1) + 1$$ 注意外面的 $ + 1$ 表示在这边重新开一行。 然后我们考虑计算答案，发现直接通过枚举中间的断点然后两个 $f$ 拼起来是错的。因为存在这样的情况。 那么我们不妨钦定一下中间这一段的长度，之后让两边严格小于即可，同时保证这个长度为 $1$，方案数就是 $f(i, c) - f(i -1, c)$。 然后我们直接暴力枚举计算即可。 $$\begin{aligned}\ ...

$$\Large\color{blue} Jhb\color{red}\text{的多项式浅谈}$$ 这个的后半部分似乎可以当做金策大佬论文的人话解读。 推销一下窝的博客,本文所有的代码都在窝的博客上。 多项式主要的用途是用来优化式子，因为笔者也刚刚入门多项式，可能谈到的内容也十分浅，有错请直接开 D。 我们从大整数乘法入手，我们经常写的算法是通过枚举两个整数的每一位，通过位权来更新答案，这里显然是 $O(n^2)$ 。还有一种是分治乘法，还是通过位权，原理是 ：$$(Ax^m + B)(Cx^m + D) =ACx^{2m} + ((A + B)(C +D) - AC - BD))x^m + BD$$我们直接分治可以算出答案复杂度 $O(n^{2})$ 复杂度比较优秀？其实这种想法和之后的 MTT 优化是相同的。其中 n 表示位数。 复杂度怎么算？ $T(n) = 4T(\frac{n}{2}) + O(n)$ $T(n) = O(n^2)$ 之后我们考虑优化 $ACx^m + ((A - B)(D - C) + AC + BD) \times x^{\frac{n}{2 ...

P2882 [USACO07MAR]Face The Right Way说实话这一题写了半个上午，主要是位运算的问题 首先要明白的是 1^1 = 0 1^0 = 1 1^0 = 1 0^0 = 0 由此可以看出如果一个一位数（二进制） 异或0 就是它 本身 由此可以看出如果一个一位数（二进制） 异或1 就是它 相反数 本题的牛只有两个状态，而且每次旋转的长度是固定(枚举k)的所以枚举n和k是无法省略的第三层循环可以差分优化 具体做法 建立数组b[ ],表示当前（差分）位置的方向情况 转向两次等于没转用now代表当前的牛是否转向 我们只要判断（now ^ v[ i ]）是否等于0 若等于0，则进行操作 一次操作是长度为k的区间，起点为i 根据差分,影响到的点为 i,i+k 将b[ i ] 和 b[i + k]进行转向操作（^1）,m++即可 注意判断是否出界 1if(i + k - 1 > n) {失败} Code12345678910111213141516171819202122232 ...

题目见P3834 首先，看到数据ai如此之大，却要用线段树做，那么就必须用离散化 以下为模板 12345678910n = r1;for(i = 1;i <= n; i++){ v[i] = r1; b[i] = v[i];}sort(b+1,b+n+1);int len = unique(b+1,b+n+1)-(b+1);for(i = 1;i <= n;i++) { int x = lower_bound(b+1,b+len+1,v[i]) - b;} 再放一张关于主席树的图 也就是相当于将不需要改动的节点不用重新建树，只要用原来的树就行 如果要查询区间内有没有在某个位置放数，只需 1tree[r].sum - tree[l-1].sum 以下是本题目的代码12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970 ...