Study notes of the third week of sophomore year

B. Orac and Medians( thinking )

A very, very thinking problem I don't want to

First notice a k And a greater than or equal to k Number of numbers , Can become k, Then these two numbers can make the adjacent third greater than or equal to k The number becomes k

So we can change all numbers to be greater than or equal to k Number of numbers , Then it can all become k

Then it becomes greater than or equal to k The number of?

You can find , Two adjacent ones are greater than or equal to k If the number of exists , Then you can change the third number to be greater than or equal to k, Then the fourth number

If not adjacent , It's three numbers , Left and right greater than or equal to k It's OK

So judge whether these two situations exist

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 1e5 + 10;
int a[N], n, k;

int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		int ans = -1;
		scanf("%d%d", &n, &k);
		_for(i, 1, n) 
		{
			scanf("%d", &a[i]);
			if(a[i] == k) ans = 0;
		}
		if(ans == -1)
		{
			puts("no");
			continue;
		}
		if(n == 1)
		{
			puts("yes");
			continue;
		}
		
		rep(i, 1, n)
			if(a[i] >= k && a[i + 1] >= k)
				ans = 1;
		rep(i, 1, n - 1)
			if(a[i] >= k && a[i + 2] >= k)
				ans = 1;
		
		puts(ans ? "yes" : "no");
	}

    return 0;
}

C. The Football Season（ enumeration ）

I used extended Euclid when I thought about it myself , However WA 了

After reading the solution, it's very clever , Direct enumeration y What's the value of

y The value of has an upper limit , Namely w

When y Greater than or equal to w when , It can be proved that there is a better strategy

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

typedef long long ll;

int main()
{
	ll n, p, w, d;
	scanf("%lld%lld%lld%lld", &n, &p, &w, &d);

	for(ll y = 0; y < w; y++)
	{
		ll x = (p - d * y) / w;
		if(w * x + d * y == p && x >= 0 && x + y <= n)
		{
			printf("%lld %lld %lld\n", x, y, n - x - y);
			return 0;
		}
	}
	puts("-1");

    return 0;
}

C. Ice Cave（bfs + thinking ）

If the end point is point

Go to the end , Then walk to another point , Just come back

So it's normal bfs That's it , Set passed as ×

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

const int N = 500 + 10;
int x1, y3, x2, y2, n, m;
struct node { int x, y; };
int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
char s[N][N];

void print()
{
	_for(i, 1, n) puts(s[i] + 1);
	puts("");
}

bool bfs()
{
	queue<node> q;
	q.push(node{x1, y3});
	while(!q.empty())
	{
		print();
		node u = q.front(); q.pop();
		int x = u.x, y = u.y;
		rep(i, 0, 4)
		{
			int xx = x + dir[i][0], yy = y + dir[i][1];
			if(xx < 1 || xx > n || yy < 1 || yy > m) continue;
			if(s[xx][yy] == 'X')
			{
				if(xx == x2 && yy == y2) return true;
			}
			else
			{
				s[xx][yy] = 'X';
				q.push(node{xx, yy});
			}
		}
	}
	return false;
}

int main()
{
	scanf("%d%d", &n, &m);
	_for(i, 1, n) scanf("%s", s[i] + 1);
	scanf("%d%d%d%d", &x1, &y3, &x2, &y2);
	puts(bfs() ? "YES" : "NO");
    return 0;
}