Hello, world!

Namomo is a non-profitable community initiated by Chinese programming contest volunteers.
Our target is to share the best programming knowledge & problems with students.

Learn more »

Fish Round 1 题解

By walkershi, 8 weeks ago.

Gym

小沃沃只有两种选项:

  1. 当小沃沃的速度大于学皇时,顺时针追学皇;
  2. 小沃沃逆时针跑,直到遇到学皇;
    我们把它们都算出来,取最小值即可。

Matrix

把格点黑白染色,横坐标 i + 纵坐标 j 为偶数染成黑色,为奇数染成白色。n \ge 2 时,答案 = 1 和 n^2 都在黑点上的方案数 + 1 和 n^2 都在白点上的方案数。
证明:假设第 j 个点的坐标为 (x_j,y_j)\sum_{j=1}^{i-1}|x_{j+1}-x_j| 奇偶性和 |x_i-x_1| 相同(把前面一个式子展开,中间项的系数都为偶数,不影响奇偶性), \sum_{j=1}^{i-1}|y_{j+1}-y_j| 奇偶性和 |y_i-y_1| 相同,所以当 1n^2 同黑同白时,\sum_{j=1}^{i-1}dist(p_j,p_{j+1}) 为偶数。

Number

首先,最后的数字小于等于 a 中的最大元素。如果最后的数字大于 a 中的最大元素,它最后一步肯定是每个数字平方得到的,不如不平方。
然后,每个数字 a_i 能够变成的数字个数是有限的,除了它不断开根得到的数字,其他只能是完全平方数,最多只有 \sqrt{100000} 个。
那么我们可以从初始的 a_i 开始 bfs,算一下最少多少步可以变成某个值 j,记为 f_{i,j}
接着我们枚举 j,算下 \sum_{i=1}^{n}f_{i,j} 的最小值就行啦。

Deadline

这题可以贪心,不过题解中介绍一个 dp 的方法。我们把 a 排序后,用 f_{i,j} 表示我们考虑了前 i 个deadline,最少用多少天可以干完其中的 j 个。针对第 i+1 个deadline,我们可以选择不干,那么有 f_{i+1,j} = min(f_{i+1,j},f_{i,j}) ;我们也可以选择干,那么我们得算算从第 f_{i,j} 天开始,最少到第几天 x 可以干完,更新 f_{i+1,j+1}=min(f_{i+1,j+1},x)

Light

这题分两种情况,第一种是我们使劲刹车也刹不下来的情况(意味着我们没办法停在红绿灯前),那么我们可以计算出在全力加速的情况下需要 x 的时间到达红路灯,在全力减速的情况下需要 y 的时间到达红路灯,意味着我们可以在 [x,y] 中的任意时刻到达红绿灯。
否则,我们可以刹住车,这意味着我们可以在 [x, +∞] 的任意时刻到达红绿灯。求出其中最早的绿灯时刻就行。

+16


Round 5 solution

By walkershi, 2 months ago, revision 5.

Number

本题答案等于在n中值最大的数位的值是几,假设这个值是x。首先我们需要至少x个串,否则最大的数位的值凑不到;其次我们需要至多x个串,对于每个数位,假设它的值是y,那么我们只要把前y个学数的这个位置设置成1,剩下x-y个学数的这个位置设置成0即可。

Mod

答案等于n操作的次数+m操作的次数,那么我们可以从0到p-1枚举最后n,m会变成几,然后算最小值即可。那么n,m到任意数i最少需要几步怎么求呢?我们写个bfs就行。

Game

我们先来看看最后一步,假设最后一步是Bob操作,那么无论剩下两个数的奇偶性如何,他都可以把数变成偶数,这对应了初始奇数个数字的情况。换句话说,当n为奇数时,Bob必胜(n=1要根据唯一的数字的奇偶性特判)。否则,最后一步是Alice操作,除了两个数字都是偶数的情况,Alice都能把最后的结果变成奇数。那我们在意的是每时每刻剩下多少个偶数,Alice每次操作最多可以消灭一个偶数,Bob每次操作最多可以生成一个偶数。所以如果初始的偶数数目至少有两个,那么Alice是赢不了的(无论什么时候Alice消灭偶数,如果此时有两个奇数,bob都能生成一个偶数。如果alice消灭偶数后仅剩1个或0个奇数,bob可以转而消灭那个奇数,这样所有的数字都是偶数了。)。当初始偶数小于2个时,Alice必胜(Bob没办法让最后的偶数个数达到2个)。

String

本题在trie上维护包含某个前缀的串的值的和,直接暴力即可。下面介绍如何分析均摊复杂度,即证明每个输入的字符只会产生常数的运行时间。插入字符串时,从trie的根开始,每个字符会往下走一步,如果没有对应的点会新建一个点。走到最下面把维护的值加上这次插入的串的值即可。这样每个字符只消耗常数时间(走一步和新建一个点)。删除类似,走到字符串对应的点后,用该点维护的值减掉它两个子树维护的值,就可以得到所有字符串s的值的和,称为d。再从这个点走回根,沿途将维护的值减少d即可。询问也类似,走到对应的点输出维护的值。最后一种修改操作,由于s和t公共前缀为空,所以代表sx的串在trie中对应的子树和代表tx的串对应的子树无交。我们找到两棵子树的根(称为s和t),递归的合并他们。首先把s维护的值加在t维护的值上,t作为合并后的根,s可以删除。对于s和t各自的左儿子(字符为0的儿子),如果至少一个儿子不存在,把存在的那个儿子作为合并后的左儿子即可。如果两个左儿子都存在,递归合并这两个左儿子。右儿子同理。这样,每次要么递归不继续进行,要么在递归的同时trie里面点的数量会减一(两个根合并后只剩一个)。由于trie里每个点都是某个输入的字符创建的,所以每次递归的复杂度平摊在每个输入的字符上只有常数。

Search

不考虑询问次数限制,本题可以每行二分一次。考虑并行运行每一行的二分,统一回答所有行需要的询问一。把所有当前需要问的询问一按照所在格子的数字的大小排序(数字大小可以用询问二确定),取数字大小处于中位数的那个询问。如果这个中位数大于等于x,那么所有比这个中位数大的数字也都大于等于x。如果这个中位数小于x,那么所有比这个中位数小的数也都小于x。这样我们虽然无法回答所有的询问一,但是至少可以回答一半。某一行的询问如果被回答了,那它的二分可以进行到下一步,否则它会暂时卡住,下次还问一样的问题。这样每轮至少可以回答一半的询问一,一半指当前二分还没结束的行的数量的一半。复杂度分析:一共有 n\log n 个问题,当剩余问题数量在 ((k-1)\log n, k\log n] 时,至少还有 k 行的二分没结束,所以这时一次询问至少回答 k/2 个问题 。那么总询问一次数就是 \sum_{i=0}^{n-1}\frac{\log n}{(i+1)/2}=O(\log ^2 n)

+27


round 4 solution

By walkershi, 3 months ago, revision 3.

t-shirt

由于得到每个名次的概率相等,所以一场比赛得到衣服的概率 = \frac{\sum_{i=l}^r{\frac{1}{i}}}{r-l+1}
根据概率论知识,已知某事件发生的概率为 p,则要让该事件发生所需的试验次数期望值为 \frac{1}{p}
所以答案 =\frac{r-l+1}{\sum_{i=l}^r{\frac{1}{i}}}

game

假设初始只有一位玩家有金币,那么他就是赢家。
否则,游戏结束前的最后一个状态是除了正在操作的玩家,外面总共只有 1 个金币。考虑一次操作,假设外面有至少 2 个金币,那么当前操作以后,外面至少还有 1 个金币,所以还有人可以操作,对于下一位操作的玩家来说,外面也至少有 2 个金币(当前操作者手上就至少有 2 个)。只有第 1 位玩家有结束游戏的可能,如果第 1 位玩家操作完以后游戏结束不了(意味着外面有至少 2 个金币),那么游戏就永远结束不了。
假设初始有两位玩家有金币,那么除非后动手的玩家手上的金币恰好只有 1 个,否则游戏不会结束。
假设初始有超过两位玩家有金币,那么游戏也不会结束。

matrix

对于每个位置来说,只有两种状态是关键的:0 或非 0。所有大于 0 的数字都一样。那么一个直观的 idea 就是我们用一个二进制状态 status 表示矩阵的每一位是不是 0。当 Astatus 确定的时候,它的后继状态也是唯一确定的。于是我们可以去寻找一个循环节,那么 f(A^i) 可以分为两个部分,第一个部分是循环节前的一段,第二部分是在循环节中的那一段。对于两部分,我们都可以求和。
由于循环节长度最长为 12,所以直接暴力即可。

point

我们假设 m=\sum_{i=1}^{n}b_i,同时取 k=2^m
如果我们在 k 维空间中进行构造,则只需要选取一个 k 维长方体即可。(边长由条件决定)
2^m 个点,每个点前 b_1 个维度的坐标为 0a_1,接下来 b_2 个维度的坐标为 0a_2,以此类推。
我们现在要做的就是把这个 k 维长方体映射到二维平面上,
我们只需把 k 个维度的单位向量替换成一个二维平面上随机单位向量:
我们假设随机 k 个二维平面上的单位向量分别为 (x_i,y_i),分别表示原本 k 维空间中的 k 个维度的单位向量。则我们将 k 维空间中的一个点 (v_1,v_2,\ldots,v_k) 映射到二维平面上的点 (\sum_{i=1}^{k}v_i*x_i,\sum_{i=1}^{k}v_i*y_i)
只要这 k 个单位向量及其它们的部分和均不为零向量,即可满足题意。
时间复杂度 O(2^m)

arrange

在数据范围内所有排列都可以成功排序。假如可以任意交换两个敌人,那么 O(n) 步之内就能成功排序。下面我们构造交换任意两个敌人的办法。

首先先通过若干操作把两个敌人的位置变成 (0, 0)(0, m/2)。交换完成后把这些操作取消即可。(如果$n$ 小于 2 或者 m 小于 4,不一定能完成这个位置变换。所以数据避免了这些情况。)

考虑旋转圆环 0 m/2 次。(0, 0)(0, m/2) 的确交换了,与此同时圆环 0 上的其他敌人也和它们对面的敌人交换了。

现在考虑把区域 0 (或者 m/2 )的上档操作和上面的旋转圆环 0 操作联合使用。我们发现通过适当的上挡,(0, 0)(0, m/2) 可以填入区域 0 和区域 m/2 中任意两个位置相邻的元素(认为位置 (n-1, 0)(n-1,m/2) 相邻, (0, 0)(0,m/2) 相邻)。配合上旋转圆环 0 m/2 次,我们就可以交换区域 0 和区域 m/2 中任意两个相邻的元素,副作用是每交换一次圆环 0 上的其他敌人也和它们对面的敌人交换。

也就是说,我们只要使用偶数次上述联合操作,就不会对区域 0 和区域 m/2 之外的敌人产生影响。为了方便描述,我们假设位置 (0, i) 上的敌人编号为 2n-i-1, 位置 (m/2, i) 上的敌人编号为 i。即区域 0 和区域 m/2 中的敌人编号为 0, 1, \ldots, 2n-1 且初始编号为 x 的敌人和编号为 x+1 的敌人相邻( 02n-1 )相邻。我们想要交换敌人 0 和敌人 1。要达到这个目的,我们可以通过联合操作依次交换敌人 0 和敌人 2n-102n-2,以此类推,不断将敌人 0 向一个方向移动,最后 0 将会绕到 1 的另一侧。因为 2n 是个偶数,所以我们使用了偶数次联合操作,只交换了 01,对除了区域 0m/2 以外的其它位置没有影响。最后只要用上档操作把区域 0m/2 中除了 01 以外的敌人位置复原即可。

于是我们成功构造了交换两个敌人的操作。

+19


namomo round 4

By walkershi, 3 months ago.

今晚五个题的分数分别是500,1000,1500,2000,2500。

+26


Namomo Cockfight Round 3 题解

By badcw, 3 months ago, revision 3.

祝贺 Winners

  1. AKEE
  2. supy
  3. Turkey
  4. QAQAutoMaton
  5. MAOoo

A. Pocker

题目的交换条件可以换一种说法,只要前面那个人手里的牌的期望比自己的牌大,就交换。
第二个人的情况比较简单,他手中是3的时候,第一个人手里可能是1,2或者4,期望为 \frac{7}{3} 。故他选择不换。对称地,第二个人手里是2的时候要换。
从第三个人开始,情况就比较复杂了。这时我们考虑如何真正计算期望值。第三个人看到手里的牌 x 后,知道前两个人会拿到除去 x 之外的牌中的随机两张,每种组合概率相同。令 S(x)=\{(a,b)|\text{第三个人拿到x,第一个人拿到a且第二个人拿到b的情况下第二个人会选择交换}\},令 T(x)=\{(a,b)|\text{第三个人拿到x,第一个人拿到a且第二个人拿到b的情况下第二个人会选择不交换}\}。第三个人在知道第二个人是否选择了交换的情况下,可以将 S(x)T(x) 中的一个排除。剩下的集合(不妨设为 S(x) )中,他只要按照上面提到的第二个人的策略,就可以判断每种组合第二个人是否选择了交换,继而确定第二个人最终手中会拿到几。由于每种情况发生的概率相同,期望就是 S(x) 中每种情况下第二个人最终手持的数字的平均值。最后,第三个人判断这个期望是否大于自己的手牌。可以验证这个期望不会等于第三个人自己的手牌。
第四个人也可以类似计算。前三个人一定拿的是除了自己的数字以外的三个数字,只是排列不知道。对于每种排列,按照上述的第二个人和第三个人的决策计算方法,可以按照第二个人和第三个人分别是否选择交换分到4个集合之一中去。第四个人看到实际情况后,就排除这4个集合中的三个。最后剩下的集合中每种情况概率相同,就可以计算期望了。剩下的集合如果是空的,代表不会有这种情况(Impossible)。

B. 嬲

题目相当于找一个长度为 k 的简单环,对其连有向边使得相邻两项距离不超过 x

那么考虑由于是在一个轴上,显然间隔的跳是最优的,假设 1<2<3<41\to4\to3\to2\to1 满足条件,那么 1\to 3\to 4 \to 2 \to 1 一定也满足条件,反之则不然。

那么我们对于一个位置 i 维护它间隔为 2 最远能到达 f_i=1+f_{i-2}*\left[a_i-a_{i-2}\le x\right]。能构成的最大环显然跟相邻两项相关,也就是 f_i + f_{i-1},需要考虑一些细节,比如 f_{i-1} \lt f_i 的时候是不合法的,需要缩小一些范围。

如果说找不到最大环长度大于等于 k,显然就是需要找到最长的一条链,直接线性扫一遍就能出结果。

复杂度: O(n)

C. 游戏

方法1:注意到 C 其实是阿贝尔群 Z_{A_1}\times \ldots \times Z_{A_n}Z_x 为大小为 x 的循环群)的元素,让 B 循环的操作次数就是 C 的 order。如果所有的 C 的order排序后一样,当且仅当 AA' 对应的这两个阿贝尔群同构。两个阿贝尔群同构,由有限阿贝尔群基本定理,当且仅当对所有质数 p 和 所有正整数 q,被 p^q 整除的 A_i 个数和 能被 p^q 整除的 A’_i 个数相同。

方法2:记第 k 次操作后的 B_iB_i^{(k)}。初始 B_i^{(0)}0。对于任意一个 ik\ge 0B_i^{(k)}=B_i^{(k+\frac{A_i}{gcd(A_i,C_i)})},因为经过 \frac{A_i}{gcd(A_i,C_i)} 次操作 B_i 会加上 \frac{A_i}{gcd(A_i,C_i)}\cdot C_i\equiv 0\pmod {A_i}。未经 \frac{A_i}{gcd(A_i,C_i)} 次操作 B_i 是不会循环的,因为假如经过 x 次操作 B_i^{(k)}=B_i^{(k+x)} ,说明 x\cdot C_i\equiv 0\pmod A_i,那么 x\cdot C_iA_i 的倍数,x 必须是 \frac{A_i}{gcd(A_i,C_i)} 的倍数。记 r(A, C, i)\frac{A_i}{gcd(A_i,C_i)},即 B_i 的循环节长度。

知道了每个 i 的循环节,那么整体的循环节就是所有 i 的循环节的最小公倍数,记为 s(A, C)=lcm(r(A, C, 1), \ldots, r(A, C, n))。本题要求判断是否对每一个正整数 x ,使得 s(A, C)=xC 数目和使得 s(A', C)=xC 数目相同。

使得 s(A, C)=xC 数目不好算。我们把上述条件等价转化为对每一个正整数 x ,使得 s(A, C)|xC 数目和使得 s(A', C)|xC 数目相同。

下面计算使得 s(A, C)|xC 数目。当 s(A, C)|x 时,因为 s(A, C)=lcm(r(A, C, 1), \ldots, r(A, C, n)),每一个 r(A, C, i) 都要整除 x 。即 \frac{A_i}{gcd(A_i,C_i)}|x 。这等价于要求存在正整数 y 使得 y\cdot\frac{A_i}{gcd(A_i,C_i)}=x,等价于存在 y 使得 gcd(A_i, C_i)=y\frac{A_i}{x} 。等式右侧必须是整数,这说明 y 必须是 \frac{x}{gcd(A_i, x)} 的倍数。所以 \frac{A_i}{gcd(A_i,C_i)}|x 等价于存在 y'y' 相当于 y/\frac{x}{gcd(A_i, x)} )使得 gcd(A_i, C_i)=y'\frac{A_i}{gcd(A_i, x)} ,等价于 \frac{A_i}{gcd(A_i, x)}|gcd(A_i, C_i) 。这样的 C_i 个数有 \sum_{\frac{A_i}{gcd(A_i, x)}|d, d|A_i}\phi\left(\frac{A_i}{d}\right)=\sum_{d|gcd(A_i, x)}\phi\left(\frac{gcd(A_i, x)}{d}\right)=gcd(A_i, x),其中 \phi 是欧拉函数。也就是说使得 r(A, C, i)|xC_i 共有 gcd(A_i, x) 个。那么使得 s(A, C)|xC 就有 \prod_{i=1}^n gcd(A_i, x) 个。

下面推理在什么情况下,对于任意的正整数x,使得 s(A, C)|xC 数量和使得 s(A', C)|xC 数量总相同。因为 h(A,x)=\prod_{i=1}^n gcd(A_i, x) 是关于 x 的积性函数,只要所有的是质数的幂次的 x 满足 h(A, x)=h(A',x) 即可。 假设 x=p^q 是质数的 q 次幂。我们有 \prod_{i=1}^n gcd(A_i, x)=p^{\sum_{j=1}^q(能被p^j整除的A_i数目)} 。我们发现这等价于对任意的正整数 q ,被 p^q 整除的 A_i 个数和 能被 p^q 整除的 A’_i 个数必须相同。即本题的条件是,对所有输入范围内的质数 p 和 所有正整数 q,被 p^q 整除的 A_i 个数和 能被 p^q 整除的 A’_i 个数相同。
从上面的结论中我们发现,不同的质数之间互不影响,所有质数对应的条件需要同时满足。如果开始就将每个质数分开考虑,即对每个 p 提取 A_ip 的幂次,可以简化思维难度。

D. 无向图

先无视复杂度,l_{u,v} 其实是从 uv2 单位的流的最小费用,其中原图每条边都是双向的(建立两条单向边),容量和费用均为 1

一个普通的费用流计算方法是,每次在残量网络中找最短路并沿此路径流 1 单位流。在本题中一共需要 2 单位的流,重复两次即可。

第一次残量网络就是原图,我们可以通过bfs求出最短路。第二次求最短路的时候,第一次的最短路已经不能正向行走,且沿着第一次最短路增加了反向的容量为 1 费用为 -1 的边。为了降低求第二次最短路的复杂度,我们将每条有向边 (a,b) 的费用加上 dis(a)-dis(b),其中 dis(x) 代表第一次最短路求出的 ux 距离。经过修改以后的图从 uv 最短路长度减少了 dis(v),但是最短路径不变。(其实每条从 uv 的路径长度都减少了 dis(v),所以最短路径不变。)修改以后的图每条边的费用都是非负整数了(因为最短路数组 dis 的性质,如果还有负数可以导出矛盾)。这样就可以用Dijkstra求最短路了。现在复杂度是 O(n^2D), 其中 n^2 来源于枚举 u,vD 是Dijkstra的复杂度。

下面叙述如何用bitset优化这个Dijkstra。发现每条边的权值都是 0,1,2 中的一个。大部分边和第一次最短路时一样,只有 O(n) 条沿着第一条最短路上的边有变化。于是我们用bitset存储每个点权值为 0,1,2 的出边。令 e[i][0], e[i][1], e[i][2] 为三个bitset,分别表示(在第二次求从 uv 的最短路过程中,修改以后的图中)点 i 的费用为 0, 1, 2 的出边的终点的集合。e 数组每次更换 u, v 只需 O(n) 时间更新。(bitset第 x 位为 1,就表示 x 在集合中。) 令 bitset q[i] 表示和 u 距离不超过 i 的点的集合。q 数组用作Dijkstra里的队列,在Dijkstra时我们需要依次求出 q[0],q[1],\ldots, q[2n]。假设 q[i] 已经被求出了。首先 q[i+1] 要包含 q[i]q[i] 中包含的所有点 ve[v][x] 里的点离 u 的距离至多为 i+x。所以我们可以把 q[i] 中所有点 ve[v][x] 的并加入 q[i+x] ,相当于批量进行了Dijkstra的更新操作。对 x=1,2 都这样操作。为了节约时间,我们只要把 q[i]\setminus q[i-1] 中的点 ve[v][x] 并起来。注意在每个 q[i] 使用前,因为我们只用 q[i-2]q[i-1] 更新了 q[i] , 还需要考虑费用为 0 的边。所有和 q[i] 中的点以费用为 0 的边相邻的点也应该被加入 q[i](注意这是一个迭代过程)。这样Dijkstra就可以在 O(n^2/W) 时间内解决了,其中 W 是bitset位运算一次可以操作的位数,大多数机器上是64。

+14


View more »

Top rated »

# user rating
1 AKEE 1974
2 huge_waxberry 1901
3 Turkey 1861
4 supy 1832
5 dreamoon 1803
6 MAOoo 1744
7 bakapiano 1740
8 diodio 1706
9 Nanakom 1705
10 LLLLLLgq 1700