A - Leftrightarrow
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ldb = long double;
#define int long long
using vi = vector<int>;
using pii = pair<int, int>;
const int mod = 1e9 + 7;
const int inf = 1e18;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
string s;
cin >> s;
if (s.front() == '<' and s.back() == '>' and s.substr(1, s.size() - 2) == string(s.size() - 2, '=')) {
cout << "Yes\n";
} else {
cout << "No\n";
}
return 0;
}
B - Integer Division Returns
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ldb = long double;
#define int long long
using vi = vector<int>;
using pii = pair<int, int>;
const int mod = 1e9 + 7;
const int inf = 1e18;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int x;
cin >> x;
if(x > 0 ) cout << ( x + 9 ) / 10 << "\n";
else cout << x / 10 << "\n";
return 0;
}
C - One Time Swap
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ldb = long double;
#define int long long
using vi = vector<int>;
using pii = pair<int, int>;
const int mod = 1e9 + 7;
const int inf = 1e18;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
map<char, int> cnt;
string s;
cin >> s;
for (auto i: s) cnt[i]++;
int sum = s.size(), res = 0, f = 0;
for (auto i: s) {
sum--, cnt[i]--;
res += sum - cnt[i], f |= cnt[i] > 0;
}
cout << res + f << "\n";
return 0;
}
D - Tiling
可以直接暴搜,但是暴搜也是要有一些技巧
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ldb = long double;
using vi = vector<int>;
using pii = pair<int, int>;
const int mod = 998244353;
const int inf = 1e18;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, h, w;
cin >> n >> h >> w;
vi a(n), b(n);
for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
vector f(h, vi(w));
vi vis(n);
auto dfs = [&](auto self, int x, int y) -> void {
if (x == h) {
cout << "Yes\n";
exit(0);
}
if (y == w) return self(self, x + 1, 0);
if (f[x][y]) return self(self, x, y + 1);
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
vis[i] = 1;
for (int t = 0, ok; t < 2; t++) {
swap(a[i], b[i]);
if( x + a[i] > h or y + b[i] > w ) continue;
ok = 1;
for (int u = 0; ok and u < a[i]; u++)
for (int v = 0; ok and v < b[i]; v++)
if (f[x + u][y + v]) ok = 0;
if (not ok) continue;
for (int u = 0; u < a[i]; u++)
for (int v = 0; v < b[i]; v++)
f[x + u][y + v] = 1;
self(self, x, y + 1);
for (int u = 0; u < a[i]; u++)
for (int v = 0; v < b[i]; v++)
f[x + u][y + v] = 0;
}
vis[i] = 0;
}
};
dfs(dfs, 0, 0);
cout << "No\n";
return 0;
}
E - Colorful Subsequence
有 \(N\) 个球,每一个球有一个颜色 \(C_i\) 和价值 \(V_i\),现在要删除其中的 \(K\) 个球,使得剩下的球没有相邻的两个球颜色相等。求剩下的球的最大价值总和。
设\(f[i][j]\)表示为前\(i\)个球删掉\(j\)个且钦定保留第\(i\)个球的最大价值总和。
假设剩下\(s\)个球,则$s = i - j \(,显然可以得到\)s\le i \le s + k\(,如果我们枚举出了\)i,s$就可以得到转移
\[f[i][i-s] = \max_{s \le p \le i, C_p\ne C_i}(f[p-1][p-s]) + v[i] \]比如我们枚举出了\(i=4,s=1\),则我们要求的就是\(f[4][3]=\max(f[3][3] , f[2][2], f[1][1],f[0][0]) + v[4]\)
所以其实我们可以统计出前缀最大值,以及与前缀最大值不同的前缀次大值的,然后根据颜色是否相同判断选择那个即可。
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
using ldb = long double;
#define int long long
using vi = vector<int>;
using pii = pair<int, int>;
const int mod = 998244353;
const int inf = 1e18;
const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, k;
cin >> n >> k;
vi C(n + 2), V(n + 2);
for (int i = 1; i <= n; i++) cin >> C[i] >> V[i];
C[0] = n + 1, C[n + 1] = n + 2;
n += 2;
vector f(n, vi(k + 1, -inf));
f[0][0] = 0;
for (int s = 1; s <= n - 1 - k; s++) {
pii mx[2] = {{-inf, 0},// 最大值
{-inf, 0}}; // 与最大值颜色不同的 次大值
for (int i = s; i <= s + k; i++) {
pii v = {f[i - 1][i - s], C[i - 1]};
if (v > mx[0])
swap(v, mx[0]);
if (mx[0].second == mx[1].second || (v > mx[1] and v.second != mx[0].second))
mx[1] = v;
f[i][i - s] = mx[mx[0].second == C[i]].first + V[i];
}
}
cout << max(-1ll, f[n - 1][k]) << "\n";
return 0;
}
标签:AtCoder,const,Beginner,int,vi,cin,long,345,using
From: https://www.cnblogs.com/PHarr/p/18083869