博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
习题一句话题解(COJ)
阅读量:6878 次
发布时间:2019-06-26

本文共 1081 字,大约阅读时间需要 3 分钟。

自二叉树开始吧

 


 

P2334 dfs 一遍字符串就行了

P2330 设字符串长度为 S,那么用暴力跑复杂度是 $ O(S^2T) $。但是有个 9 倍常数,理论上会挂。但是实际上根本跑不到那么多,所以可以过

P2011 因为是满二叉树,所以可以用数组模拟一遍树的操作,跑一遍就行了

P2274 NOIP2018PJT4,直接暴力 dfs,$ O(nlogn) $ 很稳

P2029 堆模板题,$ O(nlogn) $ 套模板就星

P2027 同滑动窗口,但是是用堆做的,用大根堆套上 pair 跑一遍,$ O(nlogn) $

P2020 这道题用堆做最低的复杂度是 $ O(nlogn) $,但是我没想出来,在暴力的基础上加上了一个特判,复杂度也从暴力的 $ O(n^2logn) $ 降到了 $ O(nlog^2n) $,意外的是跑的还挺快的,有开了 O2 和常数较小的原因吧

P2028 合并果子,每次 get 堆中最小的两个值,然后再将两数之和 put 到堆里面去,$ O(nlogn) $,在 COJ 上要开 LL,见祖宗 $ \times 1 $

P1419 杨辉三角递推 $ O(n^2) $

P2147 名字 tm 就叫最大子段和,用什么算法应该都知道了吧 跑一遍最大子段和,取一个最大值,没了 $ O(n) $

P2336 名字 tm 就叫最长上升子序列,用什么算法应该都知道了吧 跑一遍最长上升子序列 LIS,没了 暴力 DP $ O(n^2) $,通过二分优化后复杂度可以降至 $ O(nlogn) $

P2337 只要想到了 01 背包这题应该就做出来了,设 $ dp[i] $ 为在总和不超过 i 的情况下的最大值,那么 $ dp[j] = max(dp[j],dp[j-a[i]]+a[i]) $

P2338 又双叒叕是杨辉三角,比上面那题还简单些,几乎一模一样,不说了

P2340 这题题面必须给个好评,名字 tm 叫咸鱼翻身,希望我也有那么一天吧  废话不说多,开始讲题     这题首先要预处理一下,把翻过身的咸鱼(1)翻回去,变成 -1(千万要变成 -1!不能变成 0),然后再把没有翻身的咸鱼(0)翻身,变成 1,然后跑一遍最大子段和,将最大子段和加上初始状态下翻身的咸鱼数量,输出即可   这题是个多测,设共有 T 组数据,则复杂度为 $ O(TN) $,常数也并没有想象中的那么大

P2148 导弹拦截,LIS 跑一遍,不说了

转载于:https://www.cnblogs.com/Xray-luogu/p/10764307.html

你可能感兴趣的文章
RDS最佳实践(四)—如何处理Mysql的子查询
查看>>
最大流:Dinic模板
查看>>
安卓开发中个人能力的进阶进程
查看>>
人工智能10年将有颠覆性改变
查看>>
探秘AOP实现原理
查看>>
单点登录(SSO)简介
查看>>
2018最新大数据学习路线分享
查看>>
利用SVG制作不规矩背景的链接导航
查看>>
Linux - 一次运行多个命令
查看>>
10.C# -- 函数参数,参数数组,值传递函数,引用传递函数,输出函数,无参函数...
查看>>
BT5设置ip地址
查看>>
转载/验证码
查看>>
Surface、SurfaceView、SurfaceHolder和SurfaceHolder.Callback之间的联系
查看>>
什么是Data Store and Data Collector?
查看>>
我的友情链接
查看>>
php培训11.30
查看>>
Effective Java读后感
查看>>
windows下两个无线网卡 一个内网 一个外网
查看>>
tcp nat 负载均衡
查看>>
起点,游戏开发的梦想与技能点
查看>>