甲级第1084-1087题的简要题解

字符串处理的一道模拟题

介绍了两种查找算法:fibnacci,插值查找

关于距离的最值问题

Why Did the Cow Cross the Road III (G)题意：求相交区间的个数。思路 思路1：直接考虑每个数对应区间的贡献，显然相交区间的要求就是对于区间$[l,r]$，与左边相交或者与右边相交，又因为不讲顺序，所以可以

交叉乘思路化简式子，前缀和优化。 挺简单的。 代码const int mod=1e9+7; class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值

牛牛摆玩偶(二分)思路因为答案具有单调性，所以考虑二分，总是忘记有二分这个优化的玩意了，然后循环判一下，开始点为最左区间起点，然后贪心的选，如果不在某个区间内，就将$pos$定位到下一个区间的左端点即可。 代码/** * struct I

1079 Total Sales of Supply Chain (25分)思路就一个树形图，跑$dfs$或$bfs$，记录深度，遇到叶子结点计算贡献即可。 代码#include<bits/stdc++.h> using namesp

1078 Hashing (25分)思路没看到题目中的： Quadratic probing (with positive increments only) 直接暴力，用$vis$存下就好了。 代码#include<bits/std

Modern Art思路反向考虑不可能的情况，用$n^2$减即为答案，即某个位置被覆盖过一次以上的颜色，且每种颜色只有一次贡献，注意特判一下$n>1,color_{cnt}=1$的情况，因为这种情况 也不可能是第一次涂的颜色，即差分+

Barn Painting思路简单的树形$dp$，标记已经涂好色的点就行了。 代码#include<bits/stdc++.h> using namespace std; typedef long long ll; const in

Bovine Genomics (Gold)思路：一开始没考虑道答案的单调性，无脑暴力超时了，菜菜菜。 因为答案具有单调性，考虑$map+$二分解决即可。 时间复杂度 ：$O(mnlogm)$ #include<bits/stdc++