首页 > 其他分享 >CF2008场题解

CF2008场题解

时间:2024-09-02 11:04:27浏览次数:13  
标签:题意 题解 算法 偶数 字符串 简述 序列 CF2008

Sakurako's Exam

算法:模拟,分类讨论。

题意简述:给 \(a\) 个数字 \(1\) 和 \(b\) 个数字 \(2\),问能否在每个数字前加上加减号使得原始值为 \(0\)。

考虑 \(1\) 的个数如果是奇数,那么一定不行。否则如果 \(2\) 的个数是偶数,一定可以。当 \(2\) 的个数为奇数且还可能可以时,判断是否存在 \(1\) 能够抵消一个 \(2\) 即可。

Square or Not

算法:模拟。

题意简述:定义美丽的矩阵为:最外层全部为 \(1\),其他全部为 \(0\) 的矩阵。现在问能否把一个字符串 \(s\) 写为美丽的矩阵。

我们设 \(s\) 长度为 \(n\)。显然若 \(n\) 不是平方数,一定不行。否则我们暴力判断即可。

Longest Good Array

算法:模拟,数学。

题意简述:定义好序列为满足 \(a_{i+1}-a_i>a_i-a_{i-1}\) 的序列,问如果一个序列的最小值为 \(l\),最大值为 \(r\),且这个序列为好序列,求其最大长度。

首先若 \(l=r\) 则答案为 \(1\)。否则我们暴力枚举当前差,每次让差加上 \(1\),判断当前项是否超过 \(r\),超过则输出答案,否则继续。

Sakurako's Hobby

算法:搜索,图论。

题意简述:给定一个排列 \(p\),问每个位置通过走边 \(i\rightarrow p_i\) 能到达几个 \(s_i\) 为 \(0\) 的点。

首先图中肯定是一堆环,于是如果发现某个位置没有遍历过,直接暴力走边,同时记录经过的符合要求的点的数量,最后对这个环上的所有点赋值答案。

Alternating String

算法:模拟。

题意简述:定义交替字符串为奇数位置上的字母全部相等,偶数位置上的字母全部相等且字符串长度为偶数的字符串。现在有两种操作,一种是删除一个字母(最多执行 \(1\) 次),另一种是把一个字母替换为另一个字母。现在问把字符串 \(s\) 变为交替字符串的最小操作次数。

考虑如果 \(s\) 长度 \(n\) 为偶数,则判断技术位置和偶数位置上哪个字母更多,变成哪个即可。

如果是奇数,则我们记录一个后缀和为每个字母在奇数/偶数位置上出现的次数。然后扫一遍字符串,扫到的字符串代表删除它,然后分别找出奇数位置和偶数位置上出现最多次数的字母看能否更新答案即可。

Sakurako's Box

算法:数学。

题意简述:给一个序列,求出两两不同位置的数的乘积的期望值。

首先一共有 \(cnt=\dfrac{n\times(n-1)}{2}\) 对数。然后记 \(sum\) 为所有数的和。对于每个位置,先进行 \(sum\leftarrow sum-a_i\),然后 \(res\leftarrow res+sum\times a_i\)。最后答案即为 \(\dfrac{res}{cnt}\),使用乘法逆元计算即可。

Sakurako's Task

算法:数学,二分。

题意简述:定义 \(mex_k\) 为一个序列中第 \(k\) 个未出现的自然数。现在要求最大化 \(a\) 序列的 \(mex_k\),输出 \(mex_k\) 的值。

我们设 \(d\) 为所有 \(a_i\) 的 \(\gcd\),于是有最后 \(a_i\) 为 \((i-1)\times d\)。对答案二分即可。

Sakurako's Test

算法:数学,二分,前缀和。

题意简述:给一个序列 \(a\),现在 \(q\) 次询问进行操作 \(a_i\leftarrow a_i\bmod x\) 后,其第 \(\dfrac{n}{2}+1\) 大的数,询问之间相互独立。

我们开个桶维护每个数出现的次数,然后做一下前缀和。然后对于每个可能的 \(x\),预处理其答案。每次二分中位数 \(mid\),然后前缀和快速找出模 \(x\) 不超过 \(mid\) 的数的个数,每次找数复杂度为 \(O(\log n)\)。这样我们的时间复杂度为 \(O(n\log^2 n+q)\)。

代码

标签:题意,题解,算法,偶数,字符串,简述,序列,CF2008
From: https://www.cnblogs.com/zxh923aoao/p/18392077

相关文章

  • ABC369F F - Gather Coins 题解
    题目链接:https://atcoder.jp/contests/abc369/tasks/abc369_f题目大意:在一个\(H\timesW\)的二维迷宫中有\(N\)枚硬币,其中第\(i\)枚硬币在\((R_i,C_i)\)(本题中,我们用\((r,c)\)表示二维迷宫中从上到下第\(r\)行从左到右第\(c\)列的那个格子)。你一开始在迷宫的左......
  • 如何解决《罗马2全面战争》中的twitchsdk_32_release.dll错误模块跳出问题?实用技巧与
    当您启动《罗马2全面战争》时,可能会遇到与twitchsdk_32_release.dll相关的错误提示,这可能导致游戏无法正常运行。本篇文章将深入探讨这一问题的原因以及提供多种解决方法,帮助您顺利启动游戏。twitchsdk_32_release.dll错误模块跳出的原因twitchsdk_32_release.dll文件出现......
  • 【题解】Solution Set - 「蓝」题板刷
    【题解】SolutionSet-「蓝」题板刷始于:2024/9/1(其实之前大概做了十来道,但是没有记录。估计题会比较多,如果从代码里面过来的话,建议直接Ctrl/⌘+F题目名称。「USACO18JAN」MooTubeG2024/9/1一句话题意:https://www.luogu.com/discuss/125319给定一棵有边权的树,每次询......
  • 题解:AT_abc257_d [ABC257D] Jumping Takahashi 2
    [ABC257D]JumpingTakahashi2博客食用更佳:Myblog。大体思路这题是一道二分题,因为\(S\)越大,就越容易满足题目要求,\(S\)越小,就越难满足题目要求,符合二分的特点。下面先贴上二分代码。LLl=0,r=1e10;while(l<r){intmid=l+r>>1;if(check(mid))......
  • [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two--记忆化题解
    题目复述:链接跳转:[USACO2.4]两只塔姆沃斯牛TheTamworthTwo-洛谷#[USACO2.4]两只塔姆沃斯牛TheTamworthTwo##题目描述两只牛逃跑到了森林里。FarmerJohn开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为(牛和John)。追击在$10\times10$的平面网......
  • [蓝桥杯 2020 省 A1] 超级胶水--题解
    题目再现:链接跳转:[蓝桥杯2020省A1]超级胶水-洛谷#[蓝桥杯2020省A1]超级胶水##题目描述小明有$n$颗石子,按顺序摆成一排,他准备用胶水将这些石子粘在一起。 每颗石子有自己的重量,如果将两颗石子粘在一起,将合并成一颗新的石子,重量是这两颗石子的重量之和。为......
  • [蓝桥杯 2016 省 A] 密码脱落--最长公共子序列题解
    题目复述:题目链接:[蓝桥杯2016省A]密码脱落-洛谷#[蓝桥杯2016省A]密码脱落##题目描述X星球的考古学家发现了一批古代留下来的密码。这些密码是由A、B、C、D四种植物的种子串成的序列。仔细分析发现,这些密码串当初应该是前后对称的(也就是我们说的回文串)。......
  • 「NOI2022 D2T2 冒泡排序」题解
    题意uoj768构造长为\(n\)的序列\(a\),满足\(m\)条限制:\(\min_{j=L_i}^{R_i}\{a_j\}=V_i\),要求逆序对数最少题解21pts暴力先进行一些观察:逆序对只关心相对大小,所以\(\foralla_j\)必然\(\in\{V_i\}\),可以完全离散化经典结论:若\(i<j,a_i>a_j\)且交换后合法,则交换......
  • 【题解】Solution Set - NOIP2024模拟赛4
    【题解】SolutionSet-NOIP2024模拟赛4https://www.becoder.com.cn/contest/5501T2沉默乐团https://www.becoder.com.cn/submission/2593352T3深黯「军团」记录一下考场思路:首先对于长度为\(n\)所有排列,按顺序求出她的逆序对数量。然后找到了规律。后面基于此,写出......
  • abc369 题解
    切了A~F,还挺开心(但是如果上一次把G切了的话,我就上青了QAQ比赛链接:https://atcoder.jp/contests/abc369A-369题意:给定正整数\(a,b\)(\(1\lea,b\le100\)),请问有多少个整数\(x\)满足\(a,b,x\)排序后构成等差数列。思路:观察到\(a,b\)范围很小,直接枚举\(x\)即可。......