Panda2134's Blog

Not only coding

莫队笔记

莫队是一种离线解决区间查询问题的算法。记得 NOIP 之前那段时间，见到一道查询区间颜色种类数目的题目，标签是树状数组。想了很久也没有想出来怎么用树状数组做，看题解才知道有莫队这种逆天的东西……srOOrz 普通莫队以查询区间颜色种类数目为例。为了方便，假定元素个数为 $n$ ，查询数目为 $q$ . 暴力开桶扫一遍，复杂度是 $O(qn)$ 的。有没有更高效的算法呢？如果已...

Posted by panda_2134 on January 16, 2018

雅礼集训day12-drink

题面小C桌上有$n(n \leq 10^6)$杯水排成一行,第$i$杯水中有$a_i$单位体积的水. 他会选择一个区间$[l, r]$, 并拿一个初始为空的杯子(杯子的容积无限大),他可以重复无限次以下操作: • 选定任意一杯水$i$, $i \in [l, r]$. • 使i和它拿着的杯子里的水的体积变为它们的平均值. 小C希望进行若干操作后最大化杯子里的水的体积,设$g(l, r)$...

Posted by panda_2134 on January 12, 2018

WC2018学习计划

离WC2018只有一个月了…… 雅礼集训：点/链分治 Mobius反演 Prufer序列（做题） FFT DFT FWT 多项式各种操作网络流和各种建模博弈DP Link-Cut Tree 线段树（做题）一般情况的区间修改主席树划分树(暂时不学这个冷门数据结构) fhq-treap ...

Posted by panda_2134 on January 2, 2018

NOIP总结

更新中 UPD:暂时鸽了知识点动态规划序列DP 注意边界情况的特殊处理。可以设计特殊长度的序列并且输出数组来进行检查有时需要用数据结构优化。一般是单调数据结构（单调队列、单调栈）注意排列的一一对应性质，有时候可以通过映射转换问题如果可以的话不要把部分序列都扫一遍；考虑 $O(1)$ 转移二维平面DP 画出图来，再用以某个点为右下角...

Posted by panda_2134 on November 10, 2017

[ZJOI2006]物流运输

链接:Luogu-P1772 分析在输入时对每个码头的不可用时间进行差分。假设某一段连续的时间$[t_1,t_2]$选择同一条运输路线，则可以通过Dijkstra求出这段时间的$s \rightarrow t$最短路长度，记作$cost[t_1][t_2]$。总时间是$t$，点数目是$n$，那么预处理每个时间段内选择同一条路的代价的时间复杂度是$O(n) \cdot O(t^2) \cdo...

Posted by panda_2134 on November 8, 2017

浴谷八连测-R8-B

题意给定$n$个人的$m$个关系，形如:$x, y, z$，表示$x$比$y$的$z$学科成绩高。求1号学生在最坏和最好情况下的排名。学科数目$\leq 3,2\leq n \leq 50000, 2\leq m \leq 10^6$。思路考场上面想到的是SPFA求最长路，于是就爆0了。这么做显然是有问题的，因为对排名的并列理解不清楚。e.g.如果2~5的分数是1...

Posted by panda_2134 on November 6, 2017

[USACO14DEC]Piggy Back

链接:Luogu-P3110 分析分两种情况讨论。 $P \leq B+E$ 。考虑二者在某个点处相遇。在这个点后两个人如果分别走，一定是沿着到$N$的最短路。于是显然背着走更好。 $P>B+E$。二者相遇后各自独立地沿着到$N$的最短路走（其实是同一条路），比背着走更好。代码 #include <bits/stdc++.h> using...

Posted by panda_2134 on November 6, 2017

浴谷八连测-R7-B

题意给定一个序列$\{a_i\}$，求它的每个子区间的逆序对数和。包括长度为1的区间。对于$60\%$的数据，$n \leq 1000$；对于$100\%$的数据，$n \leq 1000000$。思路先看$60\%$的解法。当时在考试的时候，我选择的是用树状数组暴力扫。先离散化。对于同一个左端点$i$，依次向右边扫右端点$j$，对于每个j都统计$[i,j-1]$有几...

Posted by panda_2134 on November 5, 2017

浴谷八连测-R6-A - 不可逆的重启动

题意求两个串$A$,$B$的最长公共子序列。对于70%的数据，满足 $|A|,|B| \leq 1000$ 对于100%的数据，满足 $|A| \leq 10^{6},|B| \leq 1000$，所有字符都是小写字母。 ##思路首先对于70分的数据直接求LCS就行。对于100分的数据呢？在DP中，我们常常通过改变状态来进行优化。如果把答案...

Posted by panda_2134 on November 5, 2017

数论基础

填坑ing… 概述数论是研究整数的学问。初等数论的基础主要包括同余，扩展欧几里得定理，费马小定理，欧拉定理等。同余基本性质同加 \(\large a \equiv b \pmod m \Leftrightarrow a+c \equiv b+c \pmod m\) 同减 \(\large a \equiv b\pmod m \Leftrightarrow a-c \equiv ...

Posted by panda_2134 on November 4, 2017