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

2025.9.29 测试

T1.

马赛克上色

就是个随机题目

告诉我们烤柿要大胆

所有点都是偶度数,直接构造欧拉回路,三个截一段输出

然后有奇数点呢?

这里构出一种正确性很高的 trick

度数越小要求越严格,于是我们每次选出一个度数奇数中度数最小的点 \(a\),先随机找出一个与 \(a\) 有边的点 \(b\),再随机找出一个与 \(b\) 有边的点 \(c\),之后找出一个与 \(c\) 有边的点 \(d\),这里要求点 \(d\) 度数最好为奇数,最后删除边 \(\{a,b\},\{b,c\},\{c,d\}\)

找奇点直接暴力就行

T2

原 P13231 [GCJ 2015 #3] Log Set

发现 \(A\) 长度 log

这题先考虑都是正数

最小的一定是其中一个元素,然后扫一遍删掉其贡献

像这样写

for(int i = 1;i <= n;i++) {a[i].y -= mp[a[i].x];mp[a[i].x + c[k]] = a[i].y;
}

然后一直做就行

考虑有负数,我们自然还是想像这样每次确定一个元素

我刚开始想从 \(0\) 向两边扩,发现找不到确定的值

然后这题有结论曰最大值减去次大值一定是某个元素的绝对值

自己想想就能明白

所以我们每次可以确定一个数的绝对值

由于加不加这个元素的集合两两对应,所以不管是正是负,都可以看做是两个相同的集合删去其中一个

我们直接当做正数

就算删错了,其内部的结构也不会变化,相当于是整体平移

这样找到所有数的绝对值之后

我们再抛出一个结论

当所有正数的和等于初始幂集的最大值时,这个 A 集合就合法

证明我觉得也很简单

根据找绝对值的过程,我们同样可以逆序构造出他的幂集

自己画几个图可以发现,不管是正是负,其内部的结构也不会变化,顶多是整体平移

而我们只需要固定其一个位置的数相同整个集合就是相同的

然后直接基于这个结论,我们就能 \(dp\) 出方案数,以及最小解

然后这个题就没了,代码超级好写,我这个菜鸡发现考场上打的部分分包括暴力和特殊性质几乎包含所有正解的部分

拼一拼就过了

唯一卡了一个多小时的东西是这个( 招笑

"你猜我为什么 MLE"


sum = len = q = 0;
for(int i = 1;i <= q;i ++) f[i].clear();

AC

T3

洛谷

原题

前置
AT_joisc2016_h 回転寿司

loj

其实他们是一个题

先看前置

直接给出做法,分块每个块维护大根堆和小跟堆

大根堆维护内部元素,用于跳整块

小跟堆维护标记,用于重构块

发现如果操作覆盖整块,一定变成其最大值

散块考虑第一个位置一定留下最小值,然后往后扫即可

复杂度 \(O(n \sqrt{n} \log n)\)

看区间 LIS

扫描线右端点

维护所有左端点的答案

有结论 \(f[l + 1][r]\subseteq f[l][r]\)

然后每个数贡献的是一个前缀

考虑 LIS 经典贪心二分的过程,替换第一个大于她的数

我们维护值域序列,每个位置存她的贡献区间

答案即为 \(num_{v \ge q_l}\)

加入一个数

所以我们依次考虑大于其的数,如果他的贡献区间大于上一个的区间,就替换掉多出来的部分

操作等价于在值域 \([v , n]\) AT_joisc2016_h 回転寿司

然后将 \(v\) 修改为 i

用树状数组维护前缀加,单点查

复杂度 \(O(n \sqrt{n} \log n + q \log n)\)

卡常

  • 每次加优先队列,先判会不会操作,不进行无效操作

  • 由于 \(t = n\) 所以不需要重构最后一段

  • 不是环,不用取模

AC

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

相关文章:

  • 深度学习(CVAE)
  • c# aot orm 框架测试 mysql
  • 洛谷题单指南-进阶数论-P2303 [SDOI2012] Longge 的问题
  • PK-2877电流互感器在高频脉冲电源模块测试中的应用方案
  • VC++ 使用OpenSSL创建RSA密钥PEM档案
  • CF1699D Almost Triple Deletions
  • QMT回测模式为什么要在副图进行
  • DSA:DeepSeek Sparse Attention
  • 荒野猎手出击!启明智显ZX7981PO:专治各种恶劣环境的5G插卡路由器
  • AWS CDK重构功能发布:安全重构基础设施即代码
  • 开发即时通社交软件APP首选系统,可定制开发,可提供源码
  • 死锁的处理策略-死锁的检测和解除
  • springboot3 mybatis 数据库操控入门与实战
  • 解决winform调用wpf窗体时原窗体缩小的问题
  • 重构 Java 系统服务!JBoltAI 框架以 AIGS 方案开启企业数智化转型
  • 本土化优势凸显:Gitee如何成为中国开发团队的效率引擎
  • Linux系统OOM终止Oracle进程
  • Filebeat写ElasticSearch故障排查思路(上) - 教程
  • 数字化转型浪潮下,CI/CD工具如何成为企业软件开发效率的加速器?
  • linux 删除服务
  • Verl实验
  • 适配 20 + 主流 AI 模型!JBoltAI 框架让 Java AI 应用兼容性拉满
  • 告别 “一刀切” 管理!MyEMS 为不同行业定制专属能源优化方案
  • Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domains
  • 「突发奇想,灵光乍现」 - hello
  • jenkins 用户权限 管理配置
  • DirectX- DLL修复工具 免费下载!绿色单文件版!安装使用教程
  • 测试集成CI/CD的五大实践:构建高效质量保障体系
  • DirectX修复工具官方中文增强版下载!下载安装教程(附安装包),0xc000007b错误解决办法
  • 死锁的处理策略-避免死锁