辣鸡咯..

noip打的是真的菜.. 退役选手可能要失去各种wc的机会了..

哎争取多一次wc的机会吧（flag）

---

来看看做了多少？

56/150

Codeforces Round #443 (Div. 1)

B. Teams Formation

依次缩去$m-1$个间隔中的相同的东西，最后剩下的再搞就行了

*C. Tournament

假如A能赢B，就在图中建立A->B的边，那么一个人要是能谁都赢，就是它能到达所有其他点

现在就是要动态维护这个强连通分量

发现这个图不会存在大于等于三且中间没有边的环，也就是对于一个点对一定会存在边

然后发现缩完强连通分量之后可以拉成一条链

每次加入一个点，找出最小的能战胜它的和最大的战胜不了它的，把中间全部合起来

这样就很棒了

*D. Magic Breeding

想象如果这个题只存在$1$和$0$，最多只有$2^k$种不同的特征，这个问题就可以用bitset很好的做出来了

现在把每一列拆成$k$个点，表示他是否大于等于该列第$i$个数，然后就相当于上面的题了

可能复杂度比较大，但是就是能过，毕竟$O(\frac{q2^kk}{32})$

[2017.11.21]

发现自己不用退役真的很开心啊..

没想到有人已经自大到这种地步了啊..

4291: [PA2015]Kieszonkowe

扫一遍就好了

4236: JOIOJI

扫一遍用map维护$(s1-s0,s2-s1)$的最迟出现位置来dp

[2017.11.22]

4260: Codechef REBXOR

用trie找异或起来最大的

4247: 挂饰

发现只跟钩子个数有关，然后就很好dp了

[2017.11.25]

4237: 稻草人

cdq再维护两个单调栈即可

4245: [ONTAK2015]OR-XOR

考虑最后答案在二进制的第$i$位，如果要让它为$0$，那么就需要断某些点

从大到小考虑这个用bitset维护一下就好了

4241: 历史研究

分块sb题

[2017.11.28]

真的是越来越辣鸡了.. 线性基都不会了..

4292: [PA2015]Równanie

枚举$f(n)$即可

4276: [ONTAK2015]Bajtman i Okr?g?y Robin

可以线段树优化建图跑费用流

也可以贪心来跑匈牙利

跟yyl学到了一种$O(n^2)$的做法：

定义$f_x$表示选$x$的人最远的右端点在哪

*4269: 再见Xor

做出线性基就可以求出最大值

然后次大值就看哪一位选的和最大值不一样就好了

[2017.11.29]

今天状态还好吧..

4216: Pig

把它$20$个分一块就行了

4278: [ONTAK2015]Tasowanie

一开始太想当然，后来仔细想想就是个后缀数组裸题..

%%%王队长 其实可以贪心

只要一段是单调不升的，就可以整段拿出来

[2017.11.30-12.1]

昨天忘记写了..

天天犯sb错误，inf又没开大

4238: 电压

跟4424差不多

4289: PA2012 Tax

把边看成点，然后连到同一个点的按照边权排序

大的往小的连$0$，小的往大的连边权差

4282: 慎二的随机数列

类似于普通的最长上升子序列

4293: [PA2015]Siano

容易发现相对大小不会改变

就可以用线段树维护了

[2017.12.3]

4205: 卡牌配对

把原问题转成找至少两个不互质的

然后就增加$3\times 46\times 46$个节点就可以跑网络流的

dinic奇快无比？？

*4239: 巴士走读

把边看成点跑类似最短路的东西

md怎么这么多没有用的边..

[2017.12.4]

4264: 小C找朋友

hash一下就好了

4275: [ONTAK2015]Badania naukowe

找出$a$、$b$串中所有$c$出现的位置

dp一个前缀和后缀就行了

*4204: 取球游戏

很容易想到$O(n^3log\ inf)$的做法

然后发现那个矩阵比较特殊每一行都是前一行右移一位

所以只维护第一行就行了

4281: [ONTAK2015]Zwi?zek Harcerstwa Bajtockiego

很水啊..

[2017.12.5]

今天效率并不高..

4296: [PA2015]Mistrzostwa

从度数小的点开始删，删剩下的就是联通块的大小了

4231: 回忆树

把询问拆成三块，中间那块可以暴力搞

剩下的维护ac自动机的fail树，询问就是统计子树和

*4298: [ONTAK2015]Bajtocja

启发式合并，hash维护每个点每层所属联通快

4294: [PA2015]Fibonacci

找规律发现$60$、$300$、$1500$、$15000\cdots$

然后宽搜一下

不知道为什么wa了啊..

[2017.12.6]

效率是真的低.. 但是还是先治病吧..

3261: 最大异或和

可持久化trie裸题

4212: 神牛的养成计划

一直在想怎么排序字符串

想到后面发现要用到trie就不如直接在trie上排序

排序后对于询问的前缀就是一段区间

再找后缀就是可持久化trie的裸题了

4285: 使者

cdq裸题？？

[2017.12.7]

*4206: 最大团

最大团是npc hard的啊..

过每个点做切线，每个点相当于覆盖一条弧

不满足条件当且仅当覆盖的区间相离或者包含

现在要选若干个点使得两两互相有交集

又发现一个点取它在弧上的补集是不会影响答案的

把覆盖掉$(r,0)$的点取补集

就可以把问题转化成选取若干条线段使得

$$l_1

把它按照左端点排序，就可以通过做最长上升子序列来计算答案了

但是这样做难免会选到包含的

于是我们枚举一个让它必须选，然后剔除掉被它包含的所有线段再做就没事了

这样复杂度是$O(n^2logn)$的

4660: Crazy Rabbit

三倍经验

3663: Crazy Rabbit

三倍经验

cf575 A. Fibonotci

$n$个$n$个做，修改的用线段树维护

cf575 B. Bribes

开$nlogn$个节点维护答案

*cf575 G. Run for beer

最短路，然后反着维护..

不得不说细节是真的多

[2017.12.8-9]

*4230: 倒计时

设$f_{i,j,k}$和$g_{i,j,k}$分别表示$****9999x$这个数有连续$i$个$9$，前面最大的数是$j$，个位是$k$使得前面退位的步数和退完后的个位是啥

然后再从原数利用dp数组减就行了

4209: 西瓜王

主席树裸题

4297: [PA2015]Rozstaw szyn

dp，然后可以得到每个孩子节点取值的范围

然后扫一遍即可

4262: Sum

线段树裸题

[2017.12.10]

惨了现在没有数据都不会查错了..

晚上做了一场atcoder.. md均摊$O(n)$的都没发现..

4246: 两个人的星座

发现一对三角形有且仅有两条公切线

然后就枚举一个点，剩下的点按照极角排序扫一遍就行了

凭什么把重载运算符放在结构体内就快这么多啊..

4277: [ONTAK2015]Ci?cie

挺容易想到的dp吧

[2017.12.11-12]

做题极其不顺，很难受

*4233: [Cerc2013]Captain Obvious and the Rabbit-Man

消元找规律，发现消出$a_i$的系数刚好是$(x-f[1])(x-f[2])(x-f[3])\cdots(x-f[i-1])$的系数

然后我就被卡常了

然后想想发现每次减去前一行乘上$f_{i-1}$也是可以消的..

*4248: AAQQZ

真尼玛难做

枚举一个最长回文串然后两边展开就行了

细节真的多

4280: [ONTAK2015]Stumilowy sad

线段树裸题？？

*4207: Can

分治然后两边展开

3721: PA2014 Final Bazarek

4209弱化版

4250: [PA2014]Bazarek

同上

[2017.12.13-14]

磨出了一道题真的棒..

*3716: [PA2014]Muzeum

把它坐标拉伸使得每个警卫看到的是一个九十度的角

然后再把整个图旋转九十度

根据最小割模型连边，发现就是警卫连到手办的最大流

然后就用按$x$坐标排序，用set维护$y$坐标进行贪心就好了

4251: [PA2014]Muzeum

同上

*4271: chemistry 化学

先放一个kpm的链接以表尊敬

里面有一句超有道理的话

假如两棵无根树同构，那么以各自的重心作为根的有根树也同构

一开始还打算枚举最长链然后burnside一下的..

然后发现这样做是$O(n^3)$，用fft优化可以做到$O(n^2logn)$

但是要高精度，这样的做法就会T掉

然后看到kpm这句话感觉很有道理，就从重心开始dp，每个节点最多只有$3$个孩子，再让根的子树都小于等于$\dfrac{n}{2}$就好了

但是还有一种情况是有两个重心的..

这种情况发现可以加一个点在两个重心之间就没问题了..

然后再套上高精度就perfect了..

[2017.12.15-17]

很棒搞出了Voronoi图和Delaunay三角剖分

*4219: 跑得比谁都快

上述

3007: 拯救小云公主

上题弱化版，可以$O(n^2)$做..

5091: 摘苹果

发现无论多少次在某个点的概率都一样..

就随便搞搞行了..

[2017.12.18-22]

不知不觉又拖更了..

然后发现自己啥都没做天天颓..

2393: Cirno的完美算数教室

xjb爆搜.. 从大到小枚举会快

*3622: 已经没有什么好害怕的了

把两边排序

$f_{i,j}$表示前$i$个至少有$j$对左边大于右边的方案数

$g_i$表示恰好有$i$对左边大于右边的方案数

$g_i=\sum\limits_{k=i}^nC_k^if_{n,k}$

然后就行了

2916: [Poi1997]Monochromatic Triangles

所有-不合法的就行了

*4361: isn

$f_i$表示长度为$i$不降子序列的个数

那么答案就是$\sum\limits_{i=1}^n(f_i\times(n-i)!-f_{i+1}\times(n-i-1)!\times(i+1))$

5083: 普及

用单调栈可以求出以每个位置为开头、结尾最远的点

然后就用线段树搞搞就行了

有另一种做法，$O(n)$RMQ可以把复杂度优化到$O(n)$，可惜我不会qaq

*5097: 实时导航

询问的时候跑最短路，用bitset维护堆操作来优化就可以做到$O(q\dfrac{n^2}{32})$了

具体来说就是开$4$个bitset，维护已经出堆的点和在堆内的点的最短距离的点集

5004: 开锁魔法II

发现这个图是个基环内向树，他的叶子节点是全都要选的

然后$f_{i,j}$表是前$i$个联通块选$j$个节点最后全部搞定的方案数就没了

没想到double存$300$的组合数都可以啊..

5003: 与链

每一位分开看就是个多重背包..

*5005: 乒乓游戏

线段树维护覆盖某个区间的所有点

每次新来一个就看左右端点被哪些区间覆盖

用并查集合并下就行了

*5011: [Jx2017]颜色

很像之前做的一道coci的题目..

就是找把一个圆拆成两半且同一种颜色都在一边的方案数

hash一下..

hash值相同的就可以断开了..

Codeforces Round #453 (Div. 1)

A. Hashing Trees

连续两个大于$1$就不合法了啊..

C. Bipartite Segments

出现一个奇环就说明包含某个区间的区间都是不可取的..

维护每个点最远到达的点

离线询问

按询问右端点排序即可..

*D. Weighting a Tree

建出生成树，发现偶环不影响

对于一个奇环，选任意一个点做根，发现根多出来$s$，那么环边就两端同时减去$s/2$

再来做即可

对于$s$为偶数的证明：

因为度数和点权奇偶性相同，总度数和总点权奇偶性也相同

也就是总点权为偶数，那么多出来的$s$也为偶数