B - Buy One Carton of Milk
难度: ⭐
题目大意
选择有三种套餐, 6个鸡蛋S元, 8个鸡蛋M元, 12个鸡蛋L元; 问如果要买至少N个鸡蛋, 最少花费多少钱;
解题思路
一道入门级dp;
神秘代码
#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 = 1e6 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
int dp[N];
int p[] = {6, 8, 12};
signed main() {
int a, b, c;
memset(dp, 0x3f, sizeof dp);
cin >> n >> a >> b >> c;
int f[] = {a, b, c};
dp[0] = 0;
for(int i = 1; i <= n + 12; i++){
for(int j = 0; j < 3; j++){
dp[i] = min(dp[i], dp[i - p[j]] + f[j]);
}
}
res = dp[n];
for(int i = n + 1; i < n + 12; i++){
res = min(res, dp[i]);
}
cout << res;
return 0;
}
C - Sum of Numbers Greater Than Me
难度: ⭐
题目大意
给定一个长度为n的序列A; 对于每一个i, 输出这个序列中所以大于Ai的数的和;
解题思路
先将序列从小到大排序, 对于每个i, 利用二分加前缀和来求解;
神秘代码
#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 = 1e6 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
int p[N], f[N], sum[N];
signed main() {
cin >> n;
for(int i = 1; i <= n; i++){
cin >> p[i];
f[i] = p[i];
}
sort(f + 1, f + 1 + n);
for(int i = 1; i <= n; i++){
sum[i] = sum[i - 1] + f[i];
}
for(int i = 1; i <= n; i++){
int pos = upper_bound(f + 1, f + 1 + n, p[i]) - f;
cout << sum[n] - sum[pos - 1] << ' ';
}
return 0;
}
D - Tile Pattern
难度: ⭐⭐⭐
题目大意
给定一个n * n的字符串矩阵G, G由'W''B'组成, 'W'说明该坐标为白色, 'B'为黑色; 现在有q个询问, 每个询问给出一个矩形的左上角坐标和右下角坐标; 注意坐标(i, j)表示矩阵中的第i + 1行和第j + 1列; 对于这个矩形中的格子(i, j), 它的颜色对应G[i % n][j % n]; 请问这个矩形中黑色块的数量是多少;
解题思路
注意题面坐标的定义方式, 因为这里是把一个格子看作一个坐标, 而不是把点看作坐标; 我们先用二维前缀和预处理一下黑色块的数量; 由题意得, 该二维平面其实就是由无数个矩阵G拼接而来; 对于给定的矩形A, 我们可以先把它扩充为由若干个完整的G组成的矩形; 求出这个大矩形的黑色块的数量后再减去四周扩充的部分的黑色块即可;
神秘代码
#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 = 1e3 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
char g[N][N];
int p[N][N];
signed main() {
int n, q;
cin >> n >> q;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cin >> g[i][j];
if(g[i][j] == 'B') {
p[i][j] = 1;
}
p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
}
}
while(q--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
int w = d - b + 1, h = c - a + 1;
a %= n, b %= n, c %= n, d %= n;
a++, b++, c++, d++;
int ans = 0; // ans指扩充出来的黑色块的数量
//扩充矩形
if(a > 1) h += a - 1;
if(c < n) h += n - c;
if(b > 1) w += b - 1;
if(d < n) w += n - d;
//四周扩充的不完整的矩形G的黑色块
ans += p[a - 1][n] * (w / n);
ans += (p[n][n] - p[c][n]) * (w / n);
ans += p[n][b - 1] * (h / n);
ans += (p[n][n] - p[n][d]) * (h / n);
//扩充出来的行和列会有重合部分需要减去
ans -= p[a - 1][b - 1];
ans -= p[n][b - 1] - p[c][b - 1];
ans -= p[a - 1][n] - p[a - 1][d];
ans -= p[n][n] + p[c][d] - p[c][n] - p[n][d];
//用总的减去扩充的
ans = p[n][n] * (h / n) * (w / n) - ans;
cout << ans << '\n';
}
return 0;
}
E - Set Meal
难度: ⭐⭐⭐
题目大意
现在有n种主食和m种副食; 现在需要把一种主食和一种副食组合为套餐, 该套餐的价格就是两种食品价格的和; 但是有L种组合方式是不合适的; 请问剩下的n * m - L种套餐中价格最高的是多少;
解题思路
本题可以很暴力的用二重循环加剪枝来做; 我们把两种食物都按价格从大到小排序, 对于每一种主食i, 只要遇到第一个合法的j就可以退出这层循环了; 看似最坏是O(n * m)的复杂度, 但真正的复杂度其实是是O(n + L), 因为第二层循环进行的条件就是一直都是L中的组合; 但是由于二重循环得到的所以组合都不相同, 所以所以的第二层循环次数累加起来最多就是L种;
神秘代码
#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, k;
PII ma[N], sd[N];
map<PII, int> mp;
bool cmp(PII a, PII b){
return a.first > b.first;
}
signed main() {
IOS;
cin >> n >> m >> k;
for(int i = 1; i <= n; i++) {
cin >> ma[i].first;
ma[i].second = i;
}
for(int i = 1; i <= m; i++) {
cin >> sd[i].first;
sd[i].second = i;
}
sort(ma + 1, ma + 1 + n, cmp);
sort(sd + 1, sd + 1 + n, cmp);
for(int i = 1; i <= k; i++){
int a, b;
cin >> a >> b;
mp[{a, b}] = 1;
}
int res = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(mp[{ma[i].second, sd[j].second}]) continue;
else{
res = max(res, ma[i].first + sd[j].first);
break;
}
}
}
cout << res;
return 0;
}
F - Palindrome Query
难度: ⭐⭐⭐⭐⭐
- Beginner AtCoder Contest 331beginner atcoder contest 331 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 327