当前位置:网站首页>【学习笔记】阶段测试1
【学习笔记】阶段测试1
2022-07-05 14:10:00 【仰望星空的蚂蚁】
Menci 的序列
二进制 + 构造 + 贪心
第一眼是 dp 。想了 1.5h ,想不出来状态。
我会乱搞 !乱搞 80pts 。
首先把原序列改造一下。注意到 1000=010
这样构造后连续的 + 不超过 2 个
然后我们从高往低位贪心 。
显然是要用最少的 + 来构造。
因此最高位尽量不进位 。
不难想到贪心方案:从左往右遍历连续的 + 段,对于每一段连续的 + 只取一个,每一段连续的 * 也只取一个,这样前缀一定是 1111…
如果遇到后缀 * 不足的情况,那么这一段 * 的个数一定 >=2 ,足以隔断后面的选择对前面的影响(换句话说不可能进位了),那么我们只需让后面的 + 对答案贡献尽可能大 。
可以用两个二进制数相加来理解 。
你要问这个贪心怎么想到的,我也不知道 ,可能是感觉吧。
排序
膜拜 idsy …
这题第一感暴搜。
当然这题如果只能暴搜就太没意思了。
比如 Limak and Shooting Points 堪称搜索神题 。
其实正解挺显然啊 。
考虑 <=i 的操作都用了,那么对于长度为 2 i − 1 2^{i-1} 2i−1 的块内部顺序已定,毋宁看作一个整体 。
如果每一段都合法,则不执行操作;如果有一段不合法,则交换前后;如果有两段不合法,则分类讨论,最多有 2 2 2 种交换方法 。
这样可能的情况 2 n 2^n 2n 种,总复杂度 O ( 4 n ) O(4^n) O(4n) 。
注意别忘了乘阶乘 。
边栏推荐
- 基于伯努利原理的速度监测芯片可用于天然气管道泄露检测
- Linux下mysql数据库安装教程
- What is the ranking of GF futures? Is it safe and reliable to open an account for GF futures online?
- 分享 20 个稀奇古怪的 JS 表达式,看看你能答对多少
- R language uses the polR function of mass package to build an ordered multi classification logistic regression model, and uses the coef function to obtain the log odds ratio corresponding to each vari
- Laravel dompdf exports PDF, and the problem of Chinese garbled code is solved
- R语言ggplot2可视化条形图:通过双色渐变配色颜色主题可视化条形图、为每个条形添加标签文本(geom_text函数)
- 循环不变式
- 如何深入理解“有限状态机”的设计思想?
- Don't be unconvinced. Mobile phone function upgrade is strong
猜你喜欢
How to introduce devsecops into enterprises?
Financial one account Hong Kong listed: market value of 6.3 billion HK $Ye wangchun said to be Keeping true and true, long - term work
OSI and tcp/ip protocol cluster
The IPO of Ruineng industry was terminated: the annual revenue was 447million and it was planned to raise 376million
魅族新任董事長沈子瑜:創始人黃章先生將作為魅族科技產品戰略顧問
瑞能实业IPO被终止:年营收4.47亿 曾拟募资3.76亿
Interpretation of tiflash source code (IV) | design and implementation analysis of tiflash DDL module
世界环境日 | 周大福用心服务推动减碳环保
Simple process of penetration test
金融壹賬通香港上市:市值63億港元 葉望春稱守正篤實,久久為功
随机推荐
2022 machine fitter (Advanced) test question simulation test question bank simulation test platform operation
Current situation, trend and view of neural network Internet of things in the future
LeetCode_2(两数相加)
Oneconnect listed in Hong Kong: with a market value of HK $6.3 billion, ye Wangchun said that he was honest and trustworthy, and long-term success
昆仑太科冲刺科创板:年营收1.3亿拟募资5亿 电科太极持股40%
01. Solr7.3.1 deployment and configuration of jetty under win10 platform
非技术部门,如何参与 DevOps?
The IPO of Ruineng industry was terminated: the annual revenue was 447million and it was planned to raise 376million
不相交集
C语言中限定符的作用
TiFlash 源码解读(四) | TiFlash DDL 模块设计及实现分析
The forked VM terminated without saying properly goodbye
04_solr7.3之solrJ7.3的使用
Which Internet companies are worth going to in Shenzhen for software testers [Special Edition for software testers]
Zhizhen new energy rushes to the scientific innovation board: the annual revenue is 220million, and SAIC venture capital is the shareholder
R language ggplot2 visual bar graph: visualize the bar graph through the two-color gradient color theme, and add label text for each bar (geom_text function)
R language ggplot2 visual density map: Visual density map by group and custom configuration geom_ The alpha parameter in the density function sets the image transparency (to prevent multiple density c
为什么我认识的机械工程师都抱怨工资低?
WebRTC的学习(二)
Laravel dompdf exports PDF, and the problem of Chinese garbled code is solved