Codeforces Round 914 (Div. 2)
A - Forked!
解题思路:
枚举皇后和国王能被骑士吃到的位置,重合的点数就是答案。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
using ull = unsigned long long;
const ull base = 13331;
const int N = 1e6 + 10;
void solve()
{
ll a, b, x1, x2, y1, y2;
cin >> a >> b >> x1 >> y1 >> x2 >> y2;
map<pii, bool> q;
vector<ll> dx, dy;
ll ans = 0;
if (a != b)
{
dx.push_back(-a);
dx.push_back(a);
dx.push_back(b);
dx.push_back(-b);
dy.push_back(-a);
dy.push_back(a);
dy.push_back(b);
dy.push_back(-b);
for (int i = 0; i < 4; i++)
{
if (abs(dx[i]) == a)
{
for (int j = 2; j < 4; j++)
{
q[{x1 + dx[i], y1 + dy[j]}] = true;
}
}
else
{
for (int j = 0; j < 2; j++)
{
q[{x1 + dx[i], y1 + dy[j]}] = true;
}
}
}
for (int i = 0; i < 4; i++)
{
if (abs(dx[i]) == a)
{
for (int j = 2; j < 4; j++)
{
if (q[{x2 + dx[i], y2 + dy[j]}])
{
ans++;
}
}
}
else
{
for (int j = 0; j < 2; j++)
{
if (q[{x2 + dx[i], y2 + dy[j]}])
{
ans++;
}
}
}
}
}
else
{
dx.push_back(a);
dx.push_back(-a);
dy.push_back(a);
dy.push_back(-a);
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
q[{x1 + dx[i], y1 + dy[j]}] = true;
}
}
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
if (q[{x2 + dx[i], y2 + dy[j]}])
{
ans++;
}
}
}
}
cout << ans << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
B - Collecting Game
解题思路:
排序。排完序数组\(a\),前缀和数组为\(s\).
对于\(a[i]\),起码能删除\(i - 1\)个,也就是前\(i - 1\)个,后面一直往后走,直到\(a[j] > s[j- 1]\),我们能删的就是\(j - 2\)个。
所以,可以从后往前遍历。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
using ull = unsigned long long;
const ull base = 13331;
const int N = 1e6 + 10;
void solve()
{
ll n;
cin >> n;
vector<pii> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i].fi;
a[i].se = i;
}
sort(a.begin() + 1, a.end());
vector<int> ans(n + 1);
vector<ll> s(n + 1);
vector<ll> v;
for (int i = 1; i <= n; i++)
{
s[i] = a[i].fi + s[i - 1];
}
ans[a[n].se] = n - 1;
for (int i = n - 1; i; i--)
{
if (s[i] < a[i + 1].fi)
{
ans[a[i].se] = i - 1;
}
else
{
ans[a[i].se] = ans[a[i + 1].se];
}
}
// cout << endl;
// for (int i = 1; i <= n; i++)
// {
// auto idx = lower_bound(v.begin(), v.end(), i) - v.begin();
// cout << idx << ' ' << a[i].fi << ' ' << v[idx] << endl;
// if (i != v[idx])
// {
// ans[a[i].se] = v[idx] - 2;
// }
// else
// {
// ans[a[i].se] = v[idx] - 1;
// }
// }
for (int i = 1; i <= n; i++)
{
cout << ans[i] << ' ';
}
cout << endl;
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
C - Array Game
解题思路:
注意数据范围。\(O(n^2log(n^2))\)能过。
- \(k \geq 3\):答案为0.\(c = a - b,a - c = b, b - b = 0\)。
- \(k = 1\):我们从原数组和最小差中找答案。
- \(k = 2\):计算所有元素两两相减的差值,对于每一个元素二分查找最大的比他小的数和最小的比他大的数,分别相减取最小值即可。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
using ull = unsigned long long;
const ull base = 13331;
const int N = 1e6 + 10;
void solve()
{
ll n, k;
cin >> n >> k;
vector<ll> a(n + 1);
ll mina = 1e18 + 10;
for (int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
mina = min(a[i], mina);
}
if (k >= 3)
{
puts("0");
return;
}
if (k == 1)
{
sort(a.begin() + 1, a.end());
for (int i = 1; i < n; i++)
{
mina = min(mina, a[i + 1] - a[i]);
}
cout << mina << endl;
}
else
{
sort(a.begin() + 1, a.end());
for (int i = 1; i < n; i++)
{
mina = min(mina, a[i + 1] - a[i]);
}
// unordered_map<ll, bool> q;
// for (int i = n; i; i--)
// {
// for (int j = n; j > i; j--)
// {
// if (q[a[j] - a[i]] == true || q[2 * a[i]] == true)
// {
// puts("0");
// return;
// }
// }
// q[a[i]] = true;
// }
vector<ll> v;
set<ll> s;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < i; j++)
{
s.insert(abs(a[i] - a[j]));
}
}
// cout << mina << endl;
for (int i = 1; i <= n; i++)
{
auto it = s.lower_bound(a[i]);
if (it != s.end())
{
auto r = *it;
// cout << "r:" << r << endl;
mina = min(abs(r - a[i]), mina);
}
if (it != s.begin())
{
it--;
auto l = *(it);
// cout << "l:" << l << endl;
mina = min(abs(l - a[i]), mina);
}
}
cout << mina << endl;
}
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D1 - Set To Max (Easy Version)
解题思路:
\(n\)很小,直接暴力。
对于每个\(b[i]\),我们往两边扩,如果找到\(a[j] == b[i]\)就说明有解。找的过程中如果有\(a[j] > b[i]\)或者\(b[j] < b[i]\)就停止扩展。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
using ull = unsigned long long;
const ull base = 13331;
const int N = 1e6 + 10;
void solve()
{
ll n;
cin >> n;
vector<int> a(n + 1), b(n + 1), l(n + 1), r(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
}
vector<bool> st(n + 1, false);
for (int i = 1; i <= n; i++)
{
if (a[i] == b[i])
{
st[i] = true;
}
for (int j = i - 1; j; j--)
{
if (a[i] == b[j] && a[j] < b[j])
{
st[j] = true;
}
else if (b[j] < a[i] || a[j] > a[i])
{
break;
}
}
for (int j = i + 1; j <= n; j++)
{
if (a[i] == b[j] && a[j] <= b[j])
{
st[j] = true;
}
else if (b[j] < a[i] || a[j] > a[i])
{
break;
}
}
}
for (int i = 1; i <= n; i++)
{
if (!st[i])
{
puts("NO");
return;
}
}
puts("YES");
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
D2 - Set To Max (Hard Version)
解题思路:
优化上述思路:
分别找到左右第一个\(a[j] = b[i]\),我们查询区间最大\(a[j]\)和最小\(b[j]\)。若出现\(max(a[j]) == b[i]\)并且\(min(b[j]) >= b[i]\)则有解。
静态区间最值查询可用\(st\)表。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
using ull = unsigned long long;
const ull base = 13331;
const int N = 1e6 + 10;
void solve()
{
ll n;
cin >> n;
vector<int> a(n + 1), b(n + 1), l(n + 1, 1), r(n + 1, n);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
}
vector<vector<int>> f(n + 1, vector<int>(22)), g(n + 1, vector<int>(22));
for (int i = 1; i <= n; i++)
{
f[i][0] = a[i];
g[i][0] = b[i];
}
for (int j = 1; j <= 20; j++)
{
for (int i = 1; i + (1 << j) - 1 <= n; i++)
{
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
g[i][j] = min(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
}
}
auto qa = [&](int l, int r)
{
int len = r - l + 1;
int k = log(len) / log(2);
return max(f[l][k], f[r - (1 << k) + 1][k]);
};
auto qb = [&](int l, int r)
{
int len = r - l + 1;
int k = log(len) / log(2);
return min(g[l][k], g[r - (1 << k) + 1][k]);
};
set<int> sa[n + 1], sb[n + 1];
for (int i = 1; i <= n; i++)
{
sa[a[i]].insert(i);
// sb[b[i]].insert(i);
}
// cout << sa[2].size() << endl;
for (int i = 1; i <= n; i++)
{
bool f = false;
auto it = sa[b[i]].lower_bound(i);
if (it != sa[b[i]].end())
{
int r = *it;
if (qa(i, r) == b[i] && qb(i, r) >= b[i])
{
f = true;
}
}
if (it != sa[b[i]].begin())
{
it--;
int l = *it;
if (qa(l, i) == b[i] && qb(l, i) >= b[i])
{
f = true;
}
}
if (!f)
{
puts("NO");
return;
}
}
puts("YES");
}
int main()
{
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
标签:const,int,Codeforces,long,++,dx,using,914,Div
From: https://www.cnblogs.com/value0/p/17894627.html