Codeforces Round #358 (Div.2)

VictorWonder posted @ 2016年7月30日 18:57 in 总结 with tags 解题报告 动态规划 , 751 阅读
这套题目是从前天开始做的,本来打算是昨天搞定的,但由于昨天晚上出去吃饭(实际上是由于懒),所以最后还是拖到现在了。

Problem 2A
给出两组数1~n和1~m,从两组中各挑出一个数,问挑出的两数恰被5整除的方案数有多少。分别统计出两组中被5整除余数是x的数有多少(假设用f[x]和g[x]储存),然后答案就是$\sigma_(i+j==5) (f[i]*g[j])$要注意的是,余数为5是不存在的,所以还应当加上f[0]*g[0]。
 
Problem 2B
给出n个数(a[1]~a[n]),每个数可以变成1~a[i]之间的任何数,求出变完之后序列的mex的最大值。所谓mex就是从1开始,第一个不在该序列中的数。从1开始依次枚举,枚举到i时,将数组中剩下数中第一个大于等于i的数变成i,如果不存在大于等于i的数,那么i就是答案。
 
Problem 2C
这道题坑了我很久,我一直觉得这道题题目有问题,然而事实证明是我自己题目看错了,于是就坑了我一整天。
给出1棵以1为根的有点权和边权的树,规定一个点v是悲伤的当且仅当其子树中存在至少一个点u满足dist(v,u)>=a[u],其中dist(v,u)是点v和点u之间的边权和,a[u]是点u的点权,要求删去尽可能少的叶子结点(如果一个结点的子结点全都删去了,该结点也将成为叶子结点),使得最后树中不存在悲伤结点。然而,我开始的时候一直将判定条件中的a[u]看成了a[v],导致我根本无法看懂样例。由于我自认为没有看错题目,坑了一天也没有坑出来,直到最后看了题解才发现自己读题有误。
题目看懂了做法还是很简单的,dist(v,u)=dist(1,u)-dist(1,v),那么我们只要在深搜的过程中记录一下某个结点祖先中dist(1,v)的最大值,那么当搜索到这个结点的时候就可以直接判断dist(1,u)-dist(1,v)与a[u]之间的关系,如果dist(1,u)-dist(1,v)>a[u]那么以结点u为根的子树将全都删去,事先深搜一遍记录各个结点子树的大小就行了。
 
Problem 2D
看到这道题的时候,我还以为这题是抄Noip2015 Day2 T2的,后来翻了原题之后发现其实两题并不相同,但大体上都是差不多的。
这题给出两个字符串,要求从两个字符串中按顺序取出恰好k条公共子串,求k条子串长度和的最大值。
一道明显的DP题目,f[i][j][k][0]表示第一个字符串前i个字符和第二个字符串前j个字符中取出恰好k条子串且第一个字符串第i位和第二个字符串第j位不取的答案,同理,f[i][j][k][1]表示第i位和第j位都取的答案,然后转移一下就行了,转移方程就看我的代码吧。
PS:突然发现我的代码有一个严重的问题,然而尽管如此竟然还是AC了,我只能说这数据该有多水,这是有问题的代码,你们可以稍微感受一下。
 
Problem 2E
给出n个点,保证任意三个点组成的三角形的面积不超过S,要求你给出一个三角形,其面积不超过4S,且给出的n个点均在其内部。
这道题的做法有点巧妙,我是看了题解才明白怎么做的:一个三角形三边中点的连线也是一个三角形且面积恰好是大的三角形的1/4,那么我们现在从n个点构成的三角形中选择面积最大的那个,将其扩展成4倍大小的大三角形,那么就可以将其他所有点囊括在内了。
接下来证明得出的大三角形必定能够将所有点囊括在内,我们假设面积最大的三角形三个顶点为A、B、C,如果存在一个点D在大三角形之外(假设在点A所在边的外面),那么D到BC所在直线的距离大于A到BC所在直线的距离,那么三角形DBC的面积就会大于三角形ABC,这与三角形ABC面积最大的假设不符。
我个人的想法是先求出凸包,那么面积最大三角形的三个顶点必然在凸包上,所以之后再枚举三个点就可以了,但是很明显,这种方法是会超时的。我看了一下几个标程,做法基本上都是先定好一个三角形ABC,然后不断地枚举所有点更新这个三角形,直到无法找出更大的三角形为止。不过这种做法的正确性我并不会证明。
PS:这道题也坑了我很久,我最后对着某个AC程序改,尽管程序改得差不多了,最后却还是没有AC,经过仔细的研究之后,我发现原来我一直都在用unsigned long long,这种数据类型是不存在负数的TAT
 
 
Code:

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter