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)})\) 的容斥即可。