题解 Codeforces Round #621 (Div. 1 + Div. 2) (CF1307)

没水平没能力只会(ABCD),十二点多随便写完就爬了。其他补的。(E)考场降智,后面两道神仙题真的不看题解写不出来。

(ABC)懒得放代码了,反正也没保存,要的话博客园私信我,评论也行。后面写题解可能(ABC)代码都不放了,没意义。

[A : Cow and Haybales ]

难度评分:入门难度

发现第(i)堆移到第(1)堆需要(a[i]*(i-1))的贡献;随便算一下特判好了。

[B : Cow and Friend ]

难度评分:入门难度

走最大的即可,注意特判(a[i]=d (ans=1))以及(mx>d (ans=2))的;其它情况(ans=d/mx+(d\%mx!=0))

[C : Cow and Message ]

难度评分:普及-

题意是求出现次数最多的子序列,且这个子序列不同的元素不超过(2)个。

(cn[i])表示字母i出现的次数,(c[i][j])表示子序列((i,j))出现的次数。读入的时候处理一下,设现在处理到(s[i]),那我们枚举所有的(x),把(c[x][s[i]]+=cnt[x])。这个就是表示所有在(s[i])之前的(x)都对这个子串有了贡献,贡献是(cnt[x]),因为每个(x)和这个(s[i])都能组成一个新的子串((x,s[i]))。然后再把(cnt[s[i]]++)。最后(ans=Max(Max{cnt[i]},Max{c[i][j]}))

[D : Cow and Fields ]

难度评分:普及+

题意是选出两个关键点加边,最大化最短路。

首先明确,加边只会使最短路变小或不变;因为两点之间最短距离肯定是(1)。所以我们肯定是找到两点(i,j)连个边,使得这个新值最大;而这个新值又取决于原来1i,jn的最短路。

想到这个之后这个题就非常套路了。正反跑(dijkstra),然后就是求(Min(mindis,Max(D_i+D2_j+1)))。其中(D_i)表示1i的最短路,$D2_i$表示ni的最短路,(mindis)表示之前求出来的1~n的最短路(其实就是(Dn))。可以对第一维排个序,维护一下第二维的(Max)即可。

(Code-D)

[E : Cow and Treats ]

难度评分:提高-

本来准备看萌神代码学(E),意识到强者的码风不是蒟蒻可以读懂的。。最后去请教萌神了QwQ

题意是给你(n)头牛,它们喜欢吃的草甜度为(s_i),要吃掉的草的数量为(h_i),当一头牛吃掉(s_i)的草之后就躺那里不动了,其他牛看到她就不爽。现要求选出一些牛排在左右两边,让大家都开心。求最大化选出的牛数量以及方案数((\%1e9+7))

观察一下,发现如果有两头牛喜欢同一个甜度的草,她们又排在同一边,那她们是不会同时获得快乐的。所以如果有两头以上的奶牛喜欢上了同一个甜度的草,她们只能各排一边。

从这里开始都是萌神教我的(stO 萌神 Orz!):

对于每种草,用vector记录喜欢它的牛,两边不能放超过(1)头。记录有多少头可以放左边,多少头可以放右边,多少头两边都可以放。然后看左边放哪一类右边放哪一类,乘起来,注意判断边界只能给左边的牛吃。

(Code-E)

[F : Cow and Vacation ]

难度评分:省选/省选+

(gugugu)

[G : Cow and Exercise ]

难度评分:省选/省选+

听萌神说是裸的线性规划转费用流,可我没看出来QAQ......(3100的题在萌神那就是模板题难怪人家进队)

(gugugu)

争取今天更完剩下的,奥利给!

还是鸽让人快乐。

原文地址:https://www.cnblogs.com/Kylin-xy/p/tijieCF1307.html