# 28 条题解

• @ 2017-01-23 20:40:29

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

struct BigInteger {
typedef unsigned long long LL;

static const int BASE = 100000000;
static const int WIDTH = 8;
vector<int> s;

BigInteger& clean(){while(!s.back()&&s.size()>1)s.pop_back(); return *this;}
BigInteger(LL num = 0) {*this = num;}
BigInteger(string s) {*this = s;}
BigInteger& operator = (long long num) {
s.clear();
do {
s.push_back(num % BASE);
num /= BASE;
} while (num > 0);
return *this;
}
BigInteger& operator = (const string& str) {
s.clear();
int x, len = (str.length() - 1) / WIDTH + 1;
for (int i = 0; i < len; i++) {
int end = str.length() - i*WIDTH;
int start = max(0, end - WIDTH);
sscanf(str.substr(start,end-start).c_str(), "%d", &x);
s.push_back(x);
}
return (*this).clean();
}

BigInteger operator + (const BigInteger& b) const {
BigInteger c; c.s.clear();
for (int i = 0, g = 0; ; i++) {
if (g == 0 && i >= s.size() && i >= b.s.size()) break;
int x = g;
if (i < s.size()) x += s[i];
if (i < b.s.size()) x += b.s[i];
c.s.push_back(x % BASE);
g = x / BASE;
}
return c;
}
BigInteger operator - (const BigInteger& b) const {
assert(b <= *this); // 减数不能大于被减数
BigInteger c; c.s.clear();
for (int i = 0, g = 0; ; i++) {
if (g == 0 && i >= s.size() && i >= b.s.size()) break;
int x = s[i] + g;
if (i < b.s.size()) x -= b.s[i];
if (x < 0) {g = -1; x += BASE;} else g = 0;
c.s.push_back(x);
}
return c.clean();
}
BigInteger operator * (const BigInteger& b) const {
int i, j; LL g;
vector<LL> v(s.size()+b.s.size(), 0);
BigInteger c; c.s.clear();
for(i=0;i<s.size();i++) for(j=0;j<b.s.size();j++) v[i+j]+=LL(s[i])*b.s[j];
for (i = 0, g = 0; ; i++) {
if (g ==0 && i >= v.size()) break;
LL x = v[i] + g;
c.s.push_back(x % BASE);
g = x / BASE;
}
return c.clean();
}
BigInteger operator / (const BigInteger& b) const {
assert(b > 0); // 除数必须大于0
BigInteger c = *this; // 商:主要是让c.s和(*this).s的vector一样大
BigInteger m; // 余数:初始化为0
for (int i = s.size()-1; i >= 0; i--) {
m = m*BASE + s[i];
c.s[i] = bsearch(b, m);
m -= b*c.s[i];
}
return c.clean();
}
BigInteger operator % (const BigInteger& b) const { //方法与除法相同
BigInteger c = *this;
BigInteger m;
for (int i = s.size()-1; i >= 0; i--) {
m = m*BASE + s[i];
c.s[i] = bsearch(b, m);
m -= b*c.s[i];
}
return m;
}
// 二分法找出满足bx<=m的最大的x
int bsearch(const BigInteger& b, const BigInteger& m) const{
int L = 0, R = BASE-1, x;
while (1) {
x = (L+R)>>1;
if (b*x<=m) {if (b*(x+1)>m) return x; else L = x;}
else R = x;
}
}
BigInteger& operator += (const BigInteger& b) {*this = *this + b; return *this;}
BigInteger& operator -= (const BigInteger& b) {*this = *this - b; return *this;}
BigInteger& operator *= (const BigInteger& b) {*this = *this * b; return *this;}
BigInteger& operator /= (const BigInteger& b) {*this = *this / b; return *this;}
BigInteger& operator %= (const BigInteger& b) {*this = *this % b; return *this;}

bool operator < (const BigInteger& b) const {
if (s.size() != b.s.size()) return s.size() < b.s.size();
for (int i = s.size()-1; i >= 0; i--)
if (s[i] != b.s[i]) return s[i] < b.s[i];
return false;
}
bool operator >(const BigInteger& b) const{return b < *this;}
bool operator<=(const BigInteger& b) const{return !(b < *this);}
bool operator>=(const BigInteger& b) const{return !(*this < b);}
bool operator!=(const BigInteger& b) const{return b < *this || *this < b;}
bool operator==(const BigInteger& b) const{return !(b < *this) && !(b > *this);}
};

ostream& operator << (ostream& out, const BigInteger& x) {
out << x.s.back();
for (int i = x.s.size()-2; i >= 0; i--) {
char buf[20];
sprintf(buf, "%08d", x.s[i]);
for (int j = 0; j < strlen(buf); j++) out << buf[j];
}
return out;
}

istream& operator >> (istream& in, BigInteger& x) {
string s;
if (!(in >> s)) return in;
x = s;
return in;
}

const int N = 200 + 5;

int n, m, pa[N << 1];
bool vis[N];

int findset(int x) { return x == pa[x] ? x : pa[x] = findset(pa[x]); }

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n * 2; i++) pa[i] = i;
for (int i = 1; i <= m; i++) {
int a, b, c, d;
scanf("%d%d%d%d", &a, &b, &c, &d);
if (b == d) {
if (findset(a) == findset(c + n)) {
return 0;
}
pa[findset(a)] = findset(c);
pa[findset(a + n)] = findset(c + n);
} else {
if (findset(a) == findset(c)) {
return 0;
}
pa[findset(a)] = findset(c + n);
pa[findset(a + n)] = findset(c);
}
}
int cnt = 0;
for (int i = 1; i <= n; i++)
if (!vis[findset(i)] && findset(i) <= n) {
cnt++;
vis[findset(i)] = 1;
}
BigInteger ans = 1;
for (int i = 1; i <= cnt; i++) ans = ans * 2;
cout << ans << endl;
return 0;
}

• @ 2015-02-03 14:31:40

注意如果用拆点并查的方法,统计集合一定要多加注意...
可以试一下数据
2 1
1 0 2 1
结果应该是2而不是1或4.

<大整数bign模板省略>

//union find
int f[1000];
void INIT(int size)
{ for(int i=0;i<=size;i++) f[i]=i; }
int findf(int x)
{ return x==f[x] ? x : f[x]=findf(f[x]); }
void con(int a,int b)
{ f[findf(a)]=findf(b); }

int n,m;

#define A(i) (i)
#define B(i) ((i)+n)

int used[1000];
bign res("1",1);

int main()
{
n=getint();
m=getint();

int tot=n;
INIT(n*2+2);

for(int i=0;i<m;i++)
{
int a=getint()-1,x1=getint(),b=getint()-1,x2=getint();
int x=x1^x2;

#define FA(i) findf(A(i))
#define FB(i) findf(B(i))

if(x==1) //make difference
{
if(FA(a)==FA(b) || FB(a)==FB(b))
{
return 0;
}
else
{
if(FA(a)!=FB(b) && FB(b)!=FA(a)) tot--;
con(A(a),B(b));
con(A(b),B(a));
}
}
else if(x==0) //make same
{
if(FA(a)==FB(b) || FB(a)==FA(b))
{
return 0;
}
else
{
if(FA(a)!=FA(b) && FB(a)!=FB(b)) tot--;
con(A(a),A(b));
con(B(a),B(b));
}
}
}

for(int i=0;i<tot;i++)
res=res+res;

res.output();

return 0;
}

• @ 2015-06-03 22:26:27

解模2方程可行吗？

• @ 2014-12-17 21:26:31

设有k个集合，答案则是2^k

• @ 2014-01-22 22:15:09

#include<stdio.h>
#include<string.h>

#define MAXN 201
#define N 1000

int fa[MAXN+N+10],visit[MAXN],a[1000],c[1000];

int root(int x)
{
if (!fa[x]) return x;

return fa[x]=root(fa[x]);
}

void unit(int x ,int y)
{
x=root(x);
y=root(y);

if (x!=y)
fa[x]=y;
}

int main()
{
int cnt,i,j,n,m,l,x1,y1,x2,y2;

scanf("%d%d",&n,&m);

for (i=1;i<=m;++i)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

if (y1==y2)
{
if (root(x1)==root(x2+N))
{
return 0;
}
unit(x1,x2);
unit(x1+N,x2+N);
}
else
{
if (root(x1)==root(x2))
{
return 0;
}
else
{
unit(x1,x2+N);
unit(x1+N,x2);
}

}

}

cnt=0;
for (i=1;i<=n;++i)
{
if (!visit[root(i)]&&(root(i)<=n))
{
++cnt;
visit[root(i)]=1;
}
}

a[0]=1; l=1;
for (i=0;i<cnt;++i)
{
for (j=0;j<l;++j)
{
c[j]+=a[j]*2;
c[j+1]+=c[j]/10;
c[j]%=10;
}
++l;
while (l>=0&&c[l]==0) --l;
++l;

for (j=0;j<l;++j) a[j]=c[j];
memset(c,0,sizeof(c));
}

for (i=l-1;i>=0;--i) printf("%d",a[i]);

//while (1);
return 0;
}
谁能解释一下这个程序为啥能ac。。。。

• @ 2017-01-23 20:40:18

最后检查一下并查集形成几个集合。。

• @ 2013-12-13 23:02:22

忘记加格式了

### 代码

var n,m,i,j,a,b,c,d:longint;
b1,b2:boolean;
father:array[1..200]of longint;
relation:array[1..200]of boolean;
ans:array[0..100]of longint;
function f(i:longint):longint;
var b:boolean;
begin
if father[i]=0 then exit(i)else if father[father[i]]=0 then exit(father[i]) else f:=f(father[i]);
relation[i]:=not(relation[i]xor relation[father[i]]);
father[i]:=f;
end;
procedure noans;
begin
halt;
end;
begin
fillchar(relation,sizeof(relation),true);
for i:=1 to m do
begin
if b=1 then b1:=true else b1:=false;
if d=1 then b2:=true else b2:=false;
if f(a)=f(c) then
if (relation[a] xor relation[c])<>(b1 xor b2) then
noans
else continue;
relation[f(c)]:=not((not(b1 xor b2))xor relation[c]);
father[f(c)]:=a;
end;
ans[0]:=1;
ans[1]:=1;
for i:=1 to n do if f(i)=i then
begin
for j:=1 to ans[0] do ans[j]:=ans[j]*2;
for j:=1 to ans[0] do
begin
ans[j+1]:=ans[j+1]+(ans[j]div 10);
ans[j]:=ans[j] mod 10;
end;
if ans[ans[0]+1]<>0 then ans[0]:=ans[0]+1;
end;
for i:=ans[0] downto 1 do write(ans[i]);writeln;
end.

• @ 2013-12-13 22:59:03

lhf用的什么奇葩算法，竟然用得着hash，欺负我们不会用的是不是？
奉上50行的程序，秒杀你的120+行。

var n,m,i,j,a,b,c,d:longint;
b1,b2:boolean;
father:array[1..200]of longint;
relation:array[1..200]of boolean;
ans:array[0..100]of longint;
function f(i:longint):longint;
var b:boolean;
begin
if father[i]=0 then exit(i)else if father[father[i]]=0 then exit(father[i]) else f:=f(father[i]);
relation[i]:=not(relation[i]xor relation[father[i]]);
father[i]:=f;
end;
procedure noans;
begin
halt;
end;
begin
fillchar(relation,sizeof(relation),true);
for i:=1 to m do
begin
if b=1 then b1:=true else b1:=false;
if d=1 then b2:=true else b2:=false;
if f(a)=f(c) then
if (relation[a] xor relation[c])<>(b1 xor b2) then
noans
else continue;
relation[f(c)]:=not((not(b1 xor b2))xor relation[c]);
father[f(c)]:=a;
end;
ans[0]:=1;
ans[1]:=1;
for i:=1 to n do if f(i)=i then
begin
for j:=1 to ans[0] do ans[j]:=ans[j]*2;
for j:=1 to ans[0] do
begin
ans[j+1]:=ans[j+1]+(ans[j]div 10);
ans[j]:=ans[j] mod 10;
end;
if ans[ans[0]+1]<>0 then ans[0]:=ans[0]+1;
end;
for i:=ans[0] downto 1 do write(ans[i]);writeln;
end.

• @ 2013-11-03 19:16:56

const
p=59;
ma=400; //400000
var
j,s1,s,y,x,ss,i,pp,qq,n,m,q1,q2,a1,a2:longint;
o,fa,a,b,l,q,c,h:array[0..ma]of longint;

function gf(x:longint):longint;
//var //
begin
if x=fa[x] then
exit(x);
gf:=gf(fa[x]);
c[x]:=(c[x]+c[fa[x]])mod 2;
fa[x]:=gf;
end;
function search(qq:longint):longint;
var
x,s1,y:longint;
begin
x:=qq mod p;
s1:=l[x];
while s1<>0 do
begin
y:=h[s1];
if y=qq then
begin
search:=s1;
exit;
end;
s1:=q[s1];
end;
end;
procedure unite(x,y,z:longint);
var
pp,qq:longint;
begin
pp:=gf(x);
qq:=gf(y);
c[pp]:=(c[y]-c[x]-z+2)mod 2;
fa[pp]:=qq;
end;
procedure hash(qq:longint);
var
x,s1,y:longint;
begin
x:=qq mod p;
s1:=l[x];
while s1<>0 do
begin
y:=h[s1];
if y=qq then
exit;
s1:=q[s1];
end;
ss:=ss+1;
h[ss]:=qq;
fa[ss]:=ss;
q[ss]:=l[x];
l[x]:=ss;
end;
begin

// assign(input,'1221.in');
//reset(input);

for i:=1 to n do
begin
x:=i mod p;
s1:=l[x];
{ while s1<>0 do
begin
y:=h[s1];
if y=qq then
exit;
s1:=q[s1];
end; }
ss:=ss+1;
h[ss]:=i;
fa[ss]:=ss;
q[ss]:=l[x];
l[x]:=ss;
end;
//ss:=0;
fillchar(b,sizeof(b),0);
{ for i:=1 to n do
begin
fa[i]:=i;
c[i]:=0;
end; }
for i:=1 to m do
begin
hash(q1);
hash(q2);
pp:=search(q1);
qq:=search(q2);

if gf(pp)=gf(qq) then
begin
if ((c[pp]mod 2=c[qq]mod 2)and(a1<>a2))or((c[pp]mod 2<>c[qq]mod 2)and(a1=a2)) then
begin
close(input);
close(output);
halt;
end;
end else unite(pp,qq,a1 xor a2);
end;
s:=0;
for i :=1 to ss do
if gf(i)=i then
s:=s+1;
// s:=16;
o[1]:=1;
x:=1;
for j:=1 to s do
begin

for i:=1 to x do
o[i]:=o[i]*2;
for i:=1 to x do
begin
o[i+1]:=o[i] div 10000+o[1+i];
o[i]:=o[i] mod 10000;
end;
while o[x+1]>0 do
begin
x:=x+1;
o[x+1]:=o[x+1]+o[x] div 10000;
o[x]:=o[x] mod 10000;
end;
end;
write(o[x]);
for i:=x-1 downto 1 do
begin
if o[i]=0 then
y:=0 else y:=trunc(ln(o[i])/ln(10));
while y+1<4 do
begin
write(0);
y:=y+1;
end;
write(o[i]);
end;
writeln;

end.

我了个去 数组就开了400竟然还a 了 话说同志们 我代码写的有点麻烦（+hash）可无视

• @ 2013-10-12 19:58:24

并查集，f，e表示两个问题答案是一致的还是不一致的，f2表示和这个问题一起确定的问题集合，
答案=2^不同的f2总数

• @ 2010-04-16 20:19:40

类似小胖的奇偶……

随便并。

• @ 2009-11-09 11:00:10

是经典题吧，和食物链用了同样的方法吧，并查集，犯了个傻逼错啊，降RP啊

• @ 2009-10-09 22:11:12

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

一次AC的感觉 很爽

• @ 2009-10-09 21:16:34

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

...... 交了3次。。

• @ 2009-05-25 21:47:58

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

并查集吧，最后别忘了高精度，哈哈，一次就AC！！！

• @ 2009-04-06 11:15:56

FloodFill也不错.

• @ 2009-02-04 17:44:55

并查集+高精度2^k=AC

• @ 2008-11-10 10:43:54

在TRUE1023牛的讲解下，发现很EASY

最后的高精度打错了，让我找了1个小时。。。。。

• @ 2008-11-10 09:14:47

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

• @ 2008-11-06 23:32:14

fammiebright大牛，您的程序连样例都过不了，竟然A了！真不可思议~~

• @ 2008-11-03 15:34:08

ID
1221

6

(无)

758

192

25%

2