题解

47 条题解

  • 3
    @ 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
    @ 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
    @ 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
    @ 2016-05-18 13:02:23
  • -1
    @ 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
    @ 2010-07-22 14:15:27

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

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

  • -1
    @ 2009-11-08 11:32:54

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

  • -1
    @ 2009-07-16 10:04:08

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

  • -1
    @ 2008-07-15 22:59:57

    这题也才200*200个节点啊

    为什么用dfs老是202的

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

    我懒得改bfs了..

  • -1
    @ 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

    WA第8个点的注意:BFS要写非递归的!!!!

  • -1
    @ 2007-10-31 07:38:24

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

    好象用并查集能实现online

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

    我有了一个血的教训:fillchar少用为好!

  • -1
    @ 2007-10-22 13:36:41

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

  • -1
    @ 2007-08-07 13:27:55

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

  • -1
    @ 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
    @ 2007-07-09 15:45:33

    我.不会....

    [被 T 走]

  • -1
    @ 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
    @ 2007-03-25 09:41:52

    当心第8个点...

  • -1
    @ 2007-03-23 20:41:08

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

    用的floodfill……真是可恶……这已经是puppy的测试结果了

  • -1
    @ 2006-11-13 19:23:39

    感谢zhymaoling的证明,这道题貌似计算欧拉路径数,以前只知道结论,— —0。

信息

ID
1015
难度
7
分类
图结构 点击显示
标签
(无)
递交数
1205
已通过
269
通过率
22%
被复制
1
上传者