题解 - Vijos

0

tjc LV 9 @ 2009-03-22 11:14:54

program jumping_sol1;

const

maxn = 102;

maxm = 63;

cinc : array[1..4, 1..2] of longint =

((-1, 0), (0, 1), (1, 0), (0, -1));

type

_string = string[maxm];

coortype = record

x, y : longint;

end;

var

n, m, time, moder, points : longint;

period, left : longint;

a, _a, standard : array[0..maxn, 0..maxn] of longint;

order : array[0..maxn, 0..maxn] of _string;

transfer, last : array[0..maxn, 0..maxn] of coortype;

depth : array[0..maxn, 0..maxn] of longint;

turn : array[0..maxn, 0..maxn] of longint;

nowturn : longint;

function destination(stx, sty : longint) : coortype;

var

r : coortype;

i : longint;

BEGIN

if (stx = 0) or (sty = 0) or (stx = n+1) or (sty = m+1) then

BEGIN

r.x := stx;

r.y := sty;

exit(r);

END;

r.x := stx;

r.y := sty;

for i := 1 to maxm do

BEGIN

case order[r.x][r.y][i] of

'U': begin r.x := r.x + cinc[1][1]; r.y := r.y + cinc[1][2]; end;

'R': begin r.x := r.x + cinc[2][1]; r.y := r.y + cinc[2][2]; end;

'D': begin r.x := r.x + cinc[3][1]; r.y := r.y + cinc[3][2]; end;

'L': begin r.x := r.x + cinc[4][1]; r.y := r.y + cinc[4][2]; end;

end;

END;

exit(r);

END;

procedure act(thistime : longint);

var

i, j, k, t : longint;

BEGIN

for i := 1 to thistime do

BEGIN

for j := 1 to n do

for k := 1 to m do

BEGIN

_a[j][k] := a[j][k];

a[j][k] := 0;

END;

for j := 1 to n do

for k := 1 to m do

BEGIN

case order[j][k][i] of

'C': a[j][k] := (a[j][k] + _a[j][k] + 1) mod moder;

'U': a[j+cinc[1][1]][k+cinc[1][2]] := (a[j+cinc[1][1]][k+cinc[1][2]] + _a[j][k]) mod moder;

'R': a[j+cinc[2][1]][k+cinc[2][2]] := (a[j+cinc[2][1]][k+cinc[2][2]] + _a[j][k]) mod moder;

'D': a[j+cinc[3][1]][k+cinc[3][2]] := (a[j+cinc[3][1]][k+cinc[3][2]] + _a[j][k]) mod moder;

'L': a[j+cinc[4][1]][k+cinc[4][2]] := (a[j+cinc[4][1]][k+cinc[4][2]] + _a[j][k]) mod moder;

end;

END;

END;

END;

procedure doit(stx, sty : longint);

var

i, j, k, t : longint;

tt, ttt, addto : longint;

ttaddto : int64;

nowtime : longint;

csx, csy : longint;

sum : longint;

BEGIN

addto := standard[stx][sty];

i := stx; j := sty;

turn[i][j] := nowturn;

depth[i][j] := 1;

a[i][j] := (a[i][j] + addto) mod moder;

nowtime := period-1;

while nowtime > 0 do

BEGIN

k := transfer[i][j].x; t := transfer[i][j].y;

if turn[k][t] = nowturn then break;

turn[k][t] := nowturn;

depth[k][t] := depth[i][j] + 1;

nowtime := nowtime - 1;

a[k][t] := (a[k][t] + addto) mod moder;

i := k; j := t;

END;

if nowtime = 0 then exit;

csx := k; csy := t;

sum := depth[i][j] - depth[k][t] + 1;

tt := nowtime div sum;

ttt := nowtime mod sum;

ttaddto := tt;

ttaddto := ttaddto * addto;

i := csx;

j := csy;

repeat

a[i][j] := (a[i][j] + ttaddto) mod moder;

if ttt > 0 then

BEGIN

a[i][j] := (a[i][j] + addto) mod moder;

ttt := ttt - 1;

END

else if tt = 0 then break;

k := transfer[i][j].x; t := transfer[i][j].y;

i := k; j := t;

until (i = csx) and (j = csy);

END;

procedure print_exit;

var i, j, k : longint;

t : int64;

BEGIN

for i := 1 to n do

for j := 1 to m do

if a[i][j] > 0 then

BEGIN

t := a[i][j];

t := t * points mod moder;

a[i][j] := t;

END;

for i := 1 to n do

BEGIN

j := 1;

while j 0 then

BEGIN

nowturn := nowturn + 1;

doit(i, j);

END;

act(left);

print_exit;

END.

嘿嘿

0

海燕 LV 3 @ 2008-11-10 21:03:30

爽!太爽了!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

用的是和标程不一样的算法, 居然AC……

基本思想:先做出63秒钟之后各点的转出目的点已经每个点新增水滴的情况，根据周期性，以后的时间按照63秒为周期必然作出相同的转移与增加方式。

根据转出目的点情况，我们得到一张有向图，这张有向图上一个顶点有且仅有一个出度；根据进一步的分析我们不难得出，每一个周期增加新水滴的过程实际上就是对这个图从一个顶点出发作的一次遍历；由于该图特殊的“基环+外向树”结构，我们在遍历不久之后就会遇到一个环，这个时候，将总周期书对环的长度取模，然后用乘法得到环上应加的数据（此时之后所有的新水滴就只会周期性地落在环上了），这就起到了加速的目的。

这种算法巧妙地利用到了标程并没有利用到的性质：具有C的水滴的个子只有30个。这样，63秒之后具有水滴的格子也就是1000~2000个（最最多这么多），远小于10000的总格子数，这样算法的时间复杂度为O(NMK)，K是63秒后具有水滴的格子数。由于数据并不是很强，所有这个算法超炫地AC

//Time complexity: O(NMK), K is the number of areas which have waters on it after 63 seconds (K 0 do

BEGIN

k := transfer[i][j].x; t := transfer[i][j].y;

if turn[k][t] = nowturn then break;

turn[k][t] := nowturn;

depth[k][t] := depth[i][j] + 1;

nowtime := nowtime - 1;

a[k][t] := (a[k][t] + addto) mod moder;

i := k; j := t;

END;

if nowtime = 0 then exit;

csx := k; csy := t;

sum := depth[i][j] - depth[k][t] + 1;

tt := nowtime div sum;

ttt := nowtime mod sum;

ttaddto := tt;

ttaddto := ttaddto * addto;

i := csx;

j := csy;

repeat

a[i][j] := (a[i][j] + ttaddto) mod moder;

if ttt > 0 then

BEGIN

a[i][j] := (a[i][j] + addto) mod moder;

ttt := ttt - 1;

END

else if tt = 0 then break;

k := transfer[i][j].x; t := transfer[i][j].y;

i := k; j := t;

until (i = csx) and (j = csy);

END;

procedure print_exit;

var

i, j, k : longint;

t : int64;

BEGIN

for i := 1 to n do

for j := 1 to m do

if a[i][j] > 0 then

BEGIN

t := a[i][j];

t := t * points mod moder;

a[i][j] := t;

END;

for i := 1 to n do

BEGIN

j := 1;

while j 0 then

BEGIN

nowturn := nowturn + 1;

doit(i, j);

END;

act(left);

print_exit;

END.

-1

orz教主_boboo LV 3 @ 2008-11-09 13:58:27

占楼只会60分的。

-1

k103701 LV 10 @ 2008-11-09 13:30:06

第4题 ---|---|---|---|---|---|---|---|---|---|---|--

编译通过...

测试数据01：答案正确... 0ms

测试数据02：答案正确... 0ms

测试数据03：答案正确... 0ms

测试数据04：答案正确... 0ms

测试数据05：答案正确... 0ms

测试数据06：答案正确... 0ms

测试数据07：运行超时...

测试数据08：运行超时...

测试数据09：运行超时...

测试数据10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：60 有效耗时：0ms