AtCoder Grand Contest 003

A - Wanna go back home

题目大意：

Snuke在无限大的二维坐标平面上从原点出发，进行了\(n\le1000\)天旅行，已知每天旅行的方向（为东南西北四个方向之一），但距离是任意的，问是否存在一种方案使得最后一天旅行后恰好回到原点。

题解：

显然不能回去当且仅当某个方向的旅行存在而其反方向的旅行不存在。

B - Simplified mahjong

题目大意：

有\(n\le10^5\)种不同的卡片，第\(i\)种卡片有\(0\le a_i\le10^9\)张。

第\(i\)种卡片可以和第\(i-1,i,i+1\)种卡片之一配对，问最多可以配出多少对。

题解：

因为自己可以和自己配对，所以就是要尽可能多的解决掉奇数卡片。

形如奇奇，奇偶奇，奇偶偶奇这样的连续卡片可以完美配对（要求偶数不为零）。

按上面的策略从左往右贪心配对即可，时间复杂度\(O(n)\)。

C - BBuBBBlesort!

题目大意：

给出一个长度为\(n\le10^5\)的整数数列\(a\)，数列中的数两两不同，要用以下两种操作将其排序为升序：

• 交换相邻的两个位置（\(A_i,A_{i+1}\)）

• 交换相隔一个位置的两个位置（\(A_i,A_{i+2}\)）

求至少要用到多少次第一种操作。

题解：

第二种操作可以做到不改变位置奇偶性的任意交换，但是要改变奇偶性必须用到第一种操作。

因此设排序前后位置奇偶性改变的数有\(k\)个，则答案为\(k/2\)。

显然\(k\)为偶数，因此，可以用第二种操作使其交换到两两相邻，再用\(k/2\)次第一种操作即可。

时间复杂度为排序复杂度\(O(n\log{n})\).

D - Anticube

题目大意：

给出一个长度为\(n\le10^5\)的整数数列\(a\)，\(1\le a_i\le10^{10}\)。

要从数列中选出尽可能多的数，满足被选出的数中，任意两个数的乘积不是立方数。

输出最多可以选出的数的数量。

题解：

定义\(Norm(t)\)为\(t\)去掉所有立方因子后剩余的部分，\(Pair(t)\)为令\(t\times Pair(t)\)为立方数的最小的数。

那么\(a\times b\)为立方数当且仅当\(Norm(a)=Pair(b)\)，并且显然此时\(Pair(a)=Norm(b)\)也成立。

如果知道每个数的\(Norm\)与\(Pair\)，则\(\displaystyle ans=[|\{t|Norm(t)=x\}|>0]+\frac{\sum\limits_{x=2}\max(|\{t|Norm(t)=x\}|,|\{t|Pair(t)=x\}|)}{2}\).

利用线性筛求出\(10^{\frac{10}{3}}\)以内的质数。

\(Norm(t)\)直接枚举\(t^{\frac{1}{3}}\)以内的质数试除即可。

\(Pair(t)\)同样枚举\(t^{\frac{1}{3}}\)以内的质数，这一部分需要补上的因子就计算完毕了，剩余的部分\(s\)至多只有两个质因子。

当\(s=1\)或\(s\)为质数或\(s=p\times q\)时，这一部分需要补上的因子都是\(s^2\)，只有当\(s=p^2\)时，只需要补上\(p\)即可。

因此直接对\(s\)开方判断其是否为平方数即可。

时间复杂度为\(\displaystyle O(maxA_i^{1/3}+\frac{n\times maxA_i^{1/3}}{\log{maxA_i}}+n\log{n})\).

需要注意的是\(Pair(t)\)可能会很大，超出long long int的范围。

但是因为\(Norm(t)\le t\le10^{10}\)，这样大的\(Pair(t)\)是找不到与其匹配的\(Norm(t)\)的。

因此计算过程中简单判断一下是否会超出一个足够大的上限，会的话直接令其等于上限即可，不影响计算结果。

E - Sequential operations on Sequence

题目大意：

有一个长度为\(nle10^5\)的数列，一开始为\(1,\cdots,n\).

接下来\(q\le10^5\)次操作，每次操作使得数列长度变为\(1\le A_i\le10^18\)。

如果\(A_i\)小于等于操作前的数列长度，则保留数列前\(A_i\)项。

如果\(A_i\)大于操作前的数列长度，则不断循环重复数列直到补足\(A_i\)项。

题解：

如果\(i<j\)且\(A_i\ge A_j\)，则第\(i\)次操作可以被忽略。因此可以得到一个单调上升的操作序列\(B\)。

考虑将操作过程反过来，从\(B_{i+1}\)变为\(B_i\)等价于将线段\([1,B_{i+1}]\)变为了\(\lfloor\frac{B_{i+1}}{B_i}\rfloor\)个\([1,B_i]\)和\([1,B_{i+1}\mod{B_i}]\)。

一开始只有一个线段，最后答案为\(1,\cdots,n\)每个位置被多少条线段所覆盖。

用数组\(t[i]\)维护当前线段\([1,B_i]\)的数量，用\(k\)维护除了\([1,B_j](j<i)\)之外的零散线段的右端点，之后不断拆分线段\([1,k]\)。

每次找到最大的小于\(k\)的\(B_j\)，拆分出\(t[i]\times\lfloor\frac{k}{B_j}\rfloor\)条线段\([1,B_j]\)，然后\(k\)就变为了\(k\mod{B_j}\)。

直到\(k<=B_1\)，这时\(k\)无法再被拆分，给最终答案的区间\([1,k]\)贡献\(t[i]\)。

因为取模的下降速度很快，是\(log\)级别的，总的时间复杂度为\(O(q\log{q}\log{max_A}+n)\).

F - Fraction of Fractal

题目大意：

有一个\(H\times W\)（\(1\le H,W\le1000\)）的网格图，黑点是四连通的，白点是不连通的。

按如下规则定义该网格图的\(K\)级分形：

• \(K=0\)，为\(1\times1\)的只有黑点组成的网格图

• \(K\ge1\)，为将原网格图的每个黑点换成\(K-1\)级分形，白点换成与\(K-1\)级分形大小相同，只有白点组成的网格图后的新网格图

现在要求该网格图的\(0\le K\le10^{18}\)级分形图中连通块的数量。