Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
 Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

总结此题可以精简到一个并查集！并且用向量的思考模式想整个过程相当简单！

Posted by majiaN at 2008-10-19 10:58:32 on Problem 1182 
check(y,x,d-1);
int find(int k)
{
if (p[k]==k)
   return k;
int t=finds(p[k]);
ch[k]=(ch[k]+ch[p[k]])%3; //这个向量关系需要发现 
p[k]=t;
return t;
}

void check(int x,int y,int d)
{
    int tp=find(x),tq=find(y);
    if(x>n||y>n) 
    {
        ++lyn;
        return;
    }
if (tp==tq)
{
   if ((ch[x]-ch[y]+3)%3!=d)//这个关系根据上面的可以自己用向量推 
    {
        ++lyn;
    }
    return;
}
p[tp]=tq;
ch[tp]=(ch[y]-ch[x]+d+6)%3;//这个同理 
}
Followed by:
Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator