月度归档： 2018 年 8 月

自己看看了半天都找不到规律，倒是感觉和逆序数应该有关系，但是直接按照偶序列有解奇序列无解来算wa，因为按照我原来的理解是，偶序列4个反转一定还是偶序列，奇序列4个反转也一定是奇序列。搜了题解之后发现漏掉了一个条件，那就是这个是个环，所以他从任意一个地方开始都可以，这就相当于在原来的4个翻转的变换的基础上多了一种变换：把后面的一段整个的移动到前面的一段。这个操作是如果按照一次简单变换来衡量的话，相当于做了i*j次变换，其中i是分界点前一段的个数，j是后一段的。当n为偶数的时候可以找到一个分界点分为两个奇数段，则相乘之后仍然是奇数，等于说这时候是可以从奇序列变成偶序列的；而当n为奇数的时候，i和j必定一奇一偶，这时候相乘必定为偶数，无法变换序列的奇偶性。所以，只有当序列为奇序列且n为奇数的时候才无解，其他情况均有解，因为均可以变换为偶序列。

继续阅读“[找规律][逆序数][思维] UVa1620 Lazy Susan”

扫描线第一题，求矩形面积的并。思路很好理解，但是实现上有很多的问题。

1 维护的变量ala[o]代表含义是“当前节点对应区间全覆盖的点数”，举个例子来说，现在的区间各个节点的值如果是2 3 3 3 5 5 2，那么ala就应该是2。这个变量这么做的好处就是，当ala不为0的时候一定可以直接把整个区间的Len算出来：就是x[r]-x[l]，当他为0的时候说明中间有的点为0，那么我们再考虑左右儿子Len之和。这个东西注意是不要pushdown的，如果pushdown了反而会使得问题变得复杂，因为如果你只是往里面+1也要pushdown的话，那等于原来的可以直接得到的Len现在反而要往下走才可以得到。那么不pushdown会不会出现重复加的情况？也不会，因为这个问题里所有的形状都是矩形，有一个上下边使得ala[o]+1，则一定有另外一个边使得他-1，而这中间的呢？因为肯定这一条线段都是还是属于计算范围的，所以也没有多加，一定是对的，这个特点很重要，今早赖床的时候想了下才明白其中的奥妙所在。。。。

引用一位dalao的话描述一下

这里的区间覆盖不需要打懒惰标记。为什么呢？因为很显然，每个下边都有与之对应的上边，它显然不会被比它的长度小的上边给清除。而如果有比它长的上边，也一定有和那个上边对应的下边还存在。所以用那个上边清除下边的时候，一定会先递归到那个更长的下边，还没有递归到它就停止递归了。所以每个上下边是一一对应的，无需下传标记等。

2 这个线段树不是[l,r]，而是[l,r)，因为我们这里离散化之后，如果按照闭区间来算，那[mid,mid+1]这一段就不能被计算到了，所以要用左闭右开，这样的话对应的一开始的区间右边要+1，而这样又会有问题就是原来的整个线段，也就是o==1时候的线段，以及所有的右侧端点为整个线段树右端点的线段，他们的右侧怎么处理，这可是个必须要左闭右闭的啊？我这里用的是在xs离散化数组的后面加上一个和xs[cnt1]相等的元素，这样就可以不用特殊判断了。

继续阅读“[线段树][扫描线][面积并] HDU1542 Atlantis”

这个题也是看了一晚上，各种题解各种论文各种ppt emmmmmmm

话说发现真的线段树这东西不能看别人的代码，怎么看怎么看不懂，非得自己写一遍才是。感觉市面上常见的线段树也就两种写法，一种是pushdown以及在update预判返回的时候把维护子节点的事情做了，维护只维护当前节点所以又叫pushup，另一种是pushdown和预判都只改变标记，而所有的维护都交给maintain来做，(⊙﹏⊙)我一直写的是后一种，但是这里写前一种貌似比较方便（🌫）因为update在这里兼具了更新和搜索的功能，所以最好是在pushdown的时候就把维护子节点的事情做了。（感觉自己对pushdown标记的理解之前还是不到位啊emmmm还是得写）
继续阅读“[线段树][区间最值操作][论文题][难] HDU5306 Gorgeous Sequence”

连续做的又一道预处理+贪心的题目，一开始因为复杂度的原因一直没有下手，看了官方题解才意识到复杂度是nlogn，因为调和级数求和是logn。。。

贪心策略就是每次都选择能覆盖到的范围内的最右边的非block的点，如果这个点等于原来的出发点就直接return -1，因为说明不可行。这时候我们需要预处理出来每个点对应的它左边离他最近的那个非block的点（也有可能是他自己），当然这个预处理就很简单了。主要的思考难度在于没想到可以这么预处理，其次是复杂度的分析没有到位。

错误的点的话是对题意的理解：这里要求覆盖整条线段，而不仅仅是覆盖整点，但是放灯却只能在0到n-1的整点上放。。。第二个错误是如果0处禁止放的话那直接就是输出-1了，原来的算法在这里会失效，因为那个总是多考虑一步，而没有考虑出发点是不是合法的。

继续阅读“[思维][预处理][贪心] codeforces 990E Post Lamps”

首先确定，什么时候是NO，因为把ai全部异或起来一定是整个矩阵全异或，bi同理所以这俩数字应该相等，xor为0，如果不为0一定是不存在的。所以，如果存在，那么a全部xor和b全部xor一定是相等的，记为tmp

否则的话，把b1到bm-1全放到第一行的左边m-1个空位，剩下的右边那个补上一个t使得这一行xor为a1，此时最右边一列的xor为tmp^a1^t=tmp^(b1^bi..^bm-1)==bm，所以这样构造的矩阵一定满足要求！！！
继续阅读“[XOR][思维][构造] codeforces 1016D Vasya And The Matrix”

还是找星星，但是数据量升高了，不能用n^3复杂度的算法了

这里可以用六个预处理的矩阵来表示信息，前四个分别为上下左右到当前位置的连续的星个数，这样就不用每次到一个坐标都从新求了。后两个分别为两个标记矩阵，这里的思想很像之前有个AC自动机替换禁忌词的题目，因为那个题目禁忌词可能互相冲突，互相交错，互相包含，而这个里面的不同的星星也会出现这种情况，所以采用了类似的方法：在左端点标记+1，右端点标记-1，然后再把矩阵从左往右过一遍，h[i][j]=h[i][j]+h[i][j-1]，这样的话，就可以确定出来一个点有没有被星星覆盖到：如果他的h或v大于0就被覆盖了，否则就没有。所有的矩阵预处理都是n^2的复杂度，总共6*n^2大概。
继续阅读“[思维][预处理][区间信息技巧] codeforces 1015E2 Stars Drawing (Hard Edition)”

都是泪啊啊啊啊啊啊啊啊啊啊啊啊啊

汪聚代哥一队打了79，v5的一批Ooooooorz    我们就很惨了，4题，300多名。。据说校前三可以去现场赛，然后我们第六凉凉。。

这个题真的是。。。真的是就差了那么一点，一层窗户纸，捅破就恍然大悟，过不去就死活想不出来了。我甚至也想到了官方题解中的类似于二分图的配置，可是没想到怎么去合并，不对，是我根本就没想合并。。。。。根本就没有意识到传递性啊啊啊啊啊啊啊啊惨的一批

最扯淡的是后面发现是原题。。。虽然有一点不一样，但是能理解原题的话就完全可以做这个了，啊啊啊啊啊啊啊啊啊啊啊啊啊啊

然后lyq差点把1005做出来，沙雕数论题，她会推公式不会实现，我会实现不懂公式，如果我们不是云操作的话可能就做出来了，在线交流真的难受。。。

还有就是1007，赛后看了一眼完全可做的样子，然而最后思维全死在这个A题。。。。决定去cf上刷一波进阶贪心了aaaaaaaa
继续阅读“[比赛][思维][贪心] CCPC网络赛 HDU6438 Buy and Resell”

这个题的官方题解简直玄学，根号5取模，然后转化成等比数列，服气。

还好评论区有人给了更简便的做法：广义斐波那契数列。任意两个广义斐波那契数列相加仍然是斐波那契数列，而且只要知道了前两项的和就可以知道任意一项的和和任意一项的开始的前缀和。比如若第一二项为a,b,那么手推几下就可以发现，fab[n]=af[n-2]+bf[n-1]，然后前缀和是fsum[n]=f[n+2]-f[2]（这个也很容易推出来，甚至奇数项偶数项分别的和都能推出来）,然后这时候就很简单了，对于每一个区间只需要保存其左端点处的a，b就可以了，把ab做成lazy tag就可以实现区间修改了。注意这时候pushdown的时候，对于右孩子要计算出来fibab到这个点是多大才可以。一如既往的，add操作需要在maintain里加单节点特判（我也不知道为什么但是已经习惯了）还有一点注意ta一定是+的第一个，tb一定是+的第二个。

准备再用等比数列方法做一遍吧，看看是怎么个操作。。今天写了一下等比数列的操作方法，感觉比原来的方法简单emmm
继续阅读“[线段树][区间等比/等差数列修改] CodeForces – 446C DZY Loves Fibonacci Numbers”