给出一个由 \(1,-1\) 组成的序列。一次操作可以让一个数变相反。
要多少次操作,才能让整个序列和非负且积等于 \(1\)。
大 氵题。
定义两个数 \(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)\)。
初始给出两个字符串。
Alice 和 Bob 轮番行动,Alice 先。
Alice 每次必须修改一个字符,Bob 每次必须挑一个字符串翻转。
可能在某次 Alice 或者 Bob 操作后,两个字符串相等了。游戏结束。
Alice 的目标是最小化这个游戏的回合数(Alice 和 Bob 各走一次算两回合)。Bob 的目标相反。
问:回合数最小化是多少?
把翻转过的字符串称作反字符串,没有翻转过/翻转抵消的字符串称作正字符串。
注意到最终匹配只有两种情况:两正字符串匹配,一正一反匹配。
分两种情况讨论即可。
每个学生都有一个学习区间 \([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\) 求答案更优。这个题目只要求不漏掉,不要求不重复。
求出最小的数,使得它不能表示为给定序列中任何一个连续子串的最小公倍数。
容易发现,在左端点固定的时候,若右端点向右移动,则区间的 \(\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}\) 即可。