2014
02-23

# Collapse!!

Candy and his friends found a treasure map. With the help of the map, they successfully found the treasure inside an ancient cave, but just as they took the large treasure box, the cave started to collapse! Candy must find a way out, but the rocks are falling down so quickly that it’s impossible to run out with bare feet. After carefully examined the treasure box, they found a digit panel, a button, and a small piece of paper. "I am not an ordinary treasure box, I am a mini-spaceship, your last hope to escape. Use the digit panel to setup my speed, then press the button to launch. I’ll fly from left to right, until I reach the exit. The trouble is: I am very weak. I’ll explode immediately when hit by any falling rock, but if I’m just touching one, it’s ok. When flying, I burn the treasures inside. The higher my speed is, the more treasures I will burn. Thus, be sure to find an appropriate speed before starting your journey. The last thing you need to know is: don’t be too slow. The exit will be blocked after a while."

Fig 1. Collision between the spaceship and a rock A list of rocks that will fall down is enclosed in that piece of paper. All the rocks have the same speed. Each rock continues to fall down until its topmost point reaches the land (i.e. y = 0).You can start your journey at any time, but once you launch the spaceship, it never stops before reaching the exit or being destroyed!
Write a program to find the minimal speed that takes you out of the cave.

The input contains several test cases. The first line of each case contains seven positive integers n, a, b, L, H, V, T (1 ≤ n ≤ 50, 1 ≤ a, b ≤ 10, 1 ≤ L, H, V, T ≤ 10000). The spaceship is a units wide and b units high. Its bottom-left corner is initially (i.e. at time 0) at (0, 0). When the bottom-left corner reaches (L, 0) before time T, you succeeded. The height of the cave is H. The speed of each rock is V. There are n lines followed. Each of these lines contains three integers x, r, t (1 ≤ t ≤ T, 1 ≤ r ≤ 200, a + r ≤ x ≤ L – r, b < H – r): at time t, there will be a falling rock with a radius of r with its center at (x, H). The descriptions of rocks are sorted in increasing order of falling time. The last test case is followed by a single zero, which should not be processed.

The input contains several test cases. The first line of each case contains seven positive integers n, a, b, L, H, V, T (1 ≤ n ≤ 50, 1 ≤ a, b ≤ 10, 1 ≤ L, H, V, T ≤ 10000). The spaceship is a units wide and b units high. Its bottom-left corner is initially (i.e. at time 0) at (0, 0). When the bottom-left corner reaches (L, 0) before time T, you succeeded. The height of the cave is H. The speed of each rock is V. There are n lines followed. Each of these lines contains three integers x, r, t (1 ≤ t ≤ T, 1 ≤ r ≤ 200, a + r ≤ x ≤ L – r, b < H – r): at time t, there will be a falling rock with a radius of r with its center at (x, H). The descriptions of rocks are sorted in increasing order of falling time. The last test case is followed by a single zero, which should not be processed.

1 2 1 20 12 3 20
5 2 5
0

Case 1: 1.00

a,b,c,d的顺序为项数的从低到高。

A= [0 1 0

0 0 1

1 0 2],

B = [f[0]

f[1]

f[2]]

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define max 3
struct Matrix
{
int data[max][max];
};

Matrix A,B;
int n = 3;
int mod = 2010;

void init()
{
memset(A.data,0,sizeof(A.data));
memset(B.data,0,sizeof(B.data));
A.data[0][1] = 1;
A.data[1][2] = 1;
A.data[2][0] = 1;
A.data[2][2] = 2;
B.data[0][0] = 1;
B.data[1][0] = 1;
B.data[2][0] = 2;
}
//矩阵相乘
Matrix mul(Matrix u,Matrix v)
{
Matrix t;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
t.data[i][j] = 0;
for(int k=0;k<n;k++)
{
t.data[i][j] += (u.data[i][k] * v.data[k][j])%mod;
t.data[i][j] %= mod;
}
}
}
return t;
}
//矩阵的幂
Matrix power(Matrix matrix,int k)
{
int k_temp = k;
Matrix result,a;

memset(result.data,0,sizeof(result.data));

for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
a.data[i][j] = matrix.data[i][j];
if(i == j)
{
result.data[i][j] = 1;
}
//printf("%d ",a.data[i][j]);
}
//printf("\n");
}
while(k_temp)
{
if(k_temp&1)
{
result = mul(result,a);
}
a = mul(a,a);
k_temp = k_temp>>1;
}
return result;

}

int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int num;
init();
while(scanf(" %d",&num)!=EOF)
{
if(num == 1) printf("1\n");
else if(num == 2) printf("2\n");
else
{
Matrix temp = power(A,num - 2);
Matrix fin = mul(temp,B);
printf("%d\n",fin.data[2][0]);
}
}
return 0;
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。

3. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。