Memphis's Blog

快上一版了有点激动呢>.<，所以就拼命刷水了

估摸着就我那noip翔分数今年要进队没啥可能了

不得不Orz Stilwell未来进队爷

upd 2014.5.14

2111: [ZJOI2010]Perm 排列计数：一看就知道是一个堆，根据堆推推很快就出来了，不过BZOJ当初没过T_T。昨天追踪Stilwell的做题记录发现又把这题交了一遍，原来是搞组合数的时候会模跪，这样预处理一下就行了，恩就这样

3577: 玩手机：裸裸的网络流模型不能多说，S向每个发射塔连wi，每个发射塔向范围内的每个点连inf，每个点拆点向另外一个点连点权，另一个点向在范围内的接受塔连inf，接受塔向T连wi，但是还是不对。我们会发现如果向范围内的点连边会MLE+TLE，此时我们想起了VFK的a+b Problem，当初是用主席树优化连边，所以我们现在也可以考虑数据结构，可以代表一个矩阵的有什么数据结构呢？标算是二维st表。。。我一开始表示不想写，写了个分块乱搞，发现还是有3000000条边T_T，不得不写st表，给saffah大神跪烂，貌似还是有妹子的大神>.<，烧死

3469: ADERA：追踪jcvb大神的做题记录发现都好难T_T，终于发现一题水题，话不多说直接做掉吧，开个Trie每个点放个链表记录经过的字符串的权值，做完排个序，然后每次询问直接输出就没了

1552: [Cerc2007]robotic sort/3506: [Cqoi2014]排序机械臂：同样是追踪jcvb大神的做题记录发现了水题，裸裸的splay直接做掉，居然还是双倍经验，好开心

1815: [Shoi2006]color 有色图：Burnside一直不太熟，就来刷一下，wwt大神自己手推论文题真是吓尿了。首先我们假设是爆搜n!种点置换方案，怎么计算边的置换呢？假设一个置换圈长为A，另一个为B，我们知道对于在这两个不同置换圈中的两点间的边一共有A*B条，但是有重复两个点在各自的置换圈上走lcm(A,B)次就会循环，所以这种情况下边的置换有A*B/lcm(A,B)=gcd(A,B)个;设一个圈长为L，对于在一个置换圈的两个点之间的边，走L div 2次就会有重复，所以这种情况下边的置换有L div 2个;现在爆搜会T，考虑优化，我们可以用最小表示法搜索，从大到小搜索点置换圈长，然后考虑有多少点置换的每个点置换圈长等于这个当前搜出来的结果，首先每个圈本质不同的排列有(L-1)!种，然后对于两个长度相等的圈可以互换，设长度为i的圈有K_i个，那么需要除以K₁!*K₂!..K_N!，所以点置换的每个点置换圈长等于这个当前搜出来的结果的个数为：((L₁-1)!*(L₂-1)!...(L_N-1)!)/(K₁!*K₂!..K_N!)种。 最后还被卡了一下常数，什么快速幂之类的预处理就好了。

1488: [HNOI2009]图的同构：和上面那题几乎一样，就是边变为0和1两种颜色了

3578:  GTY的人类基因组计划2：一开始被题意虐爆了T_T，原来是相同房间算一个集合，有过的集合不能再计算，那么hash一下好了。。怎么hash都可以，然后线段树每次Query就下去Delete一下是有复杂度保证的，怎么搞都可以，我写了双关键字，貌似有点傻，他们直接XOR。。

2711: [Violet 2]After 17：好题！首先点积的x,y可以分开来，这个毫无疑问。那么现在我们的问题就是sigma(a_ia_j)[i<j]=(sigma(a_i)²-sigma(a_i²))/2；由于我们为了尽量小，我们必定选择框定范围内的最值，所以sigma(a_i²)是定值，那么我们现在就是最小化sigma(|a_i|)，直接背包。

upd 2014.5.15

3563: DZY Loves Chinese：真强制在线！23333，我会告诉你我认识出题人么

3585: mex：又见双倍经验！线段树离线搞一下就没有了

3589: 动态树：树链剖分，由于树枝只是有一段点到根的路径，所以K²log₂N找LCA减掉一些就可以了，剩下的都是裸裸的树剖

3569: DZY Loves Chinese II：连通图加强版2333，首先我们随便跑出一个生成树，然后对于非树边设定一个随机unsigned long long的权值，把一条树边的权值定义为跨越它的非树边的XOR和，这个可以On处理，这样对于一个边集，若有一个子集XOR和为0则连通图断开，如何确定呢？连通图可以用枚举子集的方法处理，这边K很大所以不可以枚举子集，高斯消元解异或方程组是个方法，其实匡正非WC讲的那个On算法更好，这题K比较小，两种方法应该都可以过

upd 2014.5.16

1797: [Ahoi2009]Mincut 最小割：这题是看了jcvb大神的blog以后去刷的，好题，>.<反正我想不到就对了，SCC的解法太好了

upd 2014.5.17

3580: 冒泡排序：智商题TAT，BZOJ最后一页多出来好多智商题。首先我们可以知道冒泡排序的总交换次数即逆序对个数，因为一次交换减少一对逆序对，这样就可判无解了。然后我就不会做了T_T，去膜拜花神代码，发现貌似是找规律，是这样的：我们先定义一对逆序对为 a_i>a_j(j>i) ，再定义一个b_j为以a_j为逆序对中较小的元素的个数，即 bj=sum(a_i>a_j)(j>i)，¹冒泡排序第二层循环每次一定会把当前非有序的一个最大值扔到最终的位置，²并且第二层循环每次会把所有非零的b_j减一，即每次第二层循环所有b_j非零的数必向前一位，相对的，所有b_j为零的后移一位，根据第二个性质（已标号），我们可以知道K次操作经过了几次（设为R次）完整的第二层循环，以及经过了R次第二层循环以后的b数组，现在我们要快速处理R次第二层循环以后的a数组，根据第一个性质，我们可以知道R次第二层循环之后a₁～a_R已经有序，a_R+1～a_N中的b_j为零的值业已有序，a_R+1～a_N中的b_j为非零的值依然相对处于原序，这样再仔细想想就可以做了，可以把a₁～a_R放到队尾处理，把b_j为零的a_j排序，按位置从小到大插入，然后把a₁～a_R放回队头，然后我们就完成了R次第二层循环的操作，剩下多出的操作暴力跑一遍，依次输出即可

3579: 破冰派对：一开始看到感觉好神，不会做，表示只会暴力。后来问了一下Stilwell，他说就是暴力+bitset。。好叭我表示确实被取模吓到了。Stilwell，准确说是Stilwell参(kan)考(dong)花神的做法是这样的：定义相互直接联通的的一块为A集合，相互不连通的为B集合，即工作人员为A集合，参加人员为B集合，由此我们可以构出一个很像2-set的连边，即把所有点拆成两个点X_A和X_B，X_A表示改点放入A集合，X_B表示改点放入B集合，若存在边(X,Y)(此处及以下X!=Y)那么如果把X选入B集合，那么Y必然选入A集合，否则若Y选入B集合，那么X和Y就联通了，因此我们在图中连边(X_B,Y_A)，相同的，连边(Y_B,X_A)，若不存在边(X,Y)，如果把X选入A集合，B必然选入B集合，因此连边(X_A,Y_B),(Y_A,X_B)。然后我们利用bitset做一次floyd，复杂度即为O(N³/w)(w为bitset压位位数)，然后要求方案数，怎么办呢。。大力出奇迹233。直接搜就过了

upd 2014.5.18

发烧了T_T，还跑去BZOJ最后一版想刷智商题结果发现被智商题刷了

3595: [Scoi2014]方伯伯的Oj：弱到又只能刷傻逼数据结构题了，又见BST，不用两只BST，还有一只用map就可以了，不知道为什么RE，对拍没有RE= =，傻逼数据结构题都RE，发烧果然会变傻 ---upd 2014.5.19---今天看了一下数据，艹BZOJ上没标数据范围，N居然有10⁸，这尼玛还要拆区间，SD题，鉴定完毕

1216: [HNOI2003]操作系统：一整天一题都没A实在不好意思，所以就找了题水题A掉了T_T，不说了说多了都是泪，怎么就发烧了呢

upd 2014.5.20

T_T怎么还没到一版

3595: [Scoi2014]方伯伯的Oj：这个今天A掉了，其实不用平衡树= =，线段树动态开点+map标号就可以了，智商低是硬伤T_T

2434: [Noi2011]阿狸的打字机：很开心，1A了，这题和我本来自己想出的一题有点像，总之就是AC自动机搞搞+dfs序搞搞啦，我们知道fail指针是从一个字符串的前缀P_i跳到另一个字符串前缀P_j，其中必须满足P_j是P_i的最长后缀，然后对于一个把fail指针倒序的fail tree，其中的一个节点x和它的子树所代表的是以P_x这个前缀作为公共后缀一坨前缀P；那么对于此题，若S_x这个字符串要在S_y中出现，那么S_y的某一个前缀P_k必定处于S_x末端节点为根的子树内，因为一个字符串的所有前缀的所有后缀为这个字符串的所有子串，上方标红的关键字满足了这个要求。那么考虑如何统计答案，既然是子树信息当然想到dfs序了，把dfs序拎出来放到bit里，对于每个询问(x,y)的y，挂一个链表在y处指向x，dfs遍历原来AC自动机上的的Trie，dfs到一个节点先把它在dfs序中的贡献计算，然后遍历询问链表在指向的x处的dfs序中用bit统计答案，然后继续dfs，回溯的时候把该节点在dfs序中的贡献删除。

upd 2014.5.21

2721: [Violet 5]樱花：参考strongioer的推导

[tex]\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}[/tex]

[tex]xn!+yn!=xy[/tex]

[tex]\frac{yn!}{y+n!}=x[/tex]

令[tex]k=y-n![/tex]

[tex]x=\frac{n!(k+n!)}{k}[/tex]

[tex]x=n!+\frac{n!^2}{k}[/tex]

[tex]k|n!^2[/tex]

故答案就是n!²约数的个数，这个就很简单了，只要把1~N所有数的不同质因子个数+1以后累成即可；首先因为数据范围只有10⁶，所以可以直接O(NlnN)裸筛质因子，也可以欧拉筛出最小质因子之后倒序DP，后者是O(N)

2124: 等差子序列/3509: [CodeChef] COUNTARI：本来一看2124，这尼玛不是3509的弱化版么。。交了四遍3509全T。。果然我的FFT太慢了OTL。顺便两题都讲了吧 2124：仔细思考以后我们发现对于a_i，我们需要找到的合法解为a_i-k在a_i前而a_i+k在a_i后或a_i-k在a_i后而a_i+k在a_i前，那么我们for i=1~N扫过去用BIT或Segtree维护两个hash，b_j表示处于1~i权值为1~j是否存在的二进制值的hash值，c_j表示处于i+1~N权值为1~j是否存在的二进制值的hash值，那么对于a_i，设d=min(i-1,N-i)，则若b_i-d~i-1和c_i+1~i+d不同或c_i-d~i-1和b_i+1~i+d不同则表示有一对​a_i-k和a_i+k处于一前一后，则输出Y，否则N。 3509：此题要求等差数列个数，那么上面那种方法就不可行了，我们考虑两种暴力，第一种，对于一个点i，for 1~i-1求出每个权值出现次数，然后for i+1~N将等差数列一一匹配。第二种暴力则相对高端了，我们推导一下式子：

[tex]i<j<k[/tex]

[tex]A_j-A_i=A_k-A_j[/tex]

[tex]2A_j=A_i+A_k[/tex]

[tex]A_i+A_k[/tex]直观上可以表示成卷积的形式，对于一个点i，把1~i-1权值作为下标累加起来为多项式P₁，i+1~N为多项式P₂，FFT一下此时2A_j的值就是此时对于A_j为等差中项时A_j的贡献。 此时我们观察这两种暴力，显然FFT很SB，有点浪费，我们发现FFT一次可以做出很多贡献但我们只统计了A_j的贡献，那么考虑分块，对每一块块内用暴力1，块外FFT，每次可以对一块内的A_j作出贡献，设块大S，此时复杂度为O(NS+(N/S)*Nlog₂(N)),此时S取sqrt(Nlog₂N)复杂度最优，大概是1300，由于FFT的常数问题，所以FFT做少一点比较好，所以实际上S取2000左右最快

upd 2014.5.22

3550: [ONTAK2010]Vacation：志愿者招募弱化版>.<，一开始边开小了真是逗比

upd 2014.5.23

2251: [2010Beijing Wc]外星联络：SA裸题就不说了，省选前练手用的

一堆USACO傻题就不说了，大家知道我是为了上一版就可以了= =。。