Practice.
A. New Scheme
题意
给定一个长度为 \(8\) 的序列 \(S\)，判断是否满足下面的条件：
不递减
\(100 \leq S_i \leq 675\)
为 \(25\) 的倍数
思路
如题
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
vector<int> s(8);
for(int i=0;i<8;i++) cin >> s[i];
for(int i=0;i<7;i++){
if(s[i] > s[i + 1]){
cout << "No\n";
return;
}
}
for(auto e : s){
if(e % 25 != 0 || e < 100 || e > 675){
cout << "No\n";
return;
}
}
cout << "Yes\n";
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}如题
B. Default Price
题意
给定 \(m\) 种菜品名称，以及对应的价格 \(p_i\)，未给菜品价格为 \(p_0\)。
现在，给定 \(n\) 个菜品，输出总价。
思路
\(map\) 存一下即可。
时间复杂度：\(O(m + n \log m)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, m;
cin >> n >> m;
map<string, int> p;
vector<string> a(n);
vector<string> b(m);
for(int i=0;i<n;i++) cin >> a[i];
for(int i=0;i<m;i++) cin >> b[i];
int x;
cin >> x;
for(int i=0;i<m;i++) {
int cur;
cin >> cur;
p[b[i]] = cur;
}
int ans = 0;
for(auto e : a) {
if(p.count(e)) ans += p[e];
else ans += x;
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}如题
C. Standings
题意
给定序列 \(X = \{1, 2, 3, \ldots,n\}\)，以及两个长为 \(n\) 的序列 \(A, B\)，按照下面的方式排序 \(X\) 后输出：
主关键字：\(\frac{A_i}{A_i + B_i}\)，降序；
次关键字：\(X_i\) 的值，升序
思路
这题是估计卡精度的，对于 \(\frac{A_x}{A_x + B_x} \leq \frac{A_y}{A_y + B_y}\)，移项得 \(A_x(A_y + B_y) \leq A_y(A_x + B_x)\)。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;;
const double eps = 1e-19;
void solve() {
int n;
cin >> n;
vector<int> c(n);
for(int i=0;i<n;i++) c[i] = i;
vector<int> a(n), b(n);
for(int i=0;i<n;i++){
cin >> a[i] >> b[i];
}
sort(all(c), [&](int o1, int o2) -> bool{
return (__int128)a[o1] * (a[o2] + b[o2]) == (__int128)a[o2] * (a[o1] + b[o1]) ? o1 < o2 : (__int128)a[o1] * (a[o2] + b[o2]) > (__int128)a[o2] * (a[o1] + b[o1]);
});
for(auto e: c) cout << e + 1 << ' ';
cout << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}有被坑到，谢谢
D. Snuke Maze
题意
给定由 \(s, n, u, k, e\) 组成的大小为 \(H \times W\) 的矩阵，判断是否存在一条从 \((1, 1)\) 到 \((H, W)\) 的路径，路径中的第 \(i\) 个元素为字符串 \(snuke\) 的第 \(((i - 1)\mod 5) + 1\) 个字符。
思路
\(\mathtt{dfs}\) 即可，不过不需要回溯。
时间复杂度：\(O(nm)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;;
const double eps = 1e-19;
void solve() {
int h, w;
cin >> h >> w;
vector<string> a(h);
for(int i=0;i<h;i++) cin >> a[i];
vector<vector<bool>> ok(h, vector<bool>(w));
vector<pii> to = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
string s = "snuke";
bool f = false;
auto dfs = [&](auto dfs, int x, int y, int st) -> void{
if(f) return;
if(x == h - 1 && y == w - 1){
cout << "Yes\n";
f = true;
return;
}
for(auto [dx, dy] : to){
int tx = x + dx, ty = y + dy;
if(tx >= 0 && ty >= 0 && tx < h && ty < w && !ok[tx][ty] && s[(st + 1) % 5] == a[tx][ty]){
ok[tx][ty] = true;
dfs(dfs, tx, ty, st + 1);
}
}
};
ok[0][0] = true;
dfs(dfs, 0, 0, 0);
if(!f) cout << "No\n";
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}最近怎么老是因为回溯 \(tle\)
E. MEX
题意
给定一个长为 \(n\) 且只包含 \(0, 1, 2\) 的序列 \(A\) 以及 一个长为 \(n\) 且只包含 \(M, E, X\) 的字符串 \(S\)。
对于所有长度为 \(3\) 的子序列（不一定连续）\(S_1S_2S_3\)，输出所有拼接后为 \(MEX\) 的字符串对应的 \(mex(A_1, A_2, A_3)\)。
其中，\(mex(x, y, z)\) 表示非负数中不等于 \(x, y, z\) 中的最小值。
思路
假设 \(E\) 的位置固定，那么如果我们知道前面有 \(x\) 个 \(M\) 和 \(y\) 个 \(X\)，以这个 \(E\) 为中心的子序列 \(MEX\) 个数即可根据乘法原理算得：\(xy\)。
那么照这个思路，因为考虑重复时 \(0, 1, 2\) 总共有 \(27\) 种放置方式，我们直接分讨即可。
举个例子，如果对于第 \(i\) 个位置，该位置为 \(E\)，且 \(A_i = 0\)，并且前面有 \(pre[0]\) 个 \(M\) 对应的 \(A\) 序列中的值为 \(0\)， 后面有 \(suf[1]\) 个 \(X\) 对应的 \(A\) 序列中的值为 \(1\)，那么这个情况对应的答案为 \(2 \times pre[0] \times suf[1]\)。
那么，我们用两个二维数组分别维护前缀和后缀个数即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;;
const double eps = 1e-19;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
string s;
cin >> s;
s = "#" + s;
vector<vector<int>> pre(n + 1, vector<int>(3));
vector<vector<int>> suf(n + 2, vector<int>(3));
for(int i=1;i<=n;i++){
for(int j=0;j<3;j++) pre[i][j] = pre[i - 1][j];
if(s[i] == 'M') pre[i][a[i]] ++;
}
for(int i=n;i>= 1;i--){
for(int j=0;j<3;j++) suf[i][j] = suf[i + 1][j];
if(s[i] == 'X') suf[i][a[i]] ++;
}
int ans = 0;
for(int i=1;i<=n;i++){
if(s[i] != 'E') continue;
if(a[i] == 0){//000 001 011 002 022 012
ans += 1 * pre[i][0] * suf[i][0];
ans += 2 * (pre[i][0] * suf[i][1] + pre[i][1] * suf[i][0]);
ans += 2 * pre[i][1] * suf[i][1];
ans += 1 * (pre[i][0] * suf[i][2] + pre[i][2] * suf[i][0]);
ans += 1 * pre[i][2] * suf[i][2];
ans += 3 * (pre[i][1] * suf[i][2] + pre[i][2] * suf[i][1]);
}else if(a[i] == 1){
ans += 2 * pre[i][0] * suf[i][0];
ans += 2 * (pre[i][0] * suf[i][1] + pre[i][1] * suf[i][0]);
ans += 0 * pre[i][1] * suf[i][1];
ans += 3 * (pre[i][0] * suf[i][2] + pre[i][2] * suf[i][0]);
ans += 0 * pre[i][2] * suf[i][2];
ans += 0 * (pre[i][1] * suf[i][2] + pre[i][2] * suf[i][1]);
}else{
ans += 1 * pre[i][0] * suf[i][0];
ans += 3 * (pre[i][0] * suf[i][1] + pre[i][1] * suf[i][0]);
ans += 0 * pre[i][1] * suf[i][1];
ans += 1 * (pre[i][0] * suf[i][2] + pre[i][2] * suf[i][0]);
ans += 0 * pre[i][2] * suf[i][2];
ans += 0 * (pre[i][1] * suf[i][2] + pre[i][2] * suf[i][1]);
}
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}就是写起来像依托史
F. Vouchers
题意
给定 \(n\) 个标价为 \(P_i\) 的商品，以及 \(m\) 个满 \(D_i\) 减 \(L_i\) 的券，在每一种券只能使用一次 并且 不能叠加使用 的条件下，输出购买所有商品需要的最小金额。
思路
简单贪心。
我们肯定希望能尽可能使用折扣力度大一点的券，那么对于某一个商品，我们就使用能使用的减价最多的券。
当然，我们也希望券能用多一点，所以我们按照商品的价格升序排序，然后依次使用能使用的减价最多的券。
上述贪心思路是显然正确的，而具体实现方式可以为优先队列。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;;
const double eps = 1e-19;
void solve() {
int n, m;
cin >> n >> m;
vector<int> p(n);
vector<pii> v(m);
int ans = 0;
for(int i=0;i<n;i++) cin >> p[i], ans += p[i];
for(int i=0;i<m;i++) cin >> v[i].fs;
for(int i=0;i<m;i++) cin >> v[i].sc;
sort(all(p)), sort(all(v));
int st = 0;
priority_queue<int> q;
for(int i=0;i<n;i++){
while(st < m && v[st].fs <= p[i]) q.emplace(v[st ++].sc);
if(!q.empty()) ans -= q.top(), q.pop();
}
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while(t --) solve();
}居然在 \(F\) 放签到
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Blog - Floating Ocean！
评论