大二上第三周学习笔记

B. Orac and Medians(思维)

非常非常思维的一道题 不好想

首先注意到一个k和一个大于等于k的数，可以变成k，接着这两个数可以把相邻的第三个大于等于k的数变成k

所以我们可以把所有的数变成大于等于k的数，之后就可以全部变成k

那么这么变成大于等于k的数呢

可以发现，两个相邻的大于等于k的数如果存在，那么就可以把第三个数变成大于等于k，接着第四个数

不相邻的话，就是三个数，左右大于等于k也行

所以判一下这两种情况是否存在就行了

#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（枚举）

我自己想的时候用了拓展欧几里得，然而WA了

看了题解很巧妙，直接枚举y的值是多少

y的值有一个上限，就是w

当y大于等于w时，可以证明是有更优的策略的

#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 + 思维）

如果终点是点的话

走到终点，然后走到另一个点，再回来就行了

所以就正常bfs就行了，走过的设为×

#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;
}