CH Round #29 - 白色情人节欢乐赛

OI - Official

From 大神cyd


小时

尚未报名

读心术 55/68 From
送花 37/91 From
聚会 36/74 From
烛光晚餐 19/38 From
朋友 30/52 From
增进感情 13/29 From
求婚 3/60 From

第一题添加SPJ重测,已经重新计算能力值。

白色情人节到了,我出了7道题目以庆祝。由于3.14/15这周末已经有一场比赛,因此推迟至22日举办。

本次比赛一共有7题,时间为4小时。比赛主要面向Div.2级别的用户,题目难度较小,不超过提高组水平,普及组的蒟蒻们也可以得到可观的部分分。

虽然我没有tangjz神牛的水平,但我希望我的比赛能给蒟蒻们一点信心。题目全部原创,与标准模型有较大区别。特别的,最后一题没有标准算法,大家可以自由发挥,自己设计方法。

欢迎大家参加比赛。

/*以下为题解*/

第1题,我的提示已经够清楚了。把1~N的每个数转换成二进制,把每个二进制位为1的数放在相应的卡片上。

第2题,就是一个裸的平衡二叉树,C++党们可以使用set。

第3题,把所有的编号放入一个哈希表(数据比较大,是给C++党用map的)。但是,这题有坑,就是能配对的两个人不仅要编号相同,而且必须是一男一女。

所以,这题可以这样做:出现一个男人的编号,出现次数+1;出现一个女人的编号,次数-1.最后累加所有出现次数的绝对值乘以编号的积即可。

第4题,是背包问题的变形,仍然使用DP解决。

方程是:f[i][j][k]=max(f[i-1][j][k],f[i-1][j-c[i]][k-x[i]]);

f[i][j][k]表示前i道菜花j元,小明的喜爱程度和为k时小红的最大喜爱度。

第5题,看到“朋友关系”,就让人想到并查集。使用两个并查集,分别表示A公司和B公司的朋友情况,然后分别统计出小明和小红的朋友数,取它们的最小值。

第6题其实很简单,就是一道搜索题。唯一的技巧在于,若搜索到一件事时,加上后面的所有正数事情,两人仍然无法在一起,就停止当前搜索。

第7题其实没有标准的算法。下面有几种思路:

1、打三个随机答案,拼人品。

2、打三个yes,祝小明幸福。

3、判断字符串中是否有not或n't,若有就输出no,否则输出yes.

4、在第三种方法的基础上,考虑以下几点:

  • 反义疑问句等包含not或n't但并非否定的语法情况;
  • 用never等否定词表示否定的情况;
  • marry(结婚)、forget(忘记)、get out(滚)、with you(和你一起)、forever(永远)等常见接受或拒绝的高频用词。

5、最标准的方法当然是进行语句和词法分析。