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}}
$$
说的很乱很乱，也跑到论坛上面去问,发现讨论的东西和一开始想的也差不太多，给个链接，供参考。