XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Gomel

Contest Info

date: 2019.03.15 18:39-23:39

practice link

Solutions

A. Aftermath

题目大意:告诉你一个数所有因子的平均值和调和平均值,求这个数。

题解:算一下就会发现,这两个平均值的乘积就是这个数。

B. Believer

题目大意:定义一个数列的价值为每个数出现次数的 bitcount 之和,求和为 \(n\) 的正整数数列的最大价值。

题解:有若干性质:每个数都只会出现 \(2^{n}-1\) 次,较小的数出现次数一定不小于较大的数。

这样我们就可以贪心了。我们维护每个数对答案的贡献加一时所需要的代价,\(i\) 开始的代价为 \(i\),每使用一次后代价翻倍,变为 \(2i,4i,\cdots\)。每次我们选取代价最小的数即可,直到代价超过 \(n\)

当然直接这样做复杂度过高,我们可以二分结束时的最小代价,这样我们可以把每个数按照选取次数分为 \(\log\) 个区间,每个区间内可以 \(\mathcal{O}(1)\) 计算贡献。

时间复杂度 \(\mathcal{O}(\log^{2}n)\)

C. Chalk Outline

题目大意:要求你构造一个 \(n\) 个点的简单多边形,使得恰有 \(k\le\frac{n(n-3)}{2}\) 条对角线严格在多边形内。

题解:根据双耳定理,每个简单多边形至少有一个三角剖分(什么你要我证?Jordan 曲线定理鬼才会证)。也就是说 \(k<n-3\) 时必定无解。对于 \(k\ge n-3\) 的情况,我们都可以构造出解。

尝试思考一下 \(k=n-3\) 的情况:我们依次放置点 \((0,0),\cdots,(i,i^{2}),\cdots(n-2,(n-2)^{2})\),然后再放置 \((0,-10^{9})\)。对于 \(k\) 更大的情况,我们考虑把形状变成前凸后凹,这样放置:\((0,x^{2}),(1,x^{2}-1),\cdots,(x,0),(x+1,0),(x+2,1),\cdots,(x+i,(i-1)^{2}),\cdots\),这样一来我们就又得到了 \(\frac{x(x-1)}{2}\) 条对角线。如果 \(n-3+\frac{x(x-1)}{2}<k<n-3+\frac{x(x+1)}{2}\),那么我们可以再上下移动 \(x+1\) 位置的点,使得恰好多出 \(k-(n-3)-\frac{x(x-1)}{2}\) 条对角线。

D. Do I Wanna Know?

题目大意:有 \(n\) 个人,\(i<j\) 的情况下,\(i\)\(j\) 强的概率为 \(p\)。对每个 \(1\le k\le n-1\) 求出存在一个大小为 \(k\) 的集合 \(S\),使得其中所有人都比其它任何一个人强的概率。

题解:显然对一个固定的 \(k\),如果 \(S\) 存在就是唯一的。因此我们可以把问题转化为,对每个 \(S\) 求出 \(S\) 满足要求的概率,然后相加即可。

\(dp_{i,j}\) 表示 \(i\) 个人中选 \(j\) 个的答案。设新加入的人为 \(n\),则有 \(dp_{i+1,j}=p^{j}dp_{i,j}+(1-p)^{i-j+1}dp_{i,j-1}\),若新加入的人为 \(1\),则有 \(dp_{i+1,j}=(1-p)^{j}dp_{i,j}+p^{i-j+1}dp_{i,j-1}\)。若 \(p\neq\frac{1}{2}\),则有 \(dp_{i,j}=\frac{p^{i-j+1}-(1-p)^{i-j+1}}{p^{j}-(1-p)^{j}}dp_{i,j-1}\),递推即可。若 \(p=\frac{1}{2}\),那么所有等大的集合都等价,也很简单。

E. Exit Song

题目大意:有一个 \(n\times m\) 的观众席,现在某些位置已被占用,问你有多少种方案选取若干连续的座位。其中被占用的位置为 \((r_{0},s_{0}),\cdots,(r_{k-1},s_{k-1})\)\(r,s\) 分别都是只依赖于前一项的递推数列。\(n,m\le10^{5}\)

题解:一个长为 \(x\) 的连续的段对答案的贡献为 \(\frac{x(x+1)}{2}\)。如果能把所有连续的段“求出”,问题也就做完了。

注意到 \(r,s\) 分别至多有长度 \(n-1,m-1\) 的非纯循环部分,这些位置我们最后加上即可。之后认为 \(r,s\) 是纯循环的。另外为便于讨论,我们假定它们的循环节长度分别是 \(n,m\)

首先有一个很显然的性质,模 \(\gcd(n,m)\) 不同的位置相互独立,我们可以分开处理。接下来设 \(\gcd(n,m)=1\)。我们来观察一下这两个数列的 pattern,设 \(n=7,m=4\)

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4

我们观察每一行依次对应了哪些列:

1 5 -> 1 4 3 2
2 6 -> 2 1 4 3
3 7 -> 3 2 1 4
  4 -> 4 3 2 1

可以发现,这些列都是循环出现的。这个性质在 \(k\) 恰等于 \(nm\) 时看似没有什么用,但是在 \(k\) 更小时是有用的。注意到任意两行之间出现的次数相差不会超过 \(1\),因此我们可以用一个双端队列来维护每一行对应的列,转移到下一行时,视情况删除开头的元素,再在末尾添上元素即可。为了使删除开头的元素复杂度正确,我们应当按照列循环不断左移的顺序来枚举行。例如上面的例子,行的枚举顺序应该是 4 -> 3 7 -> 2 6 -> 1 5

G. Gate 21

题目大意:求不同的长度为 \(n\) 的整数等差数列,使得 \(x_{i}\in[l_{i},r_{i}]\)

题解:即 \(l_{i}\le x_{0}+id\le r_{i}\)\(x_{0}\le r_{i}-id\land x_{0}\ge l_{i}-id\)。我们以 \(d\) 为自变量,\(x_{0}\) 为因变量,注意到 \(x_{0}\) 的取值范围被一个上凸壳和一个下凸壳限制,且这两个凸壳只有 \(\mathcal{O}(n)\) 个点。那么在同一条边之间,\(x_{0}\) 的取值方案数是 \(d\) 的一个一次函数,可以\(\mathcal{O}(1)\) 计算。

H. Hamilton

题目大意: 有 \(n\) 个点,标号从 \(1\)\(n\)。现在要你从 \(a\) 走一条哈密顿通路到 \(b\),其中从 \(i\) 可以花费 \(0\) 的代价到 \(i-1\)\(i+1\),花费 \(1\) 的代价走到某个和 \(i\) 互质的点。求最小代价,并给出方案。

题解:不妨设 \(a<b\)。如果 \(a,b\) 均为奇数,\(n\) 为偶数,那么无解,因为这样必须出现从一个偶数走到另一个偶数的情况。其它情况下分类讨论。

  • \(a=1,b=n\),答案为 \(0\)

  • \(b=n\),我们可以从 \(a\) 走到 \(1\),跳到 \(a+1\),再走到 \(b\),答案为 \(1\)

  • \(a+1=b\),我们可以从 \(a\) 走到 \(1\),跳到 \(n\),再走到 \(b\),答案为 \(1\)

  • \(a=1\)

    • \((b-1,n)=1\),我们可以从 \(a\) 走到 \(b-1\),跳到 \(n\),再走到 \(b\),答案为 \(1\)
    • \((b-1,n)>1\),注意 \(b+1\)\(n\) 至少有一个为奇数,因此和 \(2\) 互质。例如 \(n\) 为奇数,我们可以从 \(a\) 跳到 \(b+1\),走到 \(n\),跳到 \(2\),再走到 \(b\),答案为 \(2\)
  • 剩下的情况,由于我们至少有 \(3\) 段区间,因此答案至少为 \(2\)。要使得答案为 \(2\),那么 \(a\) 就必须要走完一个区间再跳,\(b\) 也必须是某个区间的端点。枚举 \(a\) 行走的方向以及走到 \(b\) 的方向,共有 \(3\) 种情况。以 \(a\) 向左走,\(b\)\(a+1\) 走来为例:

    • \((a+1,b+1)=1\),我们可以从 \(a\) 走到 \(1\),跳到 \(n\),走到 \(b+1\),跳到 \(a+1\),走到 \(b\),答案为 \(2\)
    • \((a+1,n)=1\),我们可以从 \(a\) 走到 \(1\),跳到 \(b+1\),走到 \(n\),跳到 \(a+1\),走到 \(b\),答案为 \(2\)

剩下两种情况这里就不赘述了。

  • 还可能会出现之前的都没法走的情况,\(3\) 步之内是一定有解的:

    • \(a\) 为偶数,我们可以从 \(a\) 走到 \(2\),跳到 \(a+1\),走到 \(b-1\),跳到 \(1\),再跳到 \(n\),走到 \(b\),答案为 \(3\)
    • 否则 \(b+1\)\(n\) 至少有一个为奇数。例如 \(n\) 为奇数,我们可以从 \(a\) 走到 \(2\),跳到 \(n\),走到 \(b+1\),跳到 \(1\),再跳到 \(a+1\),走到 \(b\),答案为 \(3\)

K. Kids Aren’t Alright

题目大意:给你一个 \(n\le10^{18}\),求 \(\gcd=1\)\(\text{lcm}=n\) 的非空集数量。

题解:首先分解 \(n\),我们可以用 \(10^{6}\) 内的质数先筛一遍,剩下有 \(1\)\(2\) 个质因子。\(1\) 个的情况可以用 miller rabin 判断;\(2\) 个的情况,要么是 \(p^{2}\),要么是 \(p_{1}p_{2}\),开根验证即可(不需要知道具体的质数是哪个)。

然后用一个 \(\mathcal{O}(3^{\omega(n)})\) 的容斥即可。