A - First ABC 2
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
using vi = vector<int>;
using pii = pair<int, int>;
void solve() {
int n;
string s;
cin >> n >> s;
auto it = s.find("ABC");
if( it >= n ) cout << "-1\n";
else cout << it + 1 << "\n";
return ;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
solve();
return 0;
}
B - Prefix and Suffix
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
using vi = vector<int>;
using pii = pair<int, int>;
void solve() {
int n, m;
cin >> n >> m;
string s, t;
cin >> s >> t;
int ans = 0;
for (int i = 0; i < n; i++) {
if (s[i] == t[i]) continue;
ans += 2;
break;
}
reverse(s.begin(), s.end());
reverse(t.begin(), t.end());
for (int i = 0; i < n; i++) {
if (s[i] == t[i]) continue;
ans += 1;
break;
}
cout << ans << "\n";
return;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
solve();
return 0;
}
C - Festival
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
using vi = vector<int>;
using pii = pair<int, int>;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m;
cin >> n >> m;
vi a(m);
for (auto &i: a) cin >> i;
reverse(a.begin(), a.end());
for( int i = 1 ; i <= n ; i ++ ){
cout << a.back() - i << "\n";
if( a.back() == i ) a.pop_back();
}
return 0;
}
D - Polyomino
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
using vi = vector<int>;
using pii = pair<int, int>;
using node = array<string, 4>;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
vector<node> g(3);
int cnt = 0;
for (auto &it: g)
for (auto &i: it) {
cin >> i;
cnt += count(i.begin(), i.end(), '#');
}
auto rotate = [](const node &a) {
auto b = a;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
b[j][3 - i] = a[i][j];
return b;
};
array<array<char, 4>, 4> page;
auto fit = [&](int k, int x, int y) {
for (int i = 0, nx = x; i < 4; i++, nx++)
for (int j = 0, ny = y; j < 4; j++, ny++) {
if (g[k][i][j] == '.') continue;
if (nx < 0 or nx > 3 or ny < 0 or ny > 3) return false;
if (page[nx][ny] == '#') return false;
page[nx][ny] = '#';
}
return true;
};
auto dfs = [&](auto &&self, int i) -> bool {
if (i == 3) return true;
auto bak = page;
for (int x = -3; x <= 7; x++)
for (int y = -3; y <= 7; y++) {
for (int t = 0; t < 4; t++) {
if (fit(i, x, y) and self(self, i + 1))
return true;
g[i] = rotate(g[i]), page = bak;
}
}
return false;
};
if (cnt == 16 and dfs(dfs, 0))
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
E - Product Development
相对来说是一个比较板的 01 背包问题,只是状态的表示比较麻烦,所以可以状压一下。
#include<bits/stdc++.h>
using namespace std;
#define int long long
using i32 = int32_t;
using vi = vector<int>;
const int inf = 1e18;
i32 main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, k, p;
cin >> n >> k >> p;
int base = p + 1;
const int N = (int) (pow(base, k));
vi f(N , inf);
f[0] = 0;
auto dtr = [k, base](int x) {
vi ret(k);
for (int i = k - 1; i >= 0; i--)
ret[i] = x % base, x /= base;
return ret;
};
auto tr = [k, base](const vi &x) {
int res = 0;
for (int i = 0; i < k; i++) res = res * base + x[i];
return res;
};
for (int i = 0, c; i < n; i++) {
cin >> c;
vi a(k);
for (auto &j: a) cin >> j;
auto g = f;
for (int i = 0; i < N; i++) {
auto lst = dtr(i);
for (int j = 0; j < k; j++)
lst[j] = min(p, lst[j] + a[j]);
auto nxt = tr(lst);
g[nxt] = min(g[nxt], f[i] + c);
}
f.swap(g);
}
if (f.back() == inf) cout << "-1\n";
else cout << f.back() << "\n";
return 0;
}
- Beginner AtCoder Contest 322beginner atcoder contest 322 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 315