Codeforces Round #338 (Div. 2)

• contest link

　　CF#338，题目质量不错，难度A、D正常，B、C稍高，分数分配不科学，榜被带歪了。
　　正式参赛(zhy)，卡在B题，略慌，WA了若干次幡然醒悟；C题成最大遗憾，稳稳的一场又给跪了。Rank 172，rating +32，离紫名还差一点。请允许我做一个悲伤的表情 :( 。

• 615A-Bulbs

  题意：
  　　就是说给出一堆数，问1~N是不是都有。 　　
  解法：
  　　布尔数组水一水呗。　　 　　 　　 　　
  code

• 615B-Longtail Hedgehog

  题意：
  　　给出图G，没有重边，没有自环，你需要做的是挑选出一条链，称为“尾部”，这条链上的结点的数值是递增的，然后尾部的端点指的是值最大的那个节点，选某个尾部的得分是尾部长度*端点度数，问从图G中选出一个尾部，最大得分是多少。
  解法：
  　　题目略难读啊，毕竟我们不是以俄语为母语的英文读者...
  　　首先得分公式中“度数”是很好求的，输入的时候顺便就能处理出来，问题是对于每个点来说，如果它作为端点，它的最长尾部长度是多少。这样考虑的话问题就很简单了，由于尾部是递增的，所以暗含了一个拓扑序，也就是对于一条边的两点，序号小的点应当比序号大的点拓扑序靠前，序号大的点的尾部长度求解并不会影响序号小的点——无后效性。所以算法为拓扑序dp。
  　　说是拓扑序dp，拓扑序其实都不需要处理的——就是序号大小嘛。方程为dp[i] = max{dp[k]+1,1}，其中k与i有边相连，且k<i。 最终输出ans = max{dp[i]*degree[i]}，degree[i]表示节点的度数。 最后注意long long。
  　　最后吐槽一句，这题放在B难了吧... 　　
  code

• 615C-Running Track

  题意：
  　　给出一个“母串”，每次可以从这个串种截取一段连续的“子串”，每个母串仅可用一次，为了拼凑成“新串”，问最少需要多少母串，以及其截取方案。 　　
  解法：
  　　这题比D简单，比D简单，然而大家一窝蜂地去做D，这榜歪的，坑了不少人。
  　　直接说做法了——贪心+二分+KMP，复杂度是O(N^2*logN)的，N是max(两个串的长度)。
  　　先说贪心——由于要从头到尾拼凑新串，所以每次截取当然是尽可能越长越好呀，因为——设f[l..r]，表示拼凑新串[l..r]这段需要的母串数，f[l1..r]>=f[l2..r]，当l1<=l2是必然的，贪心得证。
  　　然后也就是说我们每一步的操作截取的子串要匹配新串的部分中，左端点是固定的，右端点由截取的串的长度决定，当然可以一点一点枚举长度。但因为如果长度为l的可以匹配，那么长度<=l的一定可以匹配，某种意义上的单调性，于是二分长度。
  　　最后就是喜闻乐见的套模板了，O(N)判断一个串是否是另一个串的子串——KMP。
  　　很遗憾的是博主WA on test6，最终发现是想当然地认为二分过程中最后一定会处理一遍二分得到的结果，参考下面代码。算是换个教训，以此为诫。

while(st < M){
	int l = st,r = M-1;
	while(l < r){
		int m = (l+r+1)/2;
		if (check(st,m)) l = m;
		else r = m-1;
	}
//**comment this and you'll get WA.
	check(st,l);
//**
	ans[anscnt][0] = ll+1;
	ans[anscnt][1] = rr+1;
	anscnt++;
	st = l+1;
}

　　
　　code

• 615D-Multipliers

  题意：
  　　给出一个数的分解质因数的所有质因子，问其所有因数的乘积。 　　
  解法：
  　　数论，需要对质因数和因数的关系有一定理解，然后就是快速幂+费马小定理。
  　　首先，有质因数要如何表示因数？可以dfs枚举每种质因子用几个，每种组合即是一个独特的因数。比如12 = 2 * 2 * 3，也就是说有2个2，和1个3，那么就有6种组合，(0,0),(0,1),(1,0),(1,1),(2,0),(2,1)，对应1,3,2,6,4,12。
  　　当然，如果求出所有的因数是不可能的，组合数会阶乘级增长。但注意到最终求得是乘积，这时我们考虑每种质因数在所有的因数中出现了多少次，还拿12 = 2 * 2 * 3举例，2出现了几次？因为除去2的话，剩下的质因数只有2种组合——0个3，1个3，那就是说2^1出现了2次，2^2出现了2次。验证一波——2 = 2, 6 = 2 * 3, 4 = 2^2, 12 = 2^2 * 3。
  　　所以设质因数p[i]有c[i]个，那么关于求质因数p[i]出现了多少次，符合下面公式:
  　　π((p[i]^k)^π(c[j]))，其中j！=i，0<=k<=c[i]
  　　其中的π表示连乘，幂的部分通通用快速幂来做。
  　　还剩两个问题，一是求π(c[j])会超时吗？显然这里是O(n^2)，其中n表示质因数种类数；打个200000以内的素数表你会发现，素数个数不超过20000个，CF的评测机这么快，还是不会超时的。然后就是模的问题，乘法取模很简单，π(c[j])很大，又在幂指数的位置，怎么取模呢？根据费马小定理，有推论——如果MOD是一个大素数，那么
  　　(a^b) % MOD = ((a % MOD)^(b % (MOD-1))) % MOD
  　　从system test的结果来看，很多人是小看这道题了，榜整体被带歪...　 　　
  code

• 615E-Hexagons

  题意： 还没看题，待续... 　　
  解法：
  　　 　　 　　 　　
  code

Copyright © 2015-2016 zhyack. All Rights Reserved.