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

代码源国庆模拟赛

ABC 423

做题顺序a->b->c->d->c->d->c->e->d,吃了C*3+D*6共9发罚时,全部WA*1

C把一个减号左右两边写反导致出现负数爆炸了

D:能用prique别用set,常数大还会把元素去重元素去重是很关键的性质

代码源国庆 9/27 (Day 1)

B:两个序列交替进行取当前值和给定值的最小值操作,先考虑D全为0的子问题,枚举l最后一次对答案造成影响是在哪里,值域的数量变成 \(O(n)\) 级别,考虑倒推,枚举最后的答案。

对于原问题可以提前求出每个位置作为最后一次对答案有影响时,答案最终的结果, \(l_i=l_i+\sum\limits^n_{j=i+1}d_j\),将D数组优化掉,原题目转化为D全为0的子问题。

国庆 10/3 Day 3

D:对于边 \((u,v)\)\(|u-v|\leq10\),正解分治。考虑如果我们对图中连续 \(10\) 个点 \([x,y]\) 以每个点为起点跑一次最短路,那么对于查询 \((a,b),a\leq y,b\geq x\),两点的最短路径必定经过 \([x,y]\) 中任意一点,枚举其中每一个点 \(k\) 并求 \(dis(k,a)+dis(k,b)\) 最小值就好;

对于 \(a,b\) 两点都在左边或都在右边的话,若经过中间点就再求一次上面的答案,若不经过则说明这条路径只经过左边或者只经过右边,直接分治即可。

国庆 10/4 Day 4

C:最终的答案相当于对每个 \(a_i\) 决定它的 \(+-\) 值,保证 \(+-\) 标号合法的情况下的最大值。必须发现的性质:设 \(m\) 等于取 \(-\) 的元素的个数,则必须有 \((n+m)\bmod3=1\);用归纳法证明,若存在某个合法的符号序列 \((n,m),(n+m)\bmod3=1\),我们则一定能找到两个合法的符号序列,使得这两个序列取反合并后(对应题目的“之和的相反数”)等于该序列;因为若这两个区间为 \((n_1,m_1),(n_1+m_1)\bmod3=1,(n_2,m_2)\dots\),两个区间取反合并后也就是 \((n_1+n_2,(n_1-m_1)+(n_2-m_2)),2n_1-m_1+2n_2-m_2=3n_1-(n_1+m_1)+3n_2-(n_2+m_2)=-2\equiv 1 \pmod{3}\)。枚举可知所有 \(n\leq3\) 的情况都满足以上规则,便可推广到所有情况。

ABC426

F:发现如果一个产品被买空了,那么之后每次都会被买空,有区间修改,于是想到势能线段树;对于一整个区间没有 "还有存货"->“存货为空” 则直接对区间打标记整体操作,如果有则往下递归,对于会被买空的点单点暴力修改,在暴力修改后做上标记标志以后永远不会出现"还有存货"->“存货为空”的情况因为现在存货已经为空了;如此做每个点的暴力修改最多只会有一次(\(\log n\)),单次修改不计算暴力修改的话就是 \(\log n\),总复杂度 \(O(q\log n+n\log n)\)

国庆 10/5 Day 5

B:贪心,每次对所有值最大的数同时做 \(-1\),若他们连续段的长度分别为 \(l_1,l_2\dots\) 操作数为 \(\sum \lceil\frac{l_i}{2}\rceil\),链表模拟即可

C:考虑删掉 \(k\) 条边的影响,将每条边转换为 \((u,fa_u)\) 的形式,按照 \(dfn_u\) 倒序枚举,同时维护一个单调栈。枚举当前边时对应的连通块应该是 \(u\) 的子树再减去若干子树;若单调栈栈顶 v 是 u 的子树就一直弹出,弹出的 v 的子树就是 u 需要去除的子树;最后往栈内推入 u,这样就可以 \(O(k)\) 求出每个连通块所包含的点集。求出每个连通块的包含的点集应该是在 dfn 序上的一个区间(对应 u 的子树),其中去除若干个子区间(对应去除的 v 的子树);同时每个连通块分割成的区间总数是 \(O(k)\) 级别的,因为每个被去除的 v 只被一个 u 包含。考虑如何求解两个 dfn 序上的区间的直径合并问题;发现如果有两个点集 \(s_1,s_2\),其直径分别为 \((u_1,v_1),(u_2,v_2)\),那么合并两个点集后的直径只会是这四个点任选两点做直径的结果中的一个,也即 \((u_1,v_1),(u_1,v_2),(u_1,u_2),(u_2,v_1),(u_2,v_2),(v_1,v_2)\) 中的一个。有了这个逻辑就可以只用 st 表或线段树,通过点集(在dfn上的连续段)之间两两合并求解 u 对应的连通块的直径。

D:考虑如果值域只为 \(0\to1\) 的特殊序列 a,要判断操作后的序列是否可行我们只需要判断是不是每一个 1 都没有往前移即可。拓展到值域为 \(n\),也即我们枚举 \(x=1\to n\),定义 \(b_i=[a'_i<=x]\),这样就把操作后序列转化成了一个 01 序列,我们只需要保证对于任意 x 都满足条件那么该序列便合法。实现上我们考虑状压dp,\(f_i\) 就表示当 \(x=popcount(i),b=i\) 时,对于所有 \(x'<=x\) 的情况也依然合法的方案数;注意必须此时的 01 序列可以由原题的 01 序列后移达到,否则 \(f_i\) 则没有值;转移时则直接 \(f_{i\cup\{j\}}:= f_{i\cup\{j\}}+ f_i,\{j\}\notin i\)

国庆 10/6 Day 6

B:从当前连通块中找到边权最大的边,枚举一条边断开它,如果边两边的连通块 \((a,b)\) 大小之差 \(|sz_a-sz_b|<tag+1\),(tag 的定义就是大连通块中会删掉多少个点,而点的位置不确定),就认为两边的连通块所有的点都可以通过当前枚举的这条边,答案加上该边的贡献,结束枚举。否则的话我们删掉小的连通块,同时在大的连通块加上一个标记 \(tag\),表示该连通块中会删掉任意 \(sz_a\) 个点,但删哪些点不重要,递归下去即可。

C:一个等腰直角三角形直接求是三维数点,但我们将其变成一个梯形 - 一个长方形就是两个二维数点直接做就好了。梯形的数点我们就把每个点的坐标 \((x,y)\) 改成 \((x,x+y)\) 也就是经过该点的斜率为 \(-1\) 的直线的截距,用这个值放进二位数点就好了

D:首先有可能一次攻击两边都miss,直接不管这部分;考虑将一轮看成三种情况。\(\frac{(1-p)q}{1-(1-p)(1-q)}\) A 掉血,\(\frac{p(1-q)}{1-(1-p)(1-q)}\) B 掉血,\(\frac{pq}{1-(1-p)(1-q)}\) 都掉,这种情况我们记为 C,分母中的 \((1-p)(1-q)\) 就是都不中的情况直接减掉,记 \(p_A,p_B,p_c\) 为这三者的概率。考虑枚举 \(c_A,c_B,c_C\) 分别是这三种情况的数量,其中有限制,因为我们要保证 A 一定不死,B 差最后一次攻击死然后被 A 一下打死(因为是轮流攻击A先手),\(c_B+c_C=m-1,c_A+c_C<n\),答案为

\[\sum_{c_B+c_C=m-1,c_A+c_C<n}\binom{c_A+c_B+c_C}{c_A,c_B,c_C}\times{p_A}^{c_A}{p_B}^{c_B}{p_C}^{c_C}=\sum_{c_B+c_C=m-1,c_A+c_C<n}\binom{c_A+c_B+c_C}{c_A}\times\binom{c_B+c_C}{c_B}\times{p_A}^{c_A}{p_B}^{c_B}{p_C}^{c_C} \]

这里 \(\binom{A+B+C}{A,B,C}=\binom{A+B+C}{A}\times\binom{B+C}{B}\)

发现枚举 \(c_C\) 后能得出 \(c_B\) 的值,剩下还需枚举 \(c_A\),但我们思考真的需要枚举 \(c_A\) 吗?考虑将式子变形已知 \(c_C,c_B\) 的情况,记 \(i=c_A\),已知限制条件 \(c_B+c_C=m-1\)

\[{p_B}^{c_B}{p_C}^{c_C}\times\binom{m-1}{c_B}\sum_{i<n-c_C}\binom{c_A+m-1}{c_A}\times {p_A}^i \]

发现求和内的值只与 \(i\) 有关,可以前缀和。\(O(n+m)\) 解决。

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

相关文章:

  • CSP-S模拟30 2025.10.12
  • 记录fiddler抓包mumu模拟器
  • 神经网络读书报告
  • 机器学习初识
  • MinIO 介绍(2)--MinIO 客户端 mc 基本功能
  • 深度学习初识
  • 关于UE5基础关卡创建的注意点
  • 2025年10月恒温恒湿系统厂家最新推荐榜单,精加工车间/厂房/美术馆/仓库/计算机房/档案室/工业/工厂车间恒温恒湿空调系统公司推荐
  • 征集歌单
  • Hello world
  • ABC427 游记
  • 乐理 -02调式
  • Python 基于python实现的图片压缩助手
  • ElasticSearch
  • 20232302 2025-2026-1《网络与系统攻防技术》实验一实验报告
  • 2023 ICPC ECfinal J
  • 嵌入式十六进制的地址转换成十进制MB单位
  • 20232318 2025-2026-1 《网络与系统攻防技术》 实验一实验报告
  • 实时Galgame - 动漫角色 语言生成+图片生成
  • 系统响应慢分析案例
  • Linux文件系统与磁盘工作原理
  • 平安好车主小程序 充电站、加油站列表vmp+wasm逆向
  • Linux文件系统的实验
  • 软中断softirq的CPU使用率升高
  • CPU多进程切换导致过载-CPU上下文切换
  • Vue3 之pinia状态管理
  • 乐理 -01识谱
  • shader func
  • 案例分析-DDOS攻击、网络延迟(延迟确认纳格算法)、NAT延迟
  • 服务器丢包分析-iptables规则-MTU大小设置错误-perf-火焰图分析处理请求时内核线程调用