题意： 给一个纸条，问是否可以折成一个立方体，纸条用一个h*w的矩阵上的#来描述，h<=100，w<=100，T<=30（数据组数）。 分析： 当时多校赛场上读完题就想到了可以枚举点然后BFS填充格子，只要有一个起点能满足不重复地填充给出图形上的所有#号点，且立方体被填满，就输出yes。由于h<=100,w<=100，所以最大的正方体的边长为100/4=25，因此我们枚举点25*25，check使用25*25*6的复杂度可以完成。 不过因为后来跟榜先搞别的题去了这题就先放一边，结果我们队后来因为开车那题自闭到最后. 这题的难点在于处理BFS时转向的问题。 我们可以先建立一个三维坐标，第一维是所属的面，第二维和第三维是这个坐标在这个面中的位置。如下图所示，中间的数字是面坐标的编号。 然后对于编号1的面，向周围4个面走的时候都是直接走即可，不需要进行坐标变换。 而对于需要进行坐标变换的情况，比如从0这个面一直向上走，走到4，需要将x和y坐标对调，然后逆时针转90°，再继续填充这个格子。 对于6个面，向4个方向走只有6*4=24种情况，所以直接把这24种情况x和y和方向的变化写出来（可以用if或者switch），然后直接做就完了。 然后就直接上一段很丑的代码吧。（为什么这么丑还要写博客呢，因为这算是在多校期间补的题中AC的人最少的一道题吧） 代码： #include <bits/stdc++.h> using namespace std; int…
二维ST表学习笔记
众所周知，ST表是一种离线解决RMQ(区间最值)问题的方法。 可以在O(n \log {n} ) 的时间内进行预处理，然后在O(1)时间内查询到结果。 复习一维 我们先来复习一下，一维st表的预处理和查询过程。 对于预处理，我们先定义一个名为st的二维数组，其中st[i][j]表示以i为起点，从起点开始（含起点）往后2^j个元素的最值。 满足i+2^j-1不越界 因为2^0 = 1 ，因此st[i][0]=a[i] 然后我们用2个for循环去打表就行了 接着是查询，这里我画了个图来解释。 其中橙色的线表示两个区间。 一维代码…