11
9
2018
0

NOIP2018垫底记

打爆MYC不值一提

18.11.10

上午打了场NOIP,又垫底了。。。

下午苦练泡泡堂本领。。。

傍晚溜出学校吃了必胜客。。。

18.11.11

上午打了场NOIP,又垫底了。。。暴力都没堆满,没救了。。。

感觉代码能力还有很大提升空间啊,半个多小时都没写+调出T2正解。。。结果T3暴力还堆得比别人少。。。

 

考虑退役,NOIP后学文化课了。。。希望学考不要考E。。。

学好文化课,吊打方尤乐!!!

 

Category: 未分类 | Tags:
10
25
2018
1

涂论学习计划

有向图

无向图

子图:(V ′ , E ′ ) 是 (V, E) 的子图当且仅当 V ′ ⊆ V, E ′ ⊆ E

生成子图:(V, E ′ ) 是 (V, E) 的生成子图当且仅当 E ′ ⊆ E

导出子图:G ′ = (V ′ , E ′ ) 是 G = (V, E) 的导出子图当且仅当 G ′ 是 G 的子图,且对于任意 u ∈ V ′ , v ∈ V ′ , (u, v) ∈ E 有 (u, v) ∈ E ′

路径

连通性

独立集

最大独立集

极大独立集:不存在点数更多的独立集是自身超集的独立集

点覆盖:若图中所有边都至少有一个端点在点集 P 中,则称 P 是一个点覆盖

最小点覆盖

|最小点覆盖| + |最大独立集| = 图中点数

证明:设|最小点覆盖|=x,|最大独立集|=y.考虑将最小点覆盖删去,得到一个独立集(y>=n-x);将最大独立集删掉,得到一个点覆盖(x>=n-y).所以x+y=n.

支配集:对于点集 P,若 V − P 中的任意点都有边与 P 中的点相连则称 P是一个支配集

拓扑图 (有向无环图,DAG)

最短路

最短路径图:固定起点 s,求出 s 到其他所有点的所有最短路径,将不在最短路径中出现的边删掉,得到的图就是以 s 为起点的最短路径图,若边权均为正,则它还是一个 DAG

生成树

竞赛图

欧拉路径 (回路)

哈密顿路径 (回路)

匈牙利算法(不会证)

任意一个二分图的最小点覆盖等于其最大匹配数(不会证)

Hall 定理:一个二分图 G = (A ∪ B, E) 具有完备匹配当且仅当:对于任意X ⊆ A, |X| = k,至少存在 k 个 B 中的点与 X 中的点相连(不会证)

邻接矩阵

邻接表

强连通:若对于图 G 中任意两点 u, v 都存在 u → v 和 v → u 的路径,则称 G 是一个强连通图

强连通分量:有向图的极大强连通子图

割点:无向连通图 G = (V, E) 中,对于点 x ∈ V 若删去 x 后 G 不连通,称x 是 G 的割点

:无向连通图 G = (V, E) 中,对于边 e ∈ E 若删去 e 后 G 不连通,称 e是 G 的桥边

点双连通图:任意两点间都存在两条除起始点外互不相交的路径的图

类似的有边双连通图点双连通分量边双连通分量

强连通分量之间交集一定为空,点双连通分量间可能有交,交点是原图中的割点

Floyd 算法,时间复杂度 O(n^3 ),图中不能有负环,能求出任意两点间最短路
Dijkstra 算法:时间复杂度 O(n^2 ),可利用数据结构优化至 O(n log n),图中不能有负权边,适用于求单源最短路
Bellman-Ford 算法:O(nm),适用于求单源最短路,能用来判负环

判断负环:第 n 次循环时 Bellman-Ford 算法仍能成功松弛;SPFA 中某个点入队次数超过 n 次

差分约束转化成最短路问题

Prim

Kruskal

*Boruvka

斯坦纳树:给定一个点集,求连通这个点集的最小子图 (显然它也是棵树)

状态压缩 DP求解:dp[x][S] 表示包含 S 中所有点 (S 是给定点集的一个子集) 以及点 x(x 可以不在给定的点集中) 的最小生成树

Tarjan 算法

dfn i 表示点 i 在 DFS 中搜索到的次序,low i 表示从 i 点出发只经过树边 (向子孙方向) 以及至多一条非树边,所能到达的点的 dfn 最小值

强连通分量 (SCC) 的性质:1. 从任意一点出发都能遍历 SCC;2. 将 SCC缩成一个点,则图变为 DAG
由性质 1,SCC 在搜索树中一定是连续的一块点,所以搜索树最底层的SCC 一定是一个子树,重复地将它们找出后删除便能求出所有 SCC

一个以 i 为根的子树是 SCC 当且仅当 dfn i = low i 且子树中不存在满足此性质的点
利用栈存储子树中未被删除的点,则能求出 SCC 具体的点集

若 u 的儿子 v 满足 low v ≥ dfn u 则 u 是割点
若 u 的儿子 v 满足 low v > dfn u 则 (u, v) 是桥

边双连通分量之间交集为空,故将它们缩成一个点后,与所有桥边一起组成一棵树,所以求边双常常删掉桥边后利用并查集求解

点双连通分量:每条边属于恰好一个点双连通分量,tarjan的过程中在stack里存边,遇到low[v]>=u就弹stack。

*圆方树:对点双连通分量(方)和割点(圆)建点,割点与点双连通分量之前连边形成的树。

2SAT 问题:有 n 个待赋值的布尔变量 b i 以及 m 个约束条件,每个约束条件形如 b i 取 x 时 b j 必定取 y,判断是否有解并构造一组合法解。

构造一个 2n 个点的有向图,每个布尔变量 b i 有两个点 t i ,f i 分别代表取真或假,一个点被选表示使用该赋值方法
建边:边 (a, b) 表示选 a 必定选 b,此时一定存在(!b,!a)
先求出该图的 SCC,若 f i 与 t i 同在一个 SCC 中则问题无解。否则一定有解。

构造:对于每个bi,t i 和 f i这两个里面取所在SCC拓扑序靠后的。

证明:反证法。利用边的对称性。

一个技巧:缩点后的DAG的拓扑序等于可以直接用SCC的逆序

欧拉回路

Fleury's algorithm:从任意一点出发开始DFS,经过一条边就将其删去,点访问顺序的逆序就是一条欧拉回路

Category: 未分类 | Tags:
10
16
2018
0

The Boy Who Lived

Category: 未分类 | Tags:
9
8
2018
2

water record before NOIP

18.11.8

Solve LJOJ5115.

18.11.2

Solve SRM533-1000.

18.10.31

Learn SRM526-1000.

Solve SRM524-1000.  O(nlog)

Solve SRM523-900.

18.10.30

Learn CC-SAFPAR.

18.10.26

Solve SRM530-900.

Learn SRM528-1000.

Solve SRM529-900.

18.10.25

Choose the problem which will be moved for the homework.

Learn a way to get the edges which is always on the shortest path

18.10.22

Learn CF1071C.

18.10.21

Solve SRM532-1000.

18.10.19

Learn SRM539-1000.

Solve SRM535-1000.

Solve SRM534-1000.

18.10.18

Learn LJOJ5065.

*Solve LOJ2257.

Solve LOJ6270.

Solve LJOJ5067.

18.10.17

Solve SRM537-925.Firstly it can be turned into a problem of Graph Theory easily. Then we can solve it by using MCMF according to something about Euler circuit.

Solve SRM536-1000 which is a weaker version of ZJOI2017D1T3 as what jiry_2 memtioned in his solution. Let F(m,k) be the answer of the problem. Then if m is an even number,F(m,k)=F(m/2,k/2). Otherwise,F(m,k)=sigma F((m-1)/2,(k-i)/2)*a[i]. In fact the number of F we need to calculate is very small. It can be proved easily.

18.10.16

Today students of our school and other five schools had a test prepared by me. The third problem(LJOJ5061) is a little bit tricky in my mind.My solution is to check for every x in a random order so that the expected number of times to use binary search becomes O(log). However,there is another solution,check for ans in a decreasing order,every x costs O(n) in total. So we can find the range of ans using O(sqrt(nP)*n) and then the exact value in O(sqrt(nP)*n).

Solve SRM546-1000 which is even less than 900 in my opinion.What you are asked to do is to find the number of the F which satisfies F^4=G (F and G is a permutation). Firstly we find circles in G,then we can solve the problem independently for circles of different size.Let f[i][j] be the number of ways to put j circles of size i in G into F.This DP can be done easily:)

18.10.15

Solve SRM540-950.Firstly,it's not difficult to discover that the problem can be divided into two independent and similar parts:%2 and %5.Now I'll only tell you how I solve the problem in (%5).We can consider all the restrictions of product(l,r)=x(x!=0), It's evident that a[l~r] can't be 0, so we just pick up those numbers which can't be 0 and put them into a new sequence A keeping their orders in a[]. Other numbers are put into another new sequence B in the same way. Now I can easily deal with the resitrictions for A by using Disjoint Set Union. Other resitrictions are like B[l~r] has at least one zero. It's a classic DP problem. Just turn the resitrictions into p[] where p[i] means B[p[i]~i] has at least one zero and p[] is maximum. So p[i] increases not strictly. Let f[i] be the number of possiblities of f[1~i] which satisfy p[1~i]. This DP can be done easily by checking for every j which means the most right position occupied by zero in B[p[i]~i].

18.10.14

I took part in CF Round 516 and lost(missed?) a chance to get about #20 because of my failure on D. B&C are simple but A is a little bit tricky.For D,I quickly thought up a solution with a complexity of O(sqrt). However,I didn't deal with the details clearly so that (?) I spent far more time in coding than my expectation.Finally I still failed system test because of two little mistakes :(

18.10.13

Solve SRM544-900.It's just a simple matrix multiplication problem.

18.10.12

Solve SRM542-1000.Firstly,the statement and limits hinted me that it was probably a problem about flows:) Then looking at k*(200-k),I thought there were two ways:

1.Check every possible k.

2.Use binary search.

I considered about the first way but couldn't think up a solution.For the second way,I found that we can turn the problem into a classic minimal cut problem easily after the binary search.

You can see more details on https://www.cnblogs.com/Blog-of-Eden/p/9747507.html :)

18.10.6

LearnCan't learn SRM541-1000.F(S,k) means the answer from state S after k seconds.When k is an odd number,F(S,k)=F(S',k-1).Otherwise,by coding brute force,we can see I can't see:a cell A can only influence cells which have the same parity as A both in the row and the column.Therefore,F(S,k) can be divided into four independent parts.For one of the parts,we only need to calculate F(S',k/2) where S' is a field which has the size a quarter to S.

18.10.3

学习了学不来CF1053D。先找个规律,然后贪心选(p,0),(p-1,0),最后猜测把一个改成(1,1)的时候其它的不变。证明?感受了一下应该还是有点道理的?

18.10.2

学习了BZOJ3467,一边是顺的一边是倒的,对左边建trie,对右边后缀排序(a确定时,a是b的前缀=b的字典序在某个区间内),后缀排序可通过倍增+hash比较方便地实现。

18.9.15

学习了BZOJ4170 ,曼哈顿->切比雪夫,然后数据结构。bitset应该也行。 

18.9.14

学习了环套树计数(18.9.10_old.T2),大概是个prufer的应用?

学习了hdu6316,大概是%2的一些套路,f(x)^(2n)=(f(x)^n)^2=f(x^2)^n,f^(2x+1)=f(x^2)^n*f(x),奇偶次独立。

学习了hdu6310,长的像卷积的东西比较多的DP可以考虑用代点值的技巧优化。

18.9.13

学习了学不来18.8.6.T3(LJOJ4979) ,从未见过如此不讲道理神仙之出题方式,给你一个n^2的DP式子,让你优化复杂度,做法是通过观察发现这个DP是哈夫曼树的DP求法。

18.9.11

学习了CF706E ,牛逼的二维链表的应用。

18.9.9

学习了BZOJ4323,图论只有小学水平怎么办。。。

复习插头DP,写了BZOJ3187,其实插头DP就是记个插头的联通性罢了。

学习了hdu6386,最短路只有小学水平怎么办。。。

18.9.7

ztr教了我一种均摊o(1)离线求逆元法,感觉还挺妙的,思想是先全都除掉,然后求逆元只要乘上前缀积和后缀积即可。

Category: 未分类 | Tags:
7
23
2018
0

2018暑假颓废记

NOIP&清华集训&学考打爆MYC不在话下

暑假学习计划(其实感觉暑假不长了):

早上起来背单词。。

晚上睡觉前看典范英语。。

在歌单里加入新概念英语QAQ

oi的话主要以hdu(多校+百度之星)&cf上的题&noip模拟题为主。。

吃完中饭睡觉一小时。。

其余时间看物化生。。

18.8.31

打爆MYC

18.8.30

打爆MYC

18.8.29

打爆MYC

18.8.28

打爆MYC

18.8.27

打爆MYC

18.8.26

打爆MYC

18.8.25

打爆MYC

18.8.24

打爆MYC

18.8.23

上午见到了傻逼MYC。。。

下午看了点物理。。

晚上看了点化学。。

18.8.22

上午打了场NOIP模拟赛,又垫底了。。。

下午??

晚上??

18.8.21

上午打了场NOIP模拟赛,又垫底了。。。

下午??

晚上??

18.8.20

可能看了点物理??

18.8.19

上午??

中午出去吃饭了。。。

晚上打了场CF,又垫底了。。。感觉红不过两场

18.8.18

上午??

下午打了场百度之星,又垫底了。。。破破破题!!!

晚上??

18.8.17

上午??

下午??

晚上??

半夜打了场CF,又垫底了。。。不过叉了10个A还是挺爽的~~~

18.8.16

上午??

下午看牙齿去了gg

晚上看了点物理。。

18.8.15

除了计划中的学外语外,看了一整天的物理。。。

半夜打了场srm,又垫底了。。。(这次总算没爆零

18.8.14

除了计划中的学外语外,看了一整天的物理。。。

18.8.13

除了计划中的学外语外,看了一整天的物理。。。

18.8.12

上午??

下午打了场百度之星,又垫底了。。。最后时刻把02交上去不知道为啥W了。。

晚上制定了学习计划。。

18.8.11

上午看了点物理。。(生物已弃)

下午打了场百度之星,又垫底了。。。E这个破题,我tm没看到ai可以是负数。。不然我就艹标了

晚上打了场CF,又垫底了。。红不过一把。。。只过了个A,都快跟MYC五五开了。。。

18.8.10

上午学了生物必修一专题五。。

下午学了生物必修二专题六(学考五三上的专题编号,跟课本有点不太一样?雾)。。之前还打算到今天为止学完生物必修一、二的,现在还差这么多,,感觉人生充满了没有希望。。。

晚上??

18.8.9

上午??

下午让txc去LJOJ上交了我写的8.4.T2的莫队,A了。。然后学了下正解。。

晚上学完了生物必修一专题四。。。

18.8.8

上午看了点生物。。

下午打(?)了场多校,又垫底了。。

下午看了8.4.T2,还只会根号。。

晚上打了场CF,又垫底了。。

18.8.7

上午看了8.4.T3一般图匹配计数(n<=30)

下午??

晚上看了点生物。。

18.8.6

上午??

下午??

晚上??

18.8.5

上午看牙齿去了。。

下午写了个BZOJ2534。。。

晚上学完了生物必修一专题三。。

18.8.4

上午??

下午去百度之星写了签到题,又垫底了。。。

晚上看生物?

18.8.3

上午??

下午看了hdu6331,矩阵乘法多组询问的两大技巧。。一种是倍增预处理,一种是预处理根号。。

晚上打了场CF,又垫底了。。。

18.8.2

上午看了hdu6326,感觉转换成hdu6299后就是很套路的树上有依赖的排序问题,用个堆贪心就好了。。。

下午看了poj2893,根本学不来。。。

下午看了hdu6333,感觉根本没想到可以莫队啊。。

晚上学了点生物必修一专题三。。。

18.8.1

上午看了hdu6299(=usaco 2012 jan silver climb),感觉要回小学学贪心去了。。。

下午打了场多校,又垫底了。。。

晚上学完了生物必修一专题二。。。

18.7.31

上午??

下午??

晚上看了生物必修一半个专题二。。。

18.7.30

上午??

下午打了场多校,又垫底了。。。

下午打了场CF,又垫底了。。。

晚上看完了生物必修一专题一。。。

18.7.29

上午看牙齿去了。。。

下午??

晚上剪头发去了。。

18.7.28

上午看了点物理。。。

下午验MYC的NOIP模拟题,只会做d1t1,NOIP要四等奖滚粗了。。。

晚上看今天的NOIP模拟题一道都不会做,感觉NOIP根本没希望吊打MYC,估计一等奖都没了。。。

18.7.27

上午&下午看了点物理+补了会儿觉。。。

晚上去拿了眼镜。。。

18.7.26

上午看了点生物。。。

下午补了会儿觉。。。

晚上??

18.7.25

上午看了SRM517-600。

下午打了场多校,又垫底了。。。

晚上去搞了搞眼镜的事情。。。

18.7.24

上午看了usaco 2012 open gold subsets,见识了个新复杂度。

下午口胡了SRM524-1000。

晚上??

18.7.23

上午口胡了fyl's problem,去搞了搞身份证的事情。

下午打了场多校,又垫底了。。。

晚上???

Category: 未分类 | Tags:
7
16
2018
0

NOI2018

打爆MYC!!!

7.16

雅礼真是个鬼地方。。。不懂这个学校的人是怎么活下来的。。。

7.17

睡了一个下午,听说睡多了会变傻的,感觉要完。。。

7.18

上午打了场NOI,又垫底了。。。规律都不会找怎么打得了OI。。。排列嘛,,,脚趾头数数也就这么几种规律了。。。

7.19

社会活动,去韶山膜毛主席,热得头晕。。。

7.20

上午打了场noi,又垫底了。。。T2乱搞搞不出来,暴力堆不出来。。。

苟进集训队,清华集训和WC又要垫底了。。。

被MYC打爆了。。。没事我NOIP2018一定打爆MYC。。。

7.21

wori书包找不到了。。。全怪MYC。。。

7.22

4:30起床21:00到家是一种怎样的体验?

火车站里打牌把他们都打爆了。

Category: 未分类 | Tags:
7
10
2018
1

5days before NOI2018

打爆MYC指日可待!

7.11

上午打了场模拟赛,又垫底了。。。100倍都没MYC多。。。

浪了一个下午,吃烤肉+打球(?)+??

晚上???

7.12

上午打了场模拟赛,又垫底了。。。T1这种题都不会做。。。T3竟然倒着DP就行了。。。

下午??

晚上??

7.13

上午打了场UNR#3 Day1,又垫底了。。。

下午??

晚上打了场CF#497,又垫底了。。。D好像是个裸的数据结构优化2-sat?

7.14

上午打了场UNR#3 Day2,又垫底了。。。

心态良好,顺其自然就行了,NOI多写暴力。。。

 下午??

7.15

打游戏真累

阿老师说noi期间只要背背笔试就差不多了。。。其它啥都别管。。。

Category: 未分类 | Tags:
7
6
2018
0

10days before NOI2018

距离NOI2018还剩10天,打爆MYC绰绰有余。

7.6

上午打了场模拟赛,又垫底了。。T2不会字符串,T3不太会置换的基本运算。

下午??

晚上写了一晚上的上午T3没调出来。。。

7.7

上午把昨天T3调出来了。。。

上午打了场模拟赛,又垫底了。。T2、T3傻逼题不会做,T2乱搞怕TLE少了10分。

下午???

晚饭咬不动,晚上ztr安利2017多校7,看了NOIP模拟的T1、T2。

7.8

上午打了场模拟赛,又垫底了。。又没考到MYC一半。。。T2???T3???

下午???

晚上???

7.9

上午打了场模拟赛,又垫底了。。T2,T3垃圾题,T1(CF183D)还是有点意思的。。

下午去跑步了,黄叉蛙说这样没效果,要跑12分钟才行。

晚上看了CF1004E,学了两种做法,一种是直接从叶子往里贪心扔点,一种是二分后通过每个子树里是否一定要选点来check。

7.10

上午打了场模拟赛,又垫底了。。T1???T2???T3???学不来学不来。。。

下午学了CF1004E又一种做法,注意这种题往往猜测与直径有关(树上最优化问题猜直径、重心!)。容易理解选的点一定是直径的一部分。O(N)。

晚上写了CF997D,上下DP。从开始写到A掉没用到gdb。

Category: 未分类 | Tags:
7
1
2018
0

15days before NOI2018

距离NOI2018还有15天,打爆MYC不在话下。

/*

唐冠军原话:

别学新的了啊

反正能打多少都打出来就很稳啊

多看看题

简单部分分有没有写全

全的话大概前30起码了,挂一点可能也还可以,多的话就凉凉

*/

终于考完了学考,开始康复,还剩15天gg。

7.1

上午睡觉,看牙齿

下午回学校

晚上写了CF1000G,应该是最好写的上下DP了。

晚上打了arc100,罚时爆炸,F应该是个傻逼DP但是来不及了。

7.2

上午看了CF986F,注意到数据范围k=10^15的题可以猜测复杂度为k^(1/3),大概就是说后面的数%p[1]=x的时候让sigma尽量小,建成最短路模型(带%的背包好像都可以建成最短路)。

上午考了模拟赛又垫底了。T1听到别人说是论文题先扔了,T3没思路。回去做T1,想了个假做法(都不需要利用题目中的k),后来“爆零”了,其实T1直接注意到k发现是两条链就好了。

下午睡觉。

晚上听讲题,好像并没有学会什么。。。

7.3

上午考了模拟赛又垫底了。想了1个多小时的T1认为T1的做法只有可能是压位,具体没想过,T2傻逼树剖优化网络流调了半天没救了,T3来不及了少写了40暴力。

下午扫雷玩不出来。

晚上写了CF364E,分治,写+调了好久,代码能力极差。

7.4

上午考了模拟赛又垫底了。T1傻逼题,T2不会卡常(题解是四毛子?),T3???

下午??

晚上??

7.5

上午考了模拟赛又垫底了。T1傻逼题。T3是二维插值,太菜了不会写了自己YY的一维插值一维guass,其实二维插值式子和一维长得一样。T2随便写了个暴力就A了。

下午黄叉蛙说我应该减肥去跑步了。

Category: 未分类 | Tags:
3
18
2018
3

ZJOI2018

哎呀呀,省队选拔啦!真希望一个月后能喊出"Noi2018,count me in!" --18.3.18

一试已死,要靠二试翻盘了QAQ--18.3.22

要退役了嘤嘤嘤--18.4.23

bless all--18.4.25

一道题决定的省选。OI再见--18.4.28

 

从NOIP2017,到ZJOI2018 day1,再到ZJOI2018 day2.竟然已经过去半年了.

高中OI路上的第一个目标(高一进队)竟然没有实现。

确实存在一些自身以外的原因,比如d2t2决定性太大,今年省队比去年少(雾)。

但是自己实力确实还是不够强,去了noi也没把握进集训队。

况且比我强的没进队的人多了去了(雾),进队或许真的可遇不可求吧。

塞翁失马,焉知非福。高一进了队高二省选就危险了(划掉)。

 

于是,我再不能在说说里呐喊“NOI2018, count me in!"。

于是,我只能再等一年,一年后,我必当一雪前耻。

 

UPD:氪了个C类QAQ.

Category: 人生经验 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com