首页 > 其他分享 >【题解】CF1956

【题解】CF1956

时间:2024-11-06 13:08:40浏览次数:3  
标签:le CF1956 Nene 题解 sum times 序列 操作

CF1956A

简要题意

  • 有 \(n\) 个人玩一个游戏,把这 \(n\) 个人分别编号为 \(1\) 到 \(n\)。
  • 每一轮,编号为 \(a_1, a_2, \ldots, a_k\) ( \(a\) 序列递增 ) 的人会被踢出这个游戏,剩下的人会补齐空位并重新从 \(1\) 开始编号。
  • 当某一轮没有人被踢出时,游戏结束,剩下没有被踢出的人成为赢家。
  • 现在请你求出最后会有多少人成为赢家。
    \(q\) 次询问,对 \(q\) 个 \(n\) 分别给出答案。
    \(n,q \leq 100\)

Solution

  • 注意到只要 \(a_1\) 这个位置有人游戏就一定结束不了,所以游戏结束时最多剩下 \(a_1-1\) 个人。
  • 注意到 \(a_1\) 这个位置之前的人永远都不会被踢出去,所以前 \(a_1-1\) 个人永远不会被踢。
  • 显然答案最多为 \(n\),故 \(ans=min(n,a_1-1)\)
  • 单次询问时间复杂度 \(O(1)\)
    总时间复杂度 \(O(q)\)

CF1956B

简要题意

  • 你和 Nene 在玩一个纸牌游戏,这个游戏由 \(2n\) 张牌组成,每张上面都写着一个在 \(1\) 到 \(n\) 之间的数字,每个数字有两张。
  • 游戏开始前,你和 Nene 都会随机获得其中的 \(n\) 张牌。
  • 游戏的玩法如下:
    你和 Nene 轮流出牌(你是先手)直到所有的牌都被打出。
    每一个回合,(假设这个回合出牌的人是你)你需要打出一张牌,并把它放在桌子上(一开始桌子是空的)。如果在你打出这张牌的时候桌子上已经有了一张写着同样数字的牌,那么你得一分(Nene 出牌的回合同理)。
  • Nene 足够聪明,她一定会采取最优策略:使得她自己的得分最高的情况下让你的得分最低。
  • 现在给出你得到的牌 \(a_1, a_2, \ldots, a_n\) 请你求出你最高可以获得多少分。
  • \(t\) 组数据。
    \(1\le \sum n \le 2 \times 10^5\)
    \(1\le a_i \le n\)

Solution

  • 注意到对于每一种牌,我们拿到的情况只有三种:拿到两张,拿到一张,拿到零张
  • 显然双方拿到的“一张牌”个数相等
  • 又因为双方总牌数相等,所以双方拿到的“两张牌”和“零张牌”个数也相等
  • 对于拿到两张的牌:第一次打出一定不会得分,第二次打出一定得分,所以这种牌对结果的贡献是一定的
  • 对于拿到零张的牌:显然这种牌对结果没有任何贡献,所以这种牌对结果的贡献是一定的
  • 对于拿到一张的牌:可以证明:我们在任意时刻打出这张牌,Nene 都可以立即打出一张相同的牌使自己得分,也就是说我们无法使用“一张牌”得到任何一分。
  • 考虑如何使用”一张牌“来得分:在 Nene 打出第一张”一张牌“前,一直只打”两张牌“。然而,前面证明了双方的”两张牌“数量相等,且我方先手,也就是说上述情况不可能发生。
  • 综上所述,\(ans=两张牌的种类数\)
  • 实现非常简单,开桶记录即可
    时间复杂度 \(O(\sum n)\)

CF1956C

简要题意

  • 有一个 \(n\times n\) 的矩阵,初始时所有位置均为 \(0\) ,现在要对其进行若干次操作,操作有两种:
  1. 选择一个正整数 \(i~(1\le i \le n)\) 和一个 \(1\) ~ \(n\) 的排列 \(p_1,p_2,\cdots,p_n\),将每个 \(a_{i,j}~(1\le j \le n)\) 同时赋值为 \(p_j\)。
  2. 选择一个正整数 \(i~(1 \le i \le n)\) 和一个 \(1\) ~ \(n\) 的排列 \(p_1,p_2,\cdots,p_n\),将每个 \(a_{j,i}~(1\le j \le n)\) 同时赋值为 \(p_j\)。
  • 需要进行不多于 \(2\times n\) 次操作,使得数组中元素的和最大。
  • 输出最终数组中元素的和、操作次数和操作方案。
  • 一共 \(t~ (1\le t \le 500)\) 组数据,每组数据中 \(1\le n\le 500\) ,\(1\le \sum n^2 \le 5\times 10^5\)。

Solution

  • 大胆猜想最优情况一定是这样的
1 2 3 4 5 
2 2 3 4 5
3 3 3 4 5
4 4 4 4 5
5 5 5 5 5
  • 注意在这种情况的基础之上无论怎么操作都不能使答案更优,考虑如何构造出这种方案
  • 注意到第一行和第一列是排列,所以我们可以最后安置这两行/列,现在成功缩小问题为构造出右下角 \(4\times 4\) 大小的矩阵
  • 注意到新矩阵的第一行和第一列也可以通过排列构造出来,现在发现这是一个递归子问题,逐层递归即可得解,操作次数正好为 \(2\times n\),当然,最内层的操作可以少一次
  • 实现:从右下角开始,逐层向外扩展即可
  • 当然可以先构造出矩阵,再一个一个累加得到元素和,但这并不优雅,考虑 \(O(1)\) 计算元素和 \(S\)
  • \(S=\sum_{i=1}^{n} {i(2i-1)}=2\sum_{i=1}^{n}i^2-\sum_{i=1}^{n}i\)
  • 瓶颈是求 \(\sum_{i=1}^{n} i^2\)
  • \(i^2=i^2-i+i=i(i-1)+i=C_i^2+C_i^1\)
  • \(\sum_{i=1}^{n} i^2=C_1^1+C_2^1+C_3^1+\cdots+C_n^1\)
  • \(\quad \quad \quad \quad \quad+C_2^2+C_3^2+\cdots+C_n^2\)
  • \(=C_{n+1}^{2}+C_{n+1}^{3}=\frac{n(n+1)(2n+1)}{6}\)
  • 整理得:\(S=n(n+1)*(2n+1)/3-n(1+n)/2\)

CF1956D

简要题意

  • 给定长度为 \(n\) 的序列 \(a_i\)
  • 满足 \(1\leq n\leq 18,0\leq a_i\leq 10^7\)
  • 定义一次操作为将 \([l,r]\) 区间赋值为 \(a_l,\ldots,a_r\) 的 \(\mathrm{mex}\) 值
  • 求在 \(5\times 10^5\) 次操作之内序列和的最大值,并给出操作序列。

Solution

  • 首先需要有极强的注意力:注意到操作等价于:区间赋值,值为区间长度
  • 如果注意到了这点,显然问题转化为将序列划分为若干段,每段的价值为 \(max(\sum_{i=l}^r a_i,(r-l+1)^2)\)
  • 这个东西就很简单了,区间 DP 即可,时间复杂度 \(O(n^2)\)
  • 考虑如何将一个区间的值全都变为区间长度,并保证总的操作次数不大于 \(5\times 10^5\)
  • 首先把区间每个数都弄成 \(0\),这是简单的
  • 设 \(f(x)\) 表示将长度为 \(x\) 的序列从全 \(0\),变为从 \(1\) 到 \(x\) 的递增序列需要多少次操作
  • 显然 \(f(1)=1\)
  • 考虑 \(f(x)\) 的递推式与对应的构造方案
  • 若要构造长度为 \(x\) 的递增序列,则先构造长度为 \(x-1\) 的递增序列,操作次数为 \(f(x-1)\)
  • 此时加上一个 \(0\),再进行一次操作,使所有数都变成 \(x\)
  • 此时只保留最后一个数,前面的数全都弄成 \(0\),再构造一次长度为 \(x-1\) 的递增序列即可,操作次数为 \(f(x-1)\)
  • 综上:\(f(x)=2f(x-1)+1\)
  • 容易得到通项公式:\(f(x)=2^{x+1}-1\),在 \(n\) 取 18 时,操作次数为 \(f(17)+1=131073\)
  • 综上,按上述方法一定可以在操作次数限制内构造出解

CF1956E

在做了

CF1956F

别急

标签:le,CF1956,Nene,题解,sum,times,序列,操作
From: https://www.cnblogs.com/yeyou26/p/18529763

相关文章

  • “SSL 证书验证失败”问题解决方法“urllib.error.URLError: <urlopen error [SSL: CER
    第一部分:问题描述第二部分:解决方法错误的代码:dataset_train=datasets.MNIST('../data/mnist/',train=True,download=True,transform=trans_mnist)dataset_test=datasets.MNIST('../data/mnist/',train=False,download=True,transform=trans......
  • P6667 [清华集训2016] 如何优雅地求和 题解
    一道非常有启发性的题目。思路考虑对于一个给出点值的多项式函数如何处理。我们发现,对于一个\(m\)次多项式\(f(x)\),由于\(\binom{x}{i}\)为\(i\)次多项式,所以说我们必定可以把一个多项式函数写成如下模样:\[F(k)=\sum_{i=0}^m\binom{k}{i}f_i\]可以看出,\(f_i\)实际上......
  • CSP-J2024题解
    T1扑克牌本题要求:在给定的扑克牌的基础上,还需要多少张牌可以让扑克牌凑成一整套,试题中读入的字符串每个都代表一张合法的扑克牌。可以使用C++STL中的set(集合)完成本题。这是因为,set可以自动去重,去除重复的牌(字符串)后,剩下的字符串就是实际拥有的不同的牌。而一副扑克牌有......
  • ABC378 E 题解
    ABC378E题解题意给定序列\(A\),求\(\sum_{1\lel\ler\len}(\sum_{l\lei\ler}A_i\modM)\)计算所有区间和取模之后的结果再求和。注意外层是没有取模的。如果是外层也要取模的情况,那还是十分好办的,直接贡献法计算每个数字被统计了多少次就可以了。问题就在于外层没......
  • 2024强网杯web题解
    PyBlocklyfromflaskimportFlask,request,jsonifyimportreimportunidecodeimportstringimportastimportsysimportosimportsubprocessimportimportlib.utilimportjsonapp=Flask(__name__)app.config['JSON_AS_ASCII']=Falseblacklis......
  • 2024newstarweb题解
    w1headach3会赢吗源码flag碎片X1:ZmxhZ3tXQTB3再次查看源码flag碎片X2:IV95NF9yM2Fs第三个页面也是直接查看源码直接改源码flag碎片X3:MXlfR3I0c1B下一个页面直接禁用jsflag碎片X4:fSkpKcyF9ZmxhZ3tXQTB3IV95NF9yM2FsMXlfR3I0c1BfSkpKcyF9base64解码即......
  • WPF程序弹出页中按钮在触摸屏(电容屏)上点击事件需要点十次才能触发的问题解决方法
    一、事件背景介绍1.功能简述:主页面是一个DataGrid列表,点击DataGrid行,弹出子页面;子页面根据数据加载多个Button按钮,如下图,就是这个页面中的按钮,在触摸屏上触摸点击,需要点击十次才能成功,使用鼠标点击一下就能成功。 主要代码如下://WPF前端<DataGridx:Name="scanDtl......