柿子饼的 OI 经验

柿子饼同学

本帖是我自己的 OI 经验帖,
发这个是因为现在每天几乎一半时间在学校机房写题,
想直接把学得的方法技巧记下来,
方便复习.
如果你也有经验 , 欢迎在下面分享 ~~~
为了更好的未来

柿子饼同学

3/12 今天做了一个树上全渊最短路问题
当数据范围足够小, 可以用 floyd 加上

if(dist[i][j] == INF) continue;

的剪枝 , 在树上效果很好

柿子饼同学

3/13

艺测要考的歌：
嘎啦梅林
彩云追月
欢乐颂
茉莉花
我们在一起
青春舞曲
大海啊故乡

周五正式考试 ， 加油
PS : 考完了 , 相当简单 (3/18)

柿子饼同学

P8087
问最小值，可以先求出能够构造出来的最小值

        pn[0] = n + 1;
        for(int i = 1; i <= n; i++){
                pn[i] = min(pn[i - 1], pos[i]);
                px[i] = max(px[i - 1], pos[i]);
        }
        
        for(int i = 1; i <= n; i++){
                if(f[i] <= n && px[f[i]] - pn[f[i]] + 1 <= i){
                        cout << i;
                        return 0;
                }
        }

P2736 破锣摇滚乐队 DP, DFS
对于每个物品取舍的时候分几个情况比较好 , 这题 dfs 不用循环 , 直接 +1 就行了
DP

F[m][t]=max{
    f[m][t] //不选当前歌曲
    f[m-1][T]+1 //用一张新的CD来存当前歌曲（m张CD不够存的情况）
    f[m][t-time[i]]+1 //一张CD放多首歌曲
}
//F[m][t]表示用m张CD，最后一张CD用t分钟所能存的最大歌曲数 time[i]表示第i首哥的时间

柿子饼同学

P7871
由很多不等式连的可以想到 图 或者 链
然后它奇偶是分开的 , 所以可以分开讨论
这时候可以用差分优化
P2214
当发现是重复工作时就直接预处理就好了
里面那个 dp 数组只需要求一次

柿子饼同学

P4266
贪心, 策略是 先找最大的能呆多久呆多久 , 再找第二大的

P8271
神奇的题目不要害怕 , 先推点等式找找规律 , 然后尝试缩小状态到非常小的情况
大 -> 小

柿子饼同学

P2827
根据数据范围想算法
“对顶队列”
要看单调性

柿子饼同学

ACWING 146
合并问题 先找两个东西合并 再找第三个...
想问题先想最小情况

柿子饼同学

acwing 123 士兵站成一行最少步数
1. x 和 y 可以分开计算
2. 注意士兵相对顺序不变
求形如 |。。。| 的时候考虑中位数 ans += abs(a[i] - a[mid])

柿子饼同学

P2058 海港
看看数据范围 , 这里是维护人 , 实时更新 , On

柿子饼同学

状态压缩 DP
可以将 二进制表示中 1 的 个数 排序