Browsed by
分类: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

代码神马的还没有写完 ,先把思路放上来 等到代码写好之后再贴代码

Taxi Fare

水题,注意精度问题 求出来的两个费用都要四舍五入 如果只对最后一次进行四舍五入的话会WA

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之间的关系有四种 :

  1. ans喜欢i
  2. ans不喜欢i
  3. i喜欢ans
  4. i不喜欢ans

我们需要说明一下 循环中 既不满足 2 也不满足 3的i值一定不会是ans  ,很明显可以看出,这时,i和ans的关系一定是 1 4的任意一种,而这两个关系的任何一个 都说明了 i不可能是ans 所以我们这时候不去更新ans是正确的。因此这个算法的具体实现也没有问题了。 然后最后得到的ans我们还要判断一下他是不是喜欢所有人 。

—ps 这个题和性别无关哦~~~  heterosexuals 男男之间也可以互相喜欢哒 。有些人没看到这个地方以为是只有异性之间才可以互相喜欢 那么就会把问题搞错搞复杂

Count the Trees

还是用hash的思想来稿 具体实现可以用map 这个题让我们判断有多少相同的子树,每个子树的样式可以用一个标号唯一确定 一棵树总共有n棵子树,同时 每个子树的结构可以用它的左右子树来唯一表示 ,这样的话 就建立了对应关系 我们用 pair<a,b>表示一个左子树样式标号为a右子树样式标号为b的树,用 map<pair<a,b> k>表示 这棵树的样式标号映射为k 然后再用一个一维数组tree[1-N]保存每颗子树的样式标号 ,特殊处理叶子节点 叶子节点的样式标号全部为 0 然后map[pair<-1,-1>]=0即可。通过上面的方式,我们建立起第一棵树之后,用同样的方式建立第二棵树,并且每次进行合并操作的时候遇到一个pair 就去左边查询是否存在这个pair 存在的话 取出它的标号 然后去tree这个数组里循环一次,统计所有样式标号与之相同的,这些子树的结构都与其同构。然后输出总的同构树即可。

Draw Something Cheat

水题,用二维数组 a[N] [26]保存一下第i 次输入中 每个字母出现的次数(0–25表示字母) 并且,找出每个字母出现的最少次数 按照顺序输出即可

Tunnel Network

这个题属于数学题 如果不知道Cayley公式和Prufer编码这个题真的就几乎无解了,Prufer编码的详细知识可以参看这个文章,matrix巨巨写的。下面只说明本题的思路,这个题里面N个节点的图 有S个 联通分量而且 第i个联通分量一定有i这个节点,而且判断联通分量是否相同时和标号有关 即 10 11 联通 与 9 8 联通是不同的两个情况 ,我们要求的是总共有多少种可能的连通方式。我们给图中加一个根节点 0 并让 0与每个联通分量相连,这样的话 就构成了一个由n+1个节点构成的有序号的无向树,这里需要改变一下Prufer编码的方式 我们让Prufer编码从节点标号最大的叶子开始删除 其它的不变,显然这样的Prufer编码还是与无向树一一对应,然后 注意到 这个Prufer序列的最后s-1个元素一定是0 (因为最后s-1个删除的节点一定是s—–2这些节点) 然后 倒数第s个元素一定是 1–s中的某一个值 (因为在这棵树变成只含有0—–s这些节点的树之前的状态,一定有一个叶子节点与1—s中的某一个相连,则删除它的时候会添加进来1—s中的某个值) 然后 问题就解决了 根据Prufer公式 本题中有N+1个节点 ,Prufer序列的长度为 N+1-2=N-1,排除掉有特殊情况的Prufer编码序列中最后S位 剩下的n-1-s位每一位都可以取1—N的任意值构成Prufer序列 所以 总数为 N^(N-S-1)*S ,然后用快速幂搞一下即可

Find the Marble

DP到现在为止知识储备还几乎是零,队友讲解了这个题之后总算明白了 这个题由于求概率的话 数字小到double会丢精度,因而我们存频数 并且使用三维来存储状态

dp[n][m][k]表示的是: 第m次交换时,看到k次交换的情况下 球在n号杯子里的频数,它的值就是 dp[n][m-1][k]+dp[CC][m-1][k-1]  ,即 前m-1次交换时,看到了k次 (即这次没看到)  看到球在n号盒子里的频数,以及 前m-1次交换时,看到了k-1次 (即这次看到了)看到球在CC号盒子里的频数 (这里有一个判断 如果 第m-1次交换的序列中 有 (n,CC) 或 (CC,n)这样的交换 ,那么球所在的盒子就会变,否则的话,球所在的盒子还是n 所以 CC要么是 n 要么是第m-1次交换的另一个杯子的编号) 。

初始状态 要把 dp[s][0][0]置为1 其它全部置零即可 然后循环的时候,三重循环的顺序如下:

i=1 To m

j=1To i

k=1 To n

然后 最后找出 dp[1–N][m][k]中的最大值对应的N 就是我们要求的结果

Lazy Salesgirl

广告位出租…

Lazier Salesgirl

广告位出租… 简单的模拟 不过我还没做

Signal Detection

广告位出租…

Modular Inverse

本来是扩展欧几里德 不过数据很水,用一下暴力就解决了 注意特殊情况的判断 m=1的时候会有特殊情况

Yet Another Story of Rock-paper-scissors

这个故事告诉我们 做人要心怀善心为他人着想。

在题目描述下 每次都是女的会赢,所以只要输出一个字串即可