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

牛客周赛 Round 67

news 2024/11/14 23:52:50

排序危机

思路：

模拟

遍历的过程中用三个字符串进行储存即可

代码：

#include <bits/stdc++.h>
#define vec vector
#define endl '\n'
using namespace std;
using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;void solve() {int n; cin >> n;string s; cin >> s;string low, up, dig;for (char c : s) {if (isdigit(c)) dig += c;if (isupper(c)) up += c;if (islower(c)) low += c;}cout << low + dig + up << endl;return;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1; //cin >> tt;while (tt -- ) solve();return 0;
}

小歪商店故事：卷

思路：

计算amax，我们只需计算b*c/d即可，因为是严格小于，我们要在相等时减去1

代码：

#include <bits/stdc++.h>
#define vec vector
#define endl '\n'
using namespace std;
using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;void solve() {LL a, b, c, d; cin >> a >> b >> c >> d;cout << a - (b * c / d - (b * c % d == 0)) << ' ';return;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1; cin >> tt;while (tt -- ) solve();return 0;
}

小苯的计算式

思路：

暴力模拟

代码：

#include <bits/stdc++.h>
#define vec vector
#define endl '\n'
using namespace std;
using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;int cal(int x) {string s = to_string(x);return (int)s.size();
}
void solve() {int n, c; cin >> n >> c;int ans = 0;for (int i = 0, x; i <= c; i ++ ) {x = c - i;if (cal(i) + cal(x) == n - 2 - cal(c)) {ans += 1;}}cout << ans << endl;return;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1; //cin >> tt;while (tt -- ) solve();return 0;
}

K

思路：

首先最大的是n个，这是无可置疑的，我们构造n个1

其次我们考虑k=n-1的情况

我们构造010101的交替串

那么对于小于n-1的k，我们只需要构造出k+1个交替01，接着后面跟上0或者1即可

如

6 3

1 0 1 0 0 0

代码：

#include <bits/stdc++.h>
#define vec vector
#define endl '\n'
using namespace std;
using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;void solve() {int n, k; cin >> n >> k;if (k > n) cout << "NO" << endl;else {cout << "YES" << endl;if (k == n) for (int i = 1; i <= n; i ++ ) cout << 1 << ' ';else {for (int i = 1; i <= k + 1; i ++ ) cout << (i & 1) << ' ';for (int i = k + 2; i <= n; i ++ ) cout << ((k + 1) & 1) << ' ';}}return;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1; //cin >> tt;while (tt -- ) solve();return 0;
}

小苯的区间选数

思路：

数位dp，给定的两个区间可以形成得到的数的上下界up，down

接着我们对up和down从高位向低位进行遍历，如果up该位上的数大于down上面的数，那么可以此位减1，接着后面跟上一连串的9

这其实就是保留了up的前缀

比如

3xxxx，32xxx，325xx，3257x，32579

这个x上的数我们是直接填9作为最大的

代码：

#include <bits/stdc++.h>
#define vec vector
#define endl '\n'
using namespace std;
using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;void solve() {LL l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;LL down = l1 + l2, up = r1 + r2;int ans = 0, cnt = 18, now = 0;for (LL i = 1e18; i; i /= 10) {int l = down / i % 10, r = up / i % 10;now += r;if (r > l) ans = max(ans, now - 1 + cnt * 9);cnt--;}cout << max(ans,now) << endl;return;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1; cin >> tt;while (tt -- ) solve();return 0;
}

小Z的树迁移

思路：

树上前缀和+启发式合并

树上前缀和不过多赘述，对于答案我们只需要离线处理就可以了

当遍历到节点u的时候，那么我们只需要找到其子树内和其深度相差d的最大前缀和就行了。

时间复杂度是启发式合并的nloglog

代码：

#include <bits/stdc++.h>
#define vec vector
#define endl '\n'
using namespace std;
using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
const int maxn = (int)1e5 + 9;
void solve() {int n; cin >> n;vec<vec<PII>> e(n + 1);for (int i = 1, u, v, w; i < n; i ++ ) {cin >> u >> v >> w;e[u].push_back({v, w}), e[v].push_back({u, w});}vec<int> dep(n + 1);vec<LL> val(n + 1), ans(n + 1);function<void(int, int)> dfs = [&](int u, int f) {dep[u] = dep[f] + 1;for (auto [v, w] : e[u]) {if (v == f) continue;val[v] = val[u] + w;dfs(v, u);}};dfs(1, 0);vec<vec<PII>> w(n + 1);int q; cin >> q;for (int i = 1, u, d; i <= q; i ++ ) {cin >> u >> d;w[u].push_back({d, i});}function<map<int, LL>(int, int)> dfs2 = [&](int u, int f) {map<int, LL> Max;for (auto [v, w] : e[u]) {if (v == f) continue;map<int, LL> tmp = dfs2(v, u);if (Max.size() < tmp.size()) swap(Max, tmp);for (auto [deep, value] : tmp) Max[deep] = max(Max[deep], value);tmp.clear();}Max[dep[u]] = max(Max[dep[u]], val[u]);for (auto [d, id] : w[u]) {if (!Max[dep[u] + d]) ans[id] = -1;else ans[id] = Max[dep[u] + d] - val[u];}return Max;};dfs2(1, 0);for (int i = 1; i <= q; i ++ ) cout << ans[i] << endl;return;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1; //cin >> tt;while (tt -- ) solve();return 0;
}

查看全文

http://www.mrgr.cn/news/70579.html