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

20251008 模拟测 总结

\(\mathcal{Preface}\)

分数 \(50+100+40+100=290\),甚至比去年低 \(15\) 分,有点受不了了。

A 题代码上挂了 \(50\) 分,C 题思维上挂了 \(60\) 分。
简称:挂了 \(50\) 分,还“挂了”\(60\) 分。

挂的最猛烈的一次。挺愤怒的。

\(\mathcal{Problem \space{} A}\)

看到分数那一刻,我整个人愣住了。
xor 这题,\(50\) 分?!
我难以置信的揉着眼睛……不,一定是看错了,一定是……
可我一次又一次地确认:真的,是真的,是真的只有 \(50\) 分。

我震惊了,眼前一片模糊。
望向左侧的排行榜,看着那个刺眼的 rk\(6\),心里如刀绞般难受。

只有 \(290\)pts。比去年还低……我绝望着闭上了眼。

上面这段话纯属虚构哈,我当时的反应其实上是这样的:What?发生什么了,A 题咋挂了这么多分?然后就跑回座位去查错了。没有悲伤只有愤怒哈哈哈。

Tag:暴力枚举。

水题,算出总和 \(sum\),然后枚举每个 \(i\) 算出当让 \(a_i\) 异或上 \(k\) 情况下的答案 \(sum - a_i + a_i \oplus k\),全部的取 \(\max\) 即可。

但是这里有一个坑点——也许只有我这么糖——异或的优先级是很低的。也许之前用得少,大多也是用在状压里,不会出现多种符号所以没有管过优先级,不过总之这里一定不能写 sum-a[i]+a[i]^k,乍一看没问题但异或的优先级没加减法高,所以这里会直接转化为 (sum-a[i]+a[i])^k……一脸懵。总之之后长个心眼,注意位运算优先级。

upd:What?不是哥们别吓我,按位或、与和异或的优先级还没左移右移高?我死了,原来我学 OI 这么久了才知道原来它们优先级这么低?我怕是成井底之蛙了——对我就是井底之蛙!

\(\mathcal{Problem \space{} B}\)

Tag:暴力枚举,模拟 / 贪心,高精度比较。

可以暴力枚举第一种操作执行多少次(因为最多执行 \(9\) 次,第 \(10\) 次的时候就转回来了,没必要)以及第二种操作在哪个位置执行,然后挨个算出数,高精度比较,求 \(\max\)

但是赛时脑抽没想到这么水的做法,直接贪心上了。

只要高位高,低位再低也无所谓。因此肯定要求高位为 \(9\)

高位为 \(9\),有且仅有两种方案,一种是使用第一种操作将最高位调成 \(9\) 然后再在后面调一个位置做第二种操作,还有一种是使用第一种操作将最高位调成 \(8\),然后再使用第二种操作把最高位弄回 \(9\)

两种方案取 \(\max\) 即可,同样的,高精度比较。

\(\mathcal{Problem \space{} C}\)

Tag:简单思维推导,DP,调和级数,二分。

我晕。我赛时代码只要 DP 顺序反个边,查询的时候再加个二分就成功 \(40 \to 100\) 了。这还玩得下去?

易知有一个式子,$ \lfloor \frac {\lfloor \frac{k}{x} \rfloor} {y} \rfloor = \lfloor \frac{k}{x \times y} \rfloor $,也就是向下取整这玩意儿存在结合律。

那么只要找到最小的 \(p\) 使得 \(\lfloor \frac{x}{p} \rfloor \le y\),就只需要判断如何用最小代价凑出 \(p\) 这个数了。

首先对 \(a\) 取后缀 \(\min\):因为如果可以用 \(2\) 的代价 \(\div 3\),绝不会有人傻傻用 \(3\) 的代价 \(\div 2\)

然后定义 \(dp_x\) 表示要凑出 \(x\) 最少需要多少的代价,最初有 \(dp_x = \infty\)\(dp_1 = 0\)

接着我们枚举 \(x\),范围 \(2 \sim 10^5\),那么下一步就是看如何用 \(dp_x\) 去更新其他 DP 值了。容易想到枚举 \(i\),范围 \(2 \sim n\)(为什么不是 \(1 \sim n\)?因为绝不会有人花钱去做无用功),不过有一点需要保证,那就是必须得满足 \(x \times i \le 10^5\),不然超出了范围,也就更不可能查询这个位置了。

然后……你以为时间复杂度是 \(O(n^2)\) 的?如果你这么想,你就大错特错了!因为 \(i\) 必须要 \(\le \frac{10^5}{x}\),这是什么?对极了!调和级数!所以时间复杂度其实是 \(O(n \log n)\) 的……然后你就这么水灵灵的过了。

注意找 \(p\) 的那会儿需要用二分。

\(\mathcal{Problem \space{} D}\)

Tag:思维,枚举,排序,区间并集(?)。

考虑标定 \(l\),寻找有多少个满足条件的 \(r\)

不难发现,\(r\) 可取的区间,其实就是所有字母在 \(l\) 往后的后缀中出现的第一次到第二次之间的这段区间;换言之,将所有字母编码为 \(1 \sim 26\),编码为 \(i\) 的字符在 \(l\) 往后的后缀中出现的第一次和第二次的位置分别是 \(a_i\)\(b_i\),那么 \(r\) 可取的范围就是 \([a_1,b_1] \cup [a_2,b_2] \cup \dots \cup [a_{25},b_{25}] \cup [a_{26},b_{26}]\)

这些区间很好找,一开始记录下就行,但问题在于如何计算并集?可以考虑把所有区间信息存进 pair 里从小到大排序,然后一个个计算,注意不要和之前的区间重合即可。

注意这题挺卡人的——至少我这么认为——不能开数组维护字母信息!要用 vector——不能二分找字母!只能用指针扫——总之我觉得是挺卡人的,幸好我卡过了。

\(\mathcal{Summary}\)

A 题挂分太可惜,之后一定要注意;
位运算的优先级,高高低低要分清。

B 题贪心没失分,可惜没有打暴力;
D 题卡人过于猛,幸好卡过无影响。

C 题暴力已全出,只要最后小思维;
没能拿满挺可惜,幸好暴力没丢分。

A 题源于小轻敌,小小思维挂 C 题;
其实这场能 AK,只因小错挂全场……

行吧,那就记个教训吧。

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

相关文章:

  • VuePress v2是否支持Vue2的配置?
  • 新人UP主:晓牛开发者的第一篇自我介绍博客测试发布
  • ubuntu20.04服务器版安装中文输入法分享
  • DeCLIP
  • 19_win11_wsl_linux_配置jdk_mvn
  • 在AI技术唾手可得的时代,挖掘新需求成为核心竞争力——某知名CTF资源库需求洞察
  • 计蒜客 A1108 百度地图的实时路况
  • 学生管理系统面向对象问题分析
  • 解码Linux环境搭建
  • dns 委派
  • 几个重要的偏微分方程(二)
  • 如何测试台式机电源
  • 「SCOI2015」小凸解密码题解
  • 2025免费好用的度数符号的神器
  • 折腾笔记[31]-在线转换吉卜力风格图片
  • 2025 风淋室厂家 TOP 品牌推荐排行榜,不锈钢风淋室,防爆风淋室,自动门风淋室,风淋门公司推荐
  • 计算机视觉的现状与未来挑战
  • #20232408 2025-2026-1《网络与系统攻防技术》实验一实验报告
  • reLeetCode 热题 100- 239. 滑动窗口最大值 队列 - MKT
  • 深入解析:三维坐标转换
  • ToDo-List EveryDay
  • 英语_阅读_Water and digital life_待读
  • Wails + Go + React跨平台RTSP播放器分享
  • 网络与系统攻防实验报告一 20232408李易骋1
  • [KaibaMath]1003 关于[x+y]≥[x]+[y]的证明
  • 【A】Strategy above the depths
  • 完整教程:Python 训练营打卡 Day 43
  • 快读快写
  • [KaibaMath]1002 关于[x+n]=[x]+n的证明
  • SpringBoot进阶教程(八十七)数据压缩