ABC312(A-F)
A - Chord¶
判断字符串 \(S\) 是否等于
ACE,BDF,CEG,DFA,EGB,FAC,GBD之一
直接判断
#include <iostream>
using namespace std;
int main()
{
string s;
cin >> s;
if(s == "ACE" || s == "BDF" ||
s == "CEG" || s == "DFA" || s == "EGB" || s == "FAC" || s == "GBD")
puts("Yes");
else
puts("No");
return 0;
}
B - TaK Code¶
有一个 \(N \times M\) 的矩阵，矩阵中只有
#或.，问：有多少个如下形状的 \(9 \times 9\) 子矩阵###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###其中
?可以是#或.
直接枚举即可
#include <iostream>
using namespace std;
const int maxn = 110;
int n, m;
char s[maxn][maxn];
bool check1(int r, int c)
{
for(int i = 0; i < 3; i++)
for(int j = 0; j < 3; j++)
if(s[r][c] != '#')
return 0;
return 1;
}
bool check2(int r, int c)
{
for(int i = 0; i < 4; i++)
if(s[r-i][c] != '.' || s[r][c-i] != '.')
return 0;
return 1;
}
bool check3(int r, int c)
{
for(int i = 0; i < 4; i++)
if(s[r+i][c] != '.' || s[r][c+i] != '.')
return 0;
return 1;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
scanf("%s", s[i]+1);
for(int i = 1; i+8 <= n; i++)
for(int j = 1; j+8 <= m; j++)
if(check1(i, j) && check2(i+3, j+3) && check3(i+5, j+5) && check1(i+6, j+6))
printf("%d %d\n", i, j);
return 0;
}
C - Invisible Hand¶
有 \(N\) 个卖家和 \(M\) 个买家，每个卖家都有预期卖出价格 \(A_i\) ，当价格大于或等于 \(A_i\) 时卖家才愿意卖出。买个买家有预期买入价格 \(B_i\) ，当价格小于或等于 \(B_i\) 时买家才愿意买入。找出最小的数 \(X\) ，使得愿意卖出的人数大于等于愿意买入的人数。
二分，证明单调性：如果 \(X\) 的值调低，则卖家会变少，而卖家会变多，反之同理，因此满足单调性。
对买家和卖家的价格排序，然后二分，check的时候也二分就能知道有多少卖家和买家。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2E5 + 10;
int a[maxn], b[maxn], n, m;
int check(int num)
{
return lower_bound(a, a+n, num+1) - a >= b + m - lower_bound(b, b+m, num);
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
for(int i = 0; i < m; i++)
scanf("%d", &b[i]);
sort(a, a+n);
sort(b, b+m);
int l = min(a[0], b[0]) - 1, r = max(a[n-1], b[m-1]) + 1;
while(l < r)
{
int x = (l + r) / 2;
if(check(x))
r = x;
else
l = x + 1;
}
cout << l << endl;
return 0;
}
当然，如果推一下会发现答案一定是 \(A_i\) 或 \(B_i + 1\)，进一步可以参考 这个题解 ，将 \(A_i\) 和 \(B_i + 1\) 合并然后排序直接输出 \(M-1\) 元素就可以了，时间复杂度 \(O((N+M)log(N+M))\)
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
print(sorted(A + list(map(lambda x: x + 1, B)))[M - 1])
D - Count Bracket Sequences¶
给你一个长度为 \(N\) 的字符串 \(S\) ，\(S\) 由
(，)和?组成，你需要将?替换成(或)，问：有多少种方案能够将 \(S\) 替换成括号匹配的字符串。答案 \(\bmod 998244353\)数据范围：\(N ≤ 3000\)
经典括号匹配题，( 看成 1 ，) 看成 -1 ，合法字符串相当于前缀和大于等于 0
定义 \(dp[i][j]\) ：前 \(i\) 个数字使得前缀和为 \(j\) 的方案数。
转移：
时间复杂度 \(O(N^2)\)
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 3010;
const int mod = 998244353;
int n;
char s[maxn];
int dp[maxn][maxn];
int main()
{
scanf("%s", s+1);
n = strlen(s+1);
dp[0][0] = 1;
for(int i = 1; i <= n; i++)
{
if(s[i] == '(')
{
for(int j = 1; j <= n; j++)
dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % mod;
}
else if(s[i] == ')')
{
for(int j = 0; j < n; j++)
dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % mod;
}
else
{
for(int j = 1; j <= n; j++)
dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % mod;
for(int j = 0; j < n; j++)
dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % mod;
}
}
cout << dp[n][0] << endl;
return 0;
}
E - Tangency of Cuboids¶
在三维空间中，有 \(N\) 个 互不相交的长方体，如果两个长方体有一面相邻，则称这两个长方体相邻。输出每个长方体与其他长方体相邻的数量。
数据范围：
\(1 ≤ N ≤ 10^5\)
\(0 ≤ X, Y, Z ≤ 100\)
空间只有 100，分成多个 \(1\times1\times1\) 的小方块。由于长方体互不相交，所以一个小方块只能属于一个长方体，如果两个小方块相邻，则说明对应的长方体是相邻的。用一个 id[100][100][100] 记录小方块的归属，然后遍历判断就可以了。使用哈希表记录每个长方体和谁相邻。
#include <iostream>
#include <unordered_set>
using namespace std;
const int maxx = 110;
const int maxn = 1E5 + 10;
unordered_set<int> face[maxn];
int id[maxx][maxx][maxx];
int n;
int main()
{
cin >> n;
for(int i = 1, x1, y1, z1, x2, y2, z2; i <= n; i++)
{
cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
for(int x = x1; x < x2; x++)
for(int y = y1; y < y2; y++)
for(int z = z1; z < z2; z++)
id[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++)
if(id[x][y][z])
{
if(id[x+1][y][z] && id[x+1][y][z] != id[x][y][z])
{
face[id[x+1][y][z]].insert(id[x][y][z]);
face[id[x][y][z]].insert(id[x+1][y][z]);
}
if(id[x][y+1][z] && id[x][y+1][z] != id[x][y][z])
{
face[id[x][y+1][z]].insert(id[x][y][z]);
face[id[x][y][z]].insert(id[x][y+1][z]);
}
if(id[x][y][z+1] && id[x][y][z+1] != id[x][y][z])
{
face[id[x][y][z+1]].insert(id[x][y][z]);
face[id[x][y][z]].insert(id[x][y][z+1]);
}
}
for(int i = 1; i <= n; i++)
cout << face[i].size() << endl;
return 0;
}
F - Cans and Openers¶
有 \(N\) 个物品，每个物品都有一个 \(X_i\) 属性，物品有三种类型，
- 易拉罐：获得之后可以直接打开，打开之后获得 \(X_i\) 的分数。
- 密封罐：需要使用开罐器才能打开，打开之后获得 \(X_i\) 的分数。
- 开罐器：用于打开密封罐，可以使用 \(X_i\) 次。
问：从中选择 \(M\) 个物品，最多能获得多少分数？
数据范围：\(1 ≤ M ≤ N ≤ 2 \times 10^5\)
显然，对于三种物品，在能选择的情况下，都是选择 \(X_i\) 越大的越好。
接下来，固定易拉罐的数量， 假设已经选择了 \(i\) 个分数最高的易拉罐，那么剩下的 \(M-i\) 个物品就是密封罐和开罐器，按照优先级一个一个选即可。
这样的话，第一层枚举 \(i\) 需要遍历 \(M\) 次，第二层循环选择剩下的 \(M-i\) 个物品也需要 \(M\) 次，这样肯定超时。不过，由于物品之间的优先级关系，可以用类似前缀和的东西加速：具体来说，开两个数组 sa[] 和 sb[] ，sa[i] 表示选择 i 个易拉罐能获得的最高分数，由于分数越高越好，因此构造 sa[] 只需要类似前缀和的方式从高到低加起来就可以。 sb[j] 表示选择 j 个其余物品能获得最高的分数，构造 sb[] 的过程也很简单，手上没有开罐器就加一个，如果有开罐器，也是从密封罐当中选一个分数最高的加起来。
代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
int main()
{
int n, m;
cin >> n >> m;
vector<LL> a, b, c;
vector<LL> sa(n+1), sb(n+1);
for(int i = 0, t, x; i < n; i++)
{
scanf("%d %d", &t, &x);
if(t == 0)
a.push_back(x);
else if(t == 1)
b.push_back(x);
else
c.push_back(x);
}
sort(a.begin(), a.end(), greater<LL>());
sort(b.begin(), b.end());
sort(c.begin(), c.end());
for(int i = 0; i < n; i++)
if(i < a.size())
sa[i+1] = sa[i] + a[i];
else
sa[i+1] = sa[i];
for(int r = 0, i = 0; i < n; i++)
{
if(b.empty())
sb[i+1] = sb[i];
else if(r == 0)
{
if(!c.empty())
{
r += c.back();
c.pop_back();
}
sb[i+1] = sb[i];
}
else
{
sb[i+1] = sb[i] + b.back();
b.pop_back();
r--;
}
}
LL ans = 0;
for(int i = 0; i <= m; i++)
ans = max(ans, sa[i] + sb[m-i]);
cout << ans << endl;
return 0;
}
G - Avoid Straight Line¶
有一棵 \(N\) 个节点的树，求出满足下列条件的三元组 \((i, j, k)\) 的数量：
- \(1 ≤ i < j < k ≤ N\)
- 树中不存在包含 \(i\) ，\(j\) ，\(k\) 的简单路径。
数据范围：\(N ≤ 2 \times 10^5\)
参考 这个题解 的思路
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int maxn = 2E5 + 10;
const int maxm = 4E5 + 10;
int n, sz[maxn];
int head[maxn], ne[maxm], edge[maxm], idx = 1;
void add(int u, int v)
{
edge[idx] = v;
ne[idx] = head[u];
head[u] = idx++;
}
void dfs(int u, int fa)
{
sz[u] = 1;
for(int i = head[u]; i; i = ne[i])
{
int v = edge[i];
if(v == fa)
continue;
dfs(v, u);
sz[u] += sz[v];
}
}
LL ans;
void dfs2(int u, int fa)
{
LL sum = 0;
for(int i = head[u]; i; i = ne[i])
{
int v = edge[i];
sum += sz[v];
}
for(int i = head[u]; i; i = ne[i])
{
int v = edge[i];
sum -= sz[v];
ans -= sz[v] * sum;
}
for(int i = head[u]; i; i = ne[i])
{
int v = edge[i];
if(v == fa)
continue;
sz[u] -= sz[v];
sz[v] += sz[u];
dfs2(v, u);
sz[v] -= sz[u];
sz[u] += sz[v];
}
}
int main()
{
cin >> n;
ans = n * (n - 1ll) * (n - 2) / 6;
for(int m = n-1, u, v; m--; )
{
scanf("%d %d", &u, &v);
add(u, v);
add(v, u);
}
dfs(1, 0);
dfs2(1, 0);
cout << ans << endl;
return 0;
}
创建日期: 2023-09-12