2003集训队100道讨论题

IOI2003中国国家集训队难题活

0052金陵中学在一个无限的棋盘上有一个超级马，它可以进行n种动作。每一种动作都是通过两个整数来确定——第一个数说明列的数xi（正数向右，负数向左），第二个数说明行的数yi（正数向上，负数向下），得到了3个算法，分别是数学方法、搜索算法和迭代算法。搜索算法中有，而数学方法到目前为时间复杂度分别是O(n2)、O(2012*n)、O(2014*k)，空间复杂度分别是O(n)、O(2012)、O(2012)。感谢同学提出数学方法，并搜索算法的错误首先进行一个转化工作：一个超级遍历整个棋盘，等价于“一个超级马可以通过一种或几种动作x1*k1x2*k2xn*kny*ky*ky*k 但是，很快能够发现，这些转化工作似乎一点也没有降低题目的难度，还是令人毫无头绪。如果a2*k2+…+am-1*km-1+am+1*km+1+…+an*kn=c。对于这个方程，能够确定，当以下情况发生时，方程(a1,a2,…,am-1,am+1,…,an)c的约数。这如果不定方程a1*k1a2*k2am-1*km-1am+1*km+1an*kn=c不存在非负整数解，那么不定方程因此，可以将每个ki各消去一次，看看得出的不定方程是否有非负整数解，如果其中一个或不止POI2002的所有测试数据。这使我感觉到，这个条件也许就是充要条件，但是我一直题目界定了xi、yi的范围是[-100,100]，也就是说，从（0,0）出发，经过一步运动可以到达的区域这个想法（以下称为“算法2”），可以通过一个BFS来实现。但问题就在于，题目中规定，“棋盘2的主要问题就在于，人为限定了一个棋盘的大小范围，违背了为向量的R如果一个向量的R类序列SS中必然存在至少一对方向相反的向aba+bS1R类序列。同样，S1也一定满足上述性质，因此可以这样循环往复下去，直到得到一个只有1个向量的RSm，仅存的向2似乎也有类似的思想在其中：因为运动的先后顺序对最后的运动结果没有任何影响，因此如果位置”方向相反的向量，与之合并以后，再进行刚才需要进行的运动即可（2）。这时，发现了其中的，可以保证R类序列中至少存在一对方向相反的向量，但是并不能保证在这几对向量中一定包含了序列的第一个向量。这样就可能出现R类序列无法继续缩小的情况，虽说算法2错误了，但是在分析它的时候，得到了R类序列的一些性质，根据这些性质，可以4个象限中（3，蓝由于R类序列性质的保证，这个迭代算法是正确的。因为每个向量都只会和它方向相反的向量合并，因此，所有得到的向量都在(-100..100,-100..100)2012个向量。所以，这种迭代的时间复杂度是O(k*2014)，k是一个和输入数据有关的量。就肯定不能遍历棋盘。如果算法1和迭代算法合起来，就可以得到一个新的算法（算法1将绝大部分的”NIE”的情况（其实从目前来看，是所有”NIE”情况）都判定出来，因此留给迭代算法需要0.05秒能够出解。123456789300034011234567891011>11在测试的时候，发现，程序的快慢与超级马的动作总数n没有太大