首页 > 其他分享 >P7514 [省选联考 2021 A/B 卷] 卡牌游戏

P7514 [省选联考 2021 A/B 卷] 卡牌游戏

时间:2023-11-09 22:11:06浏览次数:34  
标签:10 P7514 le 省选 卡牌 Alice 联考 朝上

[省选联考 2021 A/B 卷] 卡牌游戏

题目描述

Alice 有 \(n\) 张卡牌,第 \(i\)(\(1 \le i \le n\))张卡牌的正面有数字 \(a_i\),背面有数字 \(b_i\),初始时所有卡牌正面朝上。

现在 Alice 可以将不超过 \(m\) 张卡牌翻面,即由正面朝上改为背面朝上。Alice 的目标是让最终朝上的 \(n\) 个数字的极差(最大值与最小值的差)尽量小。请你帮 Alice 算一算极差的最小值是多少。

【数据范围】

对于所有测试数据:\(3 \le n \le {10}^6\),\(1 \le m < n\),\(1 \le a_i, b_i \le {10}^9\)。

每个测试点的具体限制见下表:

测试点编号 \(n \le\) 特殊限制
\(1 \sim 2\) \(10\)
\(3 \sim 4\) \(500\)
\(5 \sim 6\) \(5 \times {10}^5\) \(m \le 1000\)
\(7\) \({10}^5\)
\(8\) \(4 \times {10}^5\)
\(9\) \(7 \times {10}^5\)
\(10\) \({10}^6\)

思路:

首先观察一下题目,我们很容易就会发现这个答案是具有单调性的,也就是对于 \(\forall x,x\in \mathbb{R}\)

标签:10,P7514,le,省选,卡牌,Alice,联考,朝上
From: https://www.cnblogs.com/Candycar/p/17823012.html

相关文章

  • 【多校联考NOIP#12】比赛复盘
    A.星穹铁道读完题面就想到了\(O(n^2)\)的暴力。很好想,但是只有40分。观察到\(z_i=\pm1\),然而即便如此,我也没有得到有用的性质。(正解是用到这个性质的)然后我就暴力写了。正解的性质“最终在一个区间L,R内,初始也一定在一个连续段内”赛事没有想到。同时题解用了逆向思维,对......
  • 2023联合省选 题解
    目录D1T1P9166[省选联考2023]火车站D1T2P9167[省选联考2023]城市建造D1T3P9168[省选联考2023]人员调度D2T1P9169[省选联考2023]过河卒D2T2P9170[省选联考2023]填数游戏D2T3P9171[省选联考2023]染色数组D1T1P9166[省选联考2023]火车站性质很好找。关......
  • 一则求总贡献的例题——联考题引发的思考
    对于一些求总贡献的题,与许多人的常识相反,直接求期望往往比求总和更容易.以今天联考T1的一个环节为例.【例】对排列\(P_n\),定义\(C(P_n):=\left|\{i:P_j>P_i,\\forallj<i\}\right|\),即其前缀最小值序列的不同数个数.给定\(n\),求全部\(n!\)个排列\(P_n\)的\((-1)^{C(......
  • [十二省联考 2019] 春节十二响
    [十二省联考2019]春节十二响感觉作为例题还是挺不错的。感官上直接分析比较困难。不妨先考虑怎样的段长集合是合法的。注意到合法等价于对每一条从根到叶子的链都合法,考虑在链上贪心,尝试将每个和比他大的最小的点做匹配,如果能匹配上就是合法。很显然,如果仅考虑一条链,那么极小......
  • P3746 [六省联考 2017] 组合数问题
    看了题解才悟了,我还是太菜了。solution要求\[\left(\sum_{i=0}^\inftyC_{nk}^{ik+r}\right)\bmodp\]这个形式很像生成函数吧。我们套用生成函数:\[G(x)=\sum_{i=0}^{\infty}\begin{pmatrix}nk\\i\end{pmatrix}x^i\]所求即为\[\sum_{i\bmodk=r}[x^i](1+x)......
  • 「联合省选 2020 A」组合数问题 题解
    非常显然的,我们展开\(f(k)\),于是有:\[\begin{align}&\sum\limits_{k=0}^{n}\sum\limits_{i=0}^{m}a_{i}k^{i}x^{k}\binom{n}{k}\\=&\sum\limits_{k=0}^{n}\sum\limits_{i=0}^{m}a_{i}{\sum\limits_{j=0}^{i}\begin{Bmatrix}i\\j\end{Bmatrix}\binom{......
  • 省选联考 2022 填树
    洛谷传送门LOJ传送门这题做得真艰难。先考虑第一问。一眼看上去并没有什么复杂度脱离值域的办法。考虑枚举一个\(x\)表示最小值,那么点权只能在\([x,x+K]\)中。点权最小值不一定为\(x\),减去点权在\([x+1,x+K]\)中的答案即可,也就是把\(K\)减\(1\)后再算一......
  • P5289 [十二省联考 2019] 皮配
    很容易想到设\(dp_{i,j,k}\)表示考虑前\(i\)个阵营,\(C_0=j\),\(D_0=k\)时的方案数,层内转移时可以用辅助数组对两种阵营决策分别转移,此时时间复杂度为\(O(nM^2)\)。考虑\(k=0\)的情况,如果我们能做这个的话,\(k=30\)其实就是在暗示我们把特殊选手拆出来单独做。而如果所有选......
  • 【多校联考NOIP#3】比赛复盘 && 题解
    A.卡牌这次比赛,一道签到题都没有。本来以为是线段树上二分。就类似于花神的数论题那道,刚开始暴力修改(修改到线段树的每一个叶子节点),然后由于boss的attack在不断增加,到了\(Att_i>=hp_j\)的时候,\(j\)这个牌顶多打一次,如果一个区间的\(max\)都小于boss的攻击力了,那么就不......
  • 八点五省联考 2018
    一双木棋状态数不多,直接爆搜https://loj.ac/s/1676274IIIDX考虑依次给\(i=1,2,\cdots,n\)填上数,每次尽量填最大的。考虑什么时候\(i\)填上\(x\)是合法的。考虑Hall定理,发现左部点约束最严的时候肯定是找一个已经填过的点\(u\),然后对所有\(d_v\ged_u\)的\(v\),选出......