牛客周赛74

目录

        C. 小数字

        E. 而后单调 

C. 小数字

        （1）向上取整函数：ceil ( x )

        （2）减到 3 直接一次性减完，跳出循环

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, INF = 1e18;

int T, n, m, ans;
string s;

signed main()
{
	cin >> T;
	while (T --)
	{
		cin >> n >> m;
		while (m --)
		{
			if (n >= 4)
				n = ceil(sqrt(n));
			else
			{
				n --;
				n -= m;
				break;
			}
		}
		cout << n << '\n';
	}
	return 0;
}

E. 而后单调 

        （1） 将数组倒序复制一遍判严格单增即为原数组严格单减

        （2）法一：符合条件的子数组，在原数组排完序之后仍然一一对应。但是代码中要反过来看，要到排完序的数组中去预处理，因为判子数组时候严格单增用到的pre 数组使用的 i，即下标，而不是 a[ i ] 数值，最终必须回到原数组中去。因此只需对排过序的数组，用 map 将首元素映射尾元素，到原数组中找到符合单增的子数组看是否对应即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, INF = 1e18;

int T, n, m, cnt, ans, a[N], b[N];
string s;

bool check(int * a)
{
	map<int, int> mp;
	int b[N], pre[N];
	for (int i = 1; i <= n; i ++)
		b[i] = a[i];
	for (int i = 1; i <= n; i ++)
	{
		if (a[i] > a[i - 1])
			pre[i] = pre[i - 1] + 1;
		else
			pre[i] = 1;
	}
	sort(b + 1, b + n + 1);
	for (int i = m; i <= n; i ++)
		mp[b[i]] = b[i - m + 1];
	for (int i = m; i <= n; i ++)
		if (pre[i] >= m)
			if (a[i - m + 1] == mp[a[i]])
				return true;
	return false;
}

signed main()
{
	cin >> T;
	while (T --)
	{
		cin >> n >> m;
		map<int, int> mp1;
		for (int i = 1, j = n; i <= n; i ++, j --)
		{
			cin >> a[i];
			mp1[a[i]] ++;
			b[j] = a[i];
		}
		if (mp1.size() != n)
		{
			cout << "NO" << '\n';
			continue;
		}
		if (check(a) || check(b))
			cout << "YES" << '\n';
		else
			cout << "NO" << '\n';
	}
	return 0;
}

        （3） 法二：因为子数组必须连续且长度固定，因此可以枚举子数组。将子数组的前后所有数扔到 set 中去，并在枚举子数组的同时实时更新 set，在 set 中二分查找第一个大于子数组最后一个数的数的位置 it，若 it 不是 set中第一个，看 it -- 对应的数是否小于子数组第一个数

        （4）set 中指针要指前一个是 it --，而不是 it = it - 1

        （5）对 pre 数组赋初值用 for，不要用 memset，pre 开到 2e5 若每次都用 memset 会超时。或者直接每次在 check 函数里定义一个 pre 数组

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18;

int T, n, m, cnt, ans, a[N], b[N], pre[N];
string s;
set<int> se;
map<int, int> mp;

bool check(int * a)
{
	se.clear();
//  int pre[N];
	for (int i = 1; i <= n; i ++)
        pre[i] = 0;
	for (int i = 1; i <= n; i ++)
	{
		if (a[i] > a[i - 1])
			pre[i] = pre[i - 1] + 1;
		else
			pre[i] = 1;
	}
	for (int i = m; i <= n; i ++)
		se.insert(a[i]);
	for (int i = m; i <= n; i ++)
	{
		se.erase(a[i]);
		if (i - m > 0)
			se.insert(a[i - m]);
		if (pre[i] < m)
			continue;
		set<int> :: iterator it;
		it = se.upper_bound(a[i]);
		if (it == se.begin())
			return true;
		it --;
		if (*it < a[i - m + 1])
			return true;
	}
	return false;
}

signed main()
{
	cin >> T;
	while (T --)
	{
		cin >> n >> m;
		mp.clear();
		for (int i = 1; i <= n; i ++)
		{
			cin >> a[i];
			mp[a[i]] ++;
			b[n - i + 1] = a[i];
		}
		if (mp.size() != n)
		{
			cout << "NO" << '\n';
			continue;
		}
		if (check(a) || check(b) )
			cout << "YES" << '\n';
		else
			cout << "NO" << '\n';
	}
	return 0;
}