codechef MARCH16

大概按做题顺序来

STRPALIN

从两个串中各选一个相同字符即可。

MAXISUM

找出$B$中绝对值最大的那个数，修改肯定改它对应的那个$A$。

CHEFSPL

注意双字符串的定义，非空，所以任意长度为$1$的输入都是不可以的。这点在大概3.11新加的数据中有体现。

然后，假设串是偶数那么直接比较两边是否相等就好，否则(大概是)把串截成长度差$1$的两段，看LCP与LCS(最长公共后缀)之和是否$\ge $短串长度。

PARITREE

树并没有什么卵用

并查集算$2$的连通块次方就好

要特判无解 wa了就换种写法 这样就好了

SEASTR2

sereja还是爱出这种鬼题

首先我们只关心输入串中每种字符的出现次数。

然后分“交换0/1/2次涉及到了几个元素”来讨论就好。复杂度是$O(26^4)$一组数据。

FLOORDIS

首先搞出所有的格子属于哪个房子

然后对每个房子我们知道选第1/2类工程师的维护费用，对两个房子我们知道选不同工程师时的改造费用

poj3469。。就没了。建图这样建：(网上一大堆，百♂度都能搜到)

$S$向每个点连边，权值为$A_i$

每个点向$T$连边，权值为$B_i$

$(a,b,w)$就是$a$和$b$互连，权值为$w$。

点数只有$500$，边数$500^2$(其实这个图是平面图，边数少的可怜)

就可以过了

CHEFPC

这帮东西的所有交点弄出来，一共是$O(NM+M^2)$个。前者是多边形与圆(一个多边形与一个圆顶多$O(N)$个交点)，后者是圆与圆(两个圆顶多两个交点)。

然后建个平面图。区域的边有可能是圆弧。。直接看成切线。。就可以抠出所有区域了。。

区域的面积怎么算?首先弄出多边形面积(把圆弧强行拉直)，剩下一堆弓形加加减减就好。

为了判断一个区域是否在圆并里面。。因为一个区域一定完全属于外界或完全属于某一个圆，所以如果所有顶点都在某圆内(含边界)那么答案就是在，否则就不在。同理可以判断它是否在凸多边形里面(凹多边形就不行咯)。以及特判无穷域(不过加了彩蛋之后应该不会把无穷域算成在里面)。注意到一种特殊情况(在多边形外的弓形)，所以我们在判断一条弧边的时候需要连带判断它的中点。

为了减少特殊情况。。比如说$360$度的弧或者平面图不连通，对每个圆中强行加入四个等分点，一个点在最底下。然后把所有图形的最底下的点与它往下走的第一个点连一条边。嗯。。最底下还要加一条横的直线，越底下越好。总之各种花式魔改之后图终于连通啦!

假设看官们都会平面图扫域的那套理论→_→不过直接扫域会出现问题，那就是一堆圆切于一个点的时候，它们斜率相同，你怎么比较大小呢?。。。其实加一点随机扰动就好了。

我的代码：用的不是atan2比较大小，直接用的向量叉积，不然会莫名萎精度。。然后这题可以配合python的turtle调试。(见我在cc的代码9626963)

题解的那个Green's Theorem我看了一下。。。太叼了，而且标程居然只有5k。。比我不知道高明到哪里去了。。

HBIRD

假设$N\le M$，那么总共只有$O(N^3)$种鸟，而且点权不超过$50$那么鸟权不超过$3\times 10^6$。$O(N^3)$遍历一下权值为$i$的鸟的个数，得到一个这样的数组然后每次询问的时候二分一下就好。

注意特判可以喂所有鸟的情况。

TULIPS

建立一棵树，叶子节点是原树中的点，非叶子节点是原树中的边，kruskal的时候边$e$连接了连通块$a,b$，那么$e$是$a,b$的父亲，并代表连通后的整个连通块。dfs序就可以把子树变成区间了。

现在变成下面的问题：郁金香排成一排，每次询问一个区间中，上一次被询问的时间小于$X$的数的个数。$X$对所有询问是相同的。

现在这个区间中每个数都是$1$，每次询问就会求一个区间中数的和，然后把这个区间置为零。

因为某些时候某些数会突然变成$1$，所以在每次询问前应该拿出所有要变成$1$的区间然后执行。

搞一棵平衡树维护区间，平衡树的节点是“$[L,R]$在时间$t$的时候会变成$1$”，再顺便把这些区间用堆维护一下，平衡树中关键字是$[L,R]$而堆中关键字是$t$。

每次询问的时候从堆中拿出所有要变成$1$的区间并变成$1$。然后插入区间$[L,R],t+x$。如果该区间覆盖了平衡树中的某些区间$I$那么删掉$I$；如果与某些区间$I$有交集那么把$I$变成$I\backslash [L,R]$。

复杂度应该是$O(n+Q\log n)$的。

以及这题一定要多读英文题面，因为有变动，中文题面就没有赶上变动。。大概就是$X$加了个$1$。cc真是坑啊。

CHNGSS

说一下我的想法

想法一：纯随机 得分$5.7\times 10^7$。(后来想了想如果全输出$25$的话应该会好一点

想法二：我们考虑所有数都在$[1,K]$中的情况，假设要求出所有是$i$的数，我们就分治，每次求一个矩阵中是$i$的数的个数，如果这个矩阵中没有确定的数都是/不是$i$那么直接退出；否则递归两边。。其实更像k-d树的思维。。

现在$K=50$。。我就把$K$设为$6$，得到每个元素在$[1,8],[9,16],\dots,[41,50]$这几个区间中的哪一个，直接用区间中位数替换。

其实取$K=7$更优，但是$K=7$的时候询问次数爆掉了，就只好取$K=6$。

(效果并不好→_→