Southern Subregional Programming Contest 2012 hints

做了一下SGU最近的那场比赛,就发个hints骗访问。。。。看了还是不会做也别问我(都说了是骗访问了XD)。。。

  • A:最后x位时要借位的一定是最后x位最小的那些,状态有限就可以dp了。
  • B:傻逼题
  • C:   我们将所有人排序,那么可以dp算出赢了k场的方案数(是赢了k场不是只赢了k场),然后可以用这个反过来推出只赢了k场的方案数。
  • D:我感觉就是一个模拟,需要考虑很多恶心情况。。。暂时没过。。。
  • E: 傻逼题
  • F: 由于王和后之间不能有相领点,所以必然存在一个点删掉之后王和后在不同的连通分量里,然后解决子问题就行了。
  • G:傻逼题
  • H:傻逼题
  • I:使用splay维护子树的dfs序并维护些信息就行了。
  • J:傻逼题
  • K:傻逼题
  • L:傻逼题

 

[坑]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,用矩阵乘法加速即可。