AtCoder Beginner Contest 318
A - Full Moon (atcoder.jp)
以\(M\)为首项,\(P\)为公差,看\(1 \sim N\)里包含了多少项的个数
#include<bits/stdc++.h>
using i64 = long long;
using namespace std;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N,M,P;
cin >> N >> M >> P;
cout << 1ll * max(N - M, 0) / P + (N >= M) << '\n';
return 0;
}
B - Overlapping sheets (atcoder.jp)
数据不大,直接枚举即可
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
i64 ans = 0;
vector<bitset<110>> g(110, 0);
for (int i = 0; i < N; i ++) {
int A, B, C, D;
cin >> A >> B >> C >> D;
for (int j = A; j < B; j ++)
for (int k = C; k < D; k ++)
g[j][k] = 1;
}
for (int i = 0; i < 100; i ++)
for (int j = 0; j < 100; j ++)
ans += g[i][j];
cout << ans << '\n';
return 0;
}
C - Blue Spring (atcoder.jp)
题意就是在\(N\)天的旅游中,每天会花费\(A_i\)元,但是可以花费\(P\)元使得\(D\)天的花费免费,这\(D\)天可以是分开的.
我们可以将每天的费用从大到小排序,做一个前缀和,将\(D\)天内的花费与\(P\)做一个比较,取其小的费用即可
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 N, D;
i64 ans = 0, P;
cin >> N >> D >> P;
vector<i64> F(N + D + 1);
for (int i = 1; i <= N; i ++)
cin >> F[i];
sort(F.begin() + 1, F.begin() + N + 1,greater<>());
for (int i = 1; i <= N + D; i ++)
F[i] += F[i - 1];
for (int i = D; i <= N + D; i += D)
ans += min(P, F[i] - F[i - D]);
cout << ans << '\n';
return 0;
}
D - General Weighted Max Matching (atcoder.jp)
\(N\)最多只有\(16\),可以直接\(dfs\)暴搜(
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<vector<int>> g(N + 1, vector<int>(N + 1));
for (int i = 1, D; i < N; i ++) {
for (int j = i + 1; j <= N; j++) {
cin >> g[i][j];
g[j][i] = g[i][j];
}
}
bitset<20> vis;
i64 ans = 0;
auto dfs = [&](auto self, int n, i64 sum) ->void{
if (n > N) {
ans = max(ans, sum);
return ;
}
if (!vis[n]) {
vis[n] = 1;
for (int i = n + 1; i <= N; i ++) {
if (!vis[i]) {
vis[i] = 1;
self(self, n + 1, sum + g[i][n]);
vis[i] = 0;
}
}
vis[n] = 0;
}
self(self, n + 1, sum);
};
dfs(dfs,1,0);
cout << ans << '\n';
return 0;
}
E - Sandwiches (atcoder.jp)
对于\(A_i\)和\(A_k\),设其中间的长度为\(L\),当只有这两个点相等时,则这两个点的贡献为\(L\),若\(A_i\)左边还有点,则它们可以与\(A_k\)产生\(Num_左 \times L\)的贡献,同理,\(A_k\)右边还有点的话则与\(A_i\)产生\(Num_右 \times L\)的贡献,所以对于相邻的两个值相等的点产生的贡献为\(L(k-i-1(不包括A_i和A_k)) \times 左边点 \times 右边点\)
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<i64> A(N), g[N + 1];
for (int i = 0; i < N; i ++) {
cin >> A[i];
g[A[i]].emplace_back(i);
}
i64 ans = 0;
for (int i = 1; i <= N; i ++) {
for (int j = 1; j < g[i].size(); j ++) {
ans += (g[i][j] - g[i][j - 1] - 1) * j * (g[i].size() - j);
}
}
cout << ans << '\n';
return 0;
}
- Beginner AtCoder Contest 318beginner atcoder contest 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 beginner atcoder contest 315 beginner atcoder contest 334