PA 2008 - HZH's Blog - 自闭症

PA 2008

nbdhhzh posted @ 2015年5月11日 00:45 in 屯题 with tags PA , 392 阅读

再次坑。。还有点多。。好吧。。怪我咯?

A Cat on a Keyboard (Round 0) (10/10)
Logarithmic Paprika [B] (Round 1) (10/10)
Bug [A] (Round 2) (10/10)
Paper Clips [B] (Round 2) (0/10)
Diagonals [B] (Round 3) (10/10)
Studies [A] (Round 3) (10/10)
Mosaicism [B] (Round 4) (10/10)
Turns [A] (Round 4) (10/10)
Cliquers [A] (Round 5) (10/10)
Journey [B] (Round 5) (10/10)
Questions [A] (Round 5) (0/10)
Chessboard [B] (Round 5) (10/10)
Cliquers Strike Back [A] (Round 6) (10/10)
Safe [B] (Round 6) (10/10)
Dragon Milkdrinker [A] (Round 6) (0/10)
Potato [B] (Round 6) (10/10)
Near 2 (Final round - practice session) (10/10)
Near (Final round - practice session) (10/10)
Balloons (Final round) (10/10)
Idempotent Functions (Final round) (10/10)
Reconstruction of Byteland (Final round) (10/10)
Return of the Cliquers (Final round) (10/10)
Electricity (Final round) (10/10)
Computation of a Road Network Plan (Final round) (10/10)
Enumeration of Road Network Plans (Final round) (0/10)

T1 模拟,注意回车符是没有的,直接gets就好了。简要题解

T2 f[i]表示sigma 2^j*a[j] j<=i。第一个满足f[i]+1<2^(i+1)的f[i]+1便是答案。

T3 拆点跑最短路。还要写堆优化,不幸福QAQ

T5 题意等价于判两个区间是否有交并且不互相包含。挂个链表,搞个计数排序,然后就扫一遍,用栈处理一下。。On还卡常,不高兴。。卡时大法好。。

T6 他一定有一些环不用经过重复的点就是正的,否则就不可能。然后这些环可以用Floyd跑出来。然后如果一个点可以到这种环,并且这种环可以回来,那么他一定也是可以正的。因为环上可以无限跑,跑到正无穷再回来。然后连通性也可以用类似Floyd的思想。

T7 啊好大,感觉扭了一个下午的脖子。。主要没有认真想。。扫每种颜色然后离线算答案就好了。。

T8 后缀数组模板题吧。。没想到怎么用SAM做。。真难过。。(好久没打SA模板了都不会写了TAT)

T9 好神啊,这种数学题像我这种数学滚粗狗肯定不会做。。参见http://zh.wikipedia.org/wiki/%E4%BA%94%E9%82%8A%E5%BD%A2%E6%95%B8%E5%AE%9A%E7%90%86

T10 容斥+矩阵乘法。时间复杂度2^k*n^3*logd,非常和谐QAQ

T12 离散化后用STL乱搞。。用set记录每条↗↘↑→的方向的点,然后把边界也放进去,就没有啦~

T13 神题。首先orz小搞堂。先把1e9-402分解质因数。

有递推式f[i]=sigma f[j]*C(j,n)。证明这里不说了。先预处理出前p项

然后又有一个性质f[i+p^k]=k*f[i]+f[i+1]。然后考虑母函数x^(i+p^k)=k*x^i+k*x^(i+1),也就是x^(p^k)=k*x^i+k*x^(i+1)。

这时,我们可以把n表示成p进制,第i位是a[i]。

然后问题转化为求Π(x+k)^a[k]模(x^p-x-1)。

然后就只要把每个(x+k)^a[k]暴力展开,然后再每次分治乘法一下,再利用性质取模。

最后求个sigma再CRT一下就好辣!我这种傻逼怎么可能想得到。。

T14 先用next数组跑一下循环节,然后把每个数都mod一下这个循环节长度。然后就求一下前缀和扫一下就好辣~

T16 先把他展开,把点复制一份,然后预处理每个区间会割多少的面积,然后就变成n^3*k的DP。由于常数小跑的很快。

T17 排序+树状数组乱搞。。时限16s我就不知道他在干些什么。。

T18 STL模板题。。

T19 最喜欢这种傻逼数据结构题辣!贪心显然成立。每次取最大的k个,这个可以用平衡树维护,也可以用线段树维护。

T20 题意简化:给g中的每个点分配一个f中的值,使g成为一颗菊花树。可知,如果f中有一个值i,那么有g[i]=i。所以,就要给剩下的所有在f中没有出现过的点分配权值。这是一个经典的组合问题。同时,因为同一个权值还可以内部分配,所以还要乘排列。

T21 把点等分成5份,然后两两组队。最后每个数再乘一个两两不同的质数保证两两不同的性质。这样的话如果读入7就会有两组2,和一起就爆炸了,所以特判一下就好辣。。

T22 先把p-1分解,然后对于每个质数枚举m的因数,然后卢卡斯一下,最后CRT一下就好辣!

T23 傻逼题。。做了那么多难题终于有道傻逼题我被感动了。。直接树状数组维护前缀和。。然后没了。。

T24 超级无敌傻逼题。。1~m+1构成一条链,其他全部接2上。。没了。。

剩下4题。一题0人A神题,一题论文题,一题恶心题,一题题目太长题。。不想切了。。坑了吧。。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee