CSPS模拟 85
WWB大佬的bitset映射真是太强了!
%%%
T1
观察样例,猜规律。
T2
对题目的翻译工作用了很长时间
翻译错了好几次..
观察到奇环没法染色,选的边必须把奇环弄断
如果在偶环上,偶环就变得没法染色了,所以不能在偶环上
翻译完成后
这是什么?
算了乱搞吧
先弄个树出来,然后对于非树边,会和树边形成一个环
树上差分一下在哪个环里,维护一下有几个奇环,那么树上的边必须不在偶环里然后必须在所有奇环里
好有道理的样子,打出来交了。
考试快结束了
非树边的贡献??
完戏
赶紧再乱搞一发,我猜每个非树边只在一个奇环里!(瞎猜)
所以直接给非树边的num赋值成1算了
然后他就A了(RP--?)
然后经大神skyh指点,我跟正解撞上了。。
(又开心又怕RP--)
其实对非树边num=1的赋值没有问题,
如果有两个奇环的话,那么两条非树边一定分离,或者形成偶环废了
然后树边的贡献就严格按照定义(题意)来就没问题
%%%skyh被大样例坑了错失正解
T3
再%%%WWB
没想到啊,真没想到,还能
真·大暴力·STL映射STL
找到相关询问集合相同的所有下标
然后让这些下标分别平衡,就可以满足题意。//平衡:把这个子序列单独拎出来,它的左右括号完美地匹配
否则一定不满足,因为每个边界都必须满足在其方向上的“括号需求”为0//括号需求:需要在最左边加上多少左括号才能使右括号都得到匹配,可能为0,右边同理
如何平衡?用一个贪心
为了防止括号资源短缺,每个子序列内部的不平衡能自己抵消就自己抵消//内部的不平衡:既有左括号需求又有右括号需求
代价为$(min(Lneed,Rneed)+1)/2$//换一对,满足两组匹配,所以除以2
如果括号不平衡,从外部引进//一种括号过多,用一些这种括号换一些其他的
引进量为$abs(Lneed-Rneed)/2$//换一个满足一组匹配,减少一组需求,所以除以2
同时维护两个变量$NeedL NeedR$
用以平衡不同子序列之间的括号流动,如果子序列A需要左括号,B需要右括号
由于贡献只能计算一次,那么两次需求只有一次花费
那么记录一下有多少左括号曾被需求,等到需要右括号时优先使用那部分的免费左括号。
右括号需求多时同理
最新文章
- HTML5 progress和meter控件
- RabbitMQ学习系列(三): C# 如何使用 RabbitMQ
- 19、ASP.NET MVC入门到精通——Unity
- swift 定时器的使用
- linux下导入、导出mysql数据库命令 下载文件到本地
- hdu 4123 Bob’s Race 树的直径+rmq+尺取
- java中的if-Switch选择结构
- 关于duilib中的list的扩展探索
- Oracle的Export用法
- 看雪 安卓 dex文件
- java Spring集合
- QT设置标签字体大小和颜色
- jQuery选择器全解
- 集中式(SVN)和分布式(Git)版本控制系统的简单比较
- one-hot编码
- 1、JPA-HelloWorld
- 用Intellij IDEA建mybatis案例
- nginx保持会话的方式
- Linux+eclipse+maven+tomcat7小项目实战
- 第二阶段冲刺——two