首页 > 其他分享 >多校A层冲刺NOIP2024模拟赛18

多校A层冲刺NOIP2024模拟赛18

时间:2024-11-06 21:23:04浏览次数:1  
标签:sz frac 18 线段 多校 tot 贡献 times NOIP2024

多校A层冲刺NOIP2024模拟赛18

T1 选彩笔(rgb)

签到题,但是没签上。。。

没想到三维前缀和,直接上了个bitset。

就是直接二分答案,然后枚举这三维每维的区间的起点,前缀和查数量是否 大于等于 $ K $ 即可,也可以把二分答案改为第一维的双指针,少一个 $ log $ 。

T2 兵蚁排序(sort)

比T1还签到,但是没写 freopen 挂 100。

从 $ b $ 数组里挨个去在 $ a $ 数组里匹配,然后 $ O(n) $ 拉过来就行。

T3 人口局 DBA(dba)

数学推式子。

但是有很多部分分的数位DP,骗了 97 分。

简单来说就是解一个方程满足 $ x_1 + x_2 + x_3 + ······ + x_{n-1} + x_{n} = sum , x1 \lt p , \forall \ \ i ∈ [1,n] \ \ 0 \le x_i \lt m $ 的解的个数。

首先不考虑 $ x1 \lt p $ 的限制,然后你就可以容斥,钦定有 $ k $ 个 $ x $ 是 大于 $ m $ 的,把他们斥掉,然后就有一个式子(直接插板):

\[f_{a,s} \sum_{k=0}^{a} (-1)^k \binom{a}{k} \binom{s-km+a-1}{a-1} \]

如果考虑上 $ x1 \lt p $ 的限制,那就可以直接枚举 $ x1 $ ,所以有:

image

那个后面求和式的化简就是因为 组合数的下面那个不变,所以在杨辉三角上就是竖着的一列

如图:

image

T4 银行的源起(banking)

因为讲过了,所以这篇讲的简单点。 算了,还是稍微详细点吧。

首先考虑只有一个银行的时候怎么求,那肯定是所有人都往一个银行跑,所以枚举点然后算贡献?

其实这种题有 $ O (n) $ 做法。

首先以 1 为根,我们直接考虑每条边的贡献,对于一条边,他的权值是 $ w $ ,连接着点 $ j $ 和他的父亲 $ fa_j $ 。

image

对于这条边,要么是 $ j $ 和他的子树里面的点往上走经过这条边,要么是上面的点下来,这时候我们设 $ sz_j $ 是 $ j $ 及其子树里面的点的权值之和, $ tot $ 表示整棵树的权值和,直接取 $ w \times \min( sz_j , tot - sz_j) $ , 作为这条边的贡献即可。

为什么对,来证明一下:

上面的式子只能保证对于一条边来说是最优的,但是不能保证全局都是这样的,但其实全局最优可以被证明只有在每个都最优的时候才成立。

image

证毕。此时我们得到了 $ O(n) $ 解决一个银行的问题的方法。那如果有两个银行呢,这个时候也一定存在一条边没有人走,所以我们枚举一条边并把它断开,然后对于两棵树分别求贡献加和,即可 $ O(n^2) $ 解决。

$ O(n^2) $ 解决不了,那就看看能不能上数据结构优化。

优化肯定要从贡献方面入手,那就再看看那个贡献的式子, $ ans_j = w_j \times \min( sz_j , tot - sz_j ) $ ,这个 min 就很难直接优化,那就分讨, 如果 $ sz_j \le \frac{tot}{2} , ans_j = w_j \times sz_j $ ,否则 $ ans_j = w_j \times (tot - sz_j ) $ ,那么这东西可以上值域线段树,具体来说,对于 $ sz $ 开一颗值域线段树,然后维护好 $ \sum w_j 、 \sum w_j \times sz_j $ 然后就可以做了。

主体思路有了,具体的分析一下:

image

在这个图里面,我们将这棵树分成了两部分,一颗红的,一颗绿的,我们分别求贡献。

对于绿色的部分很好求,就用刚才的至于线段树就行,dfs时线段树合并 $ n( log (n) ) $ ,对于红色的部分稍微麻烦一点。

首先考虑红色的部分相对于原树有哪些变化:

红树的 $ tot = sz_1 - sz_j $

对于绿树中的根 $ j $ ,从他的父亲 $ x $ 到 1 的这条链上面的点 $ i $ , $ sz_i $ 都减少了 $ sz_j $ 。

首先链上的点的贡献肯定得单求,可以维护一颗树状数组,然后每次查询时先链减 ,然后问,但是一个技巧可以不用链减,现在的分讨条件是 $ sz_i - sz_j \le \frac{tot}{2} $ ,那么直接移项,分讨条件变为 $ sz_i \le \frac{tot}{2} + sz_j $ ,同时最后求的答案要用 减去 $ sz_j $ 之后的值。(写出式子来就会了)

接下来就是红树中除了链上的部分了,我们发现这部分很难直接求,线段树也不好维护,但是他就是全局除了链上和绿树上以外的所有点,所以我们求出全局对于 $ \frac{tot}{2} $ 的贡献,这部分可以弄一颗静态的全局线段树,也可以直接离散化后前缀和 ,然后减去 链上以及绿树中对于 $ \frac{tot}{2} $ 的贡献即可,这部分都可以用刚才维护的东西直接求。

那我们就求完了,这道题主要是多注意注意细节就行了。

标签:sz,frac,18,线段,多校,tot,贡献,times,NOIP2024
From: https://www.cnblogs.com/GGrun-sum/p/18531045

相关文章

  • CSP2024 前集训:NOIP2024加赛 2
    前言T2开太晚了,没打完,别的没怎么挂。哦对,T1以为埃筛复杂度是\(nlog^2\),实际上是\(n\ln(\ln(n))\),结果以为复杂度是错的,然后本地不开O2都飞快,我甚至还在惊叹本地竟然能跑\(5e9\)……还有我之前不知道树的直径的中点时唯一的……T1新的阶乘直接埃筛做完了。点击查......
  • NOIP2024 模拟赛 #15 总结
    Larunatrecy:信心赛。赛时T1求中位数,想起前两天做过的[ABC203D]Pond,考虑了二分答案。看出二分答案后不会做了,罚坐\(20\)min。然后发现我傻逼了,选出一个区间翻转,可以通过钦定右端点,找到最优的左端点得到,神仙Heldivis就出过一道这样的题。写完后调了下二分边界过了大样......
  • CSP2024 前集训:多校A层冲刺NOIP2024模拟赛18
    前言不知道咋回事儿?脑子里一直放歌。然后T3空间给了256,开了256.23死了。T1选彩笔显然可以二分答案,所以现在有了\(O(nv^3\logv)\)的做法,去重后可以拿到\(80pts\),发现直接三维前缀和就可以做到\(O(v^3\logv)\)。点击查看代码#include<bits/stdc++.h>#definell......
  • 『模拟赛』NOIP2024加赛2
    Rank一直烂,什么时候触底反弹(A.新的阶乘赛时觉得线筛一遍同时统计每个质数的指数就做完了,然后本机怎么跑不进1s,卡常卡了半个小时,最后没T,但是vector炸了,70pts。可以换思路考虑,赛时一直没转换过来。对于每个质数枚举其倍数统计贡献。复杂度不知道多少,跑得中等速度。点......
  • 「模拟赛」NOIP2024 模拟 2
    Rank14,190pts比赛链接新的阶乘容易发现只需要处理1~n的质因子分解即可,每个数\(i\)本来有\(n-i+1\)个我们在欧拉筛的过程中同时维护每个数的一个质因子\(pri\)每次从\(n\)到1把遇到的非质数\(i\)现有的个数加到他的质因子\(pri_i\)和\(\frac{i}{pri_i......
  • 【考试题解】NOIP2024加赛2
    目录A.新的阶乘(factorial)题目内容部分分?pts正解思路代码B.博弈树(tree)题目内容部分分80pts正解思路代码C.划分(divide)题目内容部分分10pts14pts正解思路代码D.灯笼(lantern)A.新的阶乘(factorial)题目内容定义运算\(f(x)=x^1\times(x-1)^2\times(x-2)^3\dots2^{x-1......
  • P1802 5 倍经验日: 动态规划
    5倍经验日题目背景现在乐斗有活动了!每打一个人可以获得5倍经验!absi2011却无奈的看着那一些比他等级高的好友,想着能否把他们干掉。干掉能拿不少经验的。题目描述现在absi2011拿出了$x$个迷你装药物(嗑药打人可耻…),准备开始与那些人打了。由于迷你装药物每个只能用一次,......
  • 国标GB28181软件LiteGBS国标GB28181视频平台视频监控/视频监控汇聚系统方案
    随着信息技术的快速发展,视频监控系统已成为公共安全、城市管理和企业安防等领域的重要组成部分。然而,不同厂商生产的视频监控设备遵循不同的标准,导致设备之间无法互通,管理上面临困难,这为安防系统的建设带来了显著挑战。为了解决这一问题,公安部提出了GB28181标准,即GB/T28181—2016......
  • NOIP2024加赛2
    NOIP2024加赛2题目来源:2023NOIPA层联测18\(T1\)HZTG5733.新的阶乘\(100pts\)预处理素数后直接对\(1\simn\)进行质因数分解因为有太多冗余枚举导致无法通过。考虑枚举最终形式。具体地,从质因数的角度入手,设当前枚举的质数为\(p\),暴力求出\(ip\)中\(p\)的指......
  • LOJ6118 「2017 山东二轮集训 Day7」鬼牌
    题意有\(n\)个球,\(m\)种颜色,\(i\)种颜色有\(a_i\)个球。每次随机选择两个球\(x\),\(y\)。使两个球的颜色都变为\(y\)的颜色。问最终只有一个颜色的球的期望步数。\(n\le10^9,m\le10^5\)。Sol显然的,考虑先枚举最终颜色,我们只关心当前有多少个最终颜色的球。......