鉴于Round E要到了... 错过这个村就没这个店了0.0所以整理一下
此处加一个大纲。markdown在博客园怎么用……
算了格式在这先发出来吧。。and 要有目标qwq。！
## 题目2 Circuit Board
这个在LeetCode上的84 是个经典问题。LeetCode我都还只做到了.. 反正很少的,也没有接手Hard，easy感觉总是水水过去，medium也很少很少。
下一步说不定可以在github上维护一下？分单独的题解和分开的题解……完全可以在幕布上写了再移植过去的。（心情复杂.jpg）也可以不移植
### 题意
300*300矩阵，给定一大堆数字，使得每行中的最大值、最小值的差不超过K，满足这些条件的最小子矩阵是多少。
### false （大部分false的删了……）
o（n^3)的做法。
开始想的是并查集归属，串串儿一样噜过去，但是其实有点emmmm
对于这样的情况，只连续的找到个体然后从个体开始蔓延是不行的。
2 2 2 4
4 2 2 2
2 2 2 4
有种感觉，你需要抛开种族偏见，不能这样狭隘的去想，而且n很小，可以直接枚举两维，再来一维
首先呢，我们用一个三维布尔数组来记录，f[i][l][r]，记录的是i行的从 l 处到 r 处，此段里能否达到"不超过E"的条件。
这里是很死板的，甚至不用考虑最大值如果有两个的问题，只需预处理，枚举l和r。
好。如果布尔类型已经确定了
### 布尔怎么更新？
想了想，还是要至少更新n*(n-1)/2个。
那真的好笑。如果跟前面比是可，然后大小都没越界，
当前我在的位置是a2，当前已有len匹配到了(算了a2) ，那么1~ a2-len填No，a2-len+1 ~ a2填Yes（true）。
大小越界怎么看呢？
嗯，这个好像也是有时效性的，用最笨 的办法，那不如 满足K的时候正着来，不满足的时候1~a2-len+1依然可，后面一边走一边维护tmpmax和tmpmin
再想。
如果直接维护l和r呢？
嗯，这里，思维的差距就体现出来了。我们我在上面写的方法可以是可以，但是相当麻烦，而且有没有感觉到，有一种"特殊化"的感觉。
抛开这些再想想，在本文末尾，有提供一维怎么解答，可以nlogn，但没必要。
这个处理是和主程序分开写的，完全可以分开写，枚举的意思就是...
直接暴力的l和r，哪怕n^2的直接跑一遍，每次只看一个名为“l到r"的区间，只写一个false or true。即使这样n平方复杂度也足够了
剥离出来统一的看，思维要上升一个高度。。
### true =================================
我觉得好蠢哦，上面可以验证都是false的，高度根本不用管。
与其这样写题解，还是自己捋顺了是最好的吧……
……………………
这个题只有一句话。枚举l和r，那么这个串串的宽度是确定的，l和r已经n^2了
宽度确定后，到底有多长，就直接判断yes和no，然后使用累加，再乘以r-l+1就可了。
为什么要这么做？题中说要验证最长的块，那么是长度（横着）确定，去竖着撸一下更好呢，还是竖着确定，横着撸一串最好呢
显然，应该长度确定，然后看有几行能符合这个条件。直接一行一行看就可以了（图一）
如果是宽度确定的话，即使是继续扩展，是没用的，因为并不是以这个作区分的，可以看到1 1 3 这样按照这种划分方式并不能说明，因为这也不是题目的本意。（图二）
那么写一下代码。好累啊打解析打的手疼我不想写了（buxing
写个例子:
99 3 4 0
99 3 4 0
2 2 2 3
3 2 2 2
2 2 2 3
26分到手…… 思路理清之后，是没问题的，只是我写错了一个== ， 一个就是更新的时候没把1,1这样的首部更新进去
关键是思路啊！！！这还是很简单的啊！！！！26分啊！！！！kickstart错过就没了啊啊啊啊！！！
最后粘一下代码
#include<iostream> #include<algorithm> #include<queue> using namespace std; int n; bool f[305][305][305]; int a[305][305]; int a1, a2, k; int main() { int t; cin >> t; int kase = 0; while (t--) { //f好像不用清空 直接初始化就好 //输入 cin >> a1 >> a2 >> k; for (int i = 1; i <= a1; i++) { for (int j = 1; j <= a2; j++) { cin >> a[i][j]; } } //对数据处理 初始化bool f bool ff; int now; for (int i = 1; i <= a1; i++) {//行 for (int left= 1; left <= a2; left++) { //下面的列 f[i][left][left] = true; int maxx = a[i][left]; int minn = a[i][left]; //【惊！我这里多写了个等号】 //【惊！2 我忘记把第一个考虑进去！了耶】 ff = true; for (int right = left+1 ; right <= a2; right++) { if (ff == false)f[i][left][right] = false; else { now = a[i][right]; maxx = max(maxx, now); minn = min(minn, now); if (minn + k<now ||maxx-k>now) ff = false; f[i][left][right] = ff; } //这个数和minn maxx比较一下就好了 同时更新一下 // 如果已经是false了 那就全盘都是false好l } } } /* for (int i = 1; i <= a1; i++) {//行 for (int left = 1; left <= a2; left++) { //下面的列 for (int right = left; right <= a2; right++) { cout << f[i][left][right]<<" "; } cout << endl; } cout << endl; } */ int maxans = -1;int ans = 0; // ... 好.. 那处理完了还剩一次最后的循环和拍 for (int l = 1; l <= a2; l++) { for (int r = l; r <= a2; r++) { ans = 0; for (int i = 1; i <= a1; i++) { if (f[i][l][r] == true) { ans += (r - l + 1); maxans = max(ans, maxans); } else { ans = 0; } } } } cout <<"Case #"<<++kase<<": "<< maxans << endl; } return 0; }
### 变形
但就是说这样题目是个有名的变形，还有：
这个是... 饿示意图.. 这个题目的意思相当于是让我们这样求。实际上可以转化到leetcode的这样题目：
这个是... 饿示意图.. 这个题目的意思相当于是让我们这样求。实际上可以转化到leetcode的这样题目：
### 问题扩展：
#### 如果是一维的？
看起来直接横着过去就行。可以则加，不行则扔
但是有个问题，就是最大值最小值，如果是 3 4 5 7 2 7 后面来了个1，这不是完了吗，简单的双指针失效了。
有点作弊的做法：用mutiset。
而且要s.erase(s.find(7)) 这样只会删除一个，否则两个7都没了
看最大的只要s.rbegin()即可。越界就往前走（删除），不越界就安全，可以达到nlogn复杂度。
#### 如果是三维的？
想象一下，实际上n^5来 n^4在限制长度，相当于一个长方形桶，满足则继续，好像预处理有点麻烦