柿子饼同学 发表于 2023-3-12 22:25:51

柿子饼的 OI 经验

本帖最后由 柿子饼同学 于 2023-3-29 13:03 编辑

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

柿子饼同学 发表于 2023-3-12 22:30:05

3/12 今天做了一个树上全渊最短路问题
当数据范围足够小, 可以用 floyd 加上 if(dist == INF) continue;
的剪枝 , 在树上效果很好

柿子饼同学 发表于 2023-3-13 12:04:04

本帖最后由 柿子饼同学 于 2023-3-18 15:48 编辑

3/13

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

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

柿子饼同学 发表于 2023-3-13 12:57:09

本帖最后由 柿子饼同学 于 2023-3-13 23:01 编辑

P8087
问最小值，可以先求出能够构造出来的最小值
        pn = n + 1;
        for(int i = 1; i <= n; i++){
                pn = min(pn, pos);
                px = max(px, pos);
        }
       
        for(int i = 1; i <= n; i++){
                if(f <= n && px] - pn] + 1 <= i){
                        cout << i;
                        return 0;
                }
        }

P2736 破锣摇滚乐队 DP, DFS
对于每个物品取舍的时候分几个情况比较好 , 这题 dfs 不用循环 , 直接 +1 就行了
DP
F=max{
    f //不选当前歌曲
    f+1 //用一张新的CD来存当前歌曲（m张CD不够存的情况）
    f]+1 //一张CD放多首歌曲
}
//F表示用m张CD，最后一张CD用t分钟所能存的最大歌曲数 time表示第i首哥的时间

柿子饼同学 发表于 2023-3-15 22:49:19

本帖最后由 柿子饼同学 于 2023-3-15 22:56 编辑

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

柿子饼同学 发表于 2023-3-18 15:48:08

本帖最后由 柿子饼同学 于 2023-3-18 16:45 编辑

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

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

柿子饼同学 发表于 2023-3-21 13:05:30

本帖最后由 柿子饼同学 于 2023-3-21 13:14 编辑

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

柿子饼同学 发表于 2023-3-22 13:12:31

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

柿子饼同学 发表于 2023-3-29 13:04:53

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

柿子饼同学 发表于 2023-4-1 14:59:13

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

柿子饼同学 发表于 2023-4-19 12:50:26

状态压缩 DP
可以将 二进制表示中 1 的 个数 排序
页: [1]
查看完整版本: 柿子饼的 OI 经验