格雷码(Gray Code)是一种特殊的 $n$ 位二进制串排列法,它要求相邻的两个二进制串间恰好有一位不同,特别地,第一个串与最后一个串也算作相邻。
………………
现在给出 $n$,$k$,请你求出按上述算法生成的 $n$ 位格雷码中的$k$ 号二进制串。
格雷码(Gray Code)是一种特殊的 $n$ 位二进制串排列法,它要求相邻的两个二进制串间恰好有一位不同,特别地,第一个串与最后一个串也算作相邻。
………………
现在给出 $n$,$k$,请你求出按上述算法生成的 $n$ 位格雷码中的$k$ 号二进制串。
这道题目可以算是一道set
的板子题(在CJC大佬的提醒下恍然大悟,CJC的博客),于是这篇题解某种意义上其实是对于set
的讲解和复习。关于STL
的话,全称为Standard Template Library
,说白了就是一个非常多功能的库,引用时按情况引用,可能会有set
map
algorithm
等等,按情况来分析,用途很多,有封装好的快排、大根小根堆(优先队列)、二分查找、全排列、各种神仙玩意儿。set
则是其中的一个工具。
学习了 LCA(最近公共祖先)
这个高级的东西。。
于是乎来发一些理解和题解以便以后复习。
LCA就是LCA
就是求一棵树上两个节点最近的公共祖先,那么有什么用呢,用来做题。
这里用到了“爬树”的方法找
例如两个节点$x,y$:
规定$deepth_x>deepth_y$
1.让深的那个节点,$x$往树上爬,直到$deepth_x = deepth_y$;
2.让两个节点一起向上跳,如果碰在一起了,那么就找到了。
嗯,真是生动形象好理解呢!
学习了 ST表
这个高级的东西。。
于是乎来发一些理解和题解以便以后复习。
ST表的功能很简单:
它是解决RMQ
问题(区间最值问题)的一种强有力的工具。
它可以做到$O(nlogn)$预处理,$O(1)$查询最值(ohhhhhhhh)
这两节课学习了 线段树
这个高级的东西。。
于是乎来发一些理解和题解以便以后复习。
先来康康这类问题:
长度为$n$的数列${a_1, a_2, … , a_n}$
(1)求最值:给定$i$,$j<=n$,求${a_i, …, a_j}$区间内的最值。
(2)修改元素:给定$k$和$x$,把$a_k$改成$x$。
显然你可以用暴力去做,但是
The Department of National Defence (DND) wishes to connect several northern outposts by a wireless network. Two different communication technologies are to be used in establishing the network: every outpost will have a radio transceiver and some outposts will in addition have a satellite channel.