A. Three Doors
题目链接：
Problem - A - Codeforces
题面：
题意：
共有三扇门，一开始你有一把钥匙，有两扇门后面有钥匙，一扇门后面没有钥匙（如果有钥匙，就会告诉你可以开哪扇门，如果不是钥匙就是0），问你能否把三扇门全部打开
思路：
可以通过一开在我们手上的钥匙来开门，然后拿新钥匙在开门的方法循环下去，直到没有新钥匙为止来判断我们一共拿到了几把钥匙（0也算一把钥匙，但是不能开门）（如果全开的话，一共有4把）
代码：
#include<bits/stdc++.h>
using namespace std;int arr[5];int main(){int t;cin >> t;while(t--){int x;cin >> x;for(int i = 1; i <= 3; i++){cin >> arr[i];}int a = 1;while(x != 0){a ++;x = arr[x];}if(a == 4){cout << "YES" << endl;}else{cout << "NO" << endl;}}return 0;
} B. Also Try Minecraft
题目链接：
Problem - B - Codeforces
题面：
题意：
思路：
可以利用前缀和的思想来写，创造一个数组ldx表示从1号点到i号点总共收到的伤害，以及rdx表示从n号点到i号点总共收到的伤害.然后查询的值就是差值。只是需要注意从小到大，和从大到小的区别
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll arr[100005];
ll ldx[100005];
ll rdx[100005];int main(){int n, m;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> arr[i];}ldx[1] = 0;rdx[n] = 0;for(int i = 2; i <= n; i++){ldx[i] = ldx[i - 1] + max(arr[i - 1] - arr[i], (ll)0);}for(int i = n - 1; i >= 1; i--){rdx[i] = rdx[i + 1] + max(arr[i + 1] - arr[i], (ll)0);}while(m--){int a, b;cin >> a >> b;if(a < b)cout << ldx[b] - ldx[a] << endl;elsecout << rdx[b] - rdx[a] << endl;}return 0;
}D. Rorororobot
题目链接：
Problem - D - Codeforces
题面：
题意：
思路：
如果起点，终点的横纵坐标差不是k的倍数，那么无论这么走都不能刚好停在终点。然后判断一下起点和终点的位置是不是不能走的地方，然后往上走，走到最高点，在判断中间不能走的地方有没有大于最高点即可（中间的最高值可用线段树来查询）
代码：
#include<bits/stdc++.h>
using namespace std;int arr[200005];
int tree[200005 * 40];
void updata(int rt){tree[rt] = max(tree[rt * 2], tree[rt * 2 + 1]);
}
void build(int l, int r, int rt){if(l == r){tree[rt] = arr[l];return ;}int mid = (l + r) / 2;build(l, mid, rt * 2);build(mid + 1, r, rt * 2 + 1);updata(rt);
}
int query(int L, int R, int l, int r, int rt){if(L <= l && r <= R){return tree[rt];}int mid = (l + r) / 2;int ans = 0;if(L <= mid){ans = max(ans, query(L, R, l, mid, rt * 2));}if(R > mid){ans = max(ans, query(L, R, mid + 1, r, rt * 2 + 1));}return ans;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, m;cin >> n >> m;for(int i = 1; i <= m; i++){cin >> arr[i];} build(1, m, 1);int q;cin >> q;while(q--){int a, b, c, d, k;cin >> a >> b >> c >> d >> k;if(b > d){swap(a, c);swap(b, d);}if(abs(a - c) % k != 0 || (b - d) % k != 0){cout << "NO" << endl;}else if(a <= arr[b] || c <= arr[d]){cout << "NO" << endl;}else{int maxn = (a + (n - a) / k * k);int maxx = query(b, d, 1, m, 1);if(maxx >= maxn){cout << "NO" << endl;}else{cout << "YES" << endl;}}}return 0;
}
