首页 > 其他分享 >CF1834

CF1834

时间:2024-02-05 14:23:49浏览次数:27  
标签:Alice 字符串 端点 CF1834 区间 lcm operatorname

A

给出一个由 \(1,-1\) 组成的序列。一次操作可以让一个数变相反。

要多少次操作,才能让整个序列和非负且积等于 \(1\)。

大 氵题。

B

定义两个数 \(A,B\) 有一个价值:每一位上的数字的差的绝对值相加。(位数不足用前导零补齐)

给出区间 \(l,r\),问在 \([l,r]\) 内选两个数,最大的价值是多少。


找出 \(l,r\) 最大的相等前缀 \(k\)。

\(l,r\) 的最高位、次高位、第三高位、……、第 \(k\) 高位,都相等,而第 \(k+1\) 位不相等。

前 \(k\) 位一定都相等。我们让两数的第 \(k+1\) 位也不变,然后小数之后的位都选 \(9\),大数之后的位都选 \(0\)。

答案是 \(r_{k+1}-l_{k+1}+9\cdot (n-k-1)\)。

C

初始给出两个字符串。

Alice 和 Bob 轮番行动,Alice 先。

Alice 每次必须修改一个字符,Bob 每次必须挑一个字符串翻转。

可能在某次 Alice 或者 Bob 操作后,两个字符串相等了。游戏结束。

Alice 的目标是最小化这个游戏的回合数(Alice 和 Bob 各走一次算两回合)。Bob 的目标相反。

问:回合数最小化是多少?


把翻转过的字符串称作反字符串,没有翻转过/翻转抵消的字符串称作正字符串。

注意到最终匹配只有两种情况:两正字符串匹配,一正一反匹配。

分两种情况讨论即可。

D

每个学生都有一个学习区间 \([l_i,r_i]\)。初始所有手的高度为 \(0\)。

老师每次询问一个问题 \(x\),不限次数。每个问题至多询问一次

如果 \(x\) 在一个学生的学习区间中,则这个学生把手举高 \(1\) 单位;否则降低 \(1\) 单位。(高度可以是负数)

你现在就是老师,可以操控每次的询问。问:所有询问之后,手最高的学生和手最低的学生,高度差最大是多少?


考虑枚举手最高的学生和手最低的学生 \(a=[l_{high},r_{high}],b=[l_{low},r_{low}]\)。

那么最终的答案就是 \(2\times (|a|-|a\cap b|)\)。(所有 \(a\) 会 \(b\) 不会的问题个数,乘 \(2\) 是因为一个上一个下要两倍)

现在考虑对于每个区间 \(a\)(\(a\) 枚举),求出一个区间 \(b\) 使得 \(2\times (|a|-|a\cap b|)\) 最大,其实就是让交最小。

如果 \(b\) 被 \(a\) 包含,此时一定让 \(b\) 的长度最小。

如果 \(b\) 和 \(a\) 交错,且在 \(a\) 的左端点交错,此时一定让 \(b\) 的右端点越小越好。(当然,最好就是小到连 \(a\) 的左端点都够不上,此时交的长度为 \(0\))

如果 \(b\) 和 \(a\) 在 \(a\) 的右端点交错,此时让 \(b\) 的左端点越大越好。

容易发现,无论对于哪一个区间来说,我们都只需要找到 \(n\) 个中长度最小的区间、右端点最小的区间、左端点最大的区间。不可能出现区间 \(a_1\) 认为如果在包含的情况下,\(b\) 是最优的;但是 \(a_2\) 不这么认为。

问题:

如果 \(a_1\) 认为如果在包含的情况下,\(b\) 是最优的;但是 \(a_2\) 并不包含 \(b\)(交错),这个时候用 \(b\) 和 \(a_2\) 求答案,不就出错了吗?

并不会。因为这么做的答案肯定不会比我们另外两个交错情况下求出的区间,再和这个 \(a_2\) 求答案更优。这个题目只要求不漏掉,不要求不重复。

E

求出最小的数,使得它不能表示为给定序列中任何一个连续子串的最小公倍数。


容易发现,在左端点固定的时候,若右端点向右移动,则区间的 \(\operatorname{lcm}\) 值要么不变,要么至少乘 \(2\)。

而对于一个质数,它不可能成为任意两个与它不等的数的 \(\operatorname{lcm}\),而第 \(3\times 10^5+1\) 个是 \(4256233\),所以在所有区间的 \(\operatorname{lcm}\) 中,那些大于 \(4256233\) 的是没有用的。

因此,记 \(V=4256233\),则当左端点固定的时候,不同的有用 \(\operatorname{lcm}\) 只有 \(\log V\) 个。

考虑从右向左移动移动左端点,并且维护以当前点为左端点的不同 \(\operatorname{lcm}\)。

具体地,可以用两个 set \(A,B\) 分别维护当前存在的不同 \(\operatorname{lcm}\) 和所有可能有用的 \(\operatorname{lcm}\),左端点左移到 \(i\) 的时候,需要将 \(a_i\) 放入 \(A\),并遍历 \(A\) 中本来就存在的区间,对 \(a_i\) 取 \(\operatorname{lcm}\) 后重新放入 \(A\)。每次更新完之后,就把当前 \(A\) 中的元素放入 \(B\) 中。最后对 \(B\) 中的元素求 \(\operatorname{mex}\) 即可。

标签:Alice,字符串,端点,CF1834,区间,lcm,operatorname
From: https://www.cnblogs.com/FLY-lai/p/18007875

相关文章

  • cf1834E. MEX of LCM(维护右端点计算区间lcm)
    cf1834E首先可以估计一下答案的量级,因为小于答案的质数都要必须要出现,5e6以内的质数大概就是3e5,所以答案不超过5e6。我们维护以i右端点的lcm的值,这些值的数量不会太多,因为每次增长都至少×2,所以是log级别。每次新加的时候记得更新和去重即可。#include<cstdio>#include<algor......
  • CF1834E
    题目链接description给定一个长度为\(n\)的序列\(a\),求一个最小的正整数\(x\),使得它不是这个序列任意区间的最小公倍数。值域\(W=10^9\)solution显然答案最大的数量级为\(O(n\logn)\),记\(m=n\times(\lfloor\log_2n\rfloor+1)\)。考虑枚举区间右端点,维护以\(r\)为......
  • CF1834F
    原题翻译容易发现对于一个排列\(p\),其重置次数为\(\sum_{i=1}^n{[p_i<i]}\),因为如果\(p_i=i\)不用操作,\(p_i>i\)可以直接顺着带过去不用重置原问题就变成了进行左右移动操作和反转操作,和查询\(\sum_{i=1}^n{[p_i<i]}\)不妨定义\(res_i\)表示向右移动\(i\)位的答案,对于每一......
  • CF1834E
    原题翻译首先我们考虑求一下答案的上限,对于序列\(a\)的所有区间\(lcm\),他\(mex\)的上限一定是小于\(n\)个数都是质数的,也就是说答案的上限在第\(n+1\)个素数\(p_{n+1}\),这个值大概是4e6左右的我们固定左端点\(l\),可以发现所有右端点中有用的\(lcm\)显然满足\(<p_{n+1}\),而容易......
  • CF1834 题解
    CF1834题解A考虑答案与元素位置无关,只与\(1\)和\(-1\)的个数有关。要求\(1\)必须多于或等于\(-1\),并且\(-1\)个数为偶数。分讨:序列中\(num(1)\geqnum(-1)\),只需要看\(num(-1)\)正负性,奇数1步,偶数0步序列中\(num(1)<num(-1)\),先通过\(-1\)变\(1\)将数目补到第一种情况,再做......
  • CF1834
    CF1834VirtualContest做了5道题,非常不错。A.UnitArray秒切题,判断个数,然后判断一下奇偶即可。提交:https://codeforces.com/contest/1834/submission/211190220B.MaximumStrength题目描述每一种材料的力量由一个十进制整数表示。对于一个武器,由两种材料构成。假如第......
  • CF1834 Div.2 做题记录
    A题面分类讨论即可点击查看代码#include<bits/stdc++.h>#defineullunsignedlonglong#definelllonglong#definepiipair<int,int>#definepdipair<double,int>#definepbpush_back#defineeps1e-9#definempmake_pairusingnamespacestd;namesp......