AtCoder Grand Contest 003

题目链接代码链接

比的时候只做出三道,后来感觉这一期的D题是可以出的,E题的思路还是神,就感觉这种题也不靠什么特定的算法,靠思维把问题转换,跟前面Atcoder的很多题一样,挺看智商的。。。至于F题。。。那个矩阵的构造,从答案推出矩阵的正确性我是搞懂了,但是如何通过一些递推关系搞出矩阵,感觉自己还需要练习吧= =。

A Wanna go back home


题意是Snuke走|s|次,每一次东西南北四个方向,任意距离,给出走的方向,问最终能否回到原点。

相对的方向要都出现或者都不出现,这样就能够保证在这两个方向上移动的距离为0。

B Simplified mahjong


题意是Snuke有一堆卡片,每张卡片上的数字为1~N,数字i的卡片有Ai个,两张卡片上数字相差不超过1的可以形成一对,问最多形成多少对。

之前一直WA,后来就直接贪心,如果数字为i的为偶数,那就自己组成一对。如果为奇数,找后面的一个组成一对。

C BBuBBBlesort!


题意是给出N个数,想把这N个数按大小排成有序,交换方法有两种:1.交换相邻的2个;2.交换相邻的3个.

问最少必须使用多少次操作1使得数字有序。

能够发现将这N个数排序之后,如果一个数排序之前的位置与排序之后的位置之差如果是偶数的话,那么就可以通过操作2来实现,但如果是奇数的话,那没办法了,想要到达该状态就必须通过操作1来实现了。

D Anticube


题意是给出N个数,求一个集合,该集合两两数字之前相乘不是立方数,问该集合元素的最大数量。

叉姐题解

其实后来就是如何分解该数的问题,一直TLE。

数字是在10^10级别的,将10^3级别的因子过滤一遍之后,就考虑只剩下了p,pq,p^2的形式了,考虑如何将它们处理。另外p^2形式还要注意一下精度问题。

剩下的就是两者取大的问题了。

E Sequential operations on Sequence


题意是当前有一个序列1…N,有Q次操作,每次操作中,该序列被原来序列的前Qi个数不断地重复替代。问最终序列每个元素的出现次数。

能够发现规律,如果Qi>Q(i+1),那么之前的Qi就没有意义了。

这样就会变成所有的操作是一个递增的序列。

还是发现数字小的元素出现次数一定比数字大的元素出现次数多,所以最终问题考虑使用后缀和,那从后往前考虑,把最后一个元素标为1,即所有元素都是1了。

从后往前每一次操作相当于做了一次折叠,考虑将后面位置的这些贡献分别贡献到那里了,如果该位置pos>Qi,那么会发现Qi位置上的值+=(pos/Qi)*(该pos的值),pos%Qi位置上的值+=pos%Qi。

这种问题感觉很难总结出一个系统的解决方法,每次碰到就靠跳大神,求问有没有类似的问题呢。。。?

F Fraction of Fractal


题意是h*w的方格,每个格子要么是白点要么是黑点。所有这些黑点在上下左右四个方向是联通的。

现在给出求第k等的图的方法,第k等的图从第k-1等的图来,如果该位置是白点,该位置替换成h*w的白点;如果是黑点,该位置替换成最开始的图。

问第k等的图中黑点的联通块是多少个。

先把其它简单的条件过滤掉,如果该图左右上下都可以连上,那么最终结果不管k多大都是1。

如果该图左右上下都连不上,那么最终结果就是黑点数量a^(k-1)。

现在只考虑一边连上,一边连不上的情况。比如说左右连通,上下不连通。

现在这个图中黑点的数量为a,左右相连的点对数为b,边界上最左边和最右边都是黑点的对数为c。

好,现在假设你已经知道了第k-1层有多少个连通块设为x,第k-1层有y个连接的数量,那么如何推出第k层?

首先x*a,这个是完全不考虑相连的情况,假设每一个连通块就会分裂成a个,那么总和就是x*a个,之后减去x*b个,这b块不是新生成的连通块数量,要减去,是内部生成的。

之后的这个y是上一轮连接的数量,那么上一轮如果连接上了的话,每一对y分裂而成就会有c对是新生成的连接着的块,这个是新的外部的连接的。

这样总结得话可以得到一个矩阵,
$$
{\begin{pmatrix}
a&-b\\
0 &c
\end{pmatrix}}^{k-1}
{\begin{pmatrix}
1\\
1
\end{pmatrix}}
$$

说的很乱很乱,也跑到论坛上面去问,发现讨论的东西和一开始想的也差不太多,给个链接,供参考。