25 条题解
-
0
asd7160 LV 8 @ 2009-11-10 17:24:47
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms把一个排列看成一个矩阵，横坐标表示第i个数，纵坐标表示这个数在哪一个位置
那么b[i]表示的就是以(i,i)点为右下角以(1,1)点为左上角的矩形中1的个数
而b[i]-b表示的是一个'L'字形中1的个数，我们可以把矩阵拆成n个'L'字形
对于第i层:
若b[i]-b=0，ans=ans 此层不必考虑
若b[i]-b=1，这层本来有2*i-1个位置可以放'1' ,由于内层已经放了b个互不冲突的'1'，当前层必然减少了2*b个位置（之前的每个'1'在横行、纵行的方向使当前层的一个位置不可行），所以递推式:
ans=ans*(2*i-1-2*b)
若b[i]-b=2，则这两个必在'L'的两条臂上（大概没有人会不明白这点吧），同理，每条臂上剩余的位置个数都是i-1-b，i-1是臂长（不包括交点），之前的每个'1'使两条臂不可行的位置各增加1，所以递推式
ans=ans*(i-1-b)^2小弟不才,写的比较多了...
var n,i,j:longint;
x,y:int64;
b:array[0..2000] of integer;
ans:array[0..1000] of int64;
begin
readln(n);
for i:=1 to n do read(b[i]);
ans[0]:=1; ans[1]:=1;
for i:=1 to n do
begin
if b[i]-b=0 then continue;
if b[i]-b=1 then
begin
x:=0; y:=2*i-1-2*b;
for j:=1 to ans[0] do
begin
x:=x+ans[j]*y;
ans[j]:=x mod 1000000;
x:=x div 1000000;
end;
while x>0 do
begin
inc(ans[0]);
ans[ans[0]]:=x mod 1000000;
x:=x div 1000000;
end;
end;
if b[i]-b=2 then
begin
x:=0; y:=sqr((i-1-b));
for j:=1 to ans[0] do
begin
x:=x+ans[j]*y;
ans[j]:=x mod 1000000;
x:=x div 1000000;
end;
while x>0 do
begin
inc(ans[0]);
ans[ans[0]]:=x mod 1000000;
x:=x div 1000000;
end;
end;
end;
write(ans[ans[0]]);
for i:=ans[0]-1 downto 1 do
begin
if ans[i] -
0
推递推式的那个矩阵用的很不错
http://hi.baidu.com/qyjubriskxp/blog/item/ab51f40181cb927d3812bb71.html
很不错！！ -
0
yzl609271536 LV 10 @ 2009-10-05 15:40:59
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 88ms
├ 测试数据 08：答案正确... 212ms
├ 测试数据 09：答案正确... 212ms
├ 测试数据 10：答案正确... 197ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：709ms我没压位 。。。
但是 WA了 3次 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms矩形那个 很不错的转化！
-
0
压万位就爆3点，压千位就全过，晕
递推式在这
http://user.qzone.qq.com/281130306/infocenter?ptlang=2052 -
0
zhouliecheng LV 10 @ 2009-10-04 15:27:48
呃...因为一段高精交了4遍10分....好伤心啊...TAT
-
0
感谢qyjubriskxp神牛的帮助
不懂的都可以去看看他的题解http://hi.baidu.com/qyjubriskxp/blog/item/ab51f40181cb927d3812bb71.html
-
0
orz教主_tangky LV 7 @ 2009-10-04 09:11:13
你至少可以算出答案不会超过N!也就是5735位
-
0
qyjubriskxp LV 10 @ 2009-10-04 03:12:15
为了ac这题我付出了9次提交的代价，ac率下降1%，T-T（伤心ing....）
总结一下
想算法花去了n个小时，徘徊在正确算法的边缘，就是无法突破
突然给我想到了，于是提交，30分，数据范围问题
于是用double，输出指数，看看结果有多少位，结果double爆掉了（~汗）
再看看int64能否蒙混过关，30分
只好写高精，因为时间太晚，打错了一个地方，0分
找到错误，再交70分，提示我的输出出现了负数
以为是位数的问题，狠加位数n次，直至有一次不能分配足够的静态内存了，明白问题不在这里
我没专门学过高精，这题挑战了我一贯的写法，我只好对一个long的数组由压万位变成压千位，终于ac了啊！！！
实在被这题打败的牛们可以看看我的解题报告
http://hi.baidu.com/qyjubriskxp/blog/item/ab51f40181cb927d3812bb71.html -
0
xiedong1993 LV 8 @ 2009-10-03 09:07:48
我也邪恶一下~~
飘过…………
asd7160
LV 8
@ 2009-11-10 17:24:47
