首页 > 其他分享 >ZR 2024 NOIP 十连 & CSP 七连

ZR 2024 NOIP 十连 & CSP 七连

时间:2024-09-08 16:47:09浏览次数:9  
标签:NOIP ZR 距离 day 2024 七连 CSP pl

NOIP day 1

T1

简单建图跑 bfs,vector 会被卡空间,用前向星才能过。

T2

注意到原串是否确定不重要,因为无非是把每种可能的转移都多做一遍。

把所有可能出现的回文串的一半插进 AC 自动机中,就可以转移了。

CSP day 1

T3

设 \(nxt_i\) 表示下一个与 \(a_i\) 值相同的位置到 \(i\) 的距离,两个串相等当且仅当 \(a_i\) 相等,哈希维护之即可。

T4

NOIP day 2

T1

发现这玩意是一个类似字典序的东西,每次贪心取最靠前的最小值即可。

T2

经典结论:到 \(u\) 最远的点是直径的端点。可以反证,如果不是,存在比直径更长的路径。

于是只要维护直径就可以了。

但是有人看到距离就想到了点分树。跳祖先时,在每个点处维护两个二元组 \((mx, pl)\),表示 \(pl\) 子树内距离 \(u\) 最远的点的距离为 \(mx\),需要保证两个 \(pl\) 不相同。查询时一边跳点分树祖先一边更新答案,存两大值是为了保证查询点和更新点不在当前点的同一棵子树内。

T3

只考虑差分数组,转化题意为:\(n\) 张卡牌,翻转有代价 \(1\),翻最少次使得朝上的面的数字两两不同。

这不就是填数游戏吗 但是你没做过。基环树是容易枚举环方向做的,树的话做一个换根 dp。

但有人没想到啊。左边是卡牌右边是值,设一张牌正面为 \(a_i\) 背面为 \(b_i\),则 \(i \to a_i\) 连容量 \(1\) 费用 \(0\) 的边,\(i \to b_i\) 连容量 \(1\) 费用 \(1\) 的边,这里两边用了 一样的标号,跑一个费用流。卡卡卡是能过的。

T4

分治,求前后缀 \(\min\),枚举产生贡献的点在 \(mid\) 的哪一侧,找两个函数的交点。

标签:NOIP,ZR,距离,day,2024,七连,CSP,pl
From: https://www.cnblogs.com/purplevine/p/18403108

相关文章

  • 【赛后总结】トヨタ自動車プログラミングコンテスト2024#9(待补完)
    AtCoderBeginnerContest370赛后总结成绩速览:展开目录目录AtCoderBeginnerContest370赛后总结ARaiseBothHands-100ptsBBinaryAlchemy-200ptsCWordLadder-300ptsARaiseBothHands-100pts展开翻译高桥君决定制作章鱼烧,并给苏介君吃。他告诉苏介君,如果想......
  • NOIP2024模拟赛5 总结
    NOIP2024模拟赛5总结T1天才俱乐部特判了\(sum-s<0\),但没有考虑\(sum-s=0\)。挂为0pts。T2实战教学由于写的不够优,贪心+二分的思路TLE了。由于不明原因,输出\(\max(a_i+b_i)\)能过。非常神奇。T3穿越银匙之门T4绳网委托一句话总结:挂分挂成sb了。......
  • 一键解锁创意未来:AE 2024最新版安装包下载及安装教程
    一键解锁创意未来:AE 2024最新版安装包下载及安装教程一键解锁创意未来:AE2024最新版安装包下载及安装教程在数字创意领域,AdobeAfterEffects(简称AE)一直是行业标杆,为无数设计师、动画师和视频编辑者提供了强大的工具,帮助他们将创意变为现实。随着技术的不断进步,Adobe公司也在不断......
  • 官方直链,安全高效:After Effects 2024安装包下载与安装教程
    官方直链,安全高效:After Effects 2024安装包下载与安装教程官方直链,安全高效:AfterEffects2024安装包下载与安装教程AdobeAfterEffects2024是一款强大的视频后期制作软件,广泛应用于电影、电视、广告等领域。它提供了丰富的特效和动画工具,帮助用户创建令人惊叹的视觉效果。本......
  • 告别繁琐,AE 2024安装包下载与快速安装全攻略
    告别繁琐,AE 2024安装包下载与快速安装全攻略告别繁琐,AE2024安装包下载与快速安装全攻略AdobeAfterEffects(简称AE)是一款广泛应用于影视后期制作、动态图形设计、视觉效果合成等领域的专业软件。随着技术的不断进步,Adobe公司每年都会推出新版本的AE,以满足用户对更高效率和更强大......
  • 高效创作从安装开始:Adobe AE 2024安装包下载与性能优化
    高效创作从安装开始:Adobe AE 2024安装包下载与性能优化高效创作从安装开始:AdobeAE2024安装包下载与性能优化在数字内容创作领域,AdobeAfterEffects(简称AE)一直是行业标杆。无论是电影特效、动态图形设计还是视频后期制作,AE都提供了强大的工具和功能。随着AdobeAE2024的发布,创......
  • 安装无忧,创作无限:AE 2024安装包下载与安装疑难解答
    安装无忧,创作无限:AE 2024安装包下载与安装疑难解答安装无忧,创作无限:AE2024安装包下载与安装疑难解答AdobeAfterEffects(简称AE)是一款广泛应用于影视后期制作、动态图形设计、视觉效果合成等领域的专业软件。随着技术的不断进步,Adobe公司每年都会推出新版本的AE,以满足用户日益增......
  • AE 2024安装包下载与安装:为专业视频编辑师打造的指南
    AE2024安装包下载与安装:为专业视频编辑师打造的指南AdobeAfterEffects(简称AE)是一款广泛应用于电影、电视、广告和网络视频制作的专业视频合成和特效软件。随着技术的不断进步,Adobe公司定期发布新版本,以满足不断变化的市场需求和用户期望。AE2024作为最新版本,带来了许多令人兴奋......
  • 2024/9/8第六次记录:第六章数组
    第六章数组要存储大量的数据,就必须定义存储空间很大的变量,可以用数组和结构体。这里我们将数组。6.1数组与存储分配6.1.1定义数组数组是用来存放各个数据元素的一组相互间有关联的变量,这一组变量有共同的名称,用名称及在数组内的序号标识各个变量。定义数组的基本格......
  • 20240908
    T1NFLSOJ服装考虑逐次确定每个人。从前往后枚举,维护一个栈表示当前前缀里所有颜色不同的人。加入一个人的时候和栈里的东西并起来查,查出来是栈大小说明这个颜色出现过,在栈里二分找到那个颜色相同的人。否则当前颜色没出现过,将其加入栈。代码#include<iostream>usingnam......