首页 > 其他分享 >比赛记录(51~60)

比赛记录(51~60)

时间:2024-10-04 21:33:06浏览次数:11  
标签:比赛 T2 T4 51 T3 T1 60 dp Mod

51 CSP-S 模拟赛32

1 得分

题目 T1 T2 T3 T4 总分
得分 \(4\) \(20\) \(11\) \(27\) \(62\)

排名:rank \(9\)。

真正炸裂的一集。

2 题解

T1

考虑到边数较少,于是考虑能不能枚举边相关信息。通过部分分可以有如下讨论:

  • \(c_u\ne c_v\) 时,意味着原先两点间有的边没了,那么两端的两个点只能选其一。
  • \(c_u=c_v\) 时,意味着原先两点间没有边有了,那么这一条边可选可不选。

于是发现每一条边的决策只有两种,而边数 \(K\) 只有 \(20\),所以可以 \(O(2^K)\) 枚举边的状态。

接下来判断选择的边是否有冲突,以及每一个岛屿上选的边能不能构成完全图即可。

T2

首先考虑没有吃糖果变胖的机制,我们怎么走可以使初始体重最大。这就是经典问题 [货车运输],显然走的路径一定是最大生成树上的路径。

那么有了这个机制这个性质也不会变,所以考虑在最大生成树基础上求解。又由于这是边权问题,考虑 Kruskal 重构树来解决。对于单次合并的两个子树 \(u,v\),设其子树权值和为 \(s_u,s_v\),子树本身最大答案为 \(a_u,a_v\),连接两子树边权为 \(w\)。

那么此时一定是先吃其中一颗子树,再吃另外一颗最优。假设先吃 \(u\),那么此时答案会变为 \(\min\{w-s_u,a_v-s_u\}\)。先吃 \(v\) 同理。

最后根节点的 \(a\) 即是答案。

T3

容易发现,整个给钱的过程就是将儿子从小到大填满,然后再一点点往父亲给。所以如果一个节点需要 \(k\) 的钱来填它的子树,那么子树权值和比 \(k\) 小的兄弟应该都被填满,其他的兄弟都应该填上 \(k\)。那么我们就可以知道它的父亲需要的钱是 \(\sum\min\{sum_x,k\}\)。

暴力跳的复杂度是 \(O(n^2)\),考虑优化。不难发现的是,如果在某一次跳的时候出现了 \(sum_x>k\) 的情况,那么 \(k\) 就会至少翻一倍。而 \(k\) 最多就是 \(V=\sum v_i\),所以出现上述情况的次数不超过 \(\log V\)。

考虑从这里入手,我们把这样的节点称为关键点,然后利用倍增求出每一个点跳到下一个关键点的价值和以及需要多少钱才能跳到该关键点。这样复杂度就是 \(O(n\log V)\)​ 的了。

T4

讲得比我清楚

52 CSP-S 模拟赛33

1 得分

题目 T1 T2 T3 T4 总分
得分 \(100\) \(100\) \(50\) \(25\) \(275\)

排名:rank \(3\)。

2 题解

T1

直接上并查集。对于一组 \((x,y,z)\),我们将 \(x+i\) 与 \(y+i\) 连边,同时标记 \(x+z\) 与 \(y+z\) 要不同。求答案的时候从头开始贪心,求出冲突的集合中已经确定了的值,求出这些值的 \(\text{mex}\) 就是当前答案。

T2

超级大水题,先 BFS 算出每个点与传送门的连通性,然后传递闭包算传送门之间连通性,最后查答案的时候枚举一下即可。上述过程全部可以 bitset 优化,复杂度 \(O(knm+\dfrac{k^3}{w}+\dfrac{qk^2}{w})\)。

T3

首先发现 \(p\) 两边的 \(l,r\) 互不影响,因此先求出前缀和,则只需要让 \(sa_r-ksb_r\) 与 \(-sa_l+ksb_l\) 分别最大即可。

发现上面两个式子都是 \(y=kx+b\) 的一次函数的形式,也就是说每一个位置都对应一条直线。而我们要求的就是再 \(x=k\) 处与所有直线交点的最大值。这个就是李超线段树的经典问题了。

当然我们需要先离线,然后边插入边查询即可。

T4

讲得很好

53 CSP-S 模拟赛34

1 得分

题目 T1 T2 T3 T4 总分
得分 \(9\) \(50\) \(20\) \(0\) \(79\)

排名:rank \(15\)。

依然炸裂的一集。

2 题解

T1

考虑从 \(k\) 处掰开序列,然后分别求前缀和。问题就转化为移动 \(l=r=1\) 两个指针,使得每一次的 \(s_l+s_r\) 都不大于 \(0\)。

考虑贪心。我们显然是每一次只将 \(l,r\) 中一个移到值更小的位置。但是这样只能将 \(l,r\) 分别移到最小值处。不过发现后面的移动倒过来和前面是一样的,所以倒过来再跑一边即可。

T2

首先要观察到每一次会至少删一半的数,所以有效的 \(k\) 只有 \(\log n\) 个。

发现去掉序列最大值后两边可以分开求解。设 \(dp(i,j,0/1,0/1)\) 表示序列长度为 \(i\),不超过 \(j\) 次操作就删到不能再删的序列方案数。后面的 \(0/1\)​ 表示左 / 右是有一个比该序列所有数都大的数还是没有。接下来我们只需要枚举最大值位置、两个子区间的状态即可,复杂度 \(O(n^2\log n)\)。

转移方程大致如下:

(dp[i][j][0][0] += dp[k - 1][j][0][1] * dp[i - k][j][1][0] % Mod * C[i - 1][k - 1] % Mod) %= Mod;
(dp[i][j][0][1] += dp[k - 1][j][0][1] * dp[i - k][j - 1][1][1] % Mod * C[i - 1][k - 1] % Mod) %= Mod;
(dp[i][j][1][0] += dp[k - 1][j - 1][1][1] * dp[i - k][j][1][0] % Mod * C[i - 1][k - 1] % Mod) %= Mod;
int x = (dp[k - 1][j][1][1] - dp[k - 1][j - 1][1][1] + Mod) % Mod;
int y = (dp[i - k][j][1][1] - dp[i - k][j - 1][1][1] + Mod) % Mod;
(dp[i][j][1][1] += (dp[k - 1][j][1][1] * dp[i - k][j][1][1] % Mod - x * y % Mod + Mod) % Mod * C[i - 1][k - 1] % Mod) %= Mod;

T3

我们建立两张图,一张是原图,另一张是反图。于是原问题就相当于从两张图的原点走到终点的费用和。

考虑二维 Dijkstra,设 \(dis(x,y)\) 表示第一张图走到 \(x\),第二张图走到 \(y\) 所用费用最小值,使用与 Dij 相同的转移方式即可。为了维护已走过的车站,再开一个 bitset \(sta(x,y)\) 存此时走过的站点。转移时根据这个加上对应权值即可。

T4

显然使用扫描线,对于每一个区间维护当前覆盖该区间且删除时间最晚的矩阵,利用并查集更新即可。

具体还是看这里

标签:比赛,T2,T4,51,T3,T1,60,dp,Mod
From: https://www.cnblogs.com/dzbblog/p/18447330

相关文章

  • FINANCE 251: Financial Management
    FINANCE 251: Financial Management2024 Semester 2 (1245)Assignment PART 1Instructions:This isaGroupassignment(Part 1) which also includes an Individual component (Part 2). You mustform.yourowngroups (min 2, max5 people per......
  • 代码随想录算法训练营 | 134. 加油站,135. 分发糖果,860.柠檬水找零,406.根据身高重建队
    134.加油站题目链接:134.加油站文档讲解︰代码随想录(programmercarl.com)视频讲解︰加油站日期:2024-10-04想法:1.总汽油大于等于消耗一定能跑完,2.当前剩余汽油小于0了,只能从下一站开始重新计算Java代码如下:classSolution{publicintcanCompleteCircuit(int[]gas,int......
  • cnblogs内容同步到51cto上的说明(声明)
    51CTO网站上的blog地址为:https://blog.51cto.com/u_15642578该地址是个人在博客园cnblogs上的同步账号(https://cnblogs.com/xyz),在cnblogs上发表的内容会不定期的在经过51CTO审核通过后同步到该51CTO地址下。之所以将cnblogs上的文章同步到51CTO网站上,其原因有两个:希望自己的......
  • 文心一言 VS 讯飞星火 VS chatgpt (360)-- 算法导论24.3 2题
    二、请举出一个包含负权重的有向图,使得Dijkstra算法在其上运行时将产生不正确的结果。为什么在有负权重的情况下,定理24.6的证明不能成立呢?定理24.6的内容是:Dijkstra算法运行在带权重的有向图时,果所有权重为非负值,则在算法终止时,对于所有结点,我们有。如果要写代码,请用go......
  • 数据表或视图不存在 [错误代码]SQLSTATE[42S02]: Base table or view not found: 1146
    这个错误表明在执行SQL查询时,尝试访问的数据表或视图 ey_product_content 在数据库 bb9e8d602 中不存在。这可能是由于以下几个原因导致的:表名拼写错误:检查表名是否正确无误。数据库选择错误:确认当前使用的数据库是否正确,确保没有混淆数据库名称。表被删除:可能该表已经......
  • CF1051F题解
    传送门:https://codeforces.com/problemset/problem/1051/F注意到\(m-n\le20\),求一个连通图中任意两点间最短路,我们不难想到将问题转换到树上。先求出树的任意一颗生成树,此时倍增或者树刨能轻松算出仅含树边的最小路径。而对于非树边,从边的角度显然很难做到,我们不妨从点的角度思......
  • 51c嵌入式~电路~合集7
    一、借助示波器看以太网传输机制本文以双绞线以太网为分析对象,以混合信号示波器为分析工具,深入探秘了两类常见的双绞线以太网的编码,且实地查看并验证了以太网在物理层的信号传输情况。最后,通过一个实战例子对比了实际网络中软件接收的数据和示波器捕获信号之间的一致性。本文打通软......
  • 60_初识搜索引擎_上机动手实战基于scoll技术滚动搜索大量数据
    如果一次性要查出来比如10万条数据,那么性能会很差,此时一般会采取用scoll滚动查询,一批一批的查,直到所有数据都查询完处理完使用scoll滚动搜索,可以先搜索一批数据,然后下次再搜索一批数据,以此类推,直到搜索出全部的数据来scoll搜索会在第一次搜索的时候,保存一个当时的视图快照,之后只......
  • 51单片机实现流水灯
    上代码代码如下:/*如果需要从左往右将第6行,第22行temp改成0x80将第26行<<改成>>*/include<REGX51.H>//引用51库unsignedchartemp=0x01;//定义一个无符号字符变量temp,初始值为0x01(二进制为00000001),用于控制LED的状态。unsignedintc=0,i=0;voiddelay(unsignedint......
  • pbootcms后台出现"登录失败:登录失败次数太多已被锁定,请600s重试!" 情况,怎么办?
    当在PBootCMS后台出现“登录失败:登录失败次数太多已被锁定,请600s重试!”的情况时,这通常是由于多次尝试错误密码导致的账户锁定。解决这个问题的方法如下:解决方法删除 runtime 文件夹:打开你的网站根目录。找到 runtime 文件夹并删除它。通常路径为:/www/wwwroot/you......