当前位置:网站首页>7.6模拟赛总结
7.6模拟赛总结
2022-07-06 17:34:00 【Flame*】
咕咕咕咕咕
我以为会过一车人
我因为人均170+
我有点意外
时间安排
7.30-9.00
看了看题 感觉T1显然状压 T2差不多会50 T3只会n^2 想了半天T2有什么别的做法 感觉都单调性 但是没有抓住这个想法
先打了T2暴力
9.00-10.00
感觉不太行 又想了一会T3 也没啥想法
然后打了T3的暴力
10.00-10.40
打了T1的暴力 想了一会 觉得T1的第二档是不是有什么神秘做法(因为是图) 感觉有点树形dp那味 但是不是很会
10.40-12.00
重新回想T1 反应过来可以分块掏决策单调性
然后努力回想怎么维护区间逆序数 这里我犯了一个错误 因为之前听了noi那个题 就觉得区间逆序数很复杂(实际上赛场推出来了) 推出来之后还觉得有点不明所以 (其实是因为noi那个题既有区间也有值域限制)
最后时间不够了(剩了20分钟 ) 就检查一下交题了
题目分析
T1
f [ S , o p 1 , p o s , o p 2 ] f[S,op1,pos,op2] f[S,op1,pos,op2] 当前走过的点的状态为 S S S 是否在终点的状态为 o p 1 op1 op1 在点 p o s pos pos 上 上一条走过的边的状态是 o p 2 op2 op2
转移分情况考虑
正常模拟转移
o p 1 = 0 op1=0 op1=0 的时候走到了一个标记点:可以考虑转成 o p 1 = 1 op1=1 op1=1 加上贡献
o p 1 = 1 op1=1 op1=1 枚举一个没走过的标记点作为新起点 同时向 o p 2 = 1 / 0 op2=1/0 op2=1/0 转移
貌似我更擅长做状压dp一点
T2
f [ i ] f[i] f[i] 表示最后一段分到 i i i 的最小代价
可以注意到 代价就是区间逆序对 再考虑每填入一个数 前面不同位置 从小到大 增加的值是不增的 形如 5554444321111... 5 5 5 4 4 4 4 3 2 1 1 1 1... 5554444321111...(值改变的位置就是出现了一个比它大的数)
然后可以 n 2 n^2 n2 做
基于这个性质 可以证明决策单调性
所以有了 n l o g n n nlogn~\sqrt n nlogn n 的决策单调性套分块做法
upd
正解是cdq套分治决策单调性+类似莫队方法 维护两个指针 暴力跳区间逆序对
之所以需要cdq套一下 是因为分治决策单调性需要内容之间没有依赖 而这个有依赖 所以通过cdq分治搞出前面的dp值
T3
这个是真不会 只想了n^2或者撒点
边栏推荐
- Eventbus source code analysis
- Receive user input, height BMI, BMI detection small business entry case
- NEON优化:关于交叉存取与反向交叉存取
- [Niuke] [noip2015] jumping stone
- Informatics Olympiad YBT 1171: factors of large integers | 1.6 13: factors of large integers
- [牛客] [NOIP2015]跳石头
- Provincial and urban level three coordinate boundary data CSV to JSON
- ARM裸板调试之JTAG原理
- [batch dos-cmd command - summary and summary] - jump, cycle, condition commands (goto, errorlevel, if, for [read, segment, extract string]), CMD command error summary, CMD error
- C# 计算农历日期方法 2022
猜你喜欢
Dell Notebook Periodic Flash Screen Fault
动态规划思想《从入门到放弃》
Can the system hibernation file be deleted? How to delete the system hibernation file
[batch dos-cmd command - summary and summary] - jump, cycle, condition commands (goto, errorlevel, if, for [read, segment, extract string]), CMD command error summary, CMD error
重上吹麻滩——段芝堂创始人翟立冬游记
Building a dream in the digital era, the Xi'an station of the city chain science and Technology Strategy Summit ended smoothly
Installation and testing of pyflink
ARM裸板调试之JTAG调试体验
Asset security issues or constraints on the development of the encryption industry, risk control + compliance has become the key to breaking the platform
UI控件Telerik UI for WinForms新主题——VS2022启发式主题
随机推荐
mysql: error while loading shared libraries: libtinfo.so.5: cannot open shared object file: No such
Data type of pytorch tensor
Oracle: Practice of CDB restricting PDB resources
Maidong Internet won the bid of Beijing life insurance to boost customers' brand value
LLDP兼容CDP功能配置
Niuke cold training camp 6B (Freund has no green name level)
[100 cases of JVM tuning practice] 04 - Method area tuning practice (Part 1)
How to evaluate load balancing performance parameters?
如何管理分布式团队?
[batch dos-cmd command - summary and summary] - view or modify file attributes (attrib), view and modify file association types (Assoc, ftype)
Deep learning framework TF installation
A brief history of deep learning (I)
Let's see through the network i/o model from beginning to end
Install Firefox browser on raspberry pie /arm device
Building a dream in the digital era, the Xi'an station of the city chain science and Technology Strategy Summit ended smoothly
Anfulai embedded weekly report no. 272: 2022.06.27--2022.07.03
Address information parsing in one line of code
tensorflow 1.14指定gpu运行设置
Fastdfs data migration operation record
Gnet: notes on the use of a lightweight and high-performance go network framework