even” or “odd” (the answer, i.e. the parity of the number of ones in the chosen subsequence, where “even” means an even number of ones and “odd” means an odd number). The input is ended with a line containing −1.| input | output |
|---|---|
10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd -1 |
3
|
分析：带权并查集，注意离散化；
代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <climits> #include <cstring> #include <string> #include <set> #include <map> #include <queue> #include <stack> #include <vector> #include <list> #define rep(i,m,n) for(i=m;i<=n;i++) #define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++) #define mod 1000000007 #define inf 0x3f3f3f3f #define vi vector<int> #define pb push_back #define mp make_pair #define fi first #define se second #define ll long long #define pi acos(-1.0) const int maxn=1e5+10; const int dis[4][2]={{0,1},{-1,0},{0,-1},{1,0}}; using namespace std; ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);} ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;} int n,m,k,t,id,p[maxn],a[maxn],s[maxn],d[maxn],q[maxn],v[maxn]; char b[10]; int find(int x) { if(x!=p[x]) { int fa=find(p[x]); a[x]^=a[p[x]]; p[x]=fa; } return p[x]; } bool join(int x,int y,int z) { int px=find(x),py=find(y); if(px!=py) { p[py]=px; a[py]=a[y]^a[x]^z; return false; } return true; } int main() { int i,j; while(~scanf("%d",&t)&&t!=-1) { scanf("%d",&n); memset(a,0,sizeof(a)); j=1; rep(i,1,n)scanf("%d%d%s",&s[i],&d[i],b),q[j++]=s[i],q[j++]=d[i],v[i]=(b[0]==‘o‘); sort(q+1,q+j+1); int num=unique(q+1,q+j+1)-q-1; rep(i,1,n) { s[i]=lower_bound(q+1,q+num+1,s[i])-q-2; d[i]=lower_bound(q+1,q+num+1,d[i])-q-1; } rep(i,0,num)p[i]=i; rep(i,1,n) { if(join(s[i],d[i],v[i])) { if(a[s[i]]^a[d[i]]!=v[i])break; } } printf("%d\n",i-1); } //system("pause"); return 0; }
原文：http://www.cnblogs.com/dyzll/p/5778129.html