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