2020-2021 Winter Petrozavodsk Camp, Day 5: Almost Retired Dandelion Contest (XXI Opencup, Grand Prix of Nizhny Novgorod)

排名	当场过题数	至今过题数	总题数
201/?	3	9	13

A

solved by JLK

题意

有\(n\)个人，\(m\)个职位，现在对于每个职位有每个人的排名，每个职位要招一个人。

实际上有一个矩阵\(A\)，第\(i\)个职位招第\(j\)个人的收益是\(A_{i,j}\)，而且排名高的人一定收益高。但是\(A\)未知，问那些人可能被招。

\(1 \le m \le 11,1 \le n \le 1000,m \le n\)

题解

考虑枚举职位。对于某一种方案，肯定是某些职位招了第一名，然后这个第一名就被占用了，剩下有些职位只能招第二名，以此类推。这样一个方案，肯定对应着一个职位的排列，从前到后枚举，找到排名最低的没有被占用的人招走。

那么只需要枚举职位的排列然后模拟就可以了。

\(O(m!m^2)\)，需要卡常。

B

upsolved by TYB

题意

你和tourist一起比赛做题，你们两个每轮同时决策做哪道题，如果选择相同的题目，那么你不得分，比赛继续进行，这道题目不可以再被选择；如果选择了不同的题目，那么你能拿下你选择的这道题的全部分数，比赛结束，tourist想让你得分最少，你想让得分最多，问在双方均采取最优决策的情况下你的期望得分。

\(n\le22\)

题解

设\(f_S\)表示还剩下\(S\)集合的题目，期望得分是多少。设tourist的最优决策下，有\(p_i\)的概率选择第\(i\)道题，若你也选择了第\(i\)道题，那么期望得分为：\(p_if_{S\oplus2^{i-1}}+(1-p_i)a_i\)。由于你采取最优策略，所以你的决策一定是做某一道题使你的期望得分最大。问题转化为，如何分配\(p_i\)的值，使得\(\sum p_i=1\)，且\(p_if_{S\oplus2^{i-1}}+(1-p_i)a_i\)的最大值最小。注意到\(a\)越大，对应的\(f\)就会越小，不妨假设一开始所有\(p_i=0\)，按\(a_i\)排序，枚举最后的期望得分\(x\)在哪一个\(a\)的区间，那么对于所有\(a_i>x\)，必须给它的\(p_i\)分配\(\frac{a_i-x}{a_i-f_{S\oplus 2^{i-1}}}\)，判断是否可行即可。

复杂度\(\mathcal{O}(n2^n)\)。

C

upsolved by TYB

题意

给出\(n,k\)，求有多少个满足下列条件的数列\(a\)：

\(\bullet a\)的长度为\(n-k\)

\(\bullet\forall i\in[1,n-k],1\le a_i\le n\)

\(\bullet\)不存在一个子序列，使得其和为\(n\)的倍数

\(1\le k\le {n\over{4}}<n<998244353\)

题解

基本为英文题解的翻译，不知道咋想到的。

设出现次数最多的数为\(x\)，除\(x\)外的数出现了\(t\)次。

两个不同的数组成一个pair，则最多组成\(\min(\lfloor\frac{n-k}{2}\rfloor,t)\)个pair。

将这些pair从左到右排成一个序列，即\(x,a,x,b\cdots\)这样，将这个序列的前缀和求出来，为了满足题意，则这\(n-k+1\)个前缀和都要互不相同。

考虑交换一个pair里的两个数，由于交换的两个数不同，一定会恰改变一个前缀和，以此法又多了等同于pair个数种前缀和。

由于他们全都要互不相同，可以得到不等式\(n-k+1+\min(\lfloor\frac{n-k}{2}\rfloor,t)<n\)，然后可以发现\(\min\)函数一定要取\(t\)，即\(t<k-1\)，那么\(x\)的出现次数\(n-k-t>n-2k\ge n-2\frac{n}{4}=\frac{n}{2}\)次。

由此可得，\(x\)可能的取值只有\(\phi(n)\)种（否则仅考虑\(x\)就会有\(n\)的倍数）。

假设\(x\)为定值，令所有元素除以\(x\)（模意义下进行，\(x\)与\(n\)互质，有逆元存在）。设现在我们有\(o\)个\(1\)，则剩下的\(n-k-o\)个数之和必须\(<n-o\)，否则必定可以在其中选出若干个数，使它们的和\(\in[n-o,n]\)，从而用若干个\(1\)把和调整为\(n\)。然后可以发现，这等价于是\(k\)个数之和小于\(n\)的方案数（\(1\)的个数一定满足条件）。

于是答案为\(\phi(n)C_{n-1}^{k-1}\)。

实战的话可能还是要打表才可能看出来。

D

**solved/upsolved by **

题意

题解

E

upsolved by TYB

题意

给一个无向图，设其最大匹配为\(M\)，最小点覆盖为\(C\)，若\(C\le M+1\)，输出最小点覆盖的方案，否则无需输出。

\(1\le n\le500,0\le m\le\frac{n(n-1)}{2}\)

题解

先用带花树算法求出最大匹配的方案，则每条匹配边至少有一个点在最小点覆盖的方案中，所以\(C\ge M\)。那么只有两种情况。若\(C=M\)：则每条匹配边必须只能选择一个点；若\(C=M+1\)，则再分两种情况：一是额外的点在匹配边上，二是额外的点不在匹配边上，均可用2-sat解决，复杂度\(\mathcal{O}(n^3)\)。

F

**solved/upsolved by **

题意

题解

G

upsolved by TYB

题意

给一个长度为\(n\)的数列\(a\)，两个人玩游戏，每次必须选择一个质数\(p\)和一个区间\([l,r]\)，要求\([l,r]\)中每个数都包含质因子\(p\)，然后把它们所有因子\(p\)去掉，无法操作者输，求哪方获胜。

\(n\le1000,a_i\le10^{18}\)

题解

考虑用SG函数，则每个质数是独立的，可以分开考虑再把SG值异或起来。

对于每个质数\(p\)，根据\(a_i\)是否含有\(p\)的因子可以把它们分成两类，实际上又分成了若干个子游戏。打表可以发现，对于连续\(i\)个数，它们的SG值就是\(i\)。

那么现在一个很常规的思路就是把每个数都分解质因数，然后对于每个质数再求SG。然而我的miller_rabin+pollard_rho板子T了一整场，快的板子可以0.5s内通过（这题时限5s）。

考虑另外一种思路，枚举左端点\(l\)，计算这个左端点开始的所有线段的SG值。因为固定了左端点，所以要先把所有\(a_{l-1}\)的质因子去除掉。考虑线段结尾的位置，假设\([l,r]\)的\(\gcd\)和\([l,r+1]\)的\(\gcd\)不同，\(x=\frac{\gcd[l,r]}{\gcd[l,r+1]}=p_1^{k_1}p_2^{k_2}\dots p_m^{k_m}\)，那么\(p_1,p_2,\dots,p_m\)这些质数的线段就是\([l,r]\)。那么现在只需要快速知道\(m\)的值。

问题似乎又回到了分解质因数，但实际上，我们没有必要知道每个质数是多少，只需要知道有多少个。设\(C=(10^{18})^{1\over{3}}=10^6\)，对于某个数，我们只要把其\(\le C\)的所有质因子除掉，那么剩下的数只要三种可能：\(p,p^2,p_1p_2\)。这时候只需要用miller_rabin判一下即可知道最后剩下的数有多少个不同的质因子。对于一个固定的左端点，最多只有\(\log\)种不同的\(\gcd\)，如果每次\(\gcd\)发生变化时都暴力分解质因数，复杂度为\(\mathcal{O}(n\times \log\times \log \times C以内质数个数)\)，依然无法通过。但其实我们没有必要每次都枚举\(C\)以内的质数，因为\(\gcd\)如何变化，都是开始时那个数的因数，所以只需要求出开始时那个数\(C\)以内的质因数，然后每次在哪些数里面枚举即可，复杂度应该和题解相同？

H

**solved/upsolved by **

题意

题解

I

upsolved by TYB

题意

有\(n\)个商品，\(S\)元钱，每个有\(c_i,p_i\)两种属性，按某个自定的顺序购买商品，若第\(k\)个购买商品\(i\)，其价格为\(c_i+(k-1)p_i\)，求最多可以买多少个商品。

\(n\le10^5,c_i,p_i,S\le10^9\)，\(p_i\)互不相同。

题解

考虑暴力，按\(p\)从大到小排序，\(f[i][j]\)表示前\(i\)个物品买了\(j\)个，最少花了多少钱。注意到\(p_i\)互不相同，第二维很小，不超过\(1900\)，直接做即可。

J

solved by TYB

题意

给两个\(n\)的排列\(A,B\)，可以对\(A\)操作不超过\(n\)次，每次操作为把一个区间升序或降序排序，问是否可以把\(A\)变成\(B\)，并给出方案。

\(n\le500\)

题解

可以证明，先把\(A\)升序排序，再从\(1\)到\(n-1\)，逐位把\(B_i\)换过来，这样的方案一定可行。

K

**solved/upsolved by **

题意

题解

L

upsolved by JLK

题意

每一轮会出现R或者B，可以下注（不要求整数），猜对翻倍，猜错就没了。已知R和B出现的次数，一开始有1单位的钱，求能保证结束的时候最少有多少钱。超过\(10^9\)输出Extreme Wealth。

\(0 \le R,B \le 10^{13}\)

题解

考虑一个递推的想法。对于某个\((R,B)\)，如果要下注，一定是猜较多的那个。然后会有两种可能\((R-1,B)\)和\((R,B-1)\)。因为要让最少的钱最多，所以肯定是让两种可能的最少钱数相等。可以通过解方程得到。最后得到转移式为\(f_{R,B}=\frac{f_{R-1,B}+f_{R,B-1}}{2f_{R-1,B}f_{R,B-1}}\)

可以推出答案为\(\frac{2^{R+B}}{C_{R+B}^{R}}\)。

但是\(R,B\)很大，没法直接计算。

直接用斯特林公式会产生比较大的误差。题解的方法是，先用斯特林公式化简求出\((B,B)\)的答案，然后递推到\((B,R)\)（假设\(B \le R\)）。

\(f_{B,B}\approx \sqrt{\pi B}(1+\frac {1}{8B})\)

\(f_{B,R+1}=\frac{2(R+1)}{B+R+1}f_{B,R}\)

题解说除去前\(\sqrt B\)步外，每\(\sqrt B\)步会让答案至少翻倍。所以复杂度为\(O(\sqrt B \log 10^9)\)。

实际上\(B,R\)比较小的时候需要暴力算，否则精度还是有点炸。

M

**solved/upsolved by **

题意

题解

记录

YZW写M，TLE一次后AC(0:27)。

TYB过J(0:42)。

TYB和JLK讨论出了G的一个做法，TYB开始写，但是一直TLE。

扔了看A，JLK试了一下，TLE一次后AC(2:50)。

看L，JLK打了个表，YZW看出了结论，TYB给了个阶乘的近似公式，但是因为精度问题一直WA。

最后又试了一下G，还是没用。

总结

TYB：板子太垃圾，赶紧抄个好点的。I似乎是因为没有注意到一个性质，一直没想出来。以后转述题意的时候要注意，最好还是自己亲自看一遍题目。

Dirt

A(-1)

M(-1)