A. Forked!
题意：有骑士，国王，王后，给出骑士的攻击方式，骑士的攻击方式类似象棋中的马，一个方向长度为1，一个方向长度为2，有8个位置，骑士的两方向攻击长度为a，b，当a，b不等的时候，有8个位置，相同则有4个位置，询问骑士能同时攻击到国王和王后的位置有几个(采用多组输入形式) 范围：给出值<=1e8，骑士坐标不限制，坐标可以为负值
分析：枚举
代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
int n;
string str;
int d[4][2] = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
int a, b, x, y, x2, y2;
bool judge(int x, int y) {
x = abs(x2 - x);
y = abs(y2 - y);
if (x == a && y == b) return true;
if (x == b && y == a) return true;
return false;
}
void sol() {
cin >> a >> b;
cin >> x >> y;
cin >> x2 >> y2;
int sum = 0;
for (int i = 0; i < 4; i++)
if (judge(x + d[i][0] * a, y + d[i][1] * b))
sum++;
if (a != b) {
swap(a, b);
for (int i = 0; i < 4; i++)
if (judge(x + d[i][0] * a, y + d[i][1] * b))
sum++;
}
cout << sum << endl;
}
int main() {
int t = 1;
cin >> t;
while (t--)
sol();
return 0;
}
B. Collecting Game
题意：给出n，给出n个数，最初有个初始值，每次可以拿取低于拿取数的和的数，输出如果第i个数为初始值拿取，那么还可以拿取几个数(采用多组输入形式)范围：0 <= a[i] <= 1e9, n <= 1e5
分析：能加就加，sort排序后，进行前缀和，进行判断，拿第i个就拿到了所有比它低的物品，判断是否能拿到下一级的物品。
代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
typedef pair<int, int> PII;
int n;
int s[N];
PII p[N];
ll sum[N];
string str;
void sol() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> p[i].first;
p[i].second = i;
}
sort(p, p + n);
sum[0] = p[0].first;
for (int i = 1; i < n; i++)
sum[i] = sum[i-1] + p[i].first;
s[p[n-1].second] = n - 1;
for (int i = n - 2; i >= 0; i--) {
if (sum[i] >= p[i+1].first)
s[p[i].second] = s[p[i+1].second];
else
s[p[i].second] = i;
}
for (int i = 0; i < n; i++)
cout << s[i] << ' ';
cout << endl;
}
int main() {
int t = 1;
cin >> t;
while (t--)
sol();
return 0;
}
C. Array Game
题意：题意：给出n，给出n个数，最多允许k次操作，每次可以在范围内任意选i,j（i≠j），将abs(a[i] - a[j])放入到n+1的位置上，长度n变为n+1，求操作后数组最小值(采用多组输入形式)
范围：1 <= a[i] <= 1e18, n <= 2e3
分析：连续两次选一样的，k≥3，答案为0，为0，最小值，为1算一次，为2就查两次，枚举两个数的差值。
代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 4e6 + 10;
typedef long long ll;
typedef pair<int, int> PII;
int n, k;
ll s[N];
PII p[N];
//ll sum[N];
string str;
int ef(ll x) {
int l = 1, r = n;
while (l < r) {
int mid = l + r >> 1;
if (s[mid] < x)
l++;
else
r--;
}
return l;
}
void sol() {
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> s[i];
sort(s + 1, s + n + 1);
if (k >= 3) {
cout << 0 << endl;
return;
}
ll sum = s[1];
for (int i = 2; i <= n; i++)
sum = min(sum, s[i] - s[i-1]);
if (k == 1) {
cout << sum << endl;
return;
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1, k = 1; j <= n; j++) {
ll ans = s[j] - s[i];
while (k < n && s[k] < ans) k++;
if (k == 1) sum = min(sum, abs(ans - s[1]));
else sum = min(sum, min(s[k] - ans, ans - s[k-1]));
}
}
cout << sum << endl;
}
int main() {
int t = 1;
cin >> t;
while (t--)
sol();
return 0;
}
D Set To Max
题意：给出n，以下n组，每组给出a数组和b数组，变化操作为，选择l，r，将l到r范围内的数都变为l到r范围内数的最大值，问进行这样的操作，可否能将a数据变为b数组。
分析：每次只能从小变大，所以对于b数组的每个值，a数组的值都不可能会更大，对于b数组连续同样的值，直接一起讨论，对于a数组，这段连续最大的值必须是b数组对应位置的值，如果a数组这段区间内最大的值都比b数组该位置的值小，那么可以从左边或者右边多延长一点，使得找到该值，当然在范围内的值一样要小于该值，所以这种做法导致了后面的值会把前面的值覆盖，所以必须从大到小去讨论，连续最大值或最小值用st表去算，知道每个位置左边某个值在哪个位置可以预处理用map记录一下去讨论。
代码：
#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include<cmath>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
typedef pair<int, int> PII;
int n, k;
int s[N], g[N], l[N], r[N];
int st[N][20], st1[N][20];
string str;
map<int, int> ma;
queue<int> q;
struct node {
int w;
int l, r;
};
vector<node> vec;
bool cmp(node a, node b) {
return a.w > b.w;
}
void init() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> s[i];
for (int i = 1; i <= n; i++) cin >> g[i];
for (int i = 1; i <= n; i++) ma[i] = 0;
for (int i = 1; i <= n; i++) {
ma[s[i]] = i;
l[i] = ma[g[i]];
}
for (int i = 1; i <= n; i++) ma[i] = n + 1;
for (int i = n; i >= 1; i--) {
ma[s[i]] = i;
r[i] = ma[g[i]];
}
for (int i = 1; i <= n; i++) {
st[i][0] = s[i];
st1[i][0] = g[i];
}
for (int j = 1; j <= 20; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
st[i][j] = max(st[i][j-1], st[i + (1 << j - 1)][j-1]);
st1[i][j] = min(st1[i][j-1], st1[i + (1 << j - 1)][j-1]);
}
}
}
int query(int l, int r)
{
int len = r - l + 1;
int k = log(len) / log(2);
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
int query1(int l, int r)
{
int len = r - l + 1;
int k = log(len) / log(2);
return min(st1[l][k], st1[r - (1 << k) + 1][k]);
}
bool judge() {
int a = 1;
for (int i = 2; i <= n; i++) {
if (g[i] != g[i-1]) {
vec.push_back({g[i-1], a, i - 1});
a = i;
}
}
vec.push_back({g[n], a, n});
sort(vec.begin(), vec.end(), cmp);
for (int i = 0; i < vec.size(); i++) {
node a = vec[i];
int b = query(a.l, a.r);
if (b > a.w) return false;
if (b == a.w) {
continue;
}
b = n + 1;
int c = n + 1;
if (r[a.l] < n && query1(a.l, r[a.l]) >= a.w) {
b = query(a.l, r[a.l]);
}
if (l[a.r] > 0 && query1(l[a.r], a.r) >= a.w) {
c = query(l[a.r], a.r);
}
b = min(b, c);
if (b != a.w) return false;
}
return true;
}
void sol() {
init();
if (judge()) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
vec.clear();
}
int main() {
int t = 1;
cin >> t;
while (t--)
sol();
return 0;
}