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

10.14 CSP-S模拟31 改题记录

HZOJ

写在前面

终于有一场没有一大堆数学的摩尼塞了,但这个难度是认真的?码量甚至T2>T1>T3>T4?CSP-S还有十多天,貌似现在还没确定自己大概的水平。。。好像能做的只有听天由命了。再坚持一个多月就能离开这个地方了,最后再加把劲吧。

《Dlwlrma》(窝的同名曲哦)

이건 비밀이야
这是个秘密
아무에게도 고백하지 않았던
当我把对谁都不曾坦白过的
이야기를 들려주면
故事讲给你听
큰 눈으로 너는 묻지
你瞪大眼睛问我
How wow wow whatever
怎么会 wow wow 不管怎样
나 실은 말이야
其实我啊
저기 아득한 미래로부터 날아왔어
是从那遥远的未来飞过来的
쏟아질 듯이
如散落一般
빼곡한 별들 사이를 지나 fly fly fly
穿过了漫天的繁星之间 飞着 飞着 飞着
있지
说真的
그곳도 사실 바보들투성이야
其实那里也都是白痴和傻瓜
아니 매우 반짝이는 건
不 格外闪亮的事物
오히려 now now now
反而是此刻 此刻 此刻
이 하루 이 지금 우리
这一天 这一刻 我们
눈부셔 아름다워
多耀眼 多美丽
이 불꽃놀이는 끝나지 않을 거야
这场烟火永远不会结束
Ooh whatever
喔 不管怎样
흐린 날이면
当阴天到来
거짓말처럼 무섭게 깜깜했지
就会如谎言般恐怖地变得漆黑一片
새침데기 태양은 뜨겁기는 커녕 peacoke
斯文的太阳不但不滚烫 反而炫耀起自己
Blue blue blue whatever
忧伤 忧伤 忧伤 不管怎样
매일 매일
每日每夜
제멋대로인 바람결을 땋아서 만든
在编织着任性胡闹的风儿而做成的
이 나침반이 가리킨 그곳에서 발견
这个指南针指向的那个地方发现
Oh that's you you yes you
噢 那就是你 你 是的 你
있지 저런 건
说真的 那种东西
그저 자그만 돌멩이야
不过是小小的石子
빛이 나는 건 여기 있잖아
发光的事物就在这里啊
Life is cool cool cool
人生多么惬意 惬意 惬意
시간은 많아 이대로면 아마
时间还有很多 这样下去
영원히 살 수 있지 않을까
或许会一直活到永远呢
안녕 나의 주인공
你好 我的主人公
그래 너를 만나러 나
是的 为了遇见你 我
짜잔 우아하게 등장
“当当” 优雅地登场
바로 이 하루 이 지금 우리
就在这一天 这一刻 我们
눈부셔 아름다워
多耀眼 多美丽
나는 확실히 알아
我很清楚地知道
오늘의 불꽃놀이는 끝나지 않을 거야
今天的烟火永远不会结束
우우우 우우우
呜呜呜 呜呜呜
우우우 우우우
呜呜呜 呜呜呜
더 놀라운 건 지금부터야
更惊奇的将从现在开始

A. 远征

观察到\(a_i, x\) 的范围比较小,考虑预处理每个值出现次数前缀和,查询时二分搜索下一个位置即可。实现难度为0。

B. 传送

哈哈哈大概就是接近正解了但是没写出来,而且没抢赢时间然后特殊性质都没来得及交吧。

题意是给出无向图\(G\),存在一张图\(G'\) 满足前者是后者的子集,且每条长度为3的链首尾间都有一条边。给出起点和终点,求问两者之间的距离。

首先起点终点相同或没在同一连通块内可以容易地判掉。剩下的情况就需要具体实现了。对图进行分析,当起点和终点拥有一条长度为奇数的路径时答案为1,否则答案为0。

首先树上很容易实现,直接判断两个点距离奇偶性即可。

这里给出普通图的两种做法:
1.对树上的情况进行推广。先建一棵生成树。考虑树外的边如何影响答案。当一条边连接的两个点奇偶性不同则该边不产生任何贡献,因为通过该边改变的奇偶性与通过树边改变的奇偶性相同。当一条边连接的两个点奇偶性相同时,该两点间路径长度既可以是奇数也可以是偶数,改变了树上的奇偶性,所以一旦一张子图拥有这样的边,则该子图内任意两点都存在长为奇数的路径,直接输出1即可。否则说明树上的非树边不能造成任何贡献,则和树上的做法相同。由于距离只与奇偶性有关,所以深度直接对2取模即可。

2.考虑两个点经过一个中转点的路径。由于中转点到两点的路径可能存在重合的部分(没有重合则为0),则该部分的长度和一定为偶数。若中转点到两点的距离奇偶性相同那么偶数减偶数一定是偶数。反之中转点到两点的奇偶性不同,奇数减偶数还是奇数。所以我们可以每个连通块内选取一个点作为中转点,bfs预处理每个点到中转点是否有长为奇/偶数的路径。由于每个点至多入队两次,所以可以保证复杂度正确。询问时查询两点到中转点是否存在奇偶性不同的路径即可。

(正解好像是二分图之类的东西来着。就是如果同一连通块内两点距离不全是1,那么这张子图一定是张二分图)

C. 先辈

哼哼哼啊啊啊啊啊啊啊

赛时\(O(26^3n)\) 狂砍60pts。

正解其实和我赛时做法差不多,只是优化掉了一个26。然后大概就是由于取模的问题死活过不去,优化常数快了很多倍、、、

D. 矩阵

算是一道类数学(?)

题意是给出一个01矩阵的大小\(n\) 和要求的次幂\(k\),求问在该矩阵内至多有多少个1,使得该矩阵求乘方后得到一个全0矩阵。

赛时暴搜砍了60pts。竟然没忘记矩阵即重载运算符的写法。

实际上这个01矩阵可以转化为一张图的邻接矩阵。全0的限制就转化为了图上的链长度小于\(k+1\) 且图中不存在环。考虑将所有的点均分为\(k\) 份(\(k>n\)\(k=n\) 等价)。问题就转为了同一份的点间不连边,不同份的点从前往后连边,不在平均的\(k\) 份的点单独考虑连边即可。代码极短。

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

相关文章:

  • 高级程序语言第一次作业
  • 安装devc++过程的分享以及问题的记录
  • Linux之线程池 - 指南
  • zlog1
  • LlamaIndex检索调优实战:分块、HyDE、压缩等8个提效方法快速改善答案质量
  • 动火作业风险早预警!AI + 热成像技术筑牢防火安全线
  • 解题报告-P5664 [CSP-S2019] Emiya 家今天的饭
  • object类
  • Day 10
  • 2025 年生态格宾网厂家推荐榜:格宾网石笼/格宾网护坡/格宾网挡墙/格宾网网箱厂家推荐,聚焦工程安全与生态保护,助力基建项目高效落地
  • 时序博弈算法荣获时间检验奖
  • 背叛 仇恨 消极 如刀子刺穿了铁心 嘲笑 嗤之以鼻 漠然后只剩下孤寂
  • STM32主控芯片硬件设计总结
  • 亚马逊因暗黑模式订阅设计支付25亿美元和解金
  • P6645 [CCO 2020] Interval Collection
  • 2025年排烟风机厂家推荐榜:混流风机|管道风机|排烟风机|离心风机|轴流风机|轴流风机厂家,专注高效消防与节能,助力多行业绿色升级
  • 【通达信L2黑科技】 用 DLL 把 10 年机构大单净额 1 秒拖进本地,选股、排序、回测快到飞起!
  • 详细介绍:iCloud照片共享:在家庭内外分享iCloud照片
  • 对static新的认识
  • 2025年氧化镁厂家最新推荐排行榜,电工级/高温/低温/中温/防火电缆/矿物绝缘/熔盐加热器/电热管用/单头管用/合成云母用氧化镁公司推荐!
  • 智能体分析
  • 2025 年玄武岩厂家推荐榜:玄武岩/0-3mm/3-5mm/5-10mm/10-15mm/10-20mm/石子厂,聚焦基建升级与高端化需求,山东展飞建筑材料有限公司成优选
  • 2025 佛山铝合金/系统/断桥铝/耐用/推拉/封阳台/别墅/静音门窗厂家品牌实力推荐:聚焦技术与服务的五大优选标杆
  • Ubuntu22.04 server网络配置
  • 完整教程:深度学习优化器全面指南:核心参数选择与实战策略
  • 说说新版畅联云的一些重要约定
  • App.vue(完整可运行示例)
  • Windows MySQL 报错
  • agents.md和codex.md的关系:codex本尊直接答复
  • ARC/CF记录