题解 - Vijos

1

Goodhao LV 10 @ 2017-09-25 12:39:57

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
 
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
 
typedef long long ll;

const int inf=0x3f3f3f3f;
const ll linf=1e18;
const int N=1000+10;

int n;
bool gr[N][N],gc[N][N];
pi fr[N][N],fc[N][N];
int sr[N][N],sc[N][N];
int sumr[N][N],sumc[N][N];
int ans;
int qr(int x1,int y1,int x2,int y2) {
    return sumr[x2][y2]+sumr[x1-1][y1-1]-sumr[x1-1][y2]-sumr[x2][y1-1];
}
int qc(int x1,int y1,int x2,int y2) {
    return sumc[x2][y2]+sumc[x1-1][y1-1]-sumc[x1-1][y2]-sumc[x2][y1-1];
}
bool check(int x,int y) {
    if (!gc[x][y]) return 0;
    if (!gr[x][y]) return 0;
    pi a=fr[x][y],b=fc[x][y];
    int len1=b.fi-x+1,len2=a.se-y+1;
    if (sc[x+len1-1][y]-sc[x-1][y]==len1&&
        sr[x][y+len2-1]-sr[x][y-1]==len2&&
        sc[x+len1-1][y+len2]-sc[x-1][y+len2]==len1&&
        sr[x+len1][y+len2-1]-sr[x+len1][y-1]==len2) {
        if (qc(x,y,x+len1-1,y+len2)+qr(x,y,x+len1,y+len2-1)==2*(len1+len2)) {
            return 1;
        }
    }
    return 0;
}
int main() {
 
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //freopen("in.txt","r",stdin);
    cin>>n;
    FOR(i,2*n) {
        int cnt1=0,cnt2=0;
        int flag=-1;
        FOR(j,2*n) {
            char t='\n';
            while (t=='\n') cin.get(t);
            if (i<=n) {
                if ((flag==-1)&&(t=='/'||t=='\\')) {
                    flag=j%2;
                }
                if (flag==j%2) cnt1++;
                if (flag!=-1&&flag!=j%2) cnt2++;
                if (t=='/') {
                    gc[i-(cnt1-1)][1+(cnt1-1)]=1;
                } else if (t=='\\') {
                    gr[i-(cnt2-1)][1+(cnt2-1)]=1;
                }
            } else {
                if ((flag==-1)&&(t=='/'||t=='\\')) {
                    flag=j%2;
                }
                if (flag==j%2) cnt2++;// notice here is cnt2
                if (flag!=-1&&flag!=j%2) cnt1++;
                if (t=='/') {
                    gc[(n+1)-(cnt1-1)-1][i-n+(cnt1-1)+1]=1;
                } else if (t=='\\') {
                    gr[(n+1)-(cnt2-1)][i-n+(cnt2-1)]=1;
                }
            }
        }
    }

    /*
    FOR(i,n) FOR(j,n+1) if (gc[i][j]) cout<<"("<<i<<","<<j<<")"<<" ";
    cout<<endl;
    FOR(i,n+1) FOR(j,n) if (gr[i][j]) cout<<"("<<i<<","<<j<<")"<<" ";
    cout<<endl;
    */

    FOR(j,n+1) for (int i=n;i>=1;i--) {
        if (i<n) fc[i][j]=fc[i+1][j];
        if (!gc[i][j]) fc[i][j]=mp(0,0);
        else if (gr[i+1][j]||fc[i][j]==mp(0,0)) fc[i][j]=mp(i,j);
    }
    FOR(i,n+1) for (int j=n;j>=1;j--) {
        if (j<n) fr[i][j]=fr[i][j+1];
        if (!gr[i][j]) fr[i][j]=mp(0,0);
        else if (gc[i][j+1]||fr[i][j]==mp(0,0)) fr[i][j]=mp(i,j);
    }
    FOR(i,n+1) FOR(j,n) sr[i][j]=sr[i][j-1]+(gr[i][j]>0);
    FOR(j,n+1) FOR(i,n) sc[i][j]=sc[i-1][j]+(gc[i][j]>0);
    FOR(i,n+1) FOR(j,n) sumr[i][j]=sumr[i-1][j]+sr[i][j];
    FOR(j,n+1) FOR(i,n) sumc[i][j]=sumc[i][j-1]+sc[i][j];
    FOR(i,n) FOR(j,n+1) if (check(i,j)) {
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

0

caiziyi LV 8 @ 2014-07-17 21:46:08

其实这道题不用转矩阵这么麻烦，矩阵的规律推起来不容易。
我用的是直接算的方法，虽然代码很长，但实际上条理性强，十分易懂。
每次搜索时寻找一个像/\一样的平行四边形的一角，分别往左右两边扩展，一旦有转向必须停止，向另一个方向扩展，直到再次遇到一个反向的。
扩展时记录每条边的长度，因为平行四边形两条对边相等，所以这里可以做一个判断。
然后再搜索平行四边形内的字符是否都为空格，这个可以做一个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一下各位大神。

0

jacklv LV 10 @ 2009-11-06 16:14:14

发现tky的题都很不错啊

0

lirenjue LV 10 @ 2009-06-27 18:10:17

floodfill……

ac 235！

0

hfl LV 8 @ 2008-11-12 10:10:29

没转矩形果然累,不过蛮练代码能力的，最后cheat了一个数据。。。死活过不了

0

fengyi LV 9 @ 2008-11-10 19:07:42

前2次交都0分。。

0

orz教主_tangky LV 7 @ 2008-11-08 17:48:02

oibh上有

标程用的只是扫描……不是floodfill

0

msy LV 6 @ 2008-11-08 16:01:16

请问有没有标程可以提供

0

graylucky LV 10 @ 2008-11-07 20:33:32

编译通过...

├ 测试数据 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啊！

最后判断是不是矩形的时候只要把它连着的都填满，然后判断在这个被填满的里面有没有存在边

0

Fv.Cyc LV 3 @ 2008-11-07 19:40:17

ansistring...

longint...

白交兩次，而且每一次都是交給抽風狀態的DRAGON.

人品問題。

0

greatfall LV 3 @ 2008-10-31 08:50:18

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;

这是我的转换公式~~~

0

voyagec2 LV 10 @ 2008-10-27 20:00:29

第一步：转矩形。。。虽然有不少大牛说不转矩形也可以做，但是我还是建议转矩形再做，因为转化不是很复杂，转成矩形做起来更直观。。。

第二步：染色。。。先把可以连通的所有方块染成一色，判断是否是矩形可以在后面做。。1遍DFS遍历搞定。。。顺便记录下每种颜色的方块数S和这种颜色的方块的MINX，MAXX，MINY，MAXY，X，Y指坐标，这个在后边判矩形有用。

第三步：判断是否构成矩形。。。先一步（MAXX-MINX+1）*（MAXY-MINY+1）=S粗略的判断是否构成矩形，可以证明不满足上式肯定不能构成矩形。

接着判断在该颜色的方块阵，有没有不该有的分界，

比如 _ _

| | |

|_ | 在这个方块阵中虽然都是同色,但他有不该有的分界,所有不能构成矩形....

三步的空间复杂度都是O(N^2)的,所以不会超时....这年头想一遍过的也只有这样的题了...--

0

梦ぁ逍遥 LV 5 @ 2008-10-23 00:06:56

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]='|');

我的转换公式- -

就好象是模拟题一样..

0

cx24 LV 6 @ 2008-10-22 10:02:00

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

第一遍提交全超时，同样程序第二遍提交AC

卧槽泥马勒戈壁呀

0

duzeyu LV 3 @ 2008-10-22 08:03:15

编译通过...

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

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

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

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

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

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

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

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

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

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

————————————————————

很慢，搜之前预处理一个点到左上和右上的‘/' '\'数目，然后搜起来用

0

lmgood LV 7 @ 2008-10-21 19:15:56

编译通过...

├ 测试数据 01：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 02：答案错误...程序输出比正确答案长

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

├ 测试数据 04：答案错误...　├ 标准行输出

　├ 错误行输出

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

├ 测试数据 06：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 08：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 09：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 10：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

为什么???

0

LV 0 @ 2008-10-21 13:01:12

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

shelley LV 3 @ 2008-10-20 20:33:20

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

好险。。。

0

mt LV 8 @ 2008-10-20 13:48:32

对于一个有k个方块的连通块，它是矩形当且仅当

(max{x} - min{x}) * (max{y} - min{y}) = k

这样简便些

0

yuhc LV 10 @ 2008-10-20 12:41:16

用4位2进制数表示4个方向上是否有边

题解

29 条题解

菱形内的计数

信息

状态

开发

支持

题解

29 条题解

菱形内的计数

信息

状态

开发

支持

还没有账户？

登录