[uoj 509,loj 3279]「JOISC 2020 Day3」迷路的猫

题目链接

http://uoj.ac/problem/509

https://loj.ac/problem/3279(loj 暂不支持通信题,所以这道题还没公开)

题解

Subtask 4

当 \(A \geq 3\) 时,我们可以 BFS 遍历整张图,将图上的点按距离分层。

显然图上的边只有两种类型:层内边和层间边。

对于连接第 \(d\) 层和第 \(d+1\) 层的层间边,这条边的颜色可以设为 \(d \bmod 3\);对于第 \(d\) 层的层内边,边的颜色可以设为 \(d \bmod 3\)。

这样对于每一个点,我们都可以分辨出深度严格递减的方向,按照这个方向走即可。

期望得分:15 pts。

Subtask 7

只有两种颜色了,不过好消息是这种情况下我们只需解决树的问题。

如果一个点的度数大于等于 \(3\),显然颜色仅出现一次的边就是深度减小的方向。

如果一个点的度数为 \(2\),按照之前的染色方式肯定行不通,因为我们无法分清楚哪个方向是深度减小的方向。

步数限制是 \(d+6\) 步,这意味着我们最多往深度增大的方向走 \(3\) 步。

考虑按照这种方案染色(图借用了官方题解的图):

易知无论我们最开始处在链上的哪个点,我们最多向深度增大的方向走三步就可以意识到方向错误(具体讨论过程略,详见代码实现)。

且一旦我们确定了正确的方向,我们只需一直朝这个方向走即可,不用回头,从而可以将步数上限控制在 \(d+6\) 步。

期望得分:100 pts。

Anthony.cpp

#include "Anthony.h"
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> pii;
vector<pii> e[20005];
int dis[20005],fac[20005];
namespace col01
{
 vector<int> res;
 const int col[]={0,1,0,0,1,1};
 void dfs(int u,int fa,int p)
 {
  for(auto E:e[u])
  {
   int v=E.first,id=E.second;
   if(v==fa)continue;
   res[id]=col[p];
   if(e[v].size()>2)
    dfs(v,u,!col[p]);
   else
    dfs(v,u,(p+1)%6);
  }
 }
 vector<int> solve(int M)
 {
  res.resize(M);
  dfs(0,-1,0);
  return res;
 }
}
vector<int> Mark(int N,int M,int A,int B,vector<int> U,vector<int> V)
{
 for(int i=0;i<M;i++)
 {
  e[U[i]].push_back(make_pair(V[i],i));
  e[V[i]].push_back(make_pair(U[i],i));
 }
 if(A>=3)
 {
  queue<int> q;
  vector<int> res(M);
  memset(dis,-1,sizeof(dis));
  q.push(0);
  dis[0]=0;
  while(!q.empty())
  {
   int u=q.front();
   q.pop();
   for(auto E:e[u])
   {
    int v=E.first;
    if(dis[v]==-1)
    {
     dis[v]=dis[u]+1;
     q.push(v);
    }
   }
  }
  for(int i=0;i<M;i++)
   res[i]=min(dis[U[i]],dis[V[i]])%3;
  return res;
 }
 else return col01::solve(M);
}

Catherine.cpp

#include "Catherine.h"
#include <iostream>
using namespace std;
int a,b,lastc,fir,movec;
bool known,sta;
vector<int> step;
void Init(int A,int B)
{
 a=A,b=B;
}
int Move(vector<int> y)
{
 if(a>=3)//subtask 1-4
 {
  int p=-1,q=-1;
  for(int i=0;i<3;i++)
   if(y[i])p==-1?p=i:q=i;
  if(p!=-1&&q==-1)return p;
  return (p==0&&q==2)?2:p;
 }
 else//subtask 5-7
 {
  int cnt=0;
  for(auto x:y)
   cnt+=x;
  if(cnt+sta>=3)//point with >=3 degrees
  {
   known=true;
   if(!sta)
   {
    sta=true;
    return lastc=(y[1]==1);
   }
   if(!y[lastc])return -1;
   y[lastc]++;
   return lastc=(y[1]==1);
  }
  else if(cnt==1-sta)//get into leaf point
  {
   known=true;
   if(!sta)
   {
    sta=true;
    return lastc=(y[1]==1);
   }
   return -1;
  }
  else//2 degree point
  {
   sta=true;
   if(known)//only one choice
    return lastc=(y[1]==1);
   else
   {
    if(step.size()==0)//first step
    {
     if(y[0]==2)//00
     {
      fir=1,step.push_back(0);
      return lastc=0;
     }
     else if(y[1]==2)//11
     {
      fir=2,step.push_back(1);
      return lastc=1;
     }
     else //01
     {
      fir=3,step.push_back(0);
      return lastc=0;
     }
    }
    else if(step.size()==1)//second step
    {
     if(fir==1)//00
     {
      step.push_back(1);
      return lastc=1;
     }
     else if(fir==2)//11
     {
      step.push_back(0);
      return lastc=0;
     }
     else//01
     {
      if(y[1])
      {
       step.push_back(1);
       return lastc=1;
      }
      else
      {
       step.push_back(0);
       return lastc=0;
      }
     }
    }
    else if(step.size()==2)//third step
    {
     if(fir==1||fir==2)//00 or 11
     {
      known=true;
      if(y[0])//right way
       return lastc=0;
      else//wrong way
       return -1;
     }
     else//01
     {
      if(step[1]==0)
      {
       step.push_back(1);
       return lastc=1;
      }
      else
      {
       known=true;
       if(y[1])//right way
        return lastc=1;
       else//wrong way
        return -1;
      }
     }
    }
    else//last step,01 only
    {
     known=true;
     if(y[0])//right way
      return lastc=0;
     else
      return -1;
    }
   }
  }
 }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据