A - Chord
#include <bits/stdc++.h>
using namespace std;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
string s;
cin >> s;
if( s == "ACE" ) cout << "Yes\n";
else if( s == "BDF" ) cout << "Yes\n";
else if( s == "CEG" ) cout << "Yes\n";
else if( s == "DFA" ) cout << "Yes\n";
else if( s == "EGB" ) cout << "Yes\n";
else if( s == "FAC" ) cout << "Yes\n";
else if( s == "GBD" ) cout << "Yes\n";
else cout << "No\n";
return 0;
}
B - TaK Code
枚举左上角
#include <bits/stdc++.h>
using namespace std;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector<string> g(n);
for (auto &i: g)
cin >> i;
for (int i = 0; i + 8 < n; i++)
for (int j = 0; j + 8 < m; j++) {
int f = 1;
for (int l = i; f && l <= i + 2; l++)
for (int k = j; f && k <= j + 2; k++)
if (g[l][k] != '#') f = 0;
for (int l = i + 6; f && l <= i + 8; l++)
for (int k = j + 6; f && k <= j + 8; k++)
if (g[l][k] != '#') f = 0;
for (int l = i; f && l <= i + 3; l++)
if (g[l][j + 3] != '.') f = 0;
for (int k = j; f && k <= j + 3; k++)
if (g[i + 3][k] != '.') f = 0;
for (int l = i + 5; f && l <= i + 8; l++)
if (g[l][j + 5] != '.') f = 0;
for (int k = j + 5; f && k <= j + 8; k++)
if (g[i + 5][k] != '.') f = 0;
if (f == 0) continue;
cout << i + 1 << " " << j + 1 << "\n";
}
return 0;
}
C - Invisible Hand
枚举答案\(x\),设\(a\)为\(A_i\)中小于等于\(x\)的数量,设\(b\)为\(B_i\)中大于等于\(x\)的数量,则随着\(x\)递增,\(a\)递增,\(b\)递减。所以\(b-a\)递减,所以可以二分找到最小的\(x\)满足\(b-a=0\)。在计算\(a,b\)的时候也可直接二分。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (auto &i: a)
cin >> i;
for (auto &i: b)
cin >> i;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
auto f = [a, b](int x) {
int A = lower_bound(a.begin(), a.end(), x) - a.begin();
while (a[A] == x) A++;
int B = lower_bound(b.begin(), b.end(), x) - b.begin();
B = b.size() - B;
return B - A;
};
int l = 0, r = 2e9, res, mid;
while (l <= r) {
mid = (l + r) >> 1;
if (f(mid) <= 0) res = mid ,r = mid - 1;
else l = mid + 1;
}
cout << res << "\n";
return 0;
}
再来分析,可以发现答案一定是\(A_i,B_i+1\),所以把\(A,B+1\)放到数组\(C\)中排序,当\(x=0\)时\(b-a=M\),当\(x=C_1\)时,\(b-a=M-1\)以此类推当\(x=C_M\)时\(b-a=0\)。所以第\(M\)小就是答案。
这里只求第\(M\)小,可以只用nth_element
就可以\(O(N)\)求解
#include<bits/stdc++.h>
using namespace std;
int32_t main() {
int n , m;
cin >> n >> m;
vector<int> a(n+m);
for( int i = 0 ; i < n ; i ++ ) cin >> a[i];
for( int i = n ; i < n+m ; i ++ ) cin >> a[i] , a[i] ++;
nth_element( a.begin() , a.begin() + m - 1 , a.end());
cout << a[m-1];
return 0;
}
D - Count Bracket Sequences
简单 dp,f[i][j]
表示前\(i\)个字符,且\(j\)个左括号尚未匹配的方案数
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3005;
const int mod = 998244353;
int f[N][N];
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
string s;
cin >> s;
int n = s.size();
f[0][0] = 1;
for( int i = 1 ; i <= n ; i ++ ){
if( s[i-1] == '(' ){
for( int j = 1 ; j <= n ; j ++ )
f[i][j] = f[i-1][j-1];
}else if( s[i-1] == ')' ){
for( int j = 0 ; j < n ; j ++ )
f[i][j] = f[i-1][j+1];
}else {
for( int j = 0 ; j <= n ; j ++ ){
if( j-1 >= 0 ) f[i][j] += f[i-1][j-1];
if( j+1 <= n ) f[i][j] += f[i-1][j+1];
f[i][j] %= mod;
}
}
}
cout << f[n][0] << "\n";
return 0;
}
E - Tangency of Cuboids
因为长方体不会相交,所以我们暴力的标记每个立方体属于哪一个长方体,我们用每个立方体左上角的坐标表示该立方体。
如果两个长方体相邻,这会有两个相邻的立方体属于两个不同长方体。所以可以直接枚举立方体。
#include<bits/stdc++.h>
using namespace std;
const int N = 115;
int g[N][N][N];
int32_t main() {
int n;
cin >> n;
for (int t = 1, a, b, c, x, y, z; t <= n; t++) {
cin >> a >> b >> c >> x >> y >> z;
for ( int i = a ; i < x; i++)
for ( int j = b ; j < y; j++)
for ( int k = c ; k < z; k++)
g[i][j][k] = t;
}
vector ans( n+1 , set<int>() );
for (int i = 0; i < 100; i++)
for (int j = 0; j < 100; j++)
for (int k = 0; k < 100; k++) {
if (g[i][j][k] == 0) continue;
if (g[i + 1][j][k] != 0 && g[i][j][k] != g[i + 1][j][k])
ans[g[i][j][k]].emplace(g[i + 1][j][k]), ans[g[i + 1][j][k]].emplace(g[i][j][k]);
if (g[i][j + 1][k] != 0 && g[i][j][k] != g[i][j + 1][k])
ans[g[i][j][k]].emplace(g[i][j + 1][k]), ans[g[i][j + 1][k]].emplace(g[i][j][k]);
if (g[i][j][k + 1] != 0 && g[i][j][k] != g[i][j][k + 1])
ans[g[i][j][k]].emplace(g[i][j][k + 1]), ans[g[i][j][k + 1]].emplace(g[i][j][k]);
}
for (int i = 1; i <= n; i++)
cout << ans[i].size() << "\n";
return 0;
}
F - Cans and Openers
我们可以枚举选择多少个易拉罐,然后可以用二分的方式求出最多可以获得多少个普通罐。
对于易拉罐、普通罐、开罐器我们都可以贪心的选择,所以可以排序求前缀和。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3005;
const int mod = 998244353;
int f[N][N];
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, m, res = 0;
cin >> n >> m;
vector<int> a, b, c;
a.push_back(0), b.push_back(0), c.push_back(0);
for (int i = 1, t, x; i <= n; i++) {
cin >> t >> x;
if (t == 0) a.push_back(x);
else if (t == 1) b.push_back(x);
else c.push_back(x);
}
int A = a.size() - 1, B = b.size() - 1, C = c.size() - 1;
sort(a.begin() + 1, a.end(), greater<int>());
for (int i = 1; i <= A; i++) a[i] += a[i - 1];
sort(b.begin() + 1, b.end(), greater<int>());
for (int i = 1; i <= B; i++) b[i] += b[i - 1];
sort(c.begin() + 1, c.end(), greater<int>());
for (int i = 1; i <= C; i++) c[i] += c[i - 1];
for (int i = 0, l, r, cnt, mid; i <= min(m, A); i++) {
l = 0, r = min(B, m - i), cnt = 0;
while (l <= r) {
mid = (l + r) >> 1;
if (c[min(C, m - i - mid)] >= mid) cnt = mid, l = mid + 1;
else r = mid - 1;
}
res = max(res, a[i] + b[cnt]);
}
cout << res << "\n";
return 0;
}
G - Avoid Straight Line
首先不管题目要求,任意选三个\(C_n^2\),然后减去三个点在一条链上的情况。
我们枚举中间点,考虑两个端点只有两种情况
- 一个点子树中的节点,另一个不是
- 两个点都是子树中的,且属于不同的子树
这样简单的分类讨论一下就可以了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> e, g;
vector<int> f;
void dfs(int x) {
f[x] = 1;
for (auto y: e[x]) {
if (f[y]) continue;
g[x].push_back(y);
dfs(y);
f[x] += f[y];
}
return;
}
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
e.resize(n + 1), g.resize(n + 1);
for (int i = 1, x, y; i < n; i++)
cin >> x >> y, e[x].push_back(y), e[y].push_back(x);
f.resize(n + 1);
dfs(1);
int res = n * (n - 1) * (n - 2) / 6;
// f[i]i i的子树大小, cnt 中间包含 i的链的数量
for (int i = 1 , cnt ; i <= n; i++){
cnt = 0;
for( auto j : g[i] ) // 两个点在不同的子树中
cnt += f[j] * ( f[i] - 1 - f[j] );
cnt /= 2;
cnt += ( f[i] - 1 ) * ( n - f[i] );
res -= cnt;
}
cout << res;
return 0;
}
- Beginner AtCoder Contest 312beginner atcoder contest 312 contest atcoder programming 312 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 334