B - TaK Code
难度: ⭐
题目大意
题目定义一种矩阵X: 该矩阵的是一个长度为9的由黑白色块组成正方形矩阵; 该矩阵的左上角和右下角都是一个3*3的黑色矩阵(总共18个), 这两个黑色矩阵外面(边缘不算)包围一圈白色色块(总共14个); 现在一个 n * m的黑白矩阵, 问这个大矩阵中有多少个矩阵X, 只要左上角和右下角的两个黑色矩阵的位置不完全相同, 那么就视为不同的两个矩阵X;
解题思路
数据不大, 暴力即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 2e3 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
char g[110][110];
bool check(int x, int y, int u) {
bool f = true;
if (u == 1) {
for (int i = x; i <= x + 2; i++) {
for (int j = y; j <= y + 2; j++) {
if (g[i][j] != '#') {
f = false;
break;
}
}
if (!f) break;
}
for (int i = 0; i <= 3; i++) {
if (g[x+i][y + 3] != '.'||g[x+3][y+i]!='.') {
f = false;
break;
}
}
}
else{
for (int i = x-2; i <=x; i++) {
for (int j = y-2; j <= y; j++) {
if (g[i][j] != '#') {
f = false;
break;
}
}
if (!f) break;
}
for (int i = 0; i <= 3; i++) {
if (g[x - i][y - 3] != '.' || g[x - 3][y - i] != '.') {
f = false;
break;
}
}
}
return f;
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!check(i, j,1)) continue;
int x = i + 8, y = j + 8;
if (x <= n && y <= m) {
if (check(x, y,2)) {
cout << i << ' ' << j << endl;
}
}
}
}
return 0;
}
C - Invisible Hand
难度: ⭐⭐
题目大意
某个苹果市场上有n个商贩和m个顾客, 每个商贩对此都有一个起步价ai, 意思是该商贩只会以大于等于ai的价格售卖苹果; 而顾客也有一个价格bi, 意思是该顾客不会以超过bi的价格购买苹果; 问最小的满足下列要求的价格是多少;
要求是: 现在有一个价格d, 有x个商贩可能会以价格d售卖苹果, 有y个顾客可能会以价格d购买苹果, 并且x要大于等于y;
解题思路
对题意进行分析: 当价格d越高时, 可能的商贩数量x就会越多, 而顾客数量就会越少; 发现这个单调性后我们就可以考虑用二分来实现; 如果对于价格mid, x < y, 那我们就增大价格mid直到x>=y;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
int s[N], b[N];
bool check(int u) {
int numb = 0, nums = 0;
for (int i = 1; i <= n; i++) {
if (s[i] <= u) nums++;
}
for (int i = 1; i <= m; i++) {
if (b[i] >= u) numb++;
}
if (nums >= numb) return true;
else return false;
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> s[i];
for (int i = 1; i <= m; i++) cin >> b[i];
int l = 0, r = 1e9+10;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}
D - Count Bracket Sequences
难度: ⭐⭐⭐
题目大意
给定一个由'('')''?'组成的序列, 我们可以把'?'变成'('或者')'; 请问可以产生多少种合法的序列(即每一个左括号都有一个与其对应的右括号)
解题思路
因为序列长度最长为3000, dfs肯定会爆栈, 所有我们可以考虑用dp进行递推求解; 状态表示: dp[i][j]: 表示截止到第i个字符的状态是j时合法序列的个数; j初始为0, 遇到'('时j+1, 遇到')'时j-1; 对于状态转移: 当s[i] 为'('时 dp[i][j] = dp[i - 1][j - 1]; 当s[i] 为')'时 dp[i][j] = dp[i - 1][j + 1]; 当s[i] 为'?'时可以同时从两种状态转移而来: dp[i][j] = dp[i - 1][j + 1] + dp[i - 1][j - 1];
上面是主要框架, 接下来再说一下细节, 设序列长度为n, 那么状态j的范围就是-n ~ n; 但是如果j<0, 也就是说多了若干个")", 那么由j转移而来的序列都是非法的, 它并不像'('可以在后面加一个')'来凑为合法序列, j<0是无法挽回的; 所以我们遍历状态时需要遍历j>0的即可; 与此同时, 在状态转移方差中, 当j=0时, 我们就不能用j-1这个状态来转移, 所以要限制一下范围;
心得: 我一开始想状态表示的时候就是想到了这个状态表示, 但是我当时一度放弃了, 因为我觉得因为由'?'的存在, 所以状态j是无法确定的, 但是这个忧虑完全是无用的, 因为我们确实无法确定j, 所以我们直接遍历所有j不就行了吗, 只能说是还不扎实;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e4 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m , res;
int dp[N][N];
int f[N];
signed main() {
string s;
cin >> s;
n = s.size();
s = ' ' + s;
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= n; j++) {
if (s[i] == '(' && j) dp[i][j] = dp[i - 1][j - 1];
else if (s[i] == ')') dp[i][j] = dp[i - 1][j + 1];
else if(s[i]=='?') {
dp[i][j] = dp[i - 1][j + 1];
if (j) (dp[i][j] += dp[i - 1][j - 1]) %= mod;
}
}
}
cout << dp[n][0];
return 0;
}
E - Tangency of Cuboids
难度: ⭐⭐⭐⭐
题目大意
在一个三维空间中有n个长方体, 他们的边长分别与某条坐标轴平行; 我们用体对角线的两个端点来表示改长方体; 并且保证n个长方体都没有重合的部分; 虽然没用重合, 但是会有紧挨着的情况, 现在需要求出每个长方体有多少个不同的长方体和它紧挨着; 紧挨着就是指一个长方体的某个面和另一个长方体的某个面重合了, 这两面不要求大小一样;
解题思路
这题一时间确实想不到思路, 后来看到一个很妙的做法; 因为坐标的范围是(0~100), 也就是说坐标系的大小只有101101101; 所以我们可以把坐标系分为100100100个1*1的正方体, 然后根据给出的n个长方体把这这些小正方体进行编号; 然后我们遍历所有小正方体, 只要它周围(上下前后左右)的小正方体和它的编号不同, 说明就存在两个长方体紧挨着, 我们可以用set来存, 顺便去重;
注意我们遍历的是正方体而不是坐标, 所以遍历时要从1开始遍历而不是0;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
int st[110][110][110];
set<int> s[N];
int dx[] = { 1,-1,0,0,0,0 }, dy[] = { 0,0,1,-1,0,0 }, dz[] = { 0,0,0,0 ,1,-1 };
int num[N];
signed main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int x1, y1, z1, x2, y2, z2;
cin >>x1>> y1>> z1>> x2>> y2>> z2;
for (int a = x1+1; a <= x2; a++) {
for (int b = y1+1; b <= y2; b++) {
for (int c = z1+1; c <= z2; c++) {
st[a][b][c] = i;
}
}
}
}
for (int a = 1; a <= 100; a++) {
for (int b = 1; b <= 100; b++) {
for (int c = 1; c <= 100; c++) {
if (!st[a][b][c]) continue;
int u = st[a][b][c];
for (int i = 0; i < 6; i++) {
int x = a + dx[i], y = b + dy[i], z = c + dz[i];
if (!st[x][y][z]) continue;
if (st[x][y][z] != u) s[u].insert(st[x][y][z]);
}
}
}
}
for (int i = 1; i <= n; i++) {
cout << s[i].size() << endl;
}
return 0;
}
F - Cans and Openers
难度: ⭐⭐⭐⭐
题目大意
给定n个物品, 每个物品有两个属性: t和x; 如果t=0, 说明这是一个拉环罐头, 可以直接使用并且加x分; 如果t=1, 说明这是一个普通罐头, 需要用开罐器打开后才能使用并且加x分; 如果t=2, 说明这是一个开罐器, 它最多可以开x个罐头; 我们最多选择m件物品, 请问可以获得的最大分数为多少;
解题思路
设拉环罐头为a, 普通罐头为b, 开罐器为c; 模拟一下这个过程我们发现解题的关键就在于b; 如果b的数量确定了, 那c的数量也就确定, b和c的数量都知道了, 那a的数量也确定了, 这是最好玩的地方; 所以根据这个思路我们可以遍历b的数量, 然后用二分找出c的数量, 最后用m减去a和b就得到了c的数量; 忘了方便运算我们可以先把a,b,c从大到小排序之后求前缀和, 这样就省去了求和的过程, 也方便c的二分答案; 注意在二分找c的数量时, b和c加起来的数量不能大于m就行;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS sync_with_stdio(false), cin.tie(0),cout.tie(0);
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII;
int n, m, idx;
int c[N], rc[N], o[N];
int nc, nr, no;
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int a, b;
cin >> a >> b;
if (a == 0) c[++nc] = b;
else if (a == 1) rc[++nr] = b;
else if (a == 2) o[++no] = b;
}
sort(c + 1, c + nc + 1, greater<>());
sort(rc + 1, rc + nr + 1, greater<>());
sort(o + 1, o + no + 1, greater<>());
for (int i = 1; i <= nc; i++) c[i] += c[i - 1];
for (int i = 1; i <= nr; i++) rc[i] += rc[i - 1];
for (int i = 1; i <= no; i++) o[i] += o[i - 1];
int maxn = 0;
for (int i = 0; i <= min(m, nr); i++) {
int res = rc[i];
int l = 0, r = min(m - i, no);
while (l < r) {
int mid = l + r >> 1;
if (o[mid] >= i) r = mid;
else l= mid + 1;
}
if (o[l] < i) continue;
res += c[min(nc,m - i - l)];
maxn = max(maxn, res);
}
cout << maxn;
return 0;
}
- Beginner AtCoder Contest 312 abcbeginner atcoder contest 312 beginner atcoder contest abc 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