2-7 课堂总结

· · 个人记录

1.图论-二维数组

如何用一个二维数组描述一个图呢？

图的概念：有若干个点，有任意线段连接某两个点。

根据“两个点”可以使用二维数组 a[i][j]=1 代表 i \to j 是通路。

如：

4-1---2
  |   |
  |   |
5-3----

可以表示为：

  1 2 3 4 5
1 0 1 1 1 0
2 1 0 1 0 0
3 1 1 0 0 1
4 1 0 0 0 0
5 1 0 1 0 0

2.勤奋思考

老师说的不一定完全正确，

我们要乐于思考出和老师一样好或更优的方案。

3.louer_bound()和upper_bound()

louer_bound()和upper_bound()使用方法：

louer_bound(a+x,a+y,k)-a;表示从 a[x] 到 a[y-1]找a[t]使a[t]>=k且a[t]最小。

upper_bound(a+x,a+y,k)-a;表示从 a[x] 到 a[y-1]找a[t]使a[t]>k且a[t]最小。

例子：(upper_bound(a+x,a+y,r)-a)-(louer_bound(a+x,a+y,l)-a);表示从 a[x] 到 a[y]找[l,r]的个数。

louer_bound()和upper_bound()前需sort。

4.数组映射

处理a[l]~a[r]且r-l<=10^3 0<=l<=r<=10^9

int a[1000000010];会RE MLE CE。

int a[1010];，a[i]=a[i-l]

5.贪心例题

t1：

相当于将 0 移走，每移中间一个 0 就走一步。等于在计算 0 的个数。

r-l-cnt1

t3:

每遇到 M 个 0 就 cnt++ 治愈一次，指针i直接跳过 K 。

输出 cnt 。