CH Round #62 - "小Cat和Taの小伙伴s"情人节欢乐赛 #62

Codeforces - Official

From saffah lydrainbowcatwyl8899


小时

尚未报名

小Cat与Sy×Zxr 80/123 500 分 From
小Cat与小昊爷 22/50 1,000 分 From
小Cat与小Cat 16/80 1,500 分 From
小Cat与小取酒 28/88 2,000 分 From
小Cat与小鲜肉 9/38 2,500 分 From

题解:

A:送分题。

B:送分题,数据只有100行,用数组暴力即可。

C:用一个变量记录当前状态,0表示在正常代码中,1表示在/* */注释中,2表示在//注释中,3表示在双引号中4表示在单引号中。只要遇到相应的开始标志(例如/* // " ')就进入相应的状态,在这个状态下,忽略一切其它标志直至遇到对应的结束标志(例如*/ 换行符 " ')。用通俗的话讲,就是遇到/*就直接往后找下一个*/,遇到引号就直接不断输出字符直至下一个引号。用学术一点的话讲,就是一个确定性有穷自动机。

D:按照第一维排序,倒序扫描。后两维构成的点在二维平面是具有单调性的(不是凸壳,但是是满足类似单调性的结构)。可以用一个set维护这些点,每次插入一个点时就前后扫描,像单调队列一样把肯定差的决策删除。可以再用一个priority_queue+懒惰标记维护最值。当然,也可以不用STL,手写一棵线段树。

E:首先简化题意:

  • 有2n个内存位,每个位置可以放一个数字,范围为[0,2m),第i个位置放j可以得到w(i,j)的收益,每个位置还有一个临界值ti以及一个ui。
  • 除此之外,一旦有两个位置a,b满足以下两个条件,可额外获得ua xor ub的收益。
  • a和b在二进制下只有一个bit不同。
  • a位置放的数不小于ta或者b位置放的数不小于tb。
  • 求最大收益的一组方案。
如果不考虑额外收益,显然每个位置i放的都是使得w(i,j)最大的j。而考虑额外收益后,需要分两种情况,放的数小于等于ti以及大于ti。每种情况保留下来的一样都是使得w(i,j)最大的j。
由题意知,对于每一组满足条件一的a,b,只有两个位置都小于ta,tb时才获得不到收益。从这里就能大概看出一个最小割模型了,割就是要抛弃的收益。
对于比较常见的模型一般都是一个二分图,而这题看起来“选择同侧”的点有额外代价的条件似乎很迷惑,但注意到第一个条件,就可以发现可以利用二进制1的个数的奇偶性来让模型变成”选择异侧”的点有额外代价。

最小割模型建图如下:

  1. 如果这个位置的index有奇数个1,源连小于的w,汇连大于等于的w。
  2. 如果这个位置的index有偶数个1,源连大于等于的w,汇连小于的w。
  3. 每个位置左边往右边连一条inf的弧,代表这两个点不能都不割。
  4. 对于每组a,b,连边ua xor ub。
  5. 为了避免负流量可以把所有w加一个1024,不影响最后结果。
  6. 最后所有的收益加起来减掉最小割就是最大收益。

本题还要注意数据范围中加粗加红的等号的情况,这表示该点与源汇之中的某一条边要连inf,建图的时候需要取好恰当的值。

------------------------------------------------------------

UPD:第三题中形如下列程序:

  • abcd/*abcd
  • efgh*/efgh

应该输出两行

  • abcd
  • efgh

-------------------------------------------------------------------------

分值分配:500-1000-1500-2000-2500

出题人:lydrainbowcat;验题人:saffah, wyl8899;讨论题目:vfleaking, hzhwcmhf;

2.5小时5道题,Codeforces赛制(参考Div.2 Only难度)。

A B C题难度与Div.2 ABC(NOIP前两题)难度相当。当然也要考虑到有神犇选手来虐题,因此D E题难度略高于Div.2 DE(与Div.1 C D难度相当)。

---------------------------------------------------------------------------------------------------

比赛的背景(主题)是小Cat Rainbow和Ta的小伙伴儿 <DB组合 Sy×Zxr>、<小昊爷 HeHao>、<小Cat Freda>、<小取酒 SJX>、<小鲜肉 SJY> 的故事23333

欢迎大家一起来CH度过情人节的夜晚~ (什么?你说你作为Oier有配偶?为什么我的手里多了火把和汽油!!!

由于8~15日冬令营原因,推迟到16日举办。