A. 2025--[炼石计划--NOIP模拟三]--T1--矩形
赛时草了个 \(O(n^4 \log (n))\) 竟然能过 70 分虽然本来就是这么分配的，发现正解只需将二分改为双指针就可以了，最气的是上面计算的时候用到还是尺取下面就用的二分（唐诗）。
其实这题就是暴力，然后在低级的暴力上加一些操作变得稍微高级一点。
计算的话直接暴力查找不同颜色，只不过范围由小变大时只需扩展外围即可，例如下面的示例图。
这样扩展的话每次只会扩展外围，所以复杂度为 O(n) 的扩展，总复杂度为 \(O(n^3)\) ，然后就没了，不知道为什么唐诗的我没写出来。
具体复杂度分析：取最左上时的最坏情况，每次扩展 \(p\) 个外围元素，总共扩展 \(n\) 次，总计算为 \(1+2+3+4+……+n = \frac{n\times (n+1)}{2}\)，发现最坏情况都比 \(n^2\)，其实在某种情况下可以直接看成 \(n^2\) 更新了，但是梦熊数据你值得信赖，则视通常扩展时为 \(O(n)\)，故总复杂度为 \(O(n^3)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m;
int a[N][N];
int b[N][N];
int vis[N];
int main(){
ios::sync_with_stdio(false);
freopen("square.in","r",stdin);
freopen("square.out","w",stdout);
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++){
b[i][n]=1;
b[n][i]=1;
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
for(int i=n-1;i>=1;i--){
for(int j=1;j<=n-1;j++){
cnt=0;
memset(vis,0,sizeof vis);
for(int p=0;i+p<=n&&j+p<=n;p++){
for(int k=0;k<=p;k++){
if(!vis[a[i+p][j+k]]){
vis[a[i+p][j+k]]=1;
cnt++;
}
if(!vis[a[i+k][j+p]]){
vis[a[i+k][j+p]]=1;
cnt++;
}
}
if(cnt>m){
break;
}
b[i][j]=p+1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<b[i][j]<<" ";
}
cout<<"\n";
}
return 0;
}