wzz的观察
简单的递推。
\(f[i][j]\)表示以\((i,j)\)这个点为右下角时最大的正方形大小。
如果这个格子为0，\(f[i][j]=0\)
否则\(f[i][j]=min(f[i-1][j],f[i][j-1],f[i-1][j-1])+1\)
或者可以二分答案，每一次\(O(n*m)\)进行check。
递推代码：
#include<bits/stdc++.h>
#define FN "inspect"int f[2005][2005],n,m,ans;
char ch;int main() {freopen(FN".in","r",stdin);freopen(FN".out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {while(!isdigit(ch=getchar()));if(ch-'0') f[i][j]=std::min(f[i-1][j-1],std::min(f[i-1][j],f[i][j-1]))+1;else f[i][j]=0;ans=std::max(f[i][j],ans);}printf("%d",ans);return 0;
}
机房里测试的时候没有读优会少70分。
真的多到夸张
（还好我为了压行写了getchar）
wzz的军训
题解好蠢啊...
第二题
最基本的最小链覆盖
这个复杂度\(O(n^{3})\)
我不会二分图怎么办呢？
于是我用导弹拦截的做法A掉了。
把第一维排序，剩下的不就是导弹拦截吗？
能放则放，不能放就新开书架。
于是又偷税地A掉了。
#include<bits/stdc++.h>
#define FN "militarytraining"const int maxn=300+5;int n,ans=1;
std::vector<std::pair<int,int> > vc[maxn];
std::pair<int,int> b[maxn];inline int read() {int x;char ch;while(!isdigit(ch=getchar()));for(x=ch^'0';isdigit(ch=getchar());x=(x<<3)+(x<<1)+(ch^'0'));return x;
}int main() {freopen(FN".in","r",stdin);freopen(FN".out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++) b[i]=std::make_pair(read(),read());std::sort(b+1,b+n+1);vc[ans].push_back(b[1]);for(int i=2;i<=n;i++) {for(int j=1;j<=ans;j++) {if((vc[j].end()-1)->second<=b[i].second) {vc[j].push_back(b[i]);goto NXT;}}vc[++ans].push_back(b[i]);NXT:;}printf("%d",ans);return 0;
}要注意两点：
\(vc.end()\)是一个迭代器，而不是\(<>\)里面的东西，所以需要\((vc.end()-1)->second\)而非\(vc.end().second\)。
而且是最后一位之后的一位，所以要\(-1\)。
考场上差点忘了。
wzz的数数
前面的吹牛太蠢了。
第三题
很容易知道满足条件的数k一定不超过O(sqrt(n))个，所以对于70%的数据可以暴力统计有哪些数出现次数超过它本身，之后每次询问查询这些数有多少在该区间内满足要求。（可以用多一个sqrt(n)的空间复杂度换取询问少一个log）
但对于100%的数据，显然不是超时就是炸空间。
考虑将询问按左端点排序，从右向左做。
维护一个数组t，t[i]表示如果询问区间包含了点i，答案会增加t[i]（可能为负）。
初始情况下t全为0，i从n枚举到1，对某个i，考虑a[i]这个数在i位置及其以后是否出现过a[i]次及以上，假设a[i]在位置x出现了第a[i]次，在位置y出现了第a[i]+1次，即表示对于左端点为i的询问区间，当右端点在[x,y)时，a[i]会贡献1的答案，否则贡献0的答案，此时设t[x]=1且t[y]=-1即可。
用一个树状数组维护t数组，可以很容易的统计前缀和。
复杂度为O(nlogn+qlogn+qlogq）。
发现自己好多东西不会。
但依然能混230...
再接再砺。
