补题A-E Codeforces Round 953 (Div. 2)

https://codeforces.com/contest/1979

A. Guess the Maximum

原题链接：https://codeforces.com/contest/1979/problem/A

求相邻元素的最大值的最小值。

#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

原题链接：https://codeforces.com/contest/1979/problem/B

因为异或运算满足两数相同为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

原题链接：https://codeforces.com/contest/1979/problem/C

题目要求，期望收益大于成本。

• 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

原题链接：https://codeforces.com/problemset/problem/1979/D

题意是将一个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;elsecout << -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;elsecnt++;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

原题链接：https://codeforces.com/contest/1979/problem/E

对于点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;
}