B - Overlapping sheets
难度: ⭐
题目大意
在一个坐标系中给出覆盖多个矩形, 问最后所有矩形覆盖的总面积是多少;
解题思路
坐标系的范围不大, 标记后遍历即可; 还是要注意给的是坐标系的点, 计算的是边;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
bool st[110][110];
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
for (int x = a + 1; x <= b; x++) {
for (int y = c + 1; y <= d; y++) {
st[x][y] = true;
}
}
}
for (int i = 1; i <= 100; i++) {
for (int j = 1; j <= 100; j++) {
if (st[i][j]) idx++;
}
}
cout << idx;
return 0;
}
C - Blue Spring
难度: ⭐⭐
题目大意
小莫要在宾馆待n天, 宾馆第i天的住宿费用为fi; 小莫还可以选择宾馆的套餐, 支付p元可以在宾馆住d天, 这d天可以随意分配; 问小莫怎么选择可以支付最少费用;
解题思路
因为套餐的天数可以随意分配, 所以我们可以先把每天的住宿费用从大到小遍历, 然后计算当前的花费的总费用x, 如果遍历到第i个时, x>=p并且天数idx<=d, 那么这些天用套餐度过会更便宜, 决定使用套餐后我们就可以把idx和d之间差的那几天跳过就可, 即从第(i+ d - idx)个看起, 别忘了天数idx和费用x清零;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int f[N];
signed main() {
int k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
cin >> f[i];
}
sort(f + 1, f + 1 + n,greater<int>());
int x = 0, y = 0;
for (int i = 1; i <= n; i++) {
x += f[i];
idx++;
if (idx <= m && x >= k) {
i += (m - idx);
idx = 0;
x = 0;
y += k;
}
}
cout << y + x;
return 0;
}
D - General Weighted Max Matching
难度: ⭐⭐⭐
题目大意
在一个无向有权图中有n个节点, 每两个点之间都有一条带权边, 我们需要从中选出若干条边, 要求是这些边的端点各不相同, 即对于边a-b和c-d: a!=c, a!=d, b!=c, b!=d; 问可以得到的边权值和最大为多少;
解题思路
因为n最大为16, 所以我们可以考虑用状压dp来做, 当然dfs暴搜也能做但是不如状压好写; 状态表示dp[i]表示状态为i的权值和最大为多少, 对于状态i是一个n的二进制, 每一位表示一个节点是否被选择, 也就是说每选择一条边都会有两个点被选择, 也就是二进制的两个位置由0变为1; 并且题目要求每条边的端点各不相同, 所以如果状态i中1的个数是奇数说明该状态不合法; 综上所述, 对于状态转移我们可以从状态i中为1的位置中挑出两个j和k, 说明这次我们选择了j+1和k+1之间的边, 即dp[i] = max(dp[i], dp[i - (1 << j) - (1 << k)] + f[j + 1][k + 1]), 在状态转移的过程中顺便记录最大值就行;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
int f[20][20];
int dp[1 << 17];
signed main() {
cin >> n;
int res = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
cin >> f[i][j];
}
}
for (int i = 1; i < 1 << n; i++) {
int num = 0;
for (int j = 0; j < n; j++) {
if ((i >> j) & 1) num++;
}
if (num % 2) continue;
for (int j = 0; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (((i >> j) & 1) && ((i >> k) & 1)) {
int h = i - (1 << j) - (1 << k);
dp[i] = max(dp[i], dp[h] + f[j + 1][k + 1]);
res = max(res, dp[i]);
}
}
}
}
cout << res;
return 0;
}
E - Sandwiches
难度: ⭐⭐⭐
题目大意
给定一个长度为n的数列Ai, 请问其中有多少个满足条件的三元组(i, j, k);
条件是: Ai = Ak, Ai != Aj;
解题思路
这题可以线性解决, 从头遍历整个数列, 设当前位置是x, 我们用一个数组res[x]表示当三元组中k = x时有多少满足条件的三元组, 很明显k前面必须要有一个Ak相同的数, 所以设p[Ax]表示左边距离第x个数最近的Ax的位置在哪; 通过题目条件我们发现res[x]是可以从res[p[Ax]]继承过来的, res[p[Ax]]是指三元组中k = p[Ax]时有多少种三元组, 我们把k从p[Ax]换成x同样也是合法的三元组; 然后我们再分析之前没有的三元组, 新的三元组无非就是因为从p[Ax]到x之间有(x - p[Ax] - 1)个不为Ak的值, 所以我们可以把k固定为x, j从这(x - p[Ax] - 1)中选, i就可以从x之前所有值为Ax的位置中选, 所以我们再开一个数组f[Ax]表示截止到第x个数之前有多少个值为Ax的数, 所以最后得到计算式: res[x] = res[p[Ax]] + f[Ax] * (x - p[Ax] - 1); 最后再把每个位置上的res[i]加起来即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 3e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx, maxn;
int f[N], p[N], res[N];
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
maxn = max(maxn, x);
if (p[x]) {
res[i] = res[p[x]] + f[x] * (i - p[x] - 1);
}
f[x]++;
p[x] = i;
}
for (int i = 1; i <=n; i++) idx += res[i];
cout << idx;
return 0;
}
F - Octopus
难度: ⭐⭐⭐⭐
题目大意
在x轴上有一个章鱼, 章鱼有n个触手, 每个触手的长度为Li; 同时x轴上也有n个宝藏位置为Ni; 章鱼想获得宝藏有两种方式, 一是自己本身就在那个位置, 二是触手可以从够到那个位置; 设章鱼的位置在k, 那么如果k + Ai >= Ni 或者k - Ai <= Ni就说明该触手可以够到该宝藏; 如果章鱼想得到所有宝藏, 请问章鱼的位置k有多少种可以满足;
解题思路
由于本题的位置范围过大, 肯定是不能从每个位置下手, 所以我们要考虑区间; 再次之前我们先考虑如果已经确定了位置k, 我们该如何判定该位置是否合法; 我们可以把所有宝藏到位置k的相对距离Di从小到大排序, 然后把触手长度也从小到大排序, 让他们一一对应, 看是否每个Li都大于等于Di即可; 从上述方法种我们发现对于一个位置k, 他会让每个触手和宝藏实现一一对应的关系, 那么如果移动了k, 但是触手和宝藏之间的对应关系却没有变化, 那么移动后的k肯定也是合法的, 我们继续移动k直到触手和宝藏的对应关系发生了变化, 设最初是k值为l, 最后为r, l到r肯定是一段连续的区间, 这样我们就找到了可以用于计算的区间;
所以现在就是需要确定所有的区间, 那什么时候触手和宝藏的对应关系会发生变化呢, 那就是某个宝藏处于某个触手的边缘位置, 只要章鱼位置再移动一格, 宝藏就会离开触手范围, 对应关系就会发生变化; 那具体哪几个边界是我们所需要的呢, 遍历就可以了, 毕竟题目给的n的范围只有200个; 首先我们把所有上述情况的位置k找到并存在下来, 找的过程无非就是先遍历所有宝藏再遍历所有触手, k的位置就是X[i] + L[j]和X[i] - L[j]; 把这些k从小到大排序后去重就可以哪来确定有效区间了; 我们遍历这些区间(如果有m个区间端点k, 说明就m-1个区间(i和i+1)), 设左端点是l, 右端点是r; k在l时刚好可以够到一个宝藏, k在r时也刚好可以够到一个宝藏; 所以从[l+1, r-1]之间没有位置可以刚好够到一个宝藏, 所以整个区间内对应关系不变, 所以我们只检查l+1这个位置即可, 如果l+1合法, 那么区间[l+1, r-1]内的值都合法; 因为端点l和r是引起对应关系变化的位置, 所以我们最后再检查所有端点即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 3e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
int X[210], L[210], D[210];
vector<int> v;
bool check(int k) {
for (int i = 1; i <= n; i++) {
D[i] = abs(X[i] - k);
}
sort(D + 1, D + n + 1);
bool f = true;
for (int i = 1; i <= n; i++) {
if (L[i] < D[i]) {
return false;
}
}
return true;
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> X[i];
for (int i = 1; i <= n; i++) cin >> L[i];
sort(L + 1, L + n + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
v.push_back(X[i] + L[j]);
v.push_back(X[i] - L[j]);
}
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 0; i < v.size() - 1; i++) {
if (check(v[i] + 1)) res += v[i + 1] - v[i] - 1;
}
for (int i = 0; i < v.size(); i++) {
if (check(v[i])) res++;
}
cout << res;
return 0;
}