题解 - Vijos

4

PowderHan LV 10 @ 2017-05-07 12:48:35

/*
好题啊~一个经典的并查集问题~
黑书上是有哒P275
讲一下大概的思路叭
抽象成图
网格交叉点：顶点
正面的线：正边
背面的线：负边
有边相连：连通块
每个连通块分别求
对于某个顶点i
|正边数-负边数|=K>0时
以该顶点为开始或结束的针数>=K
可以恰好为K针
所有K值加起来，除以2（每一针有两个端点）
注意差值为0时，为1针而不是0针
所以直接处理一下就好啦~
细节需要注意OTZ
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=202;
int in[MAXN*MAXN];
int fa[MAXN*MAXN];
int b[MAXN*MAXN];
int c[MAXN*MAXN];
int p[MAXN*MAXN];
bool v[MAXN*MAXN];
char g[2][MAXN][MAXN];
int ans,l;
int n,m;

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

void init()
{
    cin>>n>>m;
    for(int k=0;k<2;k++)
        for(int i=0;i<n;i++)
            scanf("%s",g[k][i]);
    for(int i=0;i<=(n+1)*(m+1);i++)
        fa[i]=i;
}

void getg()
{
    for(int k=0;k<2;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                if(g[k][i][j]=='\\'||g[k][i][j]=='X')
                {
                    int x=i*(m+1)+j;    int y=(i+1)*(m+1)+j+1;
                    int fx=find(x); int fy=find(y);
                    if(fx!=fy)
                        fa[fy]=fx;
                    in[x]+=(-k*2)+1;    in[y]+=(-k*2)+1;
                    v[x]=v[y]=1;
                }
                if(g[k][i][j]=='/'||g[k][i][j]=='X')
                {
                    int x=i*(m+1)+j+1;  int y=(i+1)*(m+1)+j;
                    int fx=find(x); int fy=find(y);
                    if(fx!=fy)
                        fa[fy]=fx;
                    in[x]+=(-k*2)+1;    in[y]+=(-k*2)+1;
                    v[x]=v[y]=1;
                }
            }
}

void work()
{
    for(int i=0;i<(n+1)*(m+1);i++)
    {
        if(!v[i])   continue;
        int k=find(i);
        if(!p[k]){p[k]=1;c[++l]=k;}
        b[k]+=abs(in[i]);
    }
    for(int i=1;i<=l;i++)
        if(!b[c[i]])
            ans++;
        else
            ans+=b[c[i]]/2;
    cout<<ans<<endl;
}

int main()
{
    init();
    getg();
    work();
    return 0;
}

1

aph。 (chenqianrong) LV 10 @ 2021-08-22 18:08:37

#include<bits/stdc++.h>
using namespace std;

bool v[50010];
long long n,m,father[50010],indegree[50010],p[50010],c[50010],l,b[50010],ans,x,y,f1,f2,k;
char a[5][310][310];

int searchfather(int v){
    if(father[v]==v)
        return father[v];
    father[v]=searchfather(father[v]);
    return father[v];
}

int main(){
    cin>>n>>m;
    getchar();
    for(int k=0; k<2; k++)
        for(int i=0; i<n; i++)
            cin>>a[k][i];
    for(int i=0; i<=n*m+n+m+1; i++)
        father[i]=i;
    for(int k=0; k<2; k++){
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(a[k][i][j]=='\\'||a[k][i][j]=='X'){
                    x=i*(m+1)+j,y=(i+1)*(m+1)+j+1;
                    f1=searchfather(x),f2=searchfather(y);
                    if(father[f1]!=f2)
                        father[f1]=f2;
                    indegree[x]+=(-k)*2+1;
                    indegree[y]+=(-k)*2+1;
                    v[x]=v[y]=1;
                }
                if(a[k][i][j]=='/'||a[k][i][j]=='X'){
                    x=i*(m+1)+j+1,y=(i+1)*(m+1)+j;
                    f1=searchfather(x),f2=searchfather(y);
                    if(father[f1]!=f2)
                        father[f1]=f2;
                    indegree[x]+=(-k)*2+1;
                    indegree[y]+=(-k)*2+1;
                    v[x]=v[y]=1;
                }
            }
        }
    }
    for(int i=0; i<n*m+n+m+1; i++){
        if(v[i]==0)
            continue;
        k=searchfather(i);
        if(p[k]==0){
            p[k]=1;
            c[++l]=k;
        }
        b[k]+=abs(indegree[i]);
    }
    for(int i=1; i<=l; i++){
        if(b[c[i]]==0)
            ans++;
        else
            ans+=b[c[i]]/2;
    }
    cout<<ans;
    return 0;
}

1

xukuan LV 7 @ 2018-11-07 11:01:49

思路与@PowderHan 大佬大致相同，在此补充一些坑点：

1.(200+1)*(200+1)最大可以达到4w+，数组不要开小了

2.'\'是转义字符，'\ \'才是右斜杠（仅限c++，pascal不存在这个问题）

其他也就没什么了，就是读题是要仔细耐心，不要因为题目较长，样例难以理解就放弃，慢慢读。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

bool v[50010];
ll n,m,father[50010],indegree[50010],p[50010],c[50010],l,b[50010],ans;
char a[5][310][310];

ll searchfather(ll v){
    if(father[v]==v) return father[v];
    father[v]=searchfather(father[v]);
    return father[v];
}

int main(){
    scanf("%lld%lld",&n,&m); getchar();
    for(ll k=0; k<2; k++){
        for(ll i=0; i<n; i++) scanf("%s",a[k][i]);
    }
    
    for(ll i=0; i<=n*m+n+m+1; i++) father[i]=i;
    
    for(ll k=0; k<2; k++){
        for(ll i=0; i<n; i++){
            for(ll j=0; j<m; j++){
                if(a[k][i][j]=='\\'||a[k][i][j]=='X'){
                    ll x=i*(m+1)+j,y=(i+1)*(m+1)+j+1;
                    ll f1=searchfather(x),f2=searchfather(y);
                    if(father[f1]!=f2) father[f1]=f2;
                    indegree[x]+=(-k)*2+1;
                    indegree[y]+=(-k)*2+1;
                    v[x]=v[y]=1;
                }
                if(a[k][i][j]=='/'||a[k][i][j]=='X'){
                    ll x=i*(m+1)+j+1,y=(i+1)*(m+1)+j;
                    ll f1=searchfather(x),f2=searchfather(y);
                    if(father[f1]!=f2) father[f1]=f2;
                    indegree[x]+=(-k)*2+1;
                    indegree[y]+=(-k)*2+1;
                    v[x]=v[y]=1;
                }
            }
        }
    }
    
    for(ll i=0; i<n*m+n+m+1; i++){
        if(v[i]==0) continue;
        ll k=searchfather(i);
        if(p[k]==0){
            p[k]=1;
            c[++l]=k;
        }
        b[k]+=abs(indegree[i]);
    }
    
    for(ll i=1; i<=l; i++){
        if(b[c[i]]==0) ans++;
        else ans+=b[c[i]]/2;
    }
    printf("%lld",ans);
    return 0;
}

0

程馨语 LV 10 @ 2021-08-02 14:30:16

#include<bits/stdc++.h>
#define ll long long
using namespace std;

bool v[50010];
ll n,m,father[50010],indegree[50010],p[50010],c[50010],l,b[50010],ans;
char a[5][310][310];

ll searchfather(ll v){
if(father[v]==v) return father[v];
father[v]=searchfather(father[v]);
return father[v];
}

int main(){
scanf("%lld%lld",&n,&m); getchar();
for(ll k=0; k<2; k++){
for(ll i=0; i<n; i++) scanf("%s",a[k][i]);
}

for(ll i=0; i<=n*m+n+m+1; i++) father[i]=i;

for(ll k=0; k<2; k++){
for(ll i=0; i<n; i++){
for(ll j=0; j<m; j++){
if(a[k][i][j]=='\'||a[k][i][j]=='X'){
ll x=i*(m+1)+j,y=(i+1)*(m+1)+j+1;
ll f1=searchfather(x),f2=searchfather(y);
if(father[f1]!=f2) father[f1]=f2;
indegree[x]+=(-k)*2+1;
indegree[y]+=(-k)*2+1;
v[x]=v[y]=1;
}
if(a[k][i][j]=='/'||a[k][i][j]=='X'){
ll x=i*(m+1)+j+1,y=(i+1)*(m+1)+j;
ll f1=searchfather(x),f2=searchfather(y);
if(father[f1]!=f2) father[f1]=f2;
indegree[x]+=(-k)*2+1;
indegree[y]+=(-k)*2+1;
v[x]=v[y]=1;
}
}
}
}

for(ll i=0; i<n*m+n+m+1; i++){
if(v[i]==0) continue;
ll k=searchfather(i);
if(p[k]==0){
p[k]=1;
c[++l]=k;
}
b[k]+=abs(indegree[i]);
}

for(ll i=1; i<=l; i++){
if(b[c[i]]==0) ans++;
else ans+=b[c[i]]/2;
}
printf("%lld",ans);
return 0;
}

0

shisuan LV 8 @ 2018-07-21 15:27:19

bfs但要注意范围是m+1和n+1,巨坑

#include<stdio.h>
#include<string.h>
#include<utility>
#include<queue>
#include<math.h>
using namespace std;
char a[2][210][210];
bool b[210][210];
int  check(int x,int y)
{
    int ans=0;
    int f=0;
    if(b[x][y])
    return 0;
    queue<pair<int,int> > ppp;
    pair<int ,int> p(x,y),q;
    b[x][y]=true;
    ppp.push(p);
    while(!ppp.empty())
    {
        p=ppp.front();
        ppp.pop();
        int sss[2]={0,0};
        for(int i=0;i<=1;i++)
        {
            if(a[i][p.first-1][p.second-1]=='\\'||a[i][p.first-1][p.second-1]=='X')
            {
                f=1;
                sss[i]++;
                if(!b[p.first-1][p.second-1])
                {
                b[p.first-1][p.second-1]=true;
                q.first=p.first-1;
                q.second=p.second-1;
                ppp.push(q);
                }
            }
            if(a[i][p.first-1][p.second]=='/'||a[i][p.first-1][p.second]=='X')
            {f=1;
                sss[i]++;
                if(!b[p.first-1][p.second+1])
                {
                b[p.first-1][p.second+1]=true;
                q.first=p.first-1;
                q.second=p.second+1;
                ppp.push(q);
                }
            }
            if(a[i][p.first][p.second]=='\\'||a[i][p.first][p.second]=='X')
            {f=1;
                sss[i]++;
                if(!b[p.first+1][p.second+1])
                {
                b[p.first+1][p.second+1]=true;
                q.first=p.first+1;
                q.second=p.second+1;
                ppp.push(q);
                }
            }
            if(a[i][p.first][p.second-1]=='/'||a[i][p.first][p.second-1]=='X')
            {f=1;
                sss[i]++;
                if(!b[p.first+1][p.second-1])
                {
                b[p.first+1][p.second-1]=true;
                q.first=p.first+1;
                q.second=p.second-1;
                ppp.push(q);
                }
            }           
        }
        ans+=abs(sss[1]-sss[0]);
    }
    //printf("%d  %d  %d\n",x,y,ans);
    if(f&&ans==0)
    return 1;
    else
    return (ans)/2;
}
int main()
{int n,m;
while(scanf("%d%d",&n,&m)==2)
{
    memset(b,0,sizeof(b));
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++)
    scanf("%s",a[0][i]+1);
    for(int i=1;i<=n;i++)
    scanf("%s",a[1][i]+1);
    int ans=0;
    for(int i=1;i<=n;i++)//这个地方应该是n+1
        for(int j=1;j<=m;j++)//这个地方应该是m+1
            ans+=check(i,j);
    printf("%d\n",ans);
}
    

    return 0;
}

0

coolxxx LV 9 @ 2016-05-18 13:02:23

题解+代码

-1

qq913653500 LV 10 @ 2017-08-10 17:00:11


var
father:array[1..45000] of longint;
a:array[1..45000] of longint;
v:array[1..45000] of boolean;
map:array[1..200,1..200,1..2] of shortint;
n,m,i,j,k,x,y,fx,fy:longint;
ans:int64;
t:ansistring;
function fa(x:longint):longint;
var
i:longint;
begin
fa:=x;
while (father[fa]<>0) do fa:=father[fa]; 
while (father[x]<>0) do
begin
i:=father[x];
father[x]:=fa;
x:=i;
end;
end;
begin
readln(n,m);
for i:=1 to n do
begin
readln(t);
for j:=1 to m do
case t[j] of
'.':map[i,j,1]:=0;
'X':map[i,j,1]:=1;
'\':map[i,j,1]:=2;
'/':map[i,j,1]:=3;
end;
end;
for i:=1 to n do
begin
readln(t);
for j:=1 to m do
case t[j] of
'.':map[i,j,2]:=0;
'X':map[i,j,2]:=1;
'\':map[i,j,2]:=2;
'/':map[i,j,2]:=3;
end;
end;
fillchar(father,sizeof(father),0);
fillchar(a,sizeof(a),0);
fillchar(v,sizeof(v),false);
for k:=1 to 2 do
for i:=1 to n do
for j:=1 to m do
begin
if (abs(map[i,j,k])=1) or (abs(map[i,j,k])=2) then
begin
x:=(i-1)*(m+1)+j;y:=i*(m+1)+j+1;
fx:=fa(x);fy:=fa(y);
if fx<>fy then father[fy]:=fx;
if k=2 then begin dec(a[x]);dec(a[y]); end
else begin inc(a[x]);inc(a[y]); end;
end;
if (abs(map[i,j,k])=1) or (abs(map[i,j,k])=3) then
begin
x:=(i-1)*(m+1)+j+1;y:=i*(m+1)+j;
fx:=fa(x);fy:=fa(y);
if fx<>fy then father[fy]:=fx;
if k=2 then begin dec(a[x]);dec(a[y]); end
else begin inc(a[x]);inc(a[y]); end;
end;
end;
ans:=0;
for i:=1 to (n+1)*(m+1) do
if fa(i)<>i then 
begin
a[fa(i)]:=abs(a[fa(i)]);inc(a[fa(i)],abs(a[i]));v[fa(i)]:=true;
end;
for i:=1 to (n+1)*(m+1) do
begin
if v[i] then ans:=ans+abs(a[i]) div 2;
if v[i] and (a[i]=0) then inc(ans);
end;
writeln(ans);
end.

-1

qyjubriskxp LV 10 @ 2010-07-22 14:15:27

额，奇怪了，为什么我并查集一样秒了呢~~

而且用并查集不用考虑用邻接表还是邻接矩阵的问题，会方便很多

-1

tiancaihb LV 8 @ 2009-11-08 11:32:54

Ural 1035, bfs找连通块统计出入度差。0的特判。0ms

-1

fnoi05clyang LV 8 @ 2009-09-21 00:17:04

http://blog.sina.com.cn/u/1640843443

-1

ckz LV 8 @ 2009-07-16 10:04:08

tips:二维数组要开[1..201,1..201]

-1

fengyi LV 9 @ 2008-07-15 22:59:57

这题也才200*200个节点啊

为什么用dfs老是202的

是不是系统特别为这题设置的??

我懒得改bfs了..

-1

swxadqecz LV 5 @ 2007-12-29 20:14:46

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ＷＡ第８个点的注意：ＢＦＳ要写非递归的！！！！

-1

lonelycorn LV 3 @ 2007-10-31 07:38:24

floodfill?忘了加欧拉回路！底歇！

好象用并查集能实现online

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

我有了一个血的教训：fillchar少用为好！

-1

Sheeta LV 3 @ 2007-10-22 13:36:41

LS的"撇捺"很有创意...受教了

-1

为什么封我号？ LV 3 @ 2007-08-07 13:27:55

每个点最多四个度，用什么方法才能不MLE呢？呵呵

-1

宇宙新秀 LV 3 @ 2007-07-09 20:14:03

记录号 Flag 得分记录信息环境评测机程序提交时间

R367701 Unaccepted 94 From 宇宙新秀－

　 P1015 FPC Vivid Puppy 2007-7-9 20:13:08

From xiaomengxian

十字绣

编译通过...

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

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

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

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

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

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

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

├ 测试数据 08：运行时错误...| 错误号: 202 | 堆栈溢出错

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

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

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

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

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

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

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

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

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

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

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

我讨厌人工栈～

-1

boy-zhezhe LV 3 @ 2007-07-09 15:45:33

我.不会....

[被 T 走]

-1

mick LV 8 @ 2007-07-02 22:29:21

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

floodfill最好用bfs..dfs会202错误的..!我是这样.不知道大牛觉得怎么样..

-1

qq311755010 LV 3 @ 2007-03-25 09:41:52

当心第8个点...

题解

49 条题解

十字绣

信息

状态

开发

支持

题解

49 条题解

十字绣

信息

状态

开发

支持

还没有账户？

登录