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...

再接再礪。