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;
}
- Beginner AtCoder Contest 318 abcbeginner atcoder contest 318 beginner atcoder contest abc 小结atcoder abc 318 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328