「解题报告」freee Programming Contest 2023(AtCoder Beginner Contest 310)
比赛地址:freee Programming Contest 2023(AtCoder Beginner Contest 310) - AtCoder
后记:原本写了比较详细的题解,但是,突发意外情况,它没了,所以这份题解略写了。归根结底还是懒
A - Order Something Else
贪心的选价格最小的和优惠券一起使用,最后和原价比大小即可。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 110;
int n, q, p, mn = 1e9;
int d[N];
int main() {
n = read<int>(), p = read<int>(), q = read<int>();
for (int i = 1, x; i <= n; ++ i) {
x = read<int>();
mn = min(x, mn);
}
cout << min(p, q + mn) << '\n';
return 0;
}
B - Strictly Superior
B - Strictly Superior (atcoder.jp)
按照题意模拟即可。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 110;
int n, m;
int f[N][N], p[N], c[N];
bitset<N> vis[N];
int main() {
n = read<int>(), m = read<int>();
for (int i = 1; i <= n; ++ i) {
p[i] = read<int>(), c[i] = read<int>();
for (int j = 1; j <= c[i]; ++ j) {
vis[i].set(read<int>());
}
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= n; ++ j) {
if (i == j) continue ;
if (p[i] == p[j]) {
if (((vis[i] & vis[j]) == vis[i]) && (c[j] > c[i])) {
puts("Yes");
return 0;
}
}
else if (p[i] > p[j]) {
if ((vis[i] & vis[j]) == vis[i]) {
puts("Yes");
return 0;
}
}
}
}
puts("No");
return 0;
}
C - Reversible
字符串哈希来判断,可以搭配 map
来食用。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 2e5 + 5;
const int based = 29;
int n, len, ans;
ull Hash1[N], Hash2[N];
char s[N];
map<ull, bool> mp;
int main() {
n = read<int>();
for (int i = 1; i <= n; ++ i) {
scanf("%s", s + 1);
len = strlen(s + 1);
Hash1[0] = 0, Hash2[len + 1] = 0;
for (int j = 1; j <= len; ++ j) {
Hash1[j] = Hash1[j - 1] * based + s[j];
}
for (int j = len; j >= 1; -- j) {
Hash2[j] = Hash2[j + 1] * based + s[j];
}
if (mp.count(Hash1[len]) || mp.count(Hash2[1])) {
continue ;
}
mp[Hash1[len]] = 1;
mp[Hash2[1]] = 1;
++ ans;
}
cout << ans << '\n';
return 0;
}
D - Peaceful Teams
D - Peaceful Teams (atcoder.jp)
由于 \(n\) 很小,所以可以直接搜索。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
int n, t, m, ans;
bool ok[15][15];
vector<int> Team[15];
void dfs(int u) {
if (u == n + 1) {
for (int i = 1; i <= t; ++ i) {
if (!Team[i].size()) {
return ;
}
}
++ ans;
return ;
}
for (int i = 1; i <= t; ++ i) {
int fg = 0;
for (int j : Team[i]) {
fg |= ok[u][j];
}
if (fg) {
continue ;
}
Team[i].emplace_back(u);
dfs(u + 1);
Team[i].pop_back();
if (!Team[i].size()) {
return ;
}
}
}
int main() {
n = read<int>(), t = read<int>(), m = read<int>();
for (int i = 1, x, y; i <= m; ++ i) {
x = read<int>(), y = read<int>();
ok[x][y] = ok[y][x] = 1;
}
dfs(1);
cout << ans << '\n';
return 0;
}
E - NAND repeatedly
E - NAND repeatedly (atcoder.jp)
假设 \(i\) 位置是 \(1\),则到 \(i - 1\) 位置的值,为 \(1\) 的全变成 \(0\),为 \(0\) 的全变成 \(1\),即交换即可,当 \(i\) 位置是 \(0\),那么所有情况都会变成 \(1\),最后统计答案即可。
/*
The code was written by yifan, and yifan is neutral!!!
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>
inline T read() {
T x = 0;
bool fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 1e6 + 5;
int n;
ll ans;
string s;
ll a[N], cnt[2];
int main() {
n = read<int>();
for (int i = 1; i <= n; ++ i) {
scanf("%1lld", &a[i]);
}
for (int i = 1; i <= n; ++ i) {
if (a[i]) {
swap(cnt[1], cnt[0]);
}
else {
cnt[1] += cnt[0];
cnt[0] = 0;
}
++ cnt[a[i]];
ans += cnt[1];
}
cout << ans << '\n';
return 0;
}
F 往后没看题,就不写了。