{"id":338,"date":"2010-08-10T21:28:00","date_gmt":"2010-08-10T13:28:00","guid":{"rendered":"http:\/\/localhost\/?p=338"},"modified":"2010-08-10T21:28:00","modified_gmt":"2010-08-10T13:28:00","slug":"usaco2006_opentwo-headed_cows","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=338","title":{"rendered":"[Usaco2006 Open]Two-Headed Cows"},"content":{"rendered":"

\u3002\u3002\u3002\u516b\u4e2dOJ\u4e0a\u5c45\u7136\u6ca1\u6709\u9898\u76ee\u3002\u3002
\u4e0d\u8fc7\u6211\u8fd8\u662f\u627e\u5230\u4e86\u9898\u76ee\u3002\u3002
tdt.sjtu.edu.cn\/~rma\/USACO\/task\/2006\/Open\/twohead.txt<\/a>
\u8fd9\u4e2a\u4e0b\u5348\u6ca1\u4ec0\u4e48\u5fc3\u60c5\u3002\u3002\u5c31\u53bb\u516b\u4e2dOJ\u5237USACO\u7684\u6c34\u9898\u3002\u3002
\u6c34\u4e86\u5f88\u591a\u9053\u56e7\u3002\u53d1\u73b0\u8fd9\u9053\u7b97\u6700\u6709\u610f\u601d\u7684\u7011\u5e03\u6c57\u3002\u3002
\u9996\u5148\u53ef\u4ee5\u53d1\u73b0\u663e\u7136\u53ef\u4ee5\u8d2a\u5fc3\u7684\u5206\u914d\u3002\u3002
\u5c31\u662f\u6bcf\u6b21\u90fd\u5230\u4e00\u4e2a\u4e2a\u5f80\u5f53\u524d\u7684\u6bb5\u52a0\uff0c\u77e5\u9053\u4e0d\u6ee1\u8db3\u4e3a\u6b62\u3002\u3002
\u5224\u65ad\u662f\u5426\u6ee1\u8db3\u5c31\u662f\u4e2a\u7b80\u5355\u76842-SAT\u3002\u3002
\u6211\u8003\u8651\u4e86\u4e24\u4e2a\u60f3\u6cd5\u3002\u3002
\u8981\u4e48\u662f\u6bcf\u6b21\u66b4\u529b2-SAT\u3002\u3002\u663e\u7136TLE\u3002\u3002
\u5982\u679c\u4e8c\u5206\u7684\u8bdd\u3002\u3002\u90a3\u4e48\u4e5f\u662f\u53ef\u80fd\u4f1aTLE\u7684\u3002\u3002
\u6240\u4ee5\u53ea\u597d\u641e\u52a8\u6001\u7ef4\u62a4\u3002\u3002
\u5148\u8bf4\u4e00\u4e0b\u6784\u56fe\u3002\u3002
1A\u8868\u793aCow1\u7684\u5934A\u3002\u3002
\u90a3\u4e48\u5982\u679c1A \u8ba8\u538c 2A\u3002
\u90a3\u4e481A <-> 2B 1B<->2A..
\u8fde\u7ebf\u8868\u793a\u4e00\u5b9a\u8981\u5728\u4e00\u8fb9\u3002\u3002
\u5982\u679c\u4ec0\u4e48\u65f6\u5019\u53d1\u73b01A<->1B\u3002\u3002
\u5c31\u77db\u76fe\u4e86\u3002\u3002
\u6211\u8868\u793a\u4f20\u7edf\u7684\u5e76\u67e5\u96c6\u9762\u5bf9\u8fd9\u6837\u7684\u8be2\u95ee\u53ea\u80fd\u60b2\u5267\u3002\u3002
\u6240\u4ee5\u53ea\u597d\u4f7f\u7528\u975e\u5e38\u89c4\u7684\u3002\u3002\u5c31\u662f\u542f\u53d1\u5f0f\u5408\u5e76\u7684\u90a3\u4e2a\u3002\u3002
\u800c\u4e14\u4e3a\u4e86\u8be2\u95ee\u662f\u5426\u6709\u8fd9\u79cd\u3002\u3002\u9700\u8981\u7528set\u3002\u3002\u3002
\u7136\u540e\u5c31\u5dee\u4e0d\u591a\u4e86\u3002\u3002
\u6069\u3002\u3002\u8fd9\u4e2a\u590d\u6742\u5ea6\u6709\u70b9\u60ca\u609a\u3002\u3002
\u542f\u53d1\u5f0f\u5408\u5e76\u672c\u8eab\u5c31\u662fNLogN\u7684\uff0c\u52a0\u4e0a\u8fd8\u8981\u7528set\u3002\u3002
\u5c31\u662fNLogN^2\u7684\u3002\u3002\u3002
\u4e0d\u8fc7\u5c45\u7136AC\u4e86\u3002\u3002
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define tr(e,x) for(set<int>::iterator e=x.begin();e!=x.end();e++)
#define trV(e,x) for(vector<int>::iterator e=x.begin();e!=x.end();e++)
#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();
const int inf=~0U>>1,maxn=50000;
using namespace std;
struct UF
{
set<int> node[maxn];
int root[maxn];
UF()
{
rep(i,maxn)
root[i]=i,node[i].insert(i);
}
bool Union(int i,int j)
{
i=root[i];j=root[j];
if(i!=j)
{
if(node[i].size()<node[j].size())
swap(i,j);
tr(e,node[j])
{
int x=*e;
if(node[i].find(x^1)!=node[i].end())return false;
node[i].insert(x);root[x]=i;
}
node[j].clear();
}
return true;
}
}U;
int n,m;
vector<int> E[maxn];
void AddEdge(int s,int t)
{
if(s<t)swap(s,t);
E[s].pb(t);
}
int main()
{
\/\/freopen("in","r",stdin);
cin>>n>>m;int s;char c;
rep(i,m)
{
cin>>s>>c;–s;int a=s*2+c-‘A’;
cin>>s>>c;–s;int b=s*2+c-‘A’;
AddEdge(a,b^1);AddEdge(b,a^1);
}
int ans=0;int pre=-1;
rep(i,n)
{
for(int t=i*2;t<i*2+2;t++)
trV(e,E[t])if(*e>pre*2+1&&!U.Union(t,*e))
{
ans++;
pre=i;
continue;
}
}
ans++;
cout<<ans<<endl;
} <\/p>\n","protected":false},"excerpt":{"rendered":"

\u3002\u3002\u3002\u516b\u4e2dOJ\u4e0a\u5c45\u7136\u6ca1\u6709\u9898\u76ee\u3002\u3002\u4e0d\u8fc7\u6211\u8fd8\u662f\u627e\u5230\u4e86\u9898\u76ee\u3002\u3002tdt.sjtu.edu.cn\/~rma\/USACO\/task\/2006\/Open\/twohead.txt \u8fd9\u4e2a\u4e0b\u5348\u6ca1\u4ec0\u4e48\u5fc3\u60c5\u3002\u3002\u5c31\u53bb\u516b\u4e2dOJ\u5237USACO\u7684\u6c34\u9898\u3002\u3002\u6c34\u4e86\u5f88\u591a\u9053\u56e7\u3002\u53d1\u73b0\u8fd9\u9053\u7b97\u6700\u6709\u610f\u601d\u7684\u7011\u5e03\u6c57\u3002\u3002\u9996\u5148\u53ef\u4ee5\u53d1\u73b0\u663e\u7136\u53ef\u4ee5\u8d2a\u5fc3\u7684\u5206\u914d\u3002\u3002\u5c31\u662f\u6bcf\u6b21\u90fd\u5230\u4e00\u4e2a\u4e2a\u5f80\u5f53\u524d\u7684\u6bb5\u52a0\uff0c\u77e5\u9053\u4e0d\u6ee1\u8db3\u4e3a\u6b62\u3002\u3002\u5224\u65ad\u662f\u5426\u6ee1\u8db3\u5c31\u662f\u4e2a\u7b80\u5355\u76842-SAT\u3002\u3002\u6211\u8003\u8651\u4e86\u4e24\u4e2a\u60f3\u6cd5\u3002\u3002\u8981\u4e48\u662f\u6bcf\u6b21\u66b4\u529b2-SAT\u3002\u3002\u663e\u7136TLE\u3002\u3002\u5982\u679c\u4e8c\u5206\u7684\u8bdd\u3002\u3002\u90a3\u4e48\u4e5f\u662f\u53ef\u80fd\u4f1aTLE\u7684\u3002\u3002\u6240\u4ee5\u53ea\u597d\u641e\u52a8\u6001\u7ef4\u62a4\u3002\u3002\u5148\u8bf4\u4e00\u4e0b\u6784\u56fe\u3002\u30021A\u8868\u793aCow1\u7684\u5934A\u3002\u3002\u90a3\u4e48\u5982\u679c1A \u8ba8\u538c 2A\u3002\u90a3\u4e481A <-> 2B 1B<->2A..\u8fde\u7ebf\u8868\u793a\u4e00\u5b9a\u8981\u5728\u4e00\u8fb9\u3002\u3002\u5982\u679c\u4ec0\u4e48\u65f6\u5019\u53d1\u73b01A<->1B\u3002\u3002\u5c31\u77db\u76fe\u4e86\u3002\u3002\u6211\u8868\u793a\u4f20\u7edf\u7684\u5e76\u67e5\u96c6\u9762\u5bf9\u8fd9\u6837\u7684\u8be2\u95ee\u53ea\u80fd\u60b2\u5267\u3002\u3002\u6240\u4ee5\u53ea\u597d\u4f7f\u7528\u975e\u5e38\u89c4\u7684\u3002\u3002\u5c31\u662f\u542f\u53d1\u5f0f\u5408\u5e76\u7684\u90a3\u4e2a\u3002\u3002\u800c\u4e14\u4e3a\u4e86\u8be2\u95ee\u662f\u5426\u6709\u8fd9\u79cd\u3002\u3002\u9700\u8981\u7528set\u3002\u3002\u3002\u7136\u540e\u5c31\u5dee\u4e0d\u591a\u4e86\u3002\u3002\u6069\u3002\u3002\u8fd9\u4e2a\u590d\u6742\u5ea6\u6709\u70b9\u60ca\u609a\u3002\u3002\u542f\u53d1\u5f0f\u5408\u5e76\u672c\u8eab\u5c31\u662fNLogN\u7684\uff0c\u52a0\u4e0a\u8fd8\u8981\u7528set\u3002\u3002\u5c31\u662fNLogN^2\u7684\u3002\u3002\u3002\u4e0d\u8fc7\u5c45\u7136AC\u4e86\u3002\u3002#include <vector>#include <algorithm>#include <utility>#include <iostream>#include <cstdio>#include <cmath>#include <cstdlib>#include <set>#include <map>#include <cstring>#include <time.h>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_back#define Debug(x) cout<<#x<<"="<<x<<endl;#define For(i,l,r) for(int i=l;i<=r;i++)#define tr(e,x) for(set<int>::iterator e=x.begin();e!=x.end();e++)#define trV(e,x) for(vector<int>::iterator e=x.begin();e!=x.end();e++)#define printTime cout<<"Time:"<<pre-clock()<<endl;pre=clock();const int inf=~0U>>1,maxn=50000;using namespace std;struct UF{ set<int> node[maxn]; int root[maxn]; UF() { rep(i,maxn) root[i]=i,node[i].insert(i); } bool Union(int i,int j) { […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/338"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=338"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/338\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=338"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=338"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=338"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}