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;
}