Codeforces Round 995 (Div. 3)【题解】D ~ G

比赛地址传送门

D.Counting Pairs

在这里插入图片描述

注意到确定一个数后，第二个数可以一个范围内任选。
故排序+二分查找上下界后计数

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 4e5 + 10;int n, x, y;
int a[N];void solve() {cin >> n >> x >> y;for (int i = 1; i <= n; i ++)cin >> a[i];sort(a + 1, a + 1 + n);long long sum = 0;for (int i = 1; i <= n; i ++) {sum += a[i];}long long ans = 0;for (int i = 1; i <= n; i ++) {int l1 = 1, r1 = n;while (l1 != r1) {int mid = l1 + r1 >> 1;if (sum - (a[mid] + a[i]) <= y) {r1 = mid;} elsel1 = mid + 1;}int l2 = 1, r2 = n;while (l2 != r2) {int mid = l2 + r2 + 1 >> 1;if (sum - (a[mid] + a[i]) >= x) {l2 = mid;} elser2 = mid - 1;}if (sum - a[l1] - a[i] >= x && sum - a[l1] - a[i] <= y&& sum - a[l2] - a[i] >= x && sum - a[l2] - a[i] <= y) {if (l1 <= l2) {ans += l2 - l1 + 1;if (i <= l2 && i >= l1)ans --;}}}cout << ans / 2 << '\n';
}signed main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while (t --) {solve();}return 0;
}

E.Counting Pairs

在这里插入图片描述

如果只有1件物品，设定的价格只可能是 a1、b1
所以，虽然价格设定的范围为1~1e9，但并不是每一个价格都有可能（PS：有点离散化的意思在）
故从最终答案考虑，我们只需要枚举全部ai和bi即可。但是为了判断印象不好的顾客是否不超过k，和统计当前可购买的人数，还需要额外枚举ai+1和bi+1以更新上述两个数据

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;int n, k;
int a[N], b[N];
int st[N];
long long ans;void solve() {ans = 0;cin >> n >> k;for (int i = 1; i <= n; i ++)cin >> a[i];for (int i = 1; i <= n; i ++)cin >> b[i];priority_queue<PII, vector<PII>, greater<PII>> heap;int mi = 1e18;for (int i = 1; i <= n; i ++) {heap.push({a[i], i});st[i] = -1;}int cnt = n, neg = 0;while (!heap.empty()) {auto t = heap.top();int price = t.first;int negadd = 0;while (!heap.empty() && heap.top().first == price) {auto i = heap.top();heap.pop();int k = i.second;if (st[k] == -1) {st[k] ++;heap.push({a[k] + 1, k});} else if (st[k] == 0) {st[k] ++;neg ++;heap.push({b[k], k});} else if (st[k] == 1) {st[k] ++;heap.push({b[k] + 1, k});} else {neg --;cnt --;}}if (neg <= k) {ans = max(ans, cnt * price);}}cout << ans << '\n';
}signed main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while (t --) {solve();}return 0;
}

F. Joker

在这里插入图片描述

鬼牌最终可能在的位置是三段连续区间，看出这个这题有了。
三段分别是，中间一段、顶部一段、底部一段。
观察一组例子，发现如果抽的牌在鬼牌的下方，那么放回下方时，鬼牌位置不变；放回上方时，鬼牌位置向下移动一位。同理，鬼牌在上方类似。但是如果被抽走的牌是鬼牌，鬼牌就要么去排顶要么去排底。
那么，既然是三段连续区间，统计鬼牌可能区间的长度即是答案。
用四个变量分别维护，排顶、排底、中段上、中段下即可。统计答案时注意区间的重合问题。
有一个特例是，第一次就抽走鬼牌，那么中间段将消失。

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;int n, m, q;void solve() {cin >> n >> m >> q;long long ans = 0;int top = -1, bottom = -1;bool flag = false, flag2 = false;;int l = m, r = m;while (q --) {int x;cin >> x;if (!flag2 && x <= r && x >= l) {if (!flag) {flag = 1;top = 1, bottom = n;if (l == r) {flag2 = 1;}} else {if (x < bottom) {bottom --;}if (x > top) {top ++;}}} else {if (flag) {if (x < bottom) {bottom --;}if (x > top) {top ++;}}if (!flag2) {if (x < l) {l --;}if (x > r) {r ++;}}}if (!flag) {ans = r - l + 1;} else {if (flag2) {if (bottom <= top) {ans = n;} elseans = top + n - bottom + 1;} else {if (bottom <= r && top >= l) {ans = n;} else if (bottom <= r && top < l) {ans = n - l + 1 + top;} else if (bottom > r && top >= l) {ans = r + n - bottom + 1;} else {ans = r - l + 1 + top + n - bottom + 1;}}}cout << ans << ' ';}cout << '\n';
}signed main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;cin >> t;while (t --) {solve();}return 0;
}

G.Snakes

在这里插入图片描述

n <= 20，很特殊的数据范围，这个范围的典型算法就是爆搜和状压dp。
蛇之间越紧密越好，不犯规的情况下空隙尽量小。
定义dp[i][j]，n位二进制数 i 表示当前状态，i 的第 k 位为 1 表示该状态使用了第 k 条蛇，为 0 表示不使用。再增开一个状态表示当前结尾的是第 i 条蛇。
转移就是枚举下一条蛇，用二者之间的最短距离更新。如下:

   //i为当前状态，ne为下一状态//j为当前结尾的蛇的编，k是下一条蛇的编号，dist[i][j]为二者最短距离int ne = i + (1ll << (k - 1));dp[ne][k] = min(dp[ne][k], dp[i][j] + dist[j][k] + 1);

此dp时间复杂度为 $o(2^nn^2)$ 略高，带值后达4e8，但时限3s且dp的常数较小，2906 ms 极限通过。
dist[i][j] 可预处理出，枚举两条蛇后遍历整个操作序列处理即可。

#include <bits/stdc++.h>
#define int long longusing namespace std;typedef pair<int, int> PII;
const int N = 22, M = 1024 * 1024 + 10;int dist[N][N];
int dp[M][N];
int a[200010], b[200010];
int n, q;void solve() {cin >> n >> q;for (int i = 1; i <= q; i ++) {int x;char y;cin >> x >> y;a[i] = x, b[i] = y;}for (int i = 0; i <= n; i ++)for (int j = 0; j <= n; j ++) {if (i == j)continue;int d = 0;for (int k = 1; k <= q; k ++) {if (a[k] == i) {if (b[k] == '+')d ++;} else if (a[k] == j) {if (b[k] == '-')d --;}dist[i][j] = max(dist[i][j], d);}}int mx = (1 << n) - 1;for (int i = 0; i <= mx; i ++) {for (int j = 0; j <= n; j ++) {dp[i][j] = 1e18;}}dp[0][0] = 0;for (int j = 1; j <= n; j ++) {int ne = 1ll << (j - 1);dp[ne][j] = dist[0][j] + 1;}for (int i = 1; i <= mx; i ++) {for (int j = 1; j <= n; j ++) {for (int k = 1; k <= n; k ++) {if ((i >> (k - 1)) & 1)continue;//i为当前状态，ne为下一状态，dist为二者最短距离int ne = i + (1ll << (k - 1));dp[ne][k] = min(dp[ne][k], dp[i][j] + dist[j][k] + 1);}}}long long ans = 1e18;for (int i = 1; i <= n; i ++) {ans = min(ans, dp[mx][i] + dist[i][0]);}cout << ans << '\n';
}signed main() {ios::sync_with_stdio(false);cin.tie(0);int t = 1;//cin >> t;while (t --) {solve();}return 0;
}