├ 测试数据 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的测试结果了

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

这题实在是简单题，只是入口等于出口的地方稍稍要注意一下

玩过十字绣的就会知道粉简单……

没用欧拉回路，用并查集也AC了

注意等于0的情形

明白了。。打扰了。。不好意思。。

将正面的边视为正边，反面的则视为负边。用floodfill将由正边和负边交替连接的结点组成一个块。对于每一个块，其中的所有结点的正边数目和负边数目之差的绝对值（定为dep）之后div 2后就为这个块的所需针数。

在一个块中只用一针就可完成，假设该针由v1出发，到vn结束，那么v1到vn中间的点的dep为0，而v1和vn则为1。也就是说块中的那一针在v1有一个入口，在vn有一个出口，而每一对入口和出口就代表了一针，那么就可以通过dep之和除以2得到所需针数。由此可以拓宽到多针。

这题数据真bt，连标程都超时。。

注意：所有结点的正边数目和负边数目之差的绝对值的和 而非 其中的所有结点的正边数目和负边数目之差的和的绝对值
若和为0，则为1针.

测试数据 #0: Accepted, time = 0 ms, mem = 1360 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1396 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1396 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 1392 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 1396 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 1392 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1392 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1400 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1396 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1356 KiB, score = 10
测试数据 #10: Accepted, time = 0 ms, mem = 1360 KiB, score = 10
测试数据 #11: Accepted, time = 0 ms, mem = 1356 KiB, score = 10
测试数据 #12: Accepted, time = 15 ms, mem = 1356 KiB, score = 10
测试数据 #13: Accepted, time = 0 ms, mem = 1356 KiB, score = 10
测试数据 #14: Accepted, time = 0 ms, mem = 1360 KiB, score = 10
测试数据 #15: Accepted, time = 0 ms, mem = 1356 KiB, score = 10
测试数据 #16: Accepted, time = 0 ms, mem = 1356 KiB, score = 10
Accepted, time = 60 ms, mem = 1400 KiB, score = 170

一个很丑的并查集= =
pascal
program P1015;
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.


#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define eps 1e-8
#define J 10
#define MAX 0x7f7f7f7f
#define PI 3.1415926535897
#define N 207
using namespace std;
int n,m,lll,ans,cas;
char map[2][N][N];
bool u[N][N];
bool f;
void floodfill(int i,int j)
{
int t=0,k;
if(u[i][j])return;
u[i][j]=1;
if(i>1 && j>1)
{
for(k=0;k<2;k++)
{
if(map[k][i-1][j-1]=='\\' || map[k][i-1][j-1]=='X')
{
t=t+(-2)*k+1;
f=1;
floodfill(i-1,j-1);
}
}
}
if(i>1 && j<=m)
{
for(k=0;k<2;k++)
{
if(map[k][i-1][j]=='/' || map[k][i-1][j]=='X')
{
t=t+(-2)*k+1;
f=1;
floodfill(i-1,j+1);
}
}
}
if(i<=n && j>1)
{
for(k=0;k<2;k++)
{
if(map[k][i][j-1]=='/' || map[k][i][j-1]=='X')
{
t=t+(-2)*k+1;
f=1;
floodfill(i+1,j-1);
}
}
}
if(i<=n && j<=m)
{
for(k=0;k<2;k++)
{
if(map[k][i][j]=='\' || map[k][i][j]=='X')
{
t=t+(-2)*k+1;
f=1;
floodfill(i+1,j+1);
}
}
}
lll+=abs(t);
}
int main()
{
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j,k;
// while(~scanf("%s",s1))
while(~scanf("%d",&n))
// for(scanf("%d",&cas),l=1;l<=cas;l++)
{
memset(u,0,sizeof(u));
ans=0;
scanf("%d",&m);
for(k=0;k<2;k++)
for(i=1;i<=n;i++)
scanf("%s",map[k][i]+1);
for(i=1;i<=n+1;i++)
{
for(j=1;j<=m+1;j++)
{
lll=f=0;
floodfill(i,j);
if(f && lll==0)ans++;
else ans+=lll/2;
}
}
printf("%d\n",ans);
}
return 0;
}

发个代码啊！！！！！！！！！

编译成功

测试数据 #0: Accepted, time = 23 ms, mem = 13576 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 13868 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 13872 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 13876 KiB, score = 10
测试数据 #4: Accepted, time = 7 ms, mem = 13876 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 13584 KiB, score = 10
测试数据 #6: Accepted, time = 31 ms, mem = 13576 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 14180 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 13724 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 13576 KiB, score = 10
测试数据 #10: Accepted, time = 15 ms, mem = 13576 KiB, score = 10
测试数据 #11: Accepted, time = 0 ms, mem = 13584 KiB, score = 10
测试数据 #12: Accepted, time = 0 ms, mem = 13580 KiB, score = 10
测试数据 #13: Accepted, time = 7 ms, mem = 13584 KiB, score = 10
测试数据 #14: Accepted, time = 15 ms, mem = 13576 KiB, score = 10
测试数据 #15: Accepted, time = 15 ms, mem = 13576 KiB, score = 10
测试数据 #16: Accepted, time = 0 ms, mem = 13576 KiB, score = 10
出题人你成功逼疯了我，非要我并查集！广搜为何不行？

点击查看程序源码+详细题解

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

悲剧了……我用了并查集为什么还这么慢……6K不是挺好的吗……

感谢黑书的指导(页码 P275) 我的图论好差啊 T^T

编译通过...

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

看着这个比较爽。。。

编译通过...

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

program p1015;

var a,b,w:array[-10..205,-10..205] of longint;

v,e:array[0..44000] of longint;

c:array[0..45000,1..8] of boolean;

i,j,k,l,m,n,sum,ans,p,q,head,tail:longint;

t:char;

zt:array[0..100000] of longint;

begin

readln(n,m);

for i:=1 to n do begin

for j:=1 to m do begin read(t); {1 2} {5 6}

case t of {3 4} {7 8}

'.':a:=0;

'/':a:=1;

'\':a:=2;

'X':a:=3;

end;end;

readln;end;

for i:=1 to n do begin

for j:=1 to m do begin

read(t);

case t of

'.':b:=0;

'/':b:=1;

'\':b:=2;

'X':b:=3;

end;end;

readln;end;

fillchar(c,sizeof(c),false);

for i:=1 to n+1 do

for j:=1 to m+1 do

begin k:=(i-1)*(m+1)+j;

if a>=2 then begin inc(v[k]);c[k,4]:=true; end;

if a>=2 then begin inc(v[k]);c[k,1]:=true; end;

if a mod 2=1 then begin inc(v[k]);c[k,3]:=true; end;

if a mod 2=1 then begin inc(v[k]);c[k,2]:=true; end;

if b>=2 then begin inc(e[k]);c[k,4]:=true; end;

if b>=2 then begin inc(e[k]);c[k,1]:=true; end;

if b mod 2=1 then begin inc(e[k]);c[k,3]:=true; end;

if b mod 2=1 then begin inc(e[k]);c[k,2]:=true; end;

end;

l:=(n+1)*(m+1);

for i:=1 to l do

begin p:=e[i];q:=v[i];e[i]:=abs(p-q);v[i]:=p+q; end;

for i:=1 to l do

if v[i]>0 then begin sum:=0;

fillchar(zt,sizeof(zt),0);head:=0;tail:=1;zt[1]:=i;

while head0 then begin

inc(sum,e[p]);v[p]:=0;

if c[p,1] then begin inc(tail);zt[tail]:=p-m-2; end;

if c[p,2] then begin inc(tail);zt[tail]:=p-m; end;

if c[p,3] then begin inc(tail);zt[tail]:=p+m; end;

if c[p,4] then begin inc(tail);zt[tail]:=p+m+2; end;

end;

end;

if sum=0 then inc(ans)

else inc(ans,sum div 2);

end;

writeln(ans);

end.

把边转化成点的关系，然后floodfill，注意要用广搜不然202.。

编译通过...

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

ural1035...

orz...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

难道写并查集就是这个速度，还是我写扯了。。

编译通过...

├ 测试数据 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就可以了。（第一次读入数据打成i

我是沙茶啊！！！！

X打成小写的x了！！！！

并查集就是短！写着爽！

点击进入我写的c++程序……