29 条题解
-
1
Goodhao LV 10 @ 7 年前
-
010 年前@
其实这道题不用转矩阵这么麻烦,矩阵的规律推起来不容易。
我用的是直接算的方法,虽然代码很长,但实际上条理性强,十分易懂。
每次搜索时寻找一个像/\一样的平行四边形的一角,分别往左右两边扩展,一旦有转向必须停止,向另一个方向扩展,直到再次遇到一个反向的。
扩展时记录每条边的长度,因为平行四边形两条对边相等,所以这里可以做一个判断。
然后再搜索平行四边形内的字符是否都为空格,这个可以做一个1-->len1+len2(平行四边形两条邻边之和)的循环,模拟同一行平行四边形的最左点和最右点,检查[left+1..right-1]区间内的字符即可。测试数据 #0: Accepted, time = 0 ms, mem = 3692 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 3692 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 3692 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 3692 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 3696 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 3692 KiB, score = 10
测试数据 #6: Accepted, time = 46 ms, mem = 3696 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 3692 KiB, score = 10
测试数据 #8: Accepted, time = 109 ms, mem = 3696 KiB, score = 10
测试数据 #9: Accepted, time = 140 ms, mem = 3692 KiB, score = 10
Accepted, time = 371 ms, mem = 3696 KiB, score = 100
虽然效率不是非常快,但结果还是很可观的。以下为关键部分伪代码
这是扩展的伪代码
if pic[x+1,y]='\' then
trun_right
else
inc(x)
dec(y)TRUN_RIGHT
if pic[x,y+1]='/' then
STOP
else
inc(x)
inc(y)这是检查部分的伪代码
len1=length of first '/'
len2=length of first '\'
x=position of '/'
y=position of '\'
i:1-->len1+len2
{
go_left&down(x){i<len1}
go_right&down(y){i<len2}
go_right&down(x){i>=len1}
go_left&down(y){i>=len2}
j:x+1-->y-1
char=' '
}
注意,在扩展时,若遇到空格,即可判断为不合法。
在此Orz一下各位大神。 -
015 年前@
发现tky的题都很不错啊
-
015 年前@
floodfill……
ac 235! -
016 年前@
没转矩形果然累,不过蛮练代码能力的,最后cheat了一个数据。。。死活过不了
-
016 年前@
前2次交都0分。。
-
016 年前@
oibh上有
标程用的只是扫描……不是floodfill -
016 年前@
请问有没有标程可以提供
-
016 年前@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 41ms
├ 测试数据 10:答案正确... 56ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:97ms
数组开大啊!!!要1..2000,1..2000啊!
最后判断是不是矩形的时候只要把它连着的都填满,然后判断在这个被填满的里面有没有存在边 -
016 年前@
ansistring...
longint...白交兩次,而且每一次都是交給抽風狀態的DRAGON.
人品問題。 -
016 年前@
for i:=1 to n do
for j:=2 to n do
if ch='/' then
begin
b:=true;b:=true;
end;
for i:=2 to n do
for j:=1 to n do
if ch='\' then
begin
b:=true;b:=true;
end;
这是我的转换公式~~~ -
016 年前@
第一步:转矩形。。。虽然有不少大牛说不转矩形也可以做,但是我还是建议转矩形再做,因为转化不是很复杂,转成矩形做起来更直观。。。
第二步:染色。。。先把可以连通的所有方块染成一色,判断是否是矩形可以在后面做。。1遍DFS遍历搞定。。。顺便记录下每种颜色的方块数S和这种颜色的方块的MINX,MAXX,MINY,MAXY,X,Y指坐标,这个在后边判矩形有用。
第三步:判断是否构成矩形。。。先一步(MAXX-MINX+1)*(MAXY-MINY+1)=S粗略的判断是否构成矩形,可以证明不满足上式肯定不能构成矩形。
接着判断在该颜色的方块阵,有没有不该有的分界,
比如 _ _
| | |
|_ | 在这个方块阵中虽然都是同色,但他有不该有的分界,所有不能构成矩形....
三步的空间复杂度都是O(N^2)的,所以不会超时....这年头想一遍过的也只有这样的题了...-- -
016 年前@
for i:=0 to n do
for j:=1 to n do
f[2*i+1,2*j]:=f[2*i+1,2*j-2]+ord(w[2*i+1,2*j]='-');
for i:=1 to n do
for j:=0 to n do
f[2*i,2*j+1]:=f[2*i,2*j-1]+ord(w[2*i,2*j+1]='|');我的转换公式- -
就好象是模拟题一样..
-
016 年前@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 9ms
├ 测试数据 09:答案正确... 72ms
├ 测试数据 10:答案正确... 72ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:153ms第一遍提交全超时,同样程序第二遍提交AC
卧槽泥马勒戈壁呀 -
016 年前@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 25ms
├ 测试数据 08:答案正确... 103ms
├ 测试数据 09:答案正确... 181ms
├ 测试数据 10:答案正确... 228ms
————————————————————
很慢,搜之前预处理一个点到左上和右上的‘/' '\'数目,然后搜起来用 -
016 年前@
编译通过...
├ 测试数据 01:答案错误... ├ 标准行输出
├ 错误行输出
├ 测试数据 02:答案错误...程序输出比正确答案长
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案错误... ├ 标准行输出
├ 错误行输出
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案错误... ├ 标准行输出
├ 错误行输出
├ 测试数据 07:答案错误... ├ 标准行输出
├ 错误行输出
├ 测试数据 08:答案错误... ├ 标准行输出
├ 错误行输出
├ 测试数据 09:答案错误... ├ 标准行输出
├ 错误行输出
├ 测试数据 10:答案错误... ├ 标准行输出
├ 错误行输出
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分:20 有效耗时:0ms为什么???
-
016 年前@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 41ms
├ 测试数据 09:答案正确... 56ms
├ 测试数据 10:答案正确... 103ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:200ms -
016 年前@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 181ms
├ 测试数据 08:答案正确... 555ms
├ 测试数据 09:答案正确... 664ms
├ 测试数据 10:答案正确... 805ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:2205ms好险。。。
-
016 年前@
对于一个有k个方块的连通块,它是矩形当且仅当
(max{x} - min{x}) * (max{y} - min{y}) = k
这样简便些 -
016 年前@
用4位2进制数表示4个方向上是否有边