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

10.20 CSP-S模拟35 改题记录

HZOJ

写在前面

改不出来T3T4,遂先把这个写了,然后晚上搞搞恐怖的容斥qwq。这场模拟赛不多做评价,我不知道是我菜还是题史,虽然大概率是两者都有。

《美人》

한 번 보고 두 번 보고
一眼 再一眼
자꾸만 보고 싶네
总忍不住想多看
아름다운 그 모습을
那美丽的容颜
자꾸만 보고 싶네
总忍不住想多看
그 누구나 한 번 보면
任谁初见一面
자꾸만 보고 있네
都会驻足流连
그 누구의 애인인가
不知是谁的恋人
정말로 궁금하네
实在令人好奇
모두 사랑하네
人人都爱慕
나도 사랑하네
我也爱慕
모두 사랑하네
人人都爱慕
나도 사랑하네
我也爱慕
나도 몰래 그 미인을
我也不自觉地
자꾸만 보고 있네
频频望向那美人
그 모두 다 넋을 잃고
众人都失了神
자꾸만 보고 있네
痴痴凝望不停
모두 사랑하네
人人都爱慕
나도 사랑하네
我也爱慕
모두 사랑하네
人人都爱慕
나도 사랑하네
我也爱慕
그대여, 그대는 오월의 제비꽃을 닮은 미인
你啊 宛如五月紫罗兰的美人
하늘 높이 나는 것을 부끄럽지 않게 여기리
愿你翱翔天际 不必羞怯
그대여, 그대는 오월의 제비꽃을 닮은 미인
你啊 宛如五月紫罗兰的美人
하늘 높이 나는 것을 부끄럽지 않게 여기리
愿你翱翔天际 不必羞怯

A. 集合

疑似某场模拟赛因为太难没改的T3。题意是给出一棵树,每次可以将给定树边两端点的分别的点集更新成它们的并。求问最后每个点分别在多少个集合中出现。

赛时往启发式合并上面想了,然而根本没法启发式合并,遂每次建新点,set强行更新,然后最后跑dfs求路径经过了多少树上的最终点所在的点。瓶颈其实在于无法\(O(n)\) 就得出答案。然后其实也想到了倒着做。奈何时间不多而且还被我否决了。。。题解思路就利用集合的性质:两集合并的大小等于两集合分别的大小减去两集合交的大小。正着做能得到每个点代表点集的大小,倒着做就是该点在点集的出现次数。主要是脑筋没转过那个弯,甚至关于那个思路的图都画对了。。。然后实际代码简单得要命,甚至不用建图。

B. 存钱

疑似99.9999999999%的人都写随机化硬搞过去的。然后就纯纯性质题。

形式化题意是给出若干种区间及其长度,区间间可以有交。有一个长为\(m\) 的东西可以覆盖在区间上。求问至少要用多长的数轴才能使得无论那个东西怎么放,数轴上都还剩下至少\(k\) 种区间。

先看\(k==n-1\) 的子任务。虽然赛时想到了这个结论,但是觉得一眼假就没写。分析题目,我们的目标是使任何一个长为\(m\) 的区间都不存在两种完整的区间同时在其中。贪心地想,就可以将所有的区间尽可能往前放,放在恰好没有完整包含自己与前一个区间的位置。然后长度大于\(m\) 的区间一定不会被完整覆盖所以我们不用考虑,最后答案对其长度取max即可。对于其他的,我们推式子很容易得到\(m+1+\sum_{i=2}{n-1}(m+1-a_i)\),所以将最小的两段放在两端答案最小。所以直接算即可。

对于\(k==n-2\) 的子任务,我们考虑将其拆分成两个\(n-1\) 的子任务。然后显然可以选择四段对答案不产生影响,显然该选最小的四段。然后式子就是\(m+1+两个子任务中\sum 项较大的那个\)。显然当值越接近\(sum/2\) 答案越小。考虑01背包判断是否能达到某个值,发现无法满足所有子任务。我们大胆猜测其答案所在的区间范围不会很大,所以我们将判断是否能达到某个值改为是否能达到某个差值即可。多试几个bitset大小就能硬搞过去了。然后对于\(n<=4\) 的我们特判掉即可。

C. 串串

看出来了和border有关,奈何不会容斥。。。咕了咕了。

D. 游走

概率期望还有多项式。。。输出0给我5分算你仁慈。

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

相关文章:

  • 我写过的动态规划问题的状态表示与转移汇总
  • 基于大语言模型的具身智能语义地图与导航研究 - MKT
  • 2025最新发布|中国薪酬SaaS软件市场分析及测评
  • CSP-S模拟36
  • [图形]StructureBuffer
  • 【题解】洛谷 P3395 路障
  • (薛定谔のCSP-S)模拟35 2025.10.20
  • AI建的网站,真的对SEO友好吗?深度剖析其优势与潜在缺陷
  • 追忆
  • 高效增量综合
  • 2025年上海律师推荐排行榜,经侦律师,民事纠纷律师,刑事律师,经济律师,婚姻律师,法务律师,负债律师事务所专业解析
  • 结对项目———四则运算
  • luogu P14259 兄妹(siblings)
  • 2025年通风设备厂家权威推荐榜:通风气楼/通风天窗/排烟天窗/自然通风器,精选圆拱型/一字型/三角型/电动启闭式全系列优质厂家
  • 作业操作步骤
  • 2025年化工原料厂家推荐排行榜:双氧水/片碱/盐酸/磷酸/PAC/聚丙烯酰胺/消泡剂/阻垢剂等工业级化学品优质供应商
  • 2025年棋牌室加盟品牌权威推荐榜:自主棋牌室加盟,自助棋牌室加盟,智能棋牌室加盟,共享棋牌室加盟品牌综合评测与选址运营指南
  • 模拟赛记录
  • 结对项目--小学四则运算题目生成器
  • 2025年焊接变位机厂家权威推荐榜:变位机/双轴变位机专业制造,高精度传动与定制化解决方案实力解析
  • 阿里云智能语音简单使用:语音识别
  • 10月20日
  • 20232426 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • 10.20
  • 题单
  • 计数
  • 2025年风机盘管厂家权威推荐榜:两联供室内机/水系统空调室内机/全包围风机盘管/超薄风机盘管/静音风机盘管/半包围风机盘管/单冷源除湿新风机/五恒空调
  • Wamp 启动图标橙色(2/3 服务运行):MySQL 服务启动失败解决方案
  • 文章测试
  • 2025年防腐工程厂家最新权威推荐榜:喷砂/热喷锌/热喷铝/油漆涂装/热喷耐磨材料,专业工艺与长效防护解决方案