Loading... # 2019-10-01笔记 ## 贪心 贪心算法是指，贪心算法是指，在对问题求解时总做出当前看来最好的选择。 贪心算法是指，在对问题求解时总做出当前看来最好的选择。 也就是说，不从整体最优上加以考虑他所做出的在某种意义局 也就是说，不从整体最优上加以考虑他所做出的在某种意义局部最优解。 ### P1080 一看最大值最小先想二分。 我们考虑两个相邻的人$x$和$y$，看交换他们是否会变得更优。 设$S=a_1 a_2⋯a_{x-1}$，则$v_{x_1}=\lfloor\cfrac{S}{b_x}\rfloor,v_{y_1}=\lfloor\cfrac{Sa_x}{b_y}\rfloor$。 如果把这两个人交换一下，那么 $v_{x_2}=\lfloor\cfrac{S_{a_y}}{b_x}\rfloor,v_{y_2}=\lfloor\cfrac{S}{b_y}\rfloor$。 除了这两个人之外，其他所有人的奖赏都不会发生改变，所以我们只需要考虑$max(v_{x_1},v_{y_1})$和$max(v_{x_2},v_{y_2})$的大小关系即可。 而我们发现$v_{x_1} \leq v_{x_2},v_{y_2} \leq v_{y_1}$，所以我们其实只需要比较$v_{x_2}$和$v_{y_1}$。 $v_{x_2}<v_{y_1} \rightarrow \cfrac{S_{a_y}}{b_x} \lt \cfrac{S_{a_x}}{b_y} \rightarrow a_yb_y<a_x b_x$（下取整其实不影响结果） 也就是说$a_i b_i$较小的要排在前面。 所以直接按照$a_ib_i$排序就可以了。注意统计答案需要高精度。 ### P3045 - 能用优惠卷一定用。 - 能买便宜就不买贵。 - 先取$C_i$最小的前$k$个作为答案，这一部分物品定会在最终的答案里。 然后我们考虑用剩下的钱买物品。分两种情况： - 下一个不用优惠卷则补偿差价$p_i$ - 下一个用优惠卷，答案加上$c_i+min(p_j-c_j)$ ### CF1214C 移动左括号等价移动右括号。 当然，也可以把最左边的右括号移动到最右，判断时候合法。 $$Ans=\sum_{i=1}^k(S_{p_i}-S_{p_{i-1}})=S_{p_1}+2P_2-2S_{p_1}+3S_{P_3}-3S_{p_2}+\cdots+kS_{p_k}-kS_{p_{k-1}}=kS_n-\sum_{i=1}^{k-1}S_{p_i}$$ 也就是说我们只需要把整个数组求一前缀和，然后在$n−1$个里面选 个里面选择最大的$k−1$个减去，得到的就是最小值。 ### CF1213F 考虑拓扑排序。 ## 套路 考虑相邻两个元素，看交换它们是否会使得答案变更优。 经典模型是你需要按照一定顺序考虑所有的元素，决最后答案。 经典模型是你需要按照一定顺序考虑所有的元素，决定最后答案。 如果发现贪心发现原来的策略不是最优，可以考虑实现可以撤销的贪心。 ## 二分 二分有二分查找，二分答案等。 ### P2698 二分区间长度，然后单调队列扫。 ## 搜索 ### 枚举全排列 时间复杂度：$O(n!)$ ```cpp int a[15]; bool flag[15]; void dfs( int step ) { if ( step > n ) return; for ( int i = 1; i <= n; i++ ) { if ( flag[i] ) continue; a[step] = i; flag[i] = 1; dfs( step + 1 ); flag[i] = 0; } } ``` ### 枚举子集 时间复杂度：$O(2^n)$ ```cpp void dfs( int step ) { if ( step > n ) return; flag[step] = 1; dfs( step + 1 ); flag[step] = 0; dfs( step + 1 ); } for ( int s = 0; s < ( 1 << n ); s++ ) { //do something. } ``` ### 枚举子集的子集 时间复杂度：$O(3^n)$ ```cpp for ( int s = 0; s < ( 1 << n ); s++ ) for ( int t = s; t; t = ( t - 1 ) & s ) { //do something. } ``` ## 其他提及的内容 - `multiset` - 0/1分数规划 - 参见[0/1分数规划](https://blog.csdn.net/niiick/article/details/80925267)<hr class="content-copyright" style="margin-top:50px" /><blockquote class="content-copyright" style="font-style:normal"><p class="content-copyright">版权属于：淡淡的路瑶</p><p class="content-copyright">本文链接：<a class="content-copyright" href="https://www.starroad.top/archives/478.html">https://www.starroad.top/archives/478.html</a></p><p class="content-copyright">如果文章出现任何问题，请下方评论，紧急情况请发邮件。谢谢支持！</p></blockquote> Last modification：October 7th, 2019 at 02:15 pm © 允许规范转载 Support 如果您觉得我的文章有用，给颗糖糖吧~ ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
