首页 > 其他分享 >2024 广东省队集训

2024 广东省队集训

时间:2024-06-11 21:54:42浏览次数:3  
标签:广东省 发现 可以 对于 然后 2024 即可 集训 dp

5.21

试机赛

B. 朴素计数,写个 dp 算贡献系数就好了。

C. 网路流。建边 \((s,i_0,C),(i_1,t,C),(i_0,j_1,dis_{i,j})\),跑最大流即可。

5.22

A. 首先分析一下贡献的形式。因为这玩意是凸的,所以我们可以钦定一个选点顺序,优先让第一个最大,其次让第二个最大,以此类推。

很容易猜测选的点是不是一定位于四个角上,但仔细想想就会发现不对。但进一步观察可以发现,只要钦定了选的最多的点是谁,剩下的一定都会选在角上。这是因为去掉了选的最多的点之后,剩下的矩形一定全部有交,通过调整法即可证明上述结论。

B(寻找特殊值构造). 把 \(q\) 转化成 \(1\) 到 \(n\) 的排列,然后连边 \(i \rightarrow p_i\),不妨猜测一个答案下界,也就是 \(\frac{1}{2}\sum|i-p_i|+C \times num\)。实际上确实不可能更小的,通过打表也能证明这是对的。

然后考虑构造。我们将这玩意刻画在数轴上,不难发现我们只需要每次找到一个这样的操作:交换两个数 \(i,j\),同时使得 \((p_i,p_j)\) 被少覆盖两次。

其实我们相当于在找二元组 \(i,j\),满足 \(j < p_i < p_j < i\),在这种情况下我们一般考虑一些特殊值,比如说最大值。考虑不断从最大值往前跳,直到方向改变为止。不难发现这样我们就找到了一组合法的交换。

C(换角度扫描线). 竖着扫描线,主席树维护之即可。

5.23

A(类欧几里得思想). 先搞点分类讨论,

B. 直接 bitset 优化即可。

C(图论建模). 对于每个大小为 \(2\) 的栈连边 \(s_1 \rightarrow s_2\),这样图会分为若干环或者链。给每个元素设个状态,\(1\) 所在栈大小为 \(1\),\(2\) 表示在上面,\(3\) 表示在下面。那么每个值的状态就是个二元组。

这样我们首先肯定优先解决 \((1,1),(1,2)\),然后对于剩余的链需要一个空栈来解决,对于环则需要两个空栈。当然值得注意的是,对于二元环和顺环其实只需要一个空栈,特判一下就好了。

5.24

5.25

A. 观察到把 \(p\) 映射为 \(1\) 到 \(n\) 的排列后,答案就相当于逆序对个数。然后直接 dp 就行了。预处理子树间的逆序对数可以树上启发式合并。

B. dp of dp 题。先考虑怎么检验一个固定的串。发现只需要扫一遍,分别记录若以 \(A\) 为结尾或以 \(B\) 为结尾最短的串是什么即可。

然后建个 SAM 跑就行了。不难分析出状态其实是 \(O(len)\) 的。

C. 不会

5.26

A. 经典 trick。考虑算出每种颜色到所有点的最短路,对于 \(x,y\),最短路就是直接走到的答案和跳 \(dis_{C,x}+dis{C,y}+1\) 的最小值的较小值。

容易发现后者不超过 \(2C\),所以对于小于 \(2C\) 的我们可以暴力算。

对于剩余的,其实我们只需要枚举一个定点 \(x\),再枚举一个颜色 \(C\),不难发现对于所有 \(col_y=C\),经过同一种颜色的答案最大和最小最多差 \(1\)。那么直接预处理一个高为前缀和就好了。

这样直接做是 \(nC+2^CC\) 的。

注意到随机数据下本质不同的元素数量不多,对两两状态间求答案即可。

B.

5.28

A. 随机撒点树分块(子树大小满 \(B\) 就分裂)或者点分治到 \(O(\sqrt n)\) 停止即可。

B. 首先虚树大小可以用经典 trick 算,然后就是经典的按 lca 深度贪心了。

C. 对正方形考虑刻画对角线。发现左一是确定的,那么我们只要锁定左二就能确定上边界。

然后发现从高到低,从左到右贪心就对了。线段树维护一下就好了。

5.29

A. 抽象平衡树题。大力维护即可。

B. 很有 AGC 风格啊。对于固定的方案,首先刻画出 DFA,然后发现相当于要求所有环权值和都为 \(0\)。其实判这个东西只需要对每条边建反向边(权值也取反),看看是否有负环就好了。

然后考虑怎么枚举 lcp 并 check。这样我们发现问题等同于每条边权值固定,或为 \([-1,0]\) 或 \([0,1]\),查询是否存在一种定权方式没有负环。

这个看起来很难。但我们其实可以把固定方案的问题直接转化为差分约束的形式,然后取并,稍微刻画一下就能做了。

C. 观察到对于 \(1,2,3\) 一定选最前面的 \(1\) 和最后面的 \(3\),\(3,2,1\) 则与之相反。

于是确定两者个数 \(A,B\) 后方案也是确定的,就是点匹配区间的形式。容易贪心解决。

但其实直接用 Hall 把条件写出来就能解出 \(A,B,A+B\) 的范围,于是就做完了。

注意:范围还和三种数的个数相关。

5.31

A. 如果不限制 \(w\),最短路的形式显然走环。考虑限制 \(w\) 怎么做。

首先判掉 \(w=0,1,n-1,n\) 之类的边界情况。

考虑调整。发现相当于一个有缺口的环,每个点可以放在上面也可以放在下面。显然如果不想付出额外代价,位于缺口处就随便放,否则就只能放在一边。

注意到有缺口的一边可以卡到下界,也就是 \(2\),但上界不行。

再进一步观察可以发现,我们总是可以花费将一条边代价乘 \(3\) 的方式使上界加一。

维护优先队列即可。

B. 对于每个咒语,将不知情的两个贤者建边,发现就是最小点覆盖问题。但因为 \(k\) 很小可以每次删最大点去搜。记得特判最大点度数不超过 \(2\)。

C(定根). 注意到对于固定的区间,一个点会贡献当且仅当子树内有区间内的点,且不包含所有点。容斥掉后者,相当于减掉 \(lca\) 深度,前者可以启发式合并出合法矩形然后去算。

写个历史和就好了。得拆一下矩阵。

6.2

A. 状态间建边。注意到 \(s\) 和 \(t\) 可达当且仅当能到达的最小状态相同(其实也就是位于同一连通块)。

然后问题就是怎么求最小状态。仔细分析一下我们有一种简单的策略可以做到最优(建出克鲁斯卡尔重构树,能证明下面边权比上面小,每次跳下面的)。Xor Hash 一下就好了。

B. 归纳构造。每次取出最小的丢上去就行了,鸽巢原理。

C. 没写完。总之就是二分图最大匹配转最大独立集,然后大力维护。

6.3

6.4

A. 发现其实只有三种方向能走,于是横竖分别扫描线算一下就好了。

标签:广东省,发现,可以,对于,然后,2024,即可,集训,dp
From: https://www.cnblogs.com/Hypercube07/p/18242827

相关文章

  • [20240607]PL/SQL中sql语句的注解.txt
    [20240607]PL/SQL中sql语句的注解.txt--//别人测试遇到的问题,重复测试说明问题.1.环境:SCOTT@test01p>@verBANNER                                                                           ......
  • [20240529]简单探究FREE LISTS列表.txt
    [20240529]简单探究FREELISTS列表.txt--//简单探究shraedpool的FREELISTS列表.1.环境:SYS@test>@ver1PORT_STRING         VERSION   BANNER                                                       ......
  • [20240601]简单探究free list chunk size的分布.txt
    [20240601]简单探究freelistchunksize的分布.txt--//前几天探究探究freelist,无意中发现12c版本freelistchunksize的发生了变化.单独另外写一篇blog.--//我开始分析以为脚本执行有问题,仔细查看12c版本freelistchunksize分布发生了变化.--//我找了以前的11g下的转储,发......
  • [20240604]简单探究RESERVED FREE LISTS chunk size的分布.txt
    [20240604]简单探究RESERVEDFREELISTSchunksize的分布.txt--//前几天探究探究freelist,无意中发现12c版本freelistchunksize的发生了变化.单独另外写一篇blog.--//我开始分析以为脚本执行有问题,仔细查看12c版本freelistchunksize分布发生了变化.--//我找了以前的11g下......
  • 软著申请之-2024.6.11下证-铺就职称路,软著是基石
    软件著作权(软著)在职称评审过程中扮演着举足轻重的角色,它不仅是科研能力和创新意识的直接体现,也是评价个人专业技术水平和工作业绩的重要依据。首先,软著作为官方认可的知识产权成果,能够有力证明申报人在相关技术领域的研究深度和创新贡献,是评价科研能力和学术水平不可或缺的凭证......
  • 2024年高考作文考人工智能,人工智能写作文能否得高分
    前言众所周知,今年全国一卷考的是人工智能,那么,我们来测试一下,国内几家厉害的人工智能他们的作答情况,以及能取得多少高分呢。由于篇幅有限,我这里只测试一个高考真题,我们这里用百度的文心一言和科大讯飞的讯飞大模型,本测试结果仅供参考,无评价好坏之分。2024高考作文1.1全国甲......
  • 985 计算机硕士,2024 暑期实习 0 offer 的教训反思!
    原文地址mp.weixin.qq.com牛客上看到一位师兄分享自己暑期0offer的教训,我觉得分析的挺好的,也是我们在准备面试的过程中容易出现的问题,应该尽量去避免。我身边看到有的研二师兄,据说之前和导师有矛盾,刚换新导师,现在还在学Java基础,略微有点晚,大多数都是跳过实习,直接......
  • 2024年6月11日Arxiv大语言模型相关论文
    cs.CL:在Token经济中的推理:大语言模型推理策略的预算感知评估原标题:ReasoninginTokenEconomies:Budget-AwareEvaluationofLLMReasoningStrategies作者:JunlinWang,SiddharthaJain,DejiaoZhang,BaishakhiRay,VarunKumar,BenAthiwaratkun摘要:......
  • 整理好了!2024年最常见 20 道分布式、微服务面试题(十)
    上一篇地址:整理好了!2024年最常见20道分布式、微服务面试题(九)-CSDN博客十九、如何设计一个高可用的分布式系统?设计一个高可用的分布式系统是一个复杂的过程,需要考虑多个方面以确保系统的鲁棒性、可扩展性和容错性。以下是一些关键的设计原则和实践:1. 冗余设计:数据冗余:通......
  • 整理好了!2024年最常见 20 道分布式、微服务面试题(九)
    上一篇地址:整理好了!2024年最常见20道分布式、微服务面试题(八)-CSDN博客十七、什么是断路器模式,它如何解决服务依赖问题?断路器模式(CircuitBreakerPattern)是一种软件设计模式,用于处理分布式系统中的服务依赖问题。当一个服务由于某些原因变得不稳定或不可用时,断路器模式可以......