|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
NOIP就要来了, 祝大家好运
注意点
先仔细读题, 然后手算一下样例
有了超时做法先写上去
模块化代码, 写完一个模块就检验正确性
部分分启发正解
连通, 重边, 自环, 重复, 数据范围...
特殊数据 1, 0, ... (9199)
打表
不要慌, 你难大家也难
先加/减 后 修改答案 还是什么样子
尽量不要用 ceil, 精度不够, 可用 (x - 1) / y + 1
多测不清空, 亲人两行泪
不开 ll 见祖宗
恰好 = 不大于 + 不小于
考虑一个条件的性质, 想想去掉这个条件会影响什么
杂项
把一个东西分成两个阵营, 可以按照二进制位分 logn 次 (5304)
有不等式, 等式一定要写下来, 放在一起考虑, 防止漏 (2471) (1972)
有很多地方都满足条件, 我们只需要找最 左/右/小... 的那个 (6617)(1972)
很多问题都可以转化为区间问题, 区间问题可以想想用前缀和等等转化为单点
询问差分 (4211)
先把一个变量定下来, 然后别的看看怎么维护
从一维考虑
变换枚举的对象 (6824)
做一件事, 需要安排一个顺序
先思考不对的情况
反悔贪心, 就是先定下来, 然后用新的看看能否代替, 有些东西是需要定下来的 (3045 中, 我们默认必须买当前的牛)
奇偶性, 说明可以分成两类直接算 (7114)
有了全局的增量 d, 但是会来新的东西怎么办: 插入这个新数 - d (8767)
差分实现 01 序列反转 (2882)
小的尽量在前面 != 字典序最小, 而是相当于字典序最大的反序 (3243)
求状态的后继(前 k 大), 状态的源头 (2048) (1852)
排序去除重复
时间倒流
放宽问题限制, 容斥
一个东西想想可不可以直接枚举, 因为很小 (9118)
两个值拼起来就是答案 (7913)
一般化处理: 把常数也看成一个变量
二分和倍增
长的, 不变的, 想优化一次跳一下的东西想到倍增
二分转化为 01 序列 (2824)
平均数 (区间和 - mid > 0)
中位数 (中位数可以变成大于等于的是 1, 小于的是 -1, 做 sum)
哈希
哈希 : 构造一个充分不必要条件, 然后利用哈希把她变得大概率充要 (8819)
哈希 + 二分判断是否是循环串 (4302)
图论
模板:
Dijkstra暴力(n^2), 堆优化
SPFA 双端队列优化, dfs判断负环
Kruskal算法, 重构树(在对最大/小边权有要求...等等场合)
Tarjan 求强连通分量, 点双, 边双, 缩点, 圆方树
二分图判定
拓扑排序
欧拉回路
Floyd 枚举转移点, 传递信息...
差分约束系统 (2824) (3084)
常用技巧:
建立超级源点
建立正/反图, 枚举一条边, 两个端点各自找最短距离 (2829) (5304)
DAG应该想到的 : DP, 拓扑排序, 按照拓扑序来枚举, 划分阵营 (3573) (5304), 最短路图
严格次小生成树要注意存第二大的边 (4180)
枚举边, 看边的贡献, 两边不知道就转化为两个有向图分别看 (5304)!!!
二分图, 看看两个人之间能不能共存, 不能共存就连边
MST问题两种思考: 按照边权分类 / 建一个 MST 然后用边去代替
MST 限制问题, 先求出必须加的边, 然后再做一次, 把必须加的加上, 然后加别的 (3623)
注意自环 (5008)
树上问题
模板:
倍增, 树剖, 树上dsu
常用技巧:
dfs栈保存了根到 u 路径上的点
dfs做差可以得出子树的答案 (1600)
换根
两个不重叠路径: 一个在子树内, 一个在子树外, 枚举 u 即可
dep, dist 的关系
路径分类: 按照 lca 分上下路径
dfn
lca 的单调性, 可以预处理等等
数据结构
模板:
线段树, 动态开点, 线段树合并
树状数组
栈, 队列, 单调栈, 单调队列
set 的使用
分块
技巧
值对应下标, 下标查询值 (1972)
询问差分
离线
DP
想让转移次数最少, 可以给每次转移加一个高昂的手续费 (6647)
区间类型 dp 可以按照区间拓展的方向考虑, 想想在旁边增加一个东西的代价, 让一个东西插入的代价
也可以想想中间点, 分成两个区间和一个点 (3592)
注意求方案数不要重复
按照顺序完成问题 (2051)
连续段 dp (2467)
状压dp状态的分类可以大幅降低复杂度 (3349)
树形dp 的模板 (4516)
字符串
哈希是强力的工具
二分 + 哈希 判断循环串
回文串, kmp的next数组的相同性
next数组是一棵树
|
|
100 鱼币
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 
置顶卡
千斤顶
显身卡
楼主
发表于 
虽然不太懂但是感谢分享
