B - Default Price
题目大意
小莫买了n个寿司, 现在给出m个寿司的名称和m+1个价格, 如果小莫买的其中一个寿司不在这m个寿司之中就用价格m0; 请问小莫买的寿司花了多少钱
解题思路
数据不大, 暴力哈希即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int n, m, k, res;
map<string, int>f;
vector<string> v1,v2;
signed main() {
IOS;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
v1.push_back(s);
}
for (int i = 1; i <= m; i++) {
string s;
cin >> s;
v2.push_back(s);
}
cin >> k;
for (int i = 0; i < m; i++) {
int a;
cin >> a;
f[v2[i]] = a;
}
for (int i = 0; i < n; i++) {
if (f[v1[i]]) res += f[v1[i]];
else res += k;
}
cout << res;
return 0;
}
C - Standings
题目大意
给定n个人(编号1~n)投硬币的结果, n行每行两个数a, b表示正面和反面的次数, 现在要求按扔到正面的概率(a/(a+b))将n个人从大到小排序;
解题思路
本题有一个坑点, 不可以直接用double求概率, 这样会有一定的误差, 要尽可能的用乘法来比较大小;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int n, m, k, res;
typedef struct{
int a, b, id;
}str;
vector<str> v;
bool cf(str a, str b) {
if (a.a * (b.a + b.b) == b.a * (a.a + a.b)) return a.id < b.id;
else return a.a * (b.a + b.b) > b.a * (a.a + a.b);
}
signed main() {
IOS;
cin >> n;
for (int i = 1; i <= n; i++) {
int a, b;
cin >> a >> b;
v.push_back({ a,b,i });
}
sort(v.begin(), v.end(), cf);
for (auto x : v) {
cout << x.id<< ' ';
}
return 0;
}
D - Snuke Maze
题目大意
给定一个字符串矩阵, 要求按"snuke"的循环顺序从左上角走到右下角, 问是否有这样一条路径
解题思路
一个比较板子的bfs, 在队列中存入坐标和当前是路径中的第几个字符, 记得不要忘了标记走过的路, 以免陷入死循环;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 1e3 + 10;
int n, m, k, res;
char g[N][N];
bool st[N][N];
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
char s[] = "esnuk";
typedef struct {
int x, y;
int idx;
}str;
bool bfs() {
queue<str> q;
q.push({ 1,1,1 });
st[1][1] = true;
if (g[1][1] != 's') return false;
while (q.size()) {
auto t = q.front();
q.pop();
if (t.x == n && t.y == m) return true;
for (int i = 0; i < 4; i++) {
int x = t.x + dx[i], y = t.y + dy[i], idx = t.idx + 1;
if (x >= 1 && x <= n && y >= 1 && y <= m&&!st[x][y]) {
if (g[x][y] == s[idx % 5]) {
q.push({ x,y,idx });
st[x][y] = true;
}
}
}
}
return false;
}
signed main() {
IOS;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
}
}
bool f = bfs();
if (f) cout << "Yes";
else cout << "No";
return 0;
}
E - MEX
题目大意
给定一个n个数并且由0,1,2构成的数列q, 再给出一个长度为n的由M,E,X构成的字符串是s, 数和字母一一对应; 现在需要找出所有满足条件的下标(i,j,k), 要求1<= i< j< k<= n, 并且si='M', sj='E', sk='X'; 此时我们也会得到qi,qj,qk三个数, 我们将不等于这三个数的最小非负整数作为这一组下标的运算值, 把所有满足条件的下标的运算值相加输出;
解题思路
因为n的范围较大, 所以我们要考虑线性的复杂度来解决这个问题; 因为只有012三个值, 我们可以设立两个数组: m_num[3]表示截止到第i个数时值为x的'M'有多少个, e_num[3][3]表示截止到第i个数时'M'和'E'的值分别为x和y的组合有多少个; 当我们遇到'X'时, 就可以遍历e_num的x和y, 找到不等于这三个数的最小非负整数z, 让e_num[x][y]*x就是截止到i时这个下标组合的运算值的和;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int n, m, k, res;
int m_num[3], e_num[3][3], f[N];
signed main() {
IOS;
cin >> n;
for (int i = 0; i < n; i++) cin >> f[i];
string s;
cin >> s;
for (int i = 0; i < s.size(); i++) {
if (s[i] == 'M') m_num[f[i]]++;
else if (s[i] == 'E') {
for (int j = 0; j <= 2; j++) {
if (m_num[j]) {
e_num[j][f[i]] += m_num[j];
}
}
}
else {
for (int j = 0; j <= 2; j++) {
for (int k = 0; k <= 2; k++) {
if (e_num[j][k]) {
int x = 0;
while (x == j || x == k || x == f[i]) x++;
res += x * e_num[j][k];
}
}
}
}
}
cout << res;
return 0;
}
F - Vouchers
题目大意
小莫要买n件商品, 每件的价格为Pi, 现在小莫手上有m张优惠卷, 每个优惠卷可以让价格不低于Li的商品便宜Di元(Li>=Di); 请问小莫该如何规划使用优惠卷让自己付的钱最少;
解题思路
这道题不难想到是一个贪心问题, 价格越低的商品可以用的的优惠卷越少, 所以对于价格低的商品, 如果有优惠卷可以用那就必须用; 所以我们可以把Pi和Li从低到高进行排序, 遍历Pi, 找到最低的可以被使用的优惠卷即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int n, m, k, res;
int p[N], d[N];
vector<PII> v;
priority_queue<PII> heap;
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> p[i];
res += p[i];
}
for (int i = 1; i <= m; i++) cin >> d[i];
for (int i = 1; i <= m; i++) {
int a;
cin >> a;
v.push_back({ d[i],a });
}
sort(p + 1, p + n + 1);
sort(v.begin(), v.end());
for (int i = 1, j = 0; i <= n; i++) {
while (j<v.size()&&p[i] >= v[j].first) {
heap.push({v[j].second, v[j].first});
j++;
}
if (heap.empty()) continue;
res -= heap.top().first;
heap.pop();
}
cout << res;
return 0;
}
- Beginner AtCoder Contest 308 abcbeginner atcoder contest 308 beginner atcoder contest abc beginner atcoder 308e mex atcoder 308h make abc contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332