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