[坑]ACM用模板

大概是个坑。。。我正在填。。。
因为要去HZ赛区打ACM,所以准备一套模板,而且感觉最近太依赖Ctrl C+Ctrl V,很多都不会敲了 :cry:

目前要填的坑有好几个方面,我也打算自己实现并测试一下来复习各个算法。。。

  • 数据结构:splay/treap/LCT/树链剖分/点分治
  • 字符串:suffix array/suffix automaton/最长回文
  • 计算几何:圆交/圆点求切线/圆圆求切线/半平面交/V图/三角剖分/完全动态凸包/3D几何一些初步计算/球面几何/3D凸包/3D半空间交
  • 数值计算:FFT
  • 数论:离散对数
  • 搜索:DLX
  • 图论:sap/dinic/scc/最小费用流/最小树形图/2sat

想到其它的会补充。。。模板就在这里更新。。。。可能会在缩进上做一些调整适合打印用。

Codeforces 出题感想

总之总算把活干完了。。。花了很多个晚上搞题目和很多个晚上出数据修改我那烂的要死的英文。。。略累。。。估计很长一段时间内是不会再干这种事情了。。。

国内可能还没有人在CF上出过比赛?就简单的介绍下吧。

首先他们出题用的是一个很专业的出题网站:polygon system。。

有一些比较不错的功能就列一下把:

  1. 一个题目可以有几个writer,reader,writer可以改题目,reader只能看看,每个人会有一个working copy,你改了一些之后commit change大家都可以看到,有什么问题和建议也可以在issue里提,系统会帮你自动发邮件给别人。
  2. 硬性要求要有一个validator用于检查输入的正确性,然后validator要写的很严格,还有一个checker,检查输出的正确性,checker基本写的非常非常松,也就是说所有题目都是spj。
  3. 可以很方便的帮你把所有资料packaged。。同时是用脚本生成data的。。。也很方便。。。遇到想cha的错误算法可以跑stress然后把出错数据+进去。

主要还是第一项感觉比较赞。。。

然后熟悉了网站之后我开始出题目,我把我自己想出来的几道挺有意思的题目放上去了,C的话是很早一个SAM的idea,D是我之前暑假的时候跟超哥去逛漫展的时候想到的idea,E是我有一次打osu打到一半灵机一动凑出来的。B呢是以前跟7k+玩的时候想到的比较有意思的idea。

总体来说题目难度确实略大了,C的话SAM可能大家都不熟悉(很奇怪的是tourist在CC上弄过SAM啊,他应该会啊。。。),SA做的话又不是那么好写。。D和E都挺难的。。。现在想想D和E是不是应该交换一下。。

然后我特意把A的pretest放的很弱。。。想让challenge刺激一点。。。结果似乎弱过头了?不过还行吧。。。

比赛过程么就是Petr和tourist一间房。。。大家快速过AB之后tourist率先开始cha。。。。。

cha了很多之后,Petr交了E。。。我看了一下觉得是对的。。。他接下来又过了D。。也是对的。。。我觉得可以预祝他#1了。。。结果他的E里面在hash的时候没用long long。。。给冲突了。。。。pretest里的大数据居然都过掉了。。。可是还是fst了。。。

又有几个人过了E。。。rng58交了一发E WA了。。。我看了一下觉得他的做法跟我的完全不一样。。。感觉是歪路。。。结果他给过了。。。后来发现他的神结论真是无法直视。。。。给他跪烂了。。。

后来有人交了个C。。。是n^1.5的奇葩做法。。。居然尼玛过了大数据。。。。

我没办法只好构造了个卡他的把他卡掉了。。。

由于A的final test都有点弱。。。我不得不在比赛中途加强A的final test。

最后还有几秒的时候Egor交了E。。。我看了一下觉得会T。。。他的做法非常奇葩。。。结果他2976ms卡过了。。。我觉得我只放了一个2000 2000 2000太仁慈了。。。多放几个1999 1999 2000这种他说不定就萎了。。。

最后结果是rng58强势#1暴涨了80rating到#3了。。。跟台湾帅哥交换了一下位置。。。。我还是#4囧-窘迫。。。Petr怎么这么不给力啊T_T。。。tourist不知道什么原因0.5h之后就啥都没干了。。。

总结一下一些经验吧:

  • 以后DE可以很难,C还是中等难度吧。。。
  • test里最好是很多小数据几组大数据,这样小数据验证正确性大数据验证速度。当然D和E里面放满大数据也行。。。反正交的少。。。但是AB里放的太多就卡死了。。。
  • 似乎有很那啥的硬性要求Div2的CDE一定要是DIv1的ABC。。。结果Div2的E就没人能过了。。。以后注意一下吧。。。

我一开始还以为是义务劳动。。。不过还真的是有钱的。。。给了笔小钱。。。正好去换个耳机打osu。。。。

 

SRM 557解题报告

250:算出U和D分别有几个,然后显然应该先全U然后再histroy然后再全D。。判断一下即可。

550:求floyd传递闭包,如果f[i][i]=true那么显然选i没意义,无视掉这些点之后就是个DAG。那么就是求DAG最长反链,也就是n-最小链覆盖。

1000:我比赛的时候解方程写错了。。我是傻逼么?

注意到。。。我们实际上是要找n个互相独立的向量v1,v2,…,vn (mod 2下的向量)

他们跟输入向量A的"点积"(乘了之后xor起来)的和最大。

由于这是个拟阵,每次找一个跟之前选的向量独立的且跟A点积最大的向量就行了。

我们对A先高位到低位消一次元然后从大到小排序,

那么从i=0开始每次如果选ai更优就选,不然就不选,用解方程判断能不能选即可。

具体看我在Arena里面的代码。

这个空间最后一篇日志啦LOL。。。请岛娘帮忙开新空间xD

TCO Onsite rounds 2012 solutions

LOL。。。开个坑。。。

本来说要换新空间的但是在太懒了就拖一会儿吧。。。

目前已经在Arena里做完了Semi1 Semi 2 和Wildcard。。。

代码见Arena room

慢慢填吧。。。 

Semi 1:

250:我们不妨计算白色格子的数量,注意到一个联通块显然是一个矩形,如果我们确定了S[i]=T[j]=U[k]的这个字符x,那么比如说S中a1..a2是全是x,T中b1,..b2全是x,U中c1…c2全是x,那么显然这就是一个白色的长方体,同时只要a1..a2,b1..b2,c1..c2中有一个贴着边缘,那么就全最后生下来的白色格子。

分析到这里,只要枚举是S,T,U中的哪个贴边了,然后计算答案即可。

500:注意到说白了我们得到的信息pi是说i的前面是哪一个。

那么图论化一下就是说要建立一个最小字典序的pi序列使得i->pi这个图形成一个环。

显然只需要满足2点,这个问题就是有解的:

1:图中没有长度小于N的环。

2:图中没有出度和入度大于1的点。

我们只需要用个并查集维护连通性,然后注意不要违反了这两个条件一位位给pi填上去就行了。

1000:看起来很难。。。

题目的意思实际上是要求所有连续k个都在xor下线性相关。

我们不妨倒过来求"存在连续k个在xor下线性不相关"的序列的数量。 

我们注意到到实际上只需要记最后有几个数是线性不相关的就行了。

比如最后有k个数线性不相关么,那么有m-(1^k)+1种可能性新的数跟他们线性不相关

k->k+1

否则跟他们线性相关的话,实际上就是从这k个中选几个xor起来,不妨说选的最后一个是倒数第i个,

那么之后就只有i个线性不相关的数了,有2^(i-1)种可能性。

那么状态是k,用矩阵乘法加速即可。

 

IOI 2012 。。。酱油的解题报告。。。

我今天下午看了一下题目。。。。大致上感觉都是可以做的。。。随便写的解题报告。。。有错误请轻喷T_T。。。

Day1:

problem 1:40分还是比较好拿的。。。但是接下来2个task略恶心。。。我有几个思路不知道能拿几分。。。。。。

problem 2:我觉得这题挺简单的吧。。。让我们考虑什么情况下一个图全是链条。。。

条件1:所有点度数<=2(废话)

条件2: 没有环。

那么大致分几种情况讨论和维护一下就行了。。。

problem 3:rope秒杀。。。不用rope的话也可以用类似树的结构。。总之是sb题。。。

Day2:

problem 1:

我们不妨考虑一个简单的情况,如何解决凸多边形的问题?

由于凸多边形比较优美,两点间距离就是曼哈顿。。所以直接算即可。

那么如何解决复杂的情况呢。

不妨以格子为点,相邻点间连边。

给每个格子加权,a和b之间的距离要乘上a和b的权。。
首先处理一个情况,就是桥,显然桥被经过的次数是确定的,同时从其它方向来的点,直接当成权加在桥的两端上就行了。。。

那么现在没有桥了。。。

一开始权都是1。。。

那么如果有度数是1的格子,显然他必须要往它的唯一相邻格走一步,那么就把它的权加到它的相邻格上去然后删掉他,同时这可以看成他走了一步,故答案要加上他的权乘上所有格子的权和。

如果没有度数是1的格子,那么我们考虑最左边的一行,最靠下的点,毫无疑问他的上方和右方必须有点

同时他的右上方也必须有点(不然就有桥了)。

依次类推,可以证明这个点一直往上到不能往上的这一列的右边都有点。

那么显然这一列除了到自己内部之外,都要先往右走一步。

那么在答案中加上这一列内部的情况,然后把他们加到右边那一列上去。。。

同时可以证明之后如果产生了桥,只可能是因为出现了1度点,处理掉即可。。。

看起来很复杂的样子。。。不过复杂度是线性的。。。

UPD:这做法太傻逼了。。

from wqs:注意到把所有横向的最长连续块压成一个点,那么必然形成一棵树,然后树形dp就行了。

我的搞法搞了那么多实际上只是想办法找到树的一个叶子然后往上推。。。本质上是差不多的。。。但是太麻烦了。。。

不过这么搞也行,其实不用求桥,我们可以维护所有边界上的连续块来找。。。。上下左右四个边界上总能找到树的叶子。。。

problem 2:

注意到我们一个点只能保存2个bit。。。

其实2个bit就够了。。。

我们不妨balabala求一个最优解。

然后一个颜料根据是从脚手架上拿的与否跟放不放到脚手架上,有四种状态(注意到,就算一个颜料是从脚手架上拿的,也要记他放不放到脚手架上,不放到的话意思就是会在将来被扔掉)。

那么对于从脚手架上拿的,我们得到了一个rest,如果不放到脚手架上的话,我们维护一个垃圾堆,放到垃圾堆里去。

对于从新的地方拿的,如果不放到脚手架上->直接扔掉。

放到脚手架上->我们随便扔掉一个之前垃圾堆里的颜色。

我傻叉了...不用记是不是从脚手架拿的,直接按脚手架里有没有判断就行了.然后要记一下一开始的k个是不是要直接扔掉.

那么只要N+K bit就能搞定了。。。。

另外这个的原理是什么呢。。。只要注意到这个本质上是一个从网络流的流量中构造解决方案的过程。。。你就明白了。。。

我们可以对这个问题网络流建模,那么可以发现只要2N的信息就能记录这个网络流的流量从而构造出解决方案。

UPD:

根据wqs说的是不用记是不是从脚手架上拿的的,只要记扔不扔掉就可以了,不过这就同时要记一下一开始在脚手架里的那k个扔不扔掉。。。要N+k位。。更优一些。。。

problem 3:

我才发现原来的搞法完全是扯淡。。。

对这个比赛按位置建一个博弈树。

同时将R标称0,比他强的标成1,弱的标成-1。

那么我们注意到,实际上我们要做的是将0跟它右边位置的叶子交换位置,和从0往上数胜利者有几个0。。。

这个是很好搞的。。。

比如说找一个跟当前0 Lca最低的1。。。

这个找0前后最近的两个1试一下就行了。

总体而言day2比day1难。。但是day1有坑爹构造题。。。。momo tourist。。。。 

金华赛区网络赛解题报告。。

这次还是我跟AC跟JZP。。。连续两次#1了!!!!

1001:

如果我们有个一个数据结构,能过支持两个操作:

1。返回某给定矩形中的点

2。删除某个点。

那么对于每个操作,我们只要维护一个队列。

每次找出队列中的第一个点,然后把它能影响的点全部删除并且加入队列。

类似bfs的搞就可以了。

这个数据结构我直接使用了线段树套线段树(先离散化),勉强卡过了。

1002:

让我们只考虑上午的情况(下午一样)。

对每个柱子i分别考虑,容易发现在特定角度区间遮挡它的是特定柱子。

这个可以通过一次扫描实现,方法类似于凸包,画个图脑补一下就行了。

然后对于特定的区间,可以发现遮挡的长度是a+b*cot(t)的三角函数,

根据它跟0和H[i]的大小关系分一下段然后分别积分算答案。

(a+b*cot(t))*sin(t) = a*sin(t)+b*cos(t)。。。这个积分是比较好算的。。。

由于细节很多我跟JZP写了很久都没调出来。。。

1003:

就一坑爹题吧。。。直接爆搜,考虑一个度数剪枝。

令每个未经过点的度数为与他相邻的未经过点数。

显然除了最后一个终点,得至少有2度才能组成路径。

也就是说不能有0度点,1度点最多一个。

这样剪一下就能过了。

1004:

纱布题,不用讲吧。。。

1005:

说白了就是求一个圆跟一个多边形的并。

我们把多边形三角剖分,就能转化成圆跟很多个三角形的并(根据方向是有正负之分的)。

为了方便我们可以以圆心为坐标原点。

这样三角形的一个点就必然是圆心,求圆跟三角形的并就方便多了。

1006:

挺简单的dp呢。。令dp[i]表示从i点到终点的期望时间。。。然后dp[i]的话如果有flight就做flight做到不能做,否则就投个骰子。

1007:

比较简单的费用流问题。。。

对day和科目分别建点。。

然后从天向科目连边。。。

注意到虽然有的边费用是一个二次函数,但是由于这个函数的f[1],f[2],f[3]中,f[1]-f[0],f[2]-f[1],f[3]-f[1]是单调的。。。所以我们可以把它拆成多条边使用费用流算法。

1008:

我们可以发现一开始是1..n。这个条件很重要,因为s[i]!=i的i最多只有会O(m)个。

那样的话我们可以使用容斥原理计算出l..r这几个数跟p互质的数的和。

然后处理一下那些s[i]!=i的位置。

很多同学问如何算l..r这几个数中跟p互质的数的和.

首先不妨令p的质因子是p1,p2,p3..,pn..

同时令rec(r,i)表示1到r中跟pi,…,pn互质的数的和.

那么我们可以发现rec(r,i)=rec(r,i+1)-rec(r/pi,i+1)*pi

因为1到r中跟pi,…,pn互质的数的和=

1到r中跟pi+1,..,pn互质的数的和

-1到r中跟pi+1,…,pn互质的数,同时是pi的倍数的的数的和.

那么rec(r,0)-rec(l-1,0)就是答案了.

1009:

可以说是老原老原的题了吧。。。。

就不说了。。。

SPOJ MSTS

其它题目我不清楚。。。等下再补。。。

[我们都爱GYZ杯]NOIP模拟赛

时间过的真快啊>_<…离上次办这样的比赛也有2年了吧…

转眼间就这样了呢…

不管怎么说又来办比赛了,希望大家做的开心吧>_<…

题目效仿东方一共有4道:Easy,Normal,Hard,Lunatic.

Lunatic的话>.<,才不是专门为你们这群神犇出的呢!>_<

网址: http://new.tyvj.cn/Test_Show.aspx?id=1092 

总共3个小时.

比赛之后就会发布题解什么的.

Compacted-Trie

让我们考虑一棵Trie。

注意到实际上有用的结点只有O(n)个。

那么我们像后缀树一样的压缩方法。可以得到空间O(n)的Trie。

插入删除修改的复杂度变成了O(min(n,W)),W表示位数

有啥用呢?首先是降低时间复杂度的常数,因为可以使用位运算一次往下前进很多步。

其次是狂降空间。 

比方说:

http://www.lydsy.com/JudgeOnline/problem.php?id=1146

这题

如果使用主席树的话空间复杂度是O(nlog^2n)了。

但是如果改用树状数组套compacted-Trie。空间复杂度就变成了O(nlogn)。

当然时间复杂度不变。

 

其实基本没啥用,不过在Int上速度完艹各种平衡树。。。空间也不会挂了。。

-->
Page 2 of 5612345...102030...Last »