Home
SSC Studio
Cancel

二分

带领只会基础二分的「真正的蒟蒻」 (例如, 我) 进入一个二分新境界 AcWing 102 最佳牛围栏 Link 这道题的二分用在了找平均值上. 首先这个平均值并不是题目数据给出来的, 因此不能像别的二分题那样对数组索引进行二分; 况且, 这道题根本不用也不能对数组进行从大到小排序. 这道题的二分是在 n 块地中牛的数量上进行二分, 并且是用浮点数进行计算, 注意自定义精度判断...

快速幂

AcWing 90 64位整数乘法 Link 如果直接计算 a 乘 b 就会超过 long long 的最大范围, 所以采用快速幂的思想把 b 写成二进制形式, 如果第 i 位上为 1 就在结果上加 a*(1<<i), 并且每次加上之后取模就可以了. #include <iostream> #include <cstdio> #include &lt...

AcWing 1100 抓住那头牛

Link BFS 解法需要想清楚几种不可能发生的情况进行剪枝, 否则必定 TLE. 首先, 农夫不可能跳到负数坐标点, 不然只能通过向右跳一步回到 0, 既然这样当初就不该作出这个选择, 反而还多了一步. 因此这种情况必须排除. 而这种情况只可能发生在 cur-1 的时候, 因此在 cur-1 的时候判断. 而每个 cur 我们都是严格保持在 [0,N-1] 内的, 因此 cur-1 只...

Flood Fill

今天 昨天接触了一个叫做 Flood Fill 的算法, 其实就是深搜广搜, 可以不用 vis 记录是否被访问过, 只需要在遍历过后将值修改一下就可以了. AcWing 1106 山峰和山谷 Link 用 DFS 和 BFS 两种做法: #include <iostream> #include <cstdio> #include <cstdlib>...

PAT 1018 Public Bike Management

Link 又是带路径回溯的 Dijkstra. 记录前驱节点即可. 要注意的是, 首先是路径最短, 其次是从 PBMC 带过去的最少, 最后是带回 PBMC 的最少. 再就是只能单向匀自行车不能双向. 即, 只能是从 PBMC 出发沿着这条路径检查各个车站, 如果有多出来的就可以匀给后面的车站, 而后面的车站多出来则不能匀给前面的车站. 因此, 需要时刻记录“带回”和“带来”这两个量, ...

C++ 双端队列deque

deque (双端队列) 可以向两端插入元素, queue 只能向一端插入元素. 头文件 #include <deque> 定义和初始化 deque<int> a; // 定义一个int类型的双端队列a deque<int> a(10); // 定义一个int类型的双端队列a,并设置初始大小为10 deque<int> a(10, 1...

C++ 常量和指针

C++ multiset

multiset 是 set 库中一个非常有用的类型, 用它插入、删除一个数都能够在 O(logn) 的时间内完成, 还能时刻保证序列中的数是有序的, 并且序列中可以存在重复的数. random_shuffle 定义在 algorithm 头文件中, 可以随机打乱一个序列. #include <iostream> #include <algorithm> #inc...

字典树(Trie)

这棵字典树用边来代表字母, 从根结点到树上某一结点的路径就代表了一个字符串. 有时需要标记插入 trie 的是哪些字符串, 每次插入完成时在这个字符串所代表的节点处打上标记即可. 代码模板 (来源): // C++ Version struct trie { int nex[100000][26], cnt; bool exist[100000]; // 该结点结尾的字符...

颜文字(复制即用)

嗨~ ≖‿≖✧ o‿≖✧ (๑•̀ㅂ•́)و✧ 牵手 ╭(′▽`)╭(′▽`)╯ 逃、跑! 💨 ε=ε=ε=ε=ε=ε=┌(; ̄◇ ̄)┘ 已阅留爪 (ฅ′ω`ฅ) 撒花 🎉 。:.゚ヽ(。◕‿◕。)ノ゚.:。+゚ 瞥~ (¬、¬) (¬_¬) 加油! (ง •̀_•́)ง (*•̀ㅂ•́)و 无奈 😮‍💨 ╮(๑•́ ₃•̀๑)╭ ...