[线段树+][LCA][dfs序][二分查找][×] codeforces 1062E

http://codeforces.com/contest/1062/problem/E

这题两个难点,第一个是如何快速找到一堆不一定在一起的节点的公共LCA,第二个是如何确定这一堆节点中需要剔除哪一个。

可以先想一下,设原集合的lca为p1,可以取得最优答案的点为x,其他点为vi,那么x一定不在lca(所有的vi)这个点的子树上。这时候,任意一个vi和x的lca都是p1。这时假如维护一个S[l,r]表示[l,r]的公共LCA,根据上面说的性质,这个S序列一定存在一个断点,从这个点开始所有的S==p1,这样的话就可以利用二分查找找到这个断点,可以确定这个断点一定是候选答案之一。另外一个在二分的过程中其实是所有的lca都是基于最左边那个点积累过来的,所以除了分界点之外另外一个可能影响到答案的就是最左边这个点。到这里就算是找到了唯二可能影响答案的点,只需要对他们分别验证就可以了。从dalao的代码里学到了lca也可以作为线段树维护的变量。。。 继续阅读“[线段树+][LCA][dfs序][二分查找][×] codeforces 1062E”

[DP][二分][经典][×] UVA 1443 Garlands

没做出来看题解的时候就在想出题人是怎么搞出来的。。。这个做法emm

最大值最小化肯定要想二分,但是二分后这题目怎么check是个技术活。我最悲催的是理解错了题目意思,以为这些珠子(不管是什么吧我感觉是珠子)可以互换位置。实际上是不可以换的emm所以说看题还是要好好搞明白。

然后说说这个check,这个一开始有点迷,因为它本身是dp那一章的题,但是二分的check一般都是判断一个可行性,那加了这个二分出来的答案的约束怎么判断可行性?首先可以确定一般dp不会说去dp那种“区间上的最大值”之类的东西,他要做一定是一个量化的东西去求最优解。这里的话可以想象一下,如果用了比m更少的段就可以满足要求那么就可以继续进行下去?这样的话必须保证段数和最紧的上限是一个正比的关系!但是算一算可以发现并没有这种正比关系,一般这时候就放弃用二分的方法了,但是这个题最精彩的地方就在于他的奇偶性,由于题目本身一直在要求“半段”,所以可以利用奇偶性来保证正比单调,具体可以看这位dalao的博客

继续阅读“[DP][二分][经典][×] UVA 1443 Garlands”

[线段树+][并查集][区间信息维护] UVALive 4730 Kingdom

利用并查集处理合并,并保存每个块对应的覆盖范围(在y轴上的)上下界;利用线段树(更新区间的范围从并查集维护的信息中得到)维护每个x.5的点对应的州数和城市数。区间修改单点查询,只要确定好x.5这些点在线段树中的对应的下标就可以了,我这里是x.5在线段树中下标为(x+1)。由于我写的是1-n的线段树写完了才发现题目说的0-n-1,只能把读进来的东西都++。具体的操作:对于road,先找两个点是否在一个块里,如果是了那就不用任何操作(画图可以看出来如果这俩是一个块里的那么他们覆盖范围之间一定已经有线了),否则先把这两个的分别的块对应的区域在线段树中减去他的影响,再将两个块合并之后,再在线段树中加上这一新块的影响。先减后加,这样就可以避免繁杂的分类讨论了。。。

第一版正经的线段树ac之后想了想感觉在这个情境下只需要保证叶子节点的信息有效就行了,推了一下感觉可以去掉maintain的操作。。。试了下果然可以,而且快了很多,在vjudge上已经是用线段树的跑的最快的了(前几名都是用的BIT emmm

wa的点:本来一气呵成写完很舒服但是没想到出了很多bug,因为一些愚蠢的bug调试了很久。。。。数据结构这块还是太弱了。
继续阅读“[线段树+][并查集][区间信息维护] UVALive 4730 Kingdom”

v2ray 配置

主要参考了https://toutyrater.github.io/

啊话说不知道写这个会不会被查水表

首先是服务端的安装
先校对时间

root@itemqqSS:~# date -R
Sat, 09 Feb 2019 13:03:45 +0000

下载脚本

root@itemqqSS:~# wget https://install.direct/go.sh
--2019-02-09 13:04:54--  https://install.direct/go.sh
Resolving install.direct (install.direct)... 2606:4700:30::681b:ae47, 2606:4700:30::681b:af47, 104.27.174.71, ...
Connecting to install.direct (install.direct)|2606:4700:30::681b:ae47|:443... connected.
HTTP request sent, awaiting response... 200 OK
Length: unspecified [text/plain]
Saving to: ‘go.sh’

go.sh                   [ <=>                ]  13.59K  --.-KB/s    in 0s

2019-02-09 13:04:54 (101 MB/s) - ‘go.sh’ saved [13915]

执行脚本安装 V2Ray 继续阅读“v2ray 配置”

[线性结构DP][经典] UVA10271 Chopsticks

https://cn.vjudge.net/problem/UVA-10271

确实是经典。。。这种一开始没有什么头绪的dp,可以自己写出来几组样例,从中发掘最优解的性质,从而找到入手点。经过这样的一个xjb试探之后发现了:最优解的每组筷子中的短的那两根必定是在有序序列中相邻的。这样的话就可以确定一个转移的方法了,类似于背包里对于每个物品选还是不选,在这里对于每根筷子确定选还是不选,如果选,根据上面的性质他必须和之前的那根筷子组成一副。由此可以确定一个最基本的转移方程形式dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(len[i]-len[i-1])^2),dp[i][j]表示对于前i个筷子分给j个人的最优解。这里还有一个问题是必须要给每个人再分一根最长的筷子,其实可以发现这个条件更好处理,只要满足i>=3*j就可以了:因为这个最长的筷子其实只要比另外俩长就可以,所以在最优解中的这根筷子有些人之间甚至可以换着用,顺序也无所谓,满足这个条件一定能分配好的。

对于这个状态转移方程,可以确定一个边界条件是dp[i][0]=0(从转移方程的第二部分可以得出来)

继续阅读“[线性结构DP][经典] UVA10271 Chopsticks”

[CF][补题][线段树][树] codeforces 1076E Vasya and a Tree

这个题自己当时主要还是思维限制,只想着怎么能有类似于dfs序线段树那种操作,或者是就某个点对他的子树做一个什么类似于线段树的打标记处理。。但是感觉太复杂了,没搞出来,而且也没有把可以离线这个点利用起来,还是too young

正解是在dfs过程中维护一个线段树,这棵树的下标是代表了当前dfs到的深度(而非节点),看到这儿就感觉是个很妙的操作,这样的话只需要每次进入到一个节点的时候把对应的属于该节点的所有的操作(这个需要离线处理,把对应的操作存用个vector存起来就可以了)都处理一遍,也就是把对应的所有的区间上的数值加上,dfs离开的时候把对应的区间上的数值减去,回滚一下,就可以保证在dfs过程中就把所有的操作处理完了。

继续阅读“[CF][补题][线段树][树] codeforces 1076E Vasya and a Tree”

[CF][图论][最短路树] codeforces 1076D Edge Deletion

这个题倒是不难,但是我当时对于题目的理解导致写出来很复杂,所以记一下踩的坑。其实就是最短路树的应用,我的想法是先删掉不在树上的边,然后对于树上的边先删除连叶子的边,以此类推。这样写倒是没有错也可以过。

但是!这个题题面里说的是最多k个,所以其实根本不用考虑去掉非树边什么的,假如k>n-1的话只输出n-1条树边也是对的!这就省了好多代码了。其次,根本不用使用拓扑排序那样的处理过程(就是先去掉叶子这种),因为想一下dijkstra的过程就可以发现,每次从优先队列中取出来一个节点后,这个节点的前驱最短路其实已经确定了,只要在这时候把其前驱记录下来,根据dijkstra的每一步往外扩展一步的操作,按照这个顺序搞下去最后的记录表中的顺序其实就是拓扑序。。。。依次输出即可。 继续阅读“[CF][图论][最短路树] codeforces 1076D Edge Deletion”

[坑][计算几何][极角排序][利用已有信息] UVALive 4064 Magnetic Train Tracks

https://cn.vjudge.net/problem/UVALive-4064

简单的极角排序应用,枚举每个点作为角点,然后按照角度顺时针枚举另一个点,在这个过程中递推记录下对于枚举的点有多少个钝角/直角出现。由于一个钝角/直角唯一的对应一个钝角/直角三角形,因此最后只需要把C(n,3)-钝角数量作为答案即可。

坑点:lrj的书上和各位dalao的blog都说的是锐角直角,呵呵,wa了两个多小时最后翻别人代码发现是只能锐角不能直角,服了,改了就过了,也不知道网上这么多人都写得锐角或者直角是怎么写出来只能锐角的代码的。

继续阅读“[坑][计算几何][极角排序][利用已有信息] UVALive 4064 Magnetic Train Tracks”