A. Guess the Maximum
求相邻元素的最大值的最小值。
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
const int N = 2e5 + 5;
int n, m, k;
int a[N];
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int minmx = 1e9;
for (int i = 2; i <= n; i++) {
minmx = min(minmx, max(a[i - 1], a[i]));
}
cout << minmx - 1 << endl;
}
int main() {
IOS;
int tt;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
B. XOR Sequences
因为异或运算满足两数相同为0，不同为1。
期望是区间内的数ai = ia ^ x等于bi = ib ^ y。
满足条件的所有ia和ib一定满足：ia ^ ib等于x ^ y。
由于是求区间长度。寻找区间左端点，显然有无数对符合条件。
假如现在x ^ y等于z。
那么ia ^ ib也应该等于z，并且ia + 1 ^ ib + 1也等于z。
如果+1之后仍相等，那么低位+1时受影响的连续的1或0应该是相等的。
一直加到lowbit(z)那一位，再加会影响第lowbit(z) << 1位。
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
const int N = 2e5 + 5;
int x, y;
int lowbit(int x) { return x & -x; }
void solve() {
cin >> x >> y;
cout << lowbit(x ^ y) << endl;
}
int main() {
IOS;
int tt;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
C. Earning on Bets
题目要求，期望收益大于成本。
the total amount of coins you bet on all outcomes must be strictly less than the number of coins received back for each possible winning outcome
假设每个点都投资1元，对于a[i]，投资1元的期望收益是a[i]/n，总的期望收益是sum(a)/n。
需要sum(a)/n>n，假如在a[i]上再多投资1元，那么期望收益为(sum(a)+a[i])/n需大于n+1。
但如果没选到a[i]呢，损失会+1。
改动一处，会影响多处，需要尝试换个角度，减少变量数量。
如果让a[i]赢，那么投资1元的收益是a[i]，失败的损失是1，这个状态转移的难点在于，难以判断a[i]上投资增加之后，与其他a[j]上收益的关系。
- 比如我在
a[i]上多投资1元，可以影响多次下注，他们必须再多投资1元，获胜收益才能大于支出。而新的投资有可能影响其他的投资。
如果让a[i]赢，那么投资1/a[i]元的收益是1元。
现在固定收益，每个点获胜都是1元，那么成本为1/a[i], i in a。
- 如果当前方案可行，那么
1大于1/a[i], i in n
假如此时不满足这个式子，那么要么提高收益，要么降低成本，显然提高收益的同时会提高成本，降低成本的同时会降低收益，假如此时成本为1.2：
- 要增加收益，那么每个点的收益都应大于
1.2，那么分母也会放缩到1.2*1.2。 - 要减去成本，那么部分点获胜的收益会减少
0.2*a[i]，当该点获胜时，收益小于1，而此时总成本为1。如此递推，最终分子分母也会放缩成原来的1/1.2。
1/a[i]未必是整数。最小的整数就是lcm(a)，那么每个点的投资为lcm(a)/a[i]
期望的可行方案应满足：
lcm(a)大于sum(lcm(a)/a[i]) i in n
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
const int N = 2e5 + 5;
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int n;
int a[N];
void solve() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
ll L = 1;
for (int i = 1; i <= n; i++)
L = lcm(L, a[i]);
ll S = 0;
for (int i = 1; i <= n; i++)
S += L / a[i];
if (S >= L) {
cout << "-1" << endl;
return;
}
for (int i = 1; i <= n; i++) {
cout << L / a[i] << " \n"[i == n];
}
}
int main() {
IOS;
int tt;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
D. Fixing a Binary String
题意是将一个01串分成左右两个部分，左边翻转之后追加到右边。
如果有合法的中断位置，那么，长度不等于k的连续0/1段至多两个。
翻转操作，可以拼接，断点前的最后一段和整串的最后一段，对其他段无影响。
分情况讨论即可。
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
constexpr int N = 2e5 + 5;
int n, k;
string s;
int pre[N], suf[N];
void solve() {
cin >> n >> k;
cin >> s;
if (k == n) {
int cnt = count(s.begin(), s.end(), s.front());
if (cnt == n)
cout << n << endl;
else
cout << -1 << endl;
return;
}
s = ' ' + s + ' ';
pre[0] = suf[n + 1] = 1;
for (int i = 1; i <= n; i++)
pre[i] = pre[i - 1] && (i <= k || s[i] != s[i - k]);
for (int i = n; i; i--)
suf[i] = suf[i + 1] && (i >= n - k + 1 || s[i] != s[i + k]);
int cnt = 1;
for (int i = 2; i <= n; i++) {
if (s[i] != s[i - 1])
cnt = 1;
else
cnt++;
if (cnt >= k && s[i] != s[i + 1]) {
int p = i - k;
if (!p || !pre[p] || !suf[p + 1])
continue;
int flag = 1;
for (int j = n - k + 1; j <= n; j++) {
int x = p - (j + k - n) + 1;
if (x < 1)
break;
if (s[x] == s[j]) {
flag = 0;
break;
}
}
if (flag == 1) {
cout << p << endl;
return;
}
}
}
cout << -1 << endl;
return;
}
int main() {
IOS;
int tt;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
E. Manhattan Triangle
对于点i来说，曼哈顿距离为d的点，一定在一个以点i为中心，边长为$ \sqrt2d $的正方形边上。
假如正方形边框上又选定了图上这个点，那么第二点的合法点也是一个矩形，合法的交集为标注的边：
曼哈顿转切比雪夫，是将坐标系顺时针旋转45度，并放大$ \sqrt 2 $倍。
旋转前，第3点与前两点的距离都是$ \frac{d}{\sqrt2} $。
旋转后，由于放大了$ \sqrt 2 $倍，所以新的距离刚好是d。
预处理每条边，维护旋转后的横纵坐标和输入时的需要。
按新的横坐标分组并排序。
枚举每一个横坐标，他的点集应该在与x轴垂直的直线上。
- 枚举点集的每个点，找纵坐标
+d处的第2点。 - 二分搜索左右两侧的区间，有没有合法的第三点。
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
const int N = 2e5 + 5;
using pii = pair<int, int>;
using aiii = array<int, 3>;
int n, d;
aiii p[N];
aiii ans;
void fuck() {
map<int, set<pii>> mp;
for (int i = 1; i <= n; i++) {
mp[p[i][0]].insert({p[i][1], p[i][2]});
}
for (auto &x : mp) {
set<pii> line1 = x.second;
if (mp.count(x.first + d)) {
set<pii> line2 = mp[x.first + d];
for (pii it0 : line1) {
int y1 = it0.first;
auto it1 = line1.lower_bound({y1 + d, 0});
if (it1 == line1.end() || it1->first != y1 + d)
continue;
auto it2 = line2.lower_bound({y1, 0});
if (it2 == line2.end() || it2->first > y1 + d)
continue;
ans = {it0.second, it1->second, it2->second};
}
}
if (mp.count(x.first - d)) {
set<pii> line2 = mp[x.first - d];
for (pii it0 : line1) {
int y1 = it0.first;
auto it1 = line1.lower_bound({y1 + d, 0});
if (it1 == line1.end() || it1->first != y1 + d)
continue;
auto it2 = line2.lower_bound({y1, 0});
if (it2 == line2.end() || it2->first > y1 + d)
continue;
ans = {it0.second, it1->second, it2->second};
}
}
}
}
void solve() {
cin >> n >> d;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
p[i] = {x + y, x - y, i};
}
ans = {};
fuck();
for (int i = 1; i <= n; i++)
swap(p[i][0], p[i][1]);
fuck();
for (int x : ans)
cout << x << ' ';
cout << endl;
}
signed main() {
IOS;
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}