首页 > 其他分享 >2023牛客周赛 Round 6

2023牛客周赛 Round 6

时间:2023-08-11 13:23:05浏览次数:46  
标签:周赛 需要 整数 牛客 取整 数组 集合 思路 Round

https://ac.nowcoder.com/acm/contest/62622/C

c题

从x!作为切入点,阶乘增长的非常快,我们可以枚举x,从而达到固定x,只剩y一个变量,问题转变为一次函数绝对值求最小值的数学问题,显然可以o(1)。

\[13!=6227020800 =6.2270208 × 10^9 \]

\[12!=479001600=4.790016 × 10^8 \]

对于13的阶乘不超过int 整数范围需要作为常识熟知

  • 对于一次函数绝对值求最小值且自变量又被限制在整数,所以我们只需要考虑距离零点最近的左右两个整数点。
  • 这两个整数点的数学表达则是零点表达式的下取整函数和上取整函数
  • 对于出现上取整函数要注意对于0.x的小数判断,不能直接舍弃,因为上取整可能取成1变为可行解

D题

https://ac.nowcoder.com/acm/contest/62622/D

开始思路错误导致初始化清空clear的范围和后期正确思路不用,但思路正确后忘改了导致debug很久,得到教训:思路一旦错误,最好全部删掉重来,不然一个不小心就会有哪遗漏。

思路错误的原因时是,读题读的不够仔细,k——数组的要求是

思路分析:

  • 从微观来看k-数组的要求需要满足a[i]=a[i+k],但如果只停留于此,会在最后计算最大值的时候无法求解或者还得重新思考这里面更深层次的规律,因为需要任意连续k长度的数组sum都相等。
    a[i]=a[i+k]其实展现了,对于任意i,j,a[i%k]=a[j%k]的性质。

  • 从宏观视角来看是要求下标i(modk)的剩余系组成k个集合,这些集合里的数需要一样并且是和每个集合里的最大数一样。再回头想这样做的合理性,k-数组的定义其实就是要所有modk的剩余系的总和一样。
    代码实现过程需要注意:

  • 1.学习了使用max_element函数,后续另写文章介绍。

  • 2.首先操作次数需要满足能让每个剩余系的数都加到这个系得最大值,如果操作次数还有剩余,则选择加到集合元素个数最小得集合中,因为加需要全部加,不然就不能加,一个集合里的所有数需要保持同样大小

标签:周赛,需要,整数,牛客,取整,数组,集合,思路,Round
From: https://www.cnblogs.com/mathiter/p/17622692.html

相关文章

  • HDU 多校 Round #6 题解
    HDU多校Round#6题解\(\text{ByDaiRuiChen007}\)A.CountProblemLink题目大意求有多少个长度为\(n\),字符集大小为\(m\)的字符串有长度为\(n-k\)的周期。数据范围:\(n,m,k\le10^{18}\)。思路分析\(k=n\)时答案为\(m^n\),否则转为有长度为\(k\)的Border,答案......
  • 【题解】Educational Codeforces Round 148(CF1832)
    A.NewPalindrome题目描述:给你一个由小写字母组成的回文字符串,问你是否能在重排其之后构造出另一个与原串不同的回文字符串。多测,\(t\le1000,2\le|s|\le50\)题目分析:考虑其实就是前\(\lfloor\frac{n}{2}\rfloor\)个位置存在两种或以上的不同字符,因为这样直接交换对......
  • 2023牛客暑期多校训练营6 ABCEG
    比赛链接A题解方法一知识点:并查集,树形dp,背包dp。因为需要路径中的最大值,因此考虑按边权从小到大加入图中,保证通过这条边产生贡献的点对已经全部出现。在加边的同时进行树上背包,答案存在集合根节点里即可。树上背包需要用到上下界限制的转移优化,能将复杂度从\(O(n^3)\)降......
  • 『STAOI』G - Round 3
    『STAOI』G-Round3因为在\(STAOI\)团里,所以赛时没打。\(T1\)luoguP9508『STA-R3』存在观察题意,手搓几组样例,易知符合题意的一组解形如\(a,b,b,c,b,b,……,z,(b),(b)\)。不会证明,可以参考下隔壁jijidawang的。时间复杂度\(O(n)\),可以通过本题。#include<bi......
  • Codeforces Round 881 (Div. 3)
    A.SashaandArrayColoring为了让贡献最大,每种颜色只能染两个数显然这两个数为最大值与最小值、次大值与次小值、第三大值与第三小值……以此类推即可B.LongLong为了让和最大,我们需要的就是把所有负数变成正数那么第一问的答案就是\(\sum_{i=1}^n|a_i|\)此外,因为每次变......
  • 2018牛客多校第五场 F take[树状数组]
    理解题目画了一个二叉树,然后思维定势让我想构建一个有n层的二叉树,然后统计叶子节点。。有点恐怖。但是正解是考虑每一个箱子对答案的贡献。图片来自take_baymax520的博客对于每个箱子,它要发生交换也就是为答案贡献的条件是它当前宝石大小小于它的大小。对于比它小的宝石之前取......
  • fastapi后台任务模块<BackgroundTasks>源码理解
      该文档主要对fastapi的后台模块《BackgroundTasks》一些源码的理解,这样也可以加深理解异步及后台任务处理的理解。 使用导入例子: fromfastapiimport BackgroundTasks  fromfastapiimportBackgroundTasks,FastAPIapp=FastAPI()defwrite_file(data:st......
  • Codeforces Round 891 (Div. 3) A-G
    偷偷摆烂导致小号掉了16分,但是队友涨了16分,一定是米哈游的问题!A.ArrayColoring题意:给出一个长为\(n\)的数组,问能否把所有元素分别染成两种颜色中的一种,并且使得同种颜色的元素和它们最后的奇偶性相同。Solution算出奇数个数看是不是奇数个即可voidsolve(){ intn;cin>>n......
  • CF1857B Maximum Rounding 题解
    题面题目大意给定\(T\)组数据,每组数据一个自然数\(n\),可以多次选择第\(k\)位数进行四舍五入,求出四舍五入后该数的最大值。分析思路思想:贪心。这里给定了两种操作。四舍和五入。显然我们想要让最终的结果最大,我们的操作只能进行五入而不可以进行四舍。因为如果我们进行了......
  • 根号分治-2023牛客7 E-Star Wars
      也就是说对于大点和小点我们采用不同的方式维护对于大点来说我们只需要记录它的周围点的总和不需要知道具体的谁链接了它 对于小点我们需要维护它的所有信息他自己链接了哪些点 需要再开一个vector表示自己链接的大点这样大对大或者小对大的时候维护的信息也......