20241017晚自习

刷题

好困，想搞T

[CEOI2024] 文本编辑器

奇怪题

假如他键盘也坏了不能换行，那就是一个很简单的模拟可以搞定的

大概可以想到答案的组成：

1.直接走

2.从起点先到某一行开头再走

3.从起点先到某一行结尾再走

这个能感性理解到，用左右键换行的次数应该不是很多，仔细想能发现 ，最多两次

有了这些结论就直接求就行了

维护第一部分答案用了个st表，写的劣了一点，复杂度 $O(n\log n)$

[ABC203D] Pond

其实是一个经典套路来着但是确实没想起来

考虑二分答案一个 $x$ 为所求，然后把矩阵里 $\gt x$ 的赋为 $1$，反之为 $0$ ，然后可以二维前缀和维护一个矩阵里面有几个大于等于 $x$ 的数

做完了

#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[805][805];
int b[805][805];
bool check(int x){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            b[i][j]=(a[i][j]>x);
            b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j];
        }
    }
    int tot=0;
    for(int i=1;i+k-1<=n;i++){
        for(int j=1;j+k-1<=n;j++){
            int x1=i,x2=i+k-1;
            int y1=j,y2=j+k-1;
            int sum=b[x2][y2]+b[x1-1][y1-1]-b[x2][y1-1]-b[x1-1][y2];
            if(sum<=k*k/2) return 1;
        }
    }
    return 0;
}
int A;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            A=max(A,a[i][j]);
        }
    }
    int l=0,r=A,ans=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            r=mid-1;ans=mid;
        }
        else l=mid+1;
    }
    cout<<ans;
}