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

Educational Codeforces Round 183 (Rated for Div. 2) A~D

A - Candies for Nephews

模拟。

\(3\) 的余数。

点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;void solve() {int n;std::cin >> n;std::cout << (3 - n % 3) % 3 << "\n";}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}

B - Deck of Cards

模拟。

手玩可以发现,\(0/1\) 的顺序无所谓,对两边的影响是固定的,除开这些后,\(2\) 会影响剩余的数的两边,当 \(cnt_2 * 2 \ge n\) 的时候,中间全都不确定,否则就左右两边影响 \(cnt_2\) 个。

注意 \(k=n\) 特判,以及是 \(1\) 在上面,所以去掉上面的是从 \(1\) 开始,不是 \(n\)

点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;void solve() {int n, k;std::cin >> n >> k;std::string s;std::cin >> s;if (k == n) {std::cout << std::string(n, '-') << "\n";return;}int cnt[3] {};for (int i = 0; i < k; i += 1) {cnt[s[i] - '0'] += 1;}std::string ans = "";if (cnt[0]) {ans += std::string(cnt[0], '-');}n -= cnt[0] + cnt[1];if (2 * cnt[2] >= n) {ans += std::string(n, '?');} else {ans += std::string(cnt[2], '?');ans += std::string(n - 2 * cnt[2], '+');ans += std::string(cnt[2], '?');}if (cnt[1]) {ans += std::string(cnt[1], '-');}std::cout << ans << "\n";}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}

C - Monocarp's String

前缀和,哈希。

\(a/b\) 视为 \(+1/-1\),那么问题就是问删除一个区间使得数组总和为 \(0\)

定义 \(a_i\)\(a/b\) 的贡献,若 \(\sum_{i=1}^na_i = d\),说明我们要找一段区间和等于 \(d\) 的删掉;定义 \(pre_i\) 表示前 \(i\) 个数的和,用哈希表 \(mp\) 记录每个 \(pre_i\) 的下标,如果 \(pre_i-d\) 出现过,说明 \(i-mp[pre_i-d] + 1\) 这一段就是要删掉的,比较一下取最小值即可。

点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;void solve() {int n;std::cin >> n;std::string s;std::cin >> s;int cnt[2] {};for (int i = 0; i < n; i += 1) {int c = s[i] - 'a';cnt[c] += 1;}int d = cnt[0] - cnt[1];map<int, int> mp;mp[0] = 0;int ans = n, sum = 0;for (int i = 0; i < n; i += 1) {if (s[i] == 'a') {sum += 1;} else {sum -= 1;}if (mp.count(sum - d)) {ans = min(ans, i - mp[sum - d] + 1);}mp[sum] = i + 1;}if (ans == n) {ans = -1;}if (d == 0) {ans = 0;}std::cout << ans << "\n";}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}

D. Inversion Value of a Permutation

\(dp\)

要求构造一个长度为 $ n $ 的排列,使得其逆序值恰好为 $ k $。逆序值定义为至少包含一个逆序对的连续子数组的数量。实际上,总子数组数为 $ \frac{n(n+1)}{2} $,减去没有逆序对的子数组数(即递增连续子数组数)即为逆序值。因此,问题转化为构造一个排列,使其递增连续子数组数 $ S = \frac{n(n+1)}{2} - k $。

若 $ S $ 无法表示为若干段长度 $ l_i $ 的平方和的一半之和(即 $ \sum \frac{l_i(l_i+1)}{2} = S $,其中 $ \sum l_i = n $),则输出 \(0\)。否则,将排列分成若干连续递增的段,段间递减排列即可。具体构造时,从大到小依次分配段内数字,每段内数字递增。

设 $ dp[x][i][j] $ 表示长度为 $ x $ 的排列中能否用若干段覆盖 $ i $ 个元素且递增子数组数为 $ j $,转移方程为:

\[dp[x][i+l][j + \frac{l(l+1)}{2}] \leftarrow dp[x][i][j] \quad \text{for } l \leq x-i \]

然后根据预处理结果还原方案即可。

点击查看代码
#include <bits/stdc++.h>using namespace std;using i64 = long long;const int N = 30;
bool dp[N + 1][N + 1][500];
int len[N + 1][N + 1][500], lst[N + 1][N + 1][500];void solve() {int n, k;std::cin >> n >> k;int st = n * (n + 1) / 2 - k;if (!dp[n][n][st]) {std::cout << 0 << "\n";} else {std::vector<int> has;int i = n;while (i > 0) {int l = len[n][i][st];has.push_back(l);st = lst[n][i][st];i -= l;}std::reverse(has.begin(), has.end());std::vector<int> ans;int now = 0;for (auto &d : has) {int l = n - now - d + 1;int r = n - now;for (int num = l; num <= r; num++) {ans.push_back(num);}now += d;}for (int i = 0; i < n; i += 1) {std::cout << ans[i] << " \n"[i + 1 == n];}}}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);for (int x = 1; x <= N; x++) {int y = x * (x + 1) / 2;dp[x][0][0] = true;for (int i = 0; i < x; i++) {for (int j = 0; j <= y; j++) {if (!dp[x][i][j]) continue;for (int l = 1; l <= x - i; l++) {int ni = i + l;int nj = j + l * (l + 1) / 2;if (nj <= y) {dp[x][ni][nj] = true;len[x][ni][nj] = l;lst[x][ni][nj] = j;}}}}}int t;cin >> t;while (t--) {solve();}return 0;
}

E. Predicting Popularity

数据结构,晚上补补。

http://www.hskmm.com/?act=detail&tid=26083

相关文章:

  • Cisco vManage漏洞分析:未授权RCE与权限提升完整攻击链
  • QBXT2025S刷题 Day6题
  • 硅芯片创新如何成为云计算成功的关键
  • 东萍象棋 DhtmlXQ UBB 转 中国象棋云库查询 FEN
  • 斑马ZT210碳带及纸张安装教程
  • DHCP及DNS
  • Gitlab Runner 学习
  • AI元人文:论价值原语博弈与人文知识库共建如何重塑智能社会的决策基石
  • 算法第一张作业
  • 【高级算法】单调队列优化动态规划
  • MySQL CentOS7 本地安装
  • TypeScript装饰器 - Ref
  • 【笔记】排列与组合学习笔记
  • 【高级数据结构】线段树
  • 【高级数据结构】ST 表
  • 【高级算法】树形DP
  • 【高级数据结构】浅谈最短路
  • C++_基础
  • 2025电位仪厂家最新企业品牌推荐排行榜,纳米粒度及 Zeta 电位仪,Zeta 电位仪公司推荐
  • PCIe扫盲——物理层逻辑部分基础(二)
  • 前沿仿真未来趋势
  • StarRocks与Apache Iceberg:构建高效湖仓一体的实时分析平台 - 详解
  • 斑马打印机打印头更换教程
  • 构造中国剩余定理方程组的解
  • 2025粒度仪厂家最新品牌推荐榜,喷雾粒度分析仪, 激光粒度仪,激光粒度分析仪,纳米粒度仪公司推荐
  • MTK oppoR9m Smart Phone flash Tool 提示 ERROR: STATUS_ABORT(0xC0010002)
  • 二分图最大匹配 Dinic/EK算法
  • 基本Dos指令
  • 2025 年酒店一次性用品源头厂家最新推荐排行榜:含牙签牙线筷子套杯盖杯垫杯套外卖筷子印刷房卡套信封用品优质供应商盘点
  • 2025餐饮一次性用品厂家最新推荐排行榜:聚焦资质口碑与产品实力,助力餐饮企业精准选品!