当前位置: 代码迷 >> 综合 >> codeforces 789 div2 题解
  详细解决方案

codeforces 789 div2 题解

热度:71   发布时间:2023-09-30 17:19:43.0

被闹钟叫醒再睡过真是心塞,只好熬得更晚刮完div2作补偿.......


AB就略了吧,B稍稍有点恶心但也是代码题


C的话是可以预先处理出差分后的绝对值序列,然后发现实际上就是求这个序列的最大子段和,基础dp知识


D有点意思,要分两部分来算,一部分是自环,另一部分是其他边,发现自环集合里随便取两个作为只经过一次的都是可行的,所以是C(num,2),这个显然;对于其他边来说,选出的两条边可行当且仅当这两条边有公共顶点,那就枚举公共顶点,sigma C(out,2)即为这部分答案,原因:

a.若两条边有公共顶点,那就可以从两条边某个非公共顶点出发,对于其他路径走去走回,对于这两条边所在路径走去回时到两条边另一个非公共点终止

b.若无公共顶点,路径必须经过这四个顶点而保证这两条边只经过一次,显然不成立,因为要使某条边不被经过,必须是路径的端点在这条边端点处。

还有一部分答案,是这两条边,一条是自环,另一条是其他边,这个就显然了,所以再加num*(n-num)



E这有点玄学.....那个m的范围是吓人的,ai只有1000种取值,所以m可以缩小到<=1000

化简一下式子,发现实际上是要 (p1*a1+p2*a2...pm*am)/k=n ,k=p1+p2....+pm

将k乘到右边,变成: (p1*a1+p2*a2+...+pm*am)=k*n,将每一个n都减到左边,就变成了:

a1*(p1-n)+a2*(p2-n)+....+am*(pm-n)=0

所以构建b序列bi=ai-n,开始玄学bfs......

直接bfs显然过不了,怎么办???

发现若当前的sum>2000,此时想要到达0,就要在之后减掉-sum,而-sum<-2000,不可能只减去某一个ai达到目标,式子为 sum-ai-aj-ak-....=(ai'+al'....)-aj-ak....=0,那么完全可以将上式变成:

ai'-aj+al'-ak....=0,使得每一个前缀和sum'<=2000,所以当sum>2000时剪枝

又因为正+负等价于负+正,所以当sum'<0,剪枝 


代码:

A:http://paste.ubuntu.com/24277232/

B:http://paste.ubuntu.com/24277238/

C:http://paste.ubuntu.com/24277245/

D:http://paste.ubuntu.com/24277246/

E:http://paste.ubuntu.com/24277247/

  相关解决方案