当前位置：首页 > news >正文

atcoder abc 358

news 来源：原创 2024/9/29 17:22:14

A welcome to AtCoder Land

题目：

思路：字符串比较

代码：

#include <bits/stdc++.h>using namespace std;int main() {string a, b;cin >> a >> b;if(a == "AtCoder" && b == "Land") cout << "Yes" << endl;else cout << "No" << endl;return 0;
}

B Ticket counter

题目：

思路：记录下第 i-1个人买完票的时间now，更新now 为max t[i], now后now + a 输出now

代码：

#include <bits/stdc++.h>using namespace std;int main() {int n, a;cin >> n >> a;vector<int> t(n + 1);int now = 0;//now表示上一个人买完票的时间for(int i = 1; i <= n; i ++ ) cin >> t[i];for(int i = 1; i <= n; i ++ ) {if(i == 1) {now = t[i] + a;cout << t[i] + a << endl;} else {now = max(t[i], now);now += a;cout << now << endl;}}return 0;
}

C popcorn

问题

思路：注意到n很小，考虑爆搜，现在思考一个问题，如何把时间尽可能的压缩。

1 字符串比较是浪费时间时间，因此可以考虑优先处理下字符串，这里的做法是状态压缩，o代表二进制的1，x代表2进制的0，两个摊位的爆米花口味是a | b。这样可以极大的节省时间

2 剪枝，设全局最大值ans = 0，如果在dfs过程中方案数大于ans直接return

3 排列组合优化这里选的摊位并没有明确的顺序，因此先选a和先选b是一样的，可以在dfs中记录一个start

代码：

#include <bits/stdc++.h>using namespace std;int main() {int n, m;cin >> n >> m;vector<int> str(n + 1);for(int i = 1; i <= n; i ++ ) {int cnt = 0;for(int j = 0; j < m; j ++ ) {char ok;cin >> ok;if(ok == 'o') cnt +=  1 << j;}str[i] = cnt;}vector<bool> st(n + 1, false);int ans = n;function<void(int, int, int)> dfs = [&](int u, int cnt, int res) -> void {if(cnt >= ans) return;if(res == ((1 << m) - 1)) ans = cnt;for(int i = u + 1; i <= n; i ++ ) {if(!st[i]) {st[i] = true;int tmp = res;res |= str[i];dfs(i, cnt + 1, res);st[i] = false;res = tmp;}}};dfs(0, 0, 0);cout << ans;return 0;
}

D souvneirs

题目：

思路：堆，排序，双指针，贪心，平衡树都可以做。把a放进小根堆里，b从小到大sort，如果满足条件b索引++，每次操作把堆顶pop掉...

这里有个小坑，在对vector排序如果没用到a[0]，一定要从a.begin() + 1开始sort, 当然这里数都大于0，这个不影响

代码：

#include <bits/stdc++.h>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, m;cin >> n >> m;vector<int> a(n + 1);vector<int> b(m + 1);for(int i = 1; i <= n; i ++ ) cin >> a[i];for(int i = 1; i <= m; i ++ ) cin >> b[i];sort(b.begin(), b.end());priority_queue<int, vector<int>, greater<int>> q;for(int i = 1; i <= n; i ++ ) q.push(a[i]);long long ans = 0;int i = 1;while(q.size() && i <= m) {if(q.top() >= b[i]) {ans += q.top();i ++;q.pop();} else {q.pop();}}if(i == m + 1) cout << ans;else cout << -1;return 0;
}

E alphabet tiles

题目：