[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem

codeforces 1325 E

题意:给定一个长度1e5的数组$a$, $1 \le a_i \le 10^6$ ,满足 $a_i$的因子数量不超过7. 求 $a$ 的最短的满足所有元素相乘结果为完全平方数的子序列的长度。

这个题目做的时候。。一直在想怎么dp。。。完全没往图的方向想。太久没做题了就是这样,丢掉了很多东西,sigh
继续阅读“[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem”

[思维][贪心][贡献拆分] codeforces 1255 E2 Send Boxes to Alice (Hard Version)

题目链接

题意:

给定一个长度为 $n$ 的序列 $a$ ,$n \le 10^6$ ,每个数字 $a_i$ ,满足 $0 \le a_i \le 10^6$ .

可以对这个序列进行一种操作,把第 $i$ 个数字中的一份移动到 $i-1$ 或者 $i+1$ .即操作过后 $i$ 处变为 $a_i-1 , a_{i+1}$ 或者 $a_{i-1}$变为 原来的数字+1.

问最少需要多少次操作使得存在某个数字 $k>1$ 满足所有的 $a_i$ 都可以被k整除($0$可以被任何数整除),操作过程要满足所有的 $0\le a_i$ 。

题解:

考虑操作完成之后的结果,如果每一个数字都能被 $k$ 整除,那么显然 $S = \sum_{i=1}^{n} a_i$ 也可以被k整除。所以 $k$ 一定是 $S$ 的一个因数。

然后显然 $k$ 为合数时的情况,要么被 $k=其质因子$ 的情况包括,要么就劣于这种情况。所以我们只需要考虑 $k$ 为质数的情况,也就是 $S$ 的所有质因子。

由 $S$ 最大为 $10^{12}$ 可知,其质因子最多应该只有$10-20$种,而且分解出质因子可以用时间复杂度 $O(\sqrt{n})$ 的算法,也就是约 $10^6$ 。

继续阅读“[思维][贪心][贡献拆分] codeforces 1255 E2 Send Boxes to Alice (Hard Version)”

[类欧几里得][位运算] 2019牛客暑期多校训练营(第九场)I KM and M

题目链接

题意:

求 $$\sum_{k=1}^{N}((kM)\& M)mod(10^9+7)$$

其中 $1 \le N \le 10^{18}$ , $1 \le M \le 10^{11}$

题解:

按位来做,考虑每一个二进制位i, 假设pi是 M 中从小到大第i位上的0/1), 然后我们又可以用取模和取整来取代某一位上的运算,比如当前处理的是第i位 ,就可以写成 $$\sum_{k=1}^{N}(\lfloor \frac{k*M}{2^i} \rfloor)-2*\sum_{k=1}^{N}(\lfloor \frac{k*M}{2^{i+1}} \rfloor)$$
这显然是一个类欧几里得的模板式子,我们只需要套用一下模板即可。最后把所有位的答案累加起来即可。
继续阅读“[类欧几里得][位运算] 2019牛客暑期多校训练营(第九场)I KM and M”

[DP][后效性处理] codeforces 1247 E Rock Is Push

题目链接

题意:

给定一个 $n*m$ 的棋盘,每次你只能向右走或者向下走,要求从左上角 $(1,1)$ 走到右下角 $(n,m)$ ,问有多少种走法。
有一个限制因素是棋盘的格子里可能有石头,然后走到一个地方就会把这里的石头按照来的方向推出去,如果有多个石头就会连带着一起推过去。
数据范围 $1\le n,m\le 2000$ ,答案对 $10^9+7$ 取模。

题解:

直接DP会有后效性的问题,我们可以给状态加上约束:令 $D_{i,j} R_{i,j}$ 分别表示一个点改变原方向后向下走/向右走有多少种走法。
这样的话dp转移可以写成类似于 $D_{i,j}=\sum_{i=1}^{n-k-i}R_{i+t,j}$ 的形式,然后这样可以得到一个复杂度 $\mathcal{O}(n^3)$ 的算法,
观察这个式子发现他是线性的,当一个维度发生变化是等式右边只有一到两项会发生变化,就把复杂度降到了 $\mathcal{O}(n^2)$ ,就可以通过本题了。
继续阅读“[DP][后效性处理] codeforces 1247 E Rock Is Push”

[博弈论][组合游戏][组合计数] codeforces 812E Sagheer and Apple Tree

题目链接

题意:

给定一棵树,每个节点上有 $a_i$ 个苹果,两个人轮流操作,每次把一个节点的一部分(或全部)苹果移到他的某个儿子中(如果是叶子节点没有儿子那么就吃掉这些苹果),最后不能走的人输。现在在游戏开始前先手可以选取两个不同的节点交换他们之间的苹果数,问有多少种交换方式可以使得先手必胜。
数据范围: $1\le n \le 10^5,\;1\le a_i \le 10^7$

题解:

博弈本身是很简单的阶梯博弈。由阶梯博弈的知识,求胜负只需要计算奇数位上的SG函数异或和即可,这题只不过把阶梯转移到了树上,但是略微分析就可以发现和链状的阶梯是没有区别的,都是奇数往偶数转移当作拿走,偶数往奇数转移就对称操作。

  • 然后考虑计数:
    • 假设初始状态是必胜态,那么可以先计入奇数层自己内部交换和偶数层自己内部交换的对数,分别为 $C_{num\;of\;odd\;level}^2$ 和 $C_{num\;of\;even\;level}^2$;
    • 然后计算奇偶层之间互换的对数,设异或和结果为 $ans$ ,假设一对数 $a_u$ $a_v$ 交换之后可以使得 $ans=0$ ,那么由亦或的性质可得 $a_v=ans\oplus a_u$,那么我们就可以枚举 $a_u$ 的值,找 $a_v$ 有多少个,而后者利用 $map$ 可以很容易的预处理出来。
      继续阅读“[博弈论][组合游戏][组合计数] codeforces 812E Sagheer and Apple Tree”

[DP][CDQ分治][树状数组] bzoj2244 SDOI2011 拦截导弹

题目链接

题意:

给定一个序列,每个元素有两个属性 $h$ 和 $v$ ,是导弹的高度和速度,发射的拦截炮弹第一发可以是任意的高度和速度,但是要求每一发炮弹的高度和速度都不能大于前一发。问:
1. 选取最优的发射方案的时候最多能拦截多少发导弹
2. 当有多个拦截导弹数目相同的最优方案的时候,我方会从中随机选取一种方案,现在问在这种策略下,每发炮弹能拦截到导弹的概率是多少

题解:

第一问很明显使用cdq分治加速dp转移算LIS,难点在于第二问。把LIS各个节点的转移看成图上的连边的话,可以得到一个dag,而后可以想见使用dp求出到每个点的在LIS上的路径有多少条,便可以确定随机选取的情况下每个节点被选取到的概率为 经过该点的在LIS上的路径数/所有的在LIS上的路径数 。判断一个点是否在LIS上,我们可以两端各求一次LIS,分别记为 $dpl[i] dpr[i]$ ,则如果当前节点满足 $dpl[i]+dpr[i]=\max\limits_{1\le j\le n} dpl[j]+1$ 则说明其属于某个LIS,+1是为了去除节点本身的重复计算。 为了求出经过某个点的路径数,我们可以用之前 dp求最短路必经边的方法 ,从两端分别跑一次dp,分别记录两端到某个节点的属于LIS的路径数为 $gl[i]\;gr[i]$ ,这样的话经过节点i的路径数就可以表示为 $gl[i]*gr[i]$ ,则每个点被选中的概率就可以被表示为

$$\frac{gl[i]*gr[i}{\sum_{[dpl[k]=LIS]}gl[k]}$$

这就是第二问的答案了。因为分治中每次需要对 $[l,r]$ 之间的元素暴力排序,所以复杂度会多一个 $log$ ,也就是 $\mathcal{O}(n\log{}n)$
继续阅读“[DP][CDQ分治][树状数组] bzoj2244 SDOI2011 拦截导弹”

[KM][二分图带权匹配][优秀模板][比赛补题] codeforces gym 101635 G Cordon Bleu

题目链接

题意:

题解:

KM最大权二分图匹配。然后权值的话,左侧原来的 m 个点代表送货员的家,与右侧表示红酒地点的 n 个点之间连边,权值为送货员的家 ni 与红酒处 mi 之间的距离与 mi 到 饭店之间距离的和,选中这条边的话表示这个人直接从家里到红酒处然后把酒送到了饭店。之后在左侧新建 n-1 个点表示走到店里又出来的送货员,其与右侧n个点的权值设为2倍红酒到饭店的距离,因为回到店里之后所有的送货员就没差别了,而且一个人可以被重复利用,没有什么先后的时间限制。n-1 是因为最多就只有 n-1 瓶红酒会被从店里又出来的人送到(至少有 1 个人是直接从家里到红酒处的)。这样直接跑KM就可以了,但是有个问题是原来的KM板子太慢了,到UOJ#80找了个新的板子,能1s跑2000个点的KM。。。
继续阅读“[KM][二分图带权匹配][优秀模板][比赛补题] codeforces gym 101635 G Cordon Bleu”

[线性基][线段树][模板] 牛客多校第四场 B xor

题目链接

题意:

$n$ 个集合,每个集合最多32个unsigned int范围的整数, $m$ 个询问,每次问下标在 $[l,r]$ 之间的集合能否表示出 $x$ 。数据范围 $1\le n,m\le 50000$,每个数字都在 unsigned int 以内。

题解:

线段树维护线性基即可。学习了一发板子。
继续阅读“[线性基][线段树][模板] 牛客多校第四场 B xor”

[SAM][dp][拓扑排序][模板] 洛谷 P3975 TJOI2015 弦论

题目链接

题意:

给定一个长度为 n 的字符串,让求出它的第 $k$ 小子串是什么。每次除字符串之外还会给定两个参数 $t $和 $k$ ,$t$ 为 $0$ 则表示不同位置的相同子串算作一个, $t$ 为 $1$ 则表示不同位置的相同子串算作多个。数据范围 $n\le 5*10^5$ $t\in {0,1}$ , $k \le 10^9$.

题解:

后缀自动机板子题。我们知道每一个子串放在sam上跑一定可以走到一个合法节点,反过来说任意一个节点一定代表了一批能走到这儿的子串。那么我们可以想办法把到达每个节点有多少种子串用dag图上dp的方式求出来,然后在t=1的时候,根据sam的性质,给每个dp值再乘以一个 $|endpos|$ 就可以了。学习到的是比我原来板子更快的拓扑排序方式。。。直接用len结果在数组里排序,比起用queue来常数小了很多。另外还纠正了自己的对于sam拓扑序的一个错误认识,他其实无论是slink还是dwag的拓扑序都是一样的,因为无论哪种都一定是从小的子串往大的走。
继续阅读“[SAM][dp][拓扑排序][模板] 洛谷 P3975 TJOI2015 弦论”

[单调性优化DP][二分][比赛补题][×][思维] codeforces gym 101412 I Beautiful Spacing

题目链接

题意:

要求给一片文章排版,要求每行 $W$ 个格子,每一行的要求是首单词必须顶格,除了最后一行之外的尾单词也必须顶格,然后单词之间至少有 $1$ 个空格,单词内部不能有空格,也不能改变单词之间的顺序。现在问在排版方案满足这些要求的条件下,单词之间的最大空格最小是多少。数据量: 每一行的格子数: $3\le W \le 80,000$, 总共的单词数:$2\le N\le 50,000$ 每个单词的长度 $x_i$ 满足 $1\le x_i \le \frac{W-1}{2}$
继续阅读“[单调性优化DP][二分][比赛补题][×][思维] codeforces gym 101412 I Beautiful Spacing”