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

251009

edu 183 div2

div2

D

假若存在一个满足条件的构造,则最终的排列一定是由若干极长递增子段拼成的,一个区间如果只属于某一个极长递增子段,则这个区间就不包含逆序对,也就不会对 \(k\) 产生贡献;如果一个区间跨越了多个极长递增子段,则这个区间就包含逆序对,也就会对 \(k\) 产生贡献。相对于考虑包含了逆序对的区间,不包含逆序对的区间更容易考虑,所以我们从不包含逆序对的区间入手,尝试构造一个有 \({n(n - 1) \over 2} - k\) 个不含逆序对的区间的排列。

在考虑不包含逆序对区间的数量时,我们只关心有多少个极长递增子段和各自的长度,假设第 \(i\) 个极长递增子段的长度为 \(l_i\),则总共的不含逆序对的区间的数量就是 \(\sum _i {l_i(l_i - 1) \over 2}\),我们这道了这个式子的答案(即\({n(n - 1) \over 2} - k\)),现在要做的就是构造一组满足式子的 \(l_i\)。由于数据范围小,且也满足 dp 的条件,接下来的做法多种多样,dp 也好爆搜也好都能通过,下面给出爆搜的代码

std::vector<int> ans;
int n;
int num;bool vis[N + 5][N * N];bool dfs(int cur, int k) {if (cur == 0) {return k == 0;}int mx = cur * (cur - 1) / 2;if (vis[cur][k] || k > mx || k < 0) {return false;}vis[cur][k] = true;for (int i = 1; i <= cur; ++i) {if (dfs(cur - i, k - i * (i - 1) / 2)) {for (int j = i - 1; j >= 0; --j) {ans.push_back(num - j);}num -= i;return true;}}return false;
}void solve() {int k = 0;std::cin >> n >> k;for (int i = 1; i <= n; ++i) {for (int j = 0; j * 2 < n * n; ++j) {vis[i][j] = false;}}num = n;ans.clear();if (dfs(n, n * (n - 1) / 2 - k)) {for (auto &i : ans) {std::cout << i << ' ';}std::cout << '\n';}else {std::cout << "0\n";}return;
}

E

小清新数据结构题

假设第 \(i\) 个人对观影人数的阈值是 \(p_i\),则对于 \(i\) 来说,需要至少 \(p_i\)\(j\) 满足 \(p_j < p_i\)。于是我们可以处理出 \(cnt_p\) 表示观影人数阈值严格小于 \(p\) 的有多少人,当 \(cnt_p - p < 0\) 时,观影人数阈值为 \(p\) 的人一定都不会观影。但是 \(0 \leq cnt_p - p\) 却不一定说明观影人数阈值为 \(p\) 的会去观影,因为可能存在 \(q < p\)\(cnt_q - q < 0\)。所以我们要找的就是最小的满足 \(cnt_p - p < 0\)\(p\)\(cnt_p\) 就是总共回去观影的人。于是维护一下 \(cnt_p\)\(cnt_p - p\),实现区间修改、区间询问 \(cnt_p - p\) 的最小值和单点查询就好了,线段树易维护。下面给出线段树节点的定义和单点查询的代码:

struct Info {int mn;int r; // 最右边的值int tag;Info (int pos = 0, int val = 0) : mn(val - pos), r(val), tag(0) {}Info (const Info &u, const Info &v) {mn = std::min(u.mn, v.mn);r = v.r;tag = 0;}Info operator + (const Info &u) {return Info(*this, u);}void add(int val) {mn += val;r += val;tag += val;return;}
} tr[M << 3];// 找到第一个 mn 小于 0 的位置
Info find(int cur, int l, int r) {if (l == r) {return tr[cur];}push_down(cur);int m = l + r >> 1;if (tr[cur << 1].mn < 0) {return find(cur << 1, l, m);}else {return find(cur << 1 | 1, m + 1, r);}
}

需要注意的是线段树最后要维护 \(2e6\) 个数,空间别开小了。

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

相关文章:

  • Mybatis笔记
  • PluginMonitor - Typecho 插件监控工具
  • LibreChat-图文并茂手把手教你搭建自己的AI机器人 Step-by-step guide to building your own chatbot
  • NOISG 2025 Prelim
  • STM32 教程
  • 先进反应堆:BWRX-300
  • ch58x/ch59x系列芯片Indication添加
  • Lab 4 Challenge - Sum of Proper Elements
  • perl经典hash解决问题
  • LCR 129. 字母迷宫
  • Ignite3 竟然变成分布式数据库了!
  • NUIST 《程序设计基础》 实验1
  • 10.9总结
  • [MIT 6.828] Lab 1 C, Assembly, Tools, and Bootstrapping
  • WCH低功耗蓝牙系列芯片usb烧录故障排查
  • 使用docker构建.net api镜像及nginx反向代理 - binzi
  • 利用sprintf与snprintf巧妙实现数值变量转换为字符串型
  • Helmholtz-Gibbs自由能与熵弹性
  • 日志|电话号码的字母组合|子集|回溯
  • Docker实用篇(初识Docker,Docker的基本操作,Dockerfile自定义镜像,Docker-Compose,Docker镜像仓库) - a
  • ROIR 2023
  • Rust 的验证码图像识别系统设计与实现
  • 【题解】P12992 [GCJ 2022 #1C] Intranets
  • ysyx:pa3.1批处理系统
  • C 语言的验证码图像识别系统实现
  • Nginx典型流控配置示例
  • 基于 C 语言的验证码图像识别系统实现
  • oppoR9m刷Linux系统: 引导知识
  • 操作系统知识点
  • JAVA: Mybatis添加xml执行多行更新语句时报错