Browsed by
Category: STL

总结 The 9th Zhejiang Provincial Collegiate Programming Contest

总结 The 9th Zhejiang Provincial Collegiate Programming Contest

题目链接 http://acm.zju.edu.cn/onlinejudge/showContestProblems.do?contestId=337 代码神马的还没有写完 ,先把思路放上来 等到代码写好之后再贴代码 A Taxi Fare 水题,注意精度问题 求出来的两个费用都要四舍五入 如果只对最后一次进行四舍五入的话会WA B Unrequited Love 这个题是想法+STL搞 首先 根据名流问题的思想 我们可以通过O(N)的算法排除掉不可能是答案的人 最后剩下一个人判断一下他是不是喜欢宴会上的所有人即可。 具体思想如下:如果A喜欢B,那么B就不可能是Unrequited Love King or Queen (以下简称ans)反之,如果A不喜欢B 那么A就不可能是 ans 因此每次判断都会使问题的规模缩小1 这样就可以把问题规模在O(N)时间内缩小到 1,这样就只用判断一下这个人是不是ans即可,具体实现的时候 用 set存所有的喜欢关系 每个关系用一个二元组 pair<int,int>来表示,每一个名字映射到一个map<string,int>上 ,在具体实现时可以对上面的名流问题的解法进行优化,我们只需要一重循环从1—>N初值ans=1 然后去判断 如果ans不喜欢 i 或者 i喜欢ans 那么我们就更新ans 为 i 这里我们只判断了两种情况 实际上,ans 和 i之间的关系有四种 : ans喜欢i ans不喜欢i i喜欢ans i不喜欢ans 我们需要说明一下 循环中 既不满足 2 也不满足 3的i值一定不会是ans  ,很明显可以看出,这时,i和ans的关系一定是 1 4的任意一种,而这两个关系的任何一个 都说明了 i不可能是ans 所以我们这时候不去更新ans是正确的。因此这个算法的具体实现也没有问题了。 然后最后得到的ans我们还要判断一下他是不是喜欢所有人 。 —ps 这个题和性别无关哦~~~  heterosexuals 男男之间也可以互相喜欢哒 。有些人没看到这个地方以为是只有异性之间才可以互相喜欢 那么就会把问题搞错搞复杂 C Count the Trees 还是用hash的思想来稿 具体实现可以用map 这个题让我们判断有多少相同的子树,每个子树的样式可以用一个标号唯一确定 一棵树总共有n棵子树,同时 每个子树的结构可以用它的左右子树来唯一表示 ,这样的话 就建立了对应关系 我们用…

Read More Read More