AtCoder Grand Contest 038

A. 01 Matrix

本来很简单的一道题，因为只需随便找出一种满足条件的矩阵，所以很容易看出左上角和右下角为0，其余为1的矩阵一定满足条件。我居然想了很久，太蒻了。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>

#define M 1005

int ans[M][M];

using namespace std;

int main()
{
	int h, w, a, b;

	cin >> h >> w >> a >> b;

	for (int i = 1; i <= b; i++)
		for (int j = a + 1; j <= w; j++)
			ans[i][j] = 1;

	for (int i = b + 1; i <= h; i++)
		for (int j = 1; j <= a; j++)
			ans[i][j] = 1;

	for (int i = 1; i <= h; i++)
	{
		for (int j = 1; j <= w; j++)
			cout << ans[i][j];
		cout << endl;
	}

	return 0;
}

B. Sorting a Segment

单独考虑本身已经是升序的情况。观察发现，对于A[i]~A[i+k-1]（令其为集合S），重复的一定满足A[i-1]<min{S}且A[i+k]>max{S}，所以需要不断的寻找S中的最小值和最大值。题解用的是什么滑动窗口算法，暂时还没学，先用set顶上吧（第一次知道set可以用rbegin()反向迭代）。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <functional>
#include <map>

#define M 200000 + 5

int a[M], ans;
bool flag[M];
int n, k;

using namespace std;

int main()
{
	set <int> s;

	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	int tot = 1;
	int num = 0;
	for (int i = 1; i < n; i++)
	{
		if (a[i] < a[i + 1])
			tot++;
		else
			tot = 1;
		if (tot >= k)
		{
			num++;
			flag[i + 1] = true;
			ans = 1;
		}
	}

	for (int i = 1; i < k; i++)
		s.insert(a[i]);

	int index = 1;
	int front = (int)1e9;

	for (int i = k; i <= n; i++)
	{
		int minl = *s.begin(), maxl = *s.rbegin();

		if ((flag[i] == true) || (front < minl && a[i] > maxl))
			;
		else
			ans++;

		front = a[index];
		s.erase(s.find(a[index]));
		s.insert(a[i]);

		index++;
	}

	cout << ans << endl;

	return 0;
}