ABC312 复盘
A Chord
思路解析：水题，一个 if 即可
#include<bits/stdc++.h>
using namespace std;
string s;
int main() {
cin >> s;
if(s == "ACE" || s == "BDF" || s == "CEG" || s == "DFA" || s == "EGB" || s == "FAC" || s == "GBD") {
cout << "Yes";
}
else {
cout << "No";
}
return 0;
}
B TaK Code
思路解析：遍历每一个左上角，然后判断即可
错因： m 写成 n 。。。
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m;
char ch[N][N];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
cin >> ch[i][j];
}
}
for(int i = 1; i <= n - 9 + 1; i++) {
for(int j = 1; j <= m - 9 + 1; j++) {
bool flag = true;
for(int k = i; k <= i + 2; k++) {
for(int l = j; l <= j + 2; l++) {
if(ch[k][l] != '#') {
flag = false;
}
}
}
for(int k = i + 8; k >= i + 6; k--) {
for(int l = j + 8; l >= j + 6; l--) {
if(ch[k][l] != '#') {
flag = false;
}
}
}
for(int k = 1; k <= 4; k++) {
if(ch[i + 3][j + k - 1] != '.') {
flag = false;
}
if(ch[i + k - 1][j + 3] != '.') {
flag = false;
}
if(ch[i + 5][j + 4 + k] != '.') {
flag = false;
}
if(ch[i + 4 + k][j + 5] != '.') {
flag = false;
}
}
if(flag) {
cout << i << " " << j << "\n";
}
}
}
return 0;
}
C Invisible Hand
思路解析：二分答案，再用二分确定有多少卖家愿意出售和多少买家愿意购买
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m;
int a[N], b[N];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int j = 1; j <= m; j++) {
cin >> b[j];
}
sort(a + 1, a + n + 1);
sort(b + 1, b + m + 1);
int l = 0, r = 1e9 + 10, mid = (l + r) / 2;
int ans = 1e9 + 10;
while(l <= r) {
mid = (l + r) / 2;
int tmp1 = upper_bound(a + 1, a + n + 1, mid) - a - 1;
int tmp2 = lower_bound(b + 1, b + m + 1, mid) - b - 1;
if(tmp1 >= m - tmp2) {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout << ans;
return 0;
}
D Count Bracket Sequences
思路解析：dp，\(f[i][j]\) 表示已经计算了前 \(i\) 个字符，还差 \(j\) 个右括号就可成为“可替换字符串”的字符串数。遇到 ( 就把 \(f[i][j]\) 全部替换成 \(f[i - 1][j - 1]\) ，遇到 ) 就把 \(f[i][j]\) 全部替换成 \(f[i - 1][j + 1]\) ，遇到 ? 就要把两种情况都考虑一遍。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 998244353;
const ll N = 3010;
string s;
ll f[N][N];
int main() {
cin >> s;
int n = s.size();
for(int i = n; i > 0; i--) {
s[i] = s[i - 1];
}
f[0][0] = 1;
for(int i = 1; i <= n; i++) {
if(s[i] == '?') {
for(int j = 0; j <= n; j++) {
f[i][j] = f[i - 1][j + 1];
}
for(int j = 1; j <= n; j++) {
f[i][j] = (f[i][j] + f[i - 1][j - 1]) % mod;
}
}
else if(s[i] == '(') {
f[i][0] = 0;
for(int j = 1; j <= n; j++) {
f[i][j] = f[i - 1][j - 1];
}
}
else if(s[i] == ')') {
for(int j = 0; j <= n; j++) {
f[i][j] = f[i - 1][j + 1];
}
}
}
cout << f[n][0];
return 0;
}
E Tangency of Cuboids
思路解析：本场比赛 LG 评级最难的一题，但思路其实非常简单。我们要求共面数，又由于数据范围小\((x <= 100, y <= 100, z <= 100)\)，那我们就干脆遍历每一个面，判断是哪两个面相交，用一个 set 存起来（去重）。
#include<bits/stdc++.h>
using namespace std;
int n, xa, ya, za, xb, yb, zb;
int a[110][110][110];
int dx[6] = {-1, 1, 0, 0, 0, 0};
int dy[6] = {0, 0, -1, 1, 0, 0};
int dz[6] = {0, 0, 0, 0, -1, 1};
set<int> st[100010];
bool check(int x, int y, int z) {
return x >= 0 && x <= 100 && y >= 0 && y <= 100 && z >= 0 && z <= 100;
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> xa >> ya >> za >> xb >> yb >> zb;
for(int x = xa; x < xb; x++) {
for(int y = ya; y < yb; y++) {
for(int z = za; z < zb; z++) {
a[x][y][z] = i;
}
}
}
}
for(int x = 0; x <= 100; x++) {
for(int y = 0; y <= 100; y++){
for(int z = 0; z <= 100; z++) {
for(int i = 0; i < 6; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
int nz = z + dz[i];
if(check(nx, ny, nz)) {
if(a[x][y][z] != 0 && a[nx][ny][nz] != 0 && a[x][y][z] != a[nx][ny][nz]) {
st[a[x][y][z]].insert(a[nx][ny][nz]);
st[a[nx][ny][nz]].insert(a[x][y][z]);
}
}
}
}
}
}
for(int i = 1; i <= n; i++) {
cout << st[i].size() << "\n";
}
return 0;
}
F Cans and Openers
思路解析：贪心，可以列出等量关系：拉环罐头数 + 普通罐头数 + 开罐器 = \(m\) ，而如果我们知道了普通罐头数，那我们就一定能知道开罐器数量的最小值，同时根据等量关系也可得知拉环罐头数，所以我们只需按照开心值从大到小枚举普通罐头数即可，用二分确定开罐器数量，自然也能得到拉环罐头数
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 10;
ll n, m;
vector<ll> a, b, c;
ll sa[N], sb[N], sc[N];
int main() {
cin >> n >> m;
for(ll i = 1; i <= n; i++) {
ll t, x;
cin >> t >> x;
if(t == 0) {
a.push_back(x);
}
else if(t == 1) {
b.push_back(x);
}
else if(t == 2) {
c.push_back(x);
}
}
sort(a.begin(), a.end(), [](ll x, ll y) {
return x > y;
});
sort(b.begin(), b.end(), [](ll x, ll y) {
return x > y;
});
sort(c.begin(), c.end(), [](ll x, ll y) {
return x > y;
});
for(ll i = 1; i <= a.size(); i++) {
sa[i] = sa[i - 1] + a[i - 1];
}
for(ll i = 1; i <= b.size(); i++) {
sb[i] = sb[i - 1] + b[i - 1];
}
for(int i = 1; i <= c.size(); i++) {
sc[i] = sc[i - 1] + c[i - 1];
}
ll ans = sa[min(m, (ll)a.size())];
for(ll i = 1; i <= b.size(); i++) {
ll pc = lower_bound(sc + 1, sc + c.size() + 1, i) - sc;
if(pc <= c.size()) {
ll pa = m - i - pc;
if(pa < 0) break;
pa = min(pa, (ll)a.size());
ans = max(ans, sb[i] + sa[pa]);
}
}
cout << ans;
return 0;
}