88 条题解
-
10
PowderHan LV 10 @ 2017-05-08 08:00:28
/* 这道题目很明显是一道并查集题目~ 设f[i]表示从1-i区间内的1的个数的奇偶性 对于一个查询(a,b)如果答案是偶数 说明1-(a-1)与1-n的含1个数的奇偶性相同 即有f[a-1]==f[b] 否则f[a-1]!=f[b] 那么对于奇偶性来说就只有两种情况咯 相同奇偶性或者不同奇偶性 这就是和关押罪犯那道题有点像只有两种集合 那么我们用a和a+maxn表示一个对立面 如果a和b同奇偶就将a,b合为一个集合 a+maxn,b+maxn也会为相同集合 否则就说明a的相反面和b同集,b的相反面也和a同集合 我们就将(a,b+maxn) (b,a+maxn)合并为一个集合 判断时如果是同奇偶， 就判断a和b+maxn(或者a+maxn,b)是不是同一个集合，如果是说明矛盾 否则按上面合并 同理如果是非同奇偶， 那么就检查a,b(或者a+maxn,b+maxn)是否是一个集合不是矛盾， 否则按上面合并即可 同时我们注意到这个下标大小可能到1000000000 这实在太大了，我们就想到用hash压缩一下，不然根本放不下 这道题就这样解决了~orz */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <stack> using namespace std; char rd; int pn; template<typename Type> inline void read(Type& v) { pn=1; while((rd=getchar())<'0'||rd>'9') if(rd=='-') pn=-1; v=rd-'0'; while((rd=getchar())>='0'&&rd<='9') v=v*10+rd-'0'; v*=pn; } template<typename Type> inline void out(Type v,bool c=1) { if(v==0) putchar(48); else { if(v<0) { putchar('-'); v=-v; } int len=0,dg[20]; while(v>0) { dg[++len]=v%10; v/=10; } for(int i=len;i>=1;i--) putchar(dg[i]+48); } if(c) putchar('\n'); else putchar(' '); } const int MAXN=30009; const int MAXNN=10000; const int Hash=6007; int fa[MAXN]; int Map[MAXN]; int n,m; inline int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } void Union(int a,int b) { a=find(a),b=find(b); if(a!=b) fa[a]=b; } void init() { memset(Map,-1,sizeof(Map)); for(int i=0;i<MAXN;i++) fa[i]=i; read(n); read(m); } int change(int x) { int b=x%Hash; while(Map[b]!=-1&&Map[b]!=x) b=(b+1)%Hash; Map[b]=x; return b; } void work() { int a,b; string c; int i=1; for(;i<=m;i++) { read(a); read(b); cin>>c; a=change(a-1); b=change(b); if(c[0]=='o') { if(find(a)==find(b)) break; Union(a,b+MAXNN); Union(a+MAXNN,b); } else { if(find(a)==find(b+MAXNN)) break; Union(a,b); Union(a+MAXNN,b+MAXNN); } } out(i-1); } int main() { init(); work(); } -
2
这题可以用map，但是要注意几个坑点
#include<stdio.h> #include<map> #include<algorithm> #define M 1000000003 //这里要开大于1000000000,被坑2次 using namespace std; map<int,int> f; int n,m; char s[100]; int dx(int x){ int p=f[x]; if(p==0||p==x) return x; //这里要注意p==x的情况，因为下面可能出现a=b的情况 return f[x]=dx(p); } int main(){ scanf("%d%d",&n,&m); for(int a,b,i=0;i<m;++i){ scanf("%d%d%s",&a,&b,s);b++; int c1=dx(a),c2=dx(a+M); int d1=dx(b),d2=dx(b+M); if(*s=='e'){ if(c1==d2 || c2==d1) return 0&printf("%d\n",i); else { f[c1]=d1; f[c2]=d2; } } else { if(c1==d1 || c2==d2) return 0&printf("%d\n",i); else { f[c1]=d2; f[c2]=d1; } } } printf("%d\n",m); }具体思路参考楼下？
-
1
看了一下，没人发向量偏移的，那我就发一个
#include<iostream>
#include<cstdio>
#include<cstring>
#define MOD 50000
using namespace std;
int n,t,book[50005],pre[50005],state[50005];
int hash_(int x){
int b=x%MOD;
while(book[b]!=-1&&book[b]!=x)
b=(b+1)%MOD;
book[b]=x;
return b;
}
int find(int x){
if(x==pre[x]) return x;
int t=pre[x];
pre[x]=find(pre[x]);
state[x]=state[t]+state[x];
return pre[x];
}
int main(){
//freopen("P.in","r",stdin);
//freopen("P.out","w",stdout);
int i;
memset(book,-1,sizeof(book));
scanf("%d %d",&n,&t);
for(i=0;i<=50000;i++){
pre[i]=i;state[i]=0;
}
for(i=1;i<=t;i++){
char s[10];
int x,y;
scanf("%d %d %s",&x,&y,s);
int a=hash_(x-1);
int b=hash_(y);
int fx=find(a);
int fy=find(b);
if(fx!=fy){
pre[fy]=fx;
if(s[0]=='e')
state[fy]=(state[a]-state[b]+2)%2;
else if(s[0]=='o')
state[fy]=(state[a]-state[b]+1+2)%2;
}
else if(fx==fy){
if(s[0]=='e'&&((state[b]-state[a]+2)%2)==1){
printf("%d",i-1);
return 0;
}
else if(s[0]=='o'&&(state[b]-state[a]+2)%2==0){
printf("%d",i-1);
return 0;
}
}
}
printf("%d",t);
return 0;
}
-
0
Sakurajima_Mai LV 4 @ 2019-01-29 20:49:31
Wa
-
0
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int hash = 6000,MAXN = 10000;
//离散化的时候要记a-1int f[MAXN*2+100], map[hash+100];
char s[10];int Hash(int x){
int bri = x%hash;
while(map[bri] != -1 && map[bri] != x)
bri = (bri+1)%hash;
map[bri] = x;
return bri;
}int find(int x){
if(!f[x])
return x;
return f[x] = find(f[x]);
}void add(int a, int b){
a = find(a);
b = find(b);
if(a != b)
f[a] = b;
}int main()
{
memset(map, -1, sizeof(map));
int n, k, a, b, i;
scanf("%d%d",&n,&k);
for(i=1; i<=k; i++){
scanf("%d%d%s",&a,&b,s);
a = Hash(a-1);
b = Hash(b);
if(s[0] == 'e'){
if(find(a) == find(b+MAXN))
break;
add(a, b);
add(a+MAXN, b+MAXN);
}
else{
if(find(a) == find(b))
break;
add(a, b+MAXN);
add(a+MAXN, b);
}
}
printf("%d",i-1);
return 0;
}
hash 离散化 并查集 -
0
Block code
var n,m,i,j,k,t,max,total:longint;
b,d,f:array [1..10000] of longint;
line:array [1..5000,1..3] of longint;
c:char;
procedure swap(var a,b:longint);
var z:longint;
begin
z:=a;a:=b;b:=z;
end;
function find(x:longint):longint;
var m:longint;
begin
if f[x]=x then exit(x);
m:=f[x];
f[x]:=find(f[x]);
b[x]:=(b[x]+b[m]) mod 2;
exit(f[x]);
end;procedure sort(i,j:longint);
var key,x1,x2:longint;
begin
if i<j then
begin
x1:=i;x2:=j;key:=d[(i+j) shr 1];
repeat
while d[x1]<key do inc(x1);
while d[x2]>key do dec(x2);
if x1<=x2 then
begin
swap(d[x1],d[x2]);
inc(x1);dec(X2);
end;
until x1>x2;
if x1<j then sort(x1,j);
if x2>i then sort(i,x2);
end;
end;function ef(x:longint):longint;
var l,r,mid:longint;
begin
l:=1; r:=total;
while l<=r do
begin
mid:=(l+r) div 2;
if d[mid]<x then l:=mid+1
else if d[mid]>x then r:=mid-1
else exit(mid);
end;
exit(-1);
end;procedure union(x,y,p:longint);
var
i,x1,x2:longint;
begin
x1:=find(x);
x2:=find(y);
if (x1<>x2) then
begin
f[x1]:=x2;
i:=b[x]+b[y]+p;
i:=i mod 2;
b[x1]:=i;
end;
end;procedure init;
var x,y,l,r:longint;
begin
readln(n);readln(m);
for i:=1 to m do
begin
read(line[i,1],line[i,2]);
read(c); readln(c);
if c='e' then line[i,3]:=0 else line[i,3]:=1;
d[2*i-1]:=line[i,1]-1;
d[2*i]:=line[i,2];
end;
sort(1,2*m);
total:=1;
for i:=2 to 2*m do
begin
if d[i]<>d[total] then
begin
inc(total);
d[total]:=d[i];
end;
end;
for i:=1 to total do
f[i]:=i;
for i:=1 to m do
begin
x:=line[i,1]-1; y:=line[i,2];
x:=ef(x); y:=ef(y);
l:=find(x); r:=find(y);
if l<>r then
union(x,y,line[i,3])
else
begin
x:=b[x]; y:=b[y];
if (y+x+line[i,3]+2) mod 2<>0 then
begin
writeln(i-1);
halt;
end;
end;
end;
writeln(m);
end;begin
init;
end. -
0
type
new=record
l,r:longint;
f:boolean;
end;
var
n:longint;
i,j,k,l,m,p:integer;
s:string;
ch:char;
a:array[0..10001] of longint;
b:array[0..5001] of integer;
c:array[0..5001] of new;
procedure sort(l,r:longint);
var
i,j,x,y:longint;
begin
x:=a[(l+r) div 2];
i:=l;
j:=r;
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if i<=j then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
begin
readln(n);
readln(m);
for i:=1 to m do
begin
read(c[i].l,c[i].r);
a[2*i-1]:=c[i].l-1;
a[2*i]:=c[i].r;
read(ch);
readln(s);
if ch<>' ' then s:=ch+s;
if s='even' then c[i].f:=true;
end;
sort(1,2*m);
l:=0;
for i:=1 to 2*m do
if (l=0) or (a[i]<>a[l]) then
begin
inc(l);
a[l]:=a[i];
end;
for i:=1 to l do b[i]:=i;
for i:=1 to m do
begin
for j:=1 to l do if a[j]=c[i].l-1 then break;
for k:=j+1 to l do if a[k]=c[i].r then break;
if (c[i].f and (b[j]+b[k]=0)) or ((not c[i].f) and (b[j]=b[k])) then
begin
writeln(i-1);
exit;
end;
if c[i].f then
if b[j]<>b[k] then
for p:=1 to l do
if b[p]=b[k] then b[p]:=b[j] else else else
if b[j]+b[k]<>0 then
for p:=1 to l do if b[p]=b[k] then b[p]:=-b[j];
end;
writeln(m);
end.-
半度微凉 @ 2014-10-23 11:05:56
-
-
0
测试数据 #0: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 824 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 824 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 824 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 824 KiB, score = 10
Accepted, time = 45 ms, mem = 824 KiB, score = 100#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int HASH = 6000, N = 10000;
int map[HASH + 100], f[N * 2 + 100];
int n, k;
int hash(int x)
{
int ret;
ret = x % HASH;
while(map[ret] != -1 && map[ret] != x)
ret = (ret + 1) % HASH;
map[ret] = x;
return ret;
}
int find(int x)
{
if(!f[x]) return x;
return f[x] = find(f[x]);
}
void un(int x, int y)
{
x = find(x);
y = find(y);
if(x != y) f[x] = y;
}
int main()
{
memset(map, -1, sizeof(map));
char s[10];
bool flag;
scanf("%d%d", &n, &k);
int i, a, b;
for(i = 1; i <= k; ++i)
{
scanf("%d%d%s", &a, &b, s);
flag = (0 == strcmp(s, "even")) ? true : false;
a = hash(a - 1);
b = hash(b);
if(flag)
{
if(find(a) == find(b + N)) break;
un(a, b);
un(a + N, b + N);
}
else
{
if(find(a) == find(b)) break;
un(a, b + N);
un(a + N, b);
}
}
printf("%d", i - 1);
return 0;
} -
0
问个问题，合并时，为什么f[y]=x只能50分额……
#include
#include
#include
#include
using namespace std;
const int HASH=6000,N=10000;
int map[HASH+100],f[N*2+100];
int n,k;
int hash(int x)
{
int ret;
ret=x%HASH;
while(map[ret]!=-1 && map[ret]!=x)
ret=(ret+1)%HASH;
map[ret]=x;
return ret;
}
int find(int x)
{
if(!f[x]) return x;
return f[x]=find(f[x]);
}
void un(int x,int y)
{
x=find(x);
y=find(y);
if(x!=y) f[x]=y;
}
int main()
{
memset(map,-1,sizeof(map));
char s[10];
bool flag;
scanf("%d%d",&n,&k);
int i,a,b;
for(i=1;i -
0
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
1A了
表示自从ac了食物链后，并查集无压力。 -
0
xiegengsheng LV 7 @ 2010-07-24 19:30:12
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
并查集+前向星 -
0
sixhomeland LV 9 @ 2009-11-09 20:30:45
好题！
赞一个！ -
0
program dsf;
var n:longint;
begin
read(n);
read(n);
writeln(n);
end.
通过它，知道了问题数是小于5000的，爽！-
yuyilahanbao @ 2014-01-16 18:21:20
话说你坑爹大大草稿行不行，vijos是**不会**显示输出的
-
PowderHan
LV 10
@ 2017-05-08 08:00:28
