【LOJ3279】「JOISC 2020 Day3」迷路的猫

题目链接

点击打开链接

题目解法

对于 A≥3A\geq 3A≥3 的情况,考虑从 000 号点出发,求出到各个点的最短路 distidist_idisti​ 。
则对于一条边 (x,y)(x,y)(x,y) , ∣distx−disty∣≤1|dist_x-dist_y|\leq 1∣distx​−disty​∣≤1 ,将其染色为 min{distx,disty}%3min\{dist_x,dist_y\}\%3min{distx​,disty​}%3 。
对于任意一个点 xxx ,与其相邻的边权值应当至多有两种,找出表示 distdistdist 减一的那一种即可。

时间复杂度 O(N+M)O(N+M)O(N+M) ,没有多余步数。

对于 A=2A=2A=2 的情况,首先考虑树是一条链的情况。
考虑对边进行 001101001101001101 为一个循环节的染色,则无论身处何处,向一个方向走 333 步即可唯一确定自己的位置和方向,从而在多余步数不超过 666 的情况下达成目标。

对于树不是一条链的情况,考虑将度数 ≥3\geq 3≥3 的点的父边与子树边染上不同的颜色。那么,一旦经过度数 ≥3\geq 3≥3 的点,方向便能确定,从而我们只需要在树上的每一条链重复链上的算法即可。

时间复杂度 O(N)O(N)O(N) ,多余步数不超过 666 。

#include "stray.h"
#include
using namespace std;
namespace Anthony {
const int MAXN = 2e4 + 5;
const int value[6] = {0, 0, 1, 1, 0, 1};
vector res; int n, m;
vector <pair > a[MAXN];
void dfs(int pos, int fa) {
if (fa == -1) {
for (auto x : a[pos]) {
res[x.second] = 0;
dfs(x.first, x.second);
}
} else if (a[pos].size() <= 2) {
int ans = (res[fa] + 1) % 6;
for (auto x : a[pos])
if (x.second != fa) {
res[x.second] = ans;
dfs(x.first, x.second);
}
} else {
int ans = (value[res[fa]] == 0) ? 2 : 0;
for (auto x : a[pos])
if (x.second != fa) {
res[x.second] = ans;
dfs(x.first, x.second);
}
}
}
}
vector Mark(int N, int M, int A, int B, vector u, vector v) {
using namespace Anthony;
n = N, m = M, res.resize(m);
for (int i = 0; i 2) {
static int q[MAXN], dist[MAXN];
int l = 0, r = 0; dist[0] = 1, q[l = r = 0] = 0;
while (l <= r) {
int pos = q[l++];
for (auto x : a[pos])
if (dist[x.first] == 0) {
dist[x.first] = dist[pos] + 1;
q[++r] = x.first;
}
}
for (int i = 0; i <= m - 1; i++)
res[i] = min(dist[u[i]], dist[v[i]]) % 3;
return res;
}
dfs(0, -1);
for (int i = 0; i <= m - 1; i++)
res[i] = value[res[i]];
return res;
}
namespace Catherine {
const int MAXN = 2e4 + 5;
const int v[6] = {1, 0, 1, 1, 0, 0};
bool sure, type;
int r; vector a[5];
int cur, last, edge[5];
}
void Init(int A, int B) {
using namespace Catherine;
sure = false, type = A == 2, r = 0, last = -1;
}
int Move(vector y) {
using namespace Catherine;
if (!type) {
if (last != -1) y[last]++;
for (int i = 0; i = 3 || y[0] + y[1] <= 1) {
sure = true;
if (y[0] == 1) last = 0;
else last = 1;
} else {
a[++r] = y;
if (y[0] != 0) last = 0;
else last = 1;
edge[r] = last;
}
} else {
if (sure) {
if (y[0] + y[1] == 1) {
if (y[0] != 0) last = 0;
else last = 1;
} else {
y[last]++;
if (y[0] == 1) last = 0;
else last = 1;
}
} else if (y[0] + y[1] != 1) {
sure = true;
if (y[0] + y[1] == 0) return -1;
if (y[last] != 0) last ^= 1;
else return -1;
} else if (r < 3) {
int nxt = 0;
if (y[0] != 0) nxt = 0;
else nxt = 1;
y[last]++, last = nxt;
a[++r] = y;
edge[r] = last;
} else {
bool ans = false;
y[last]++, a[4] = y;
for (int i = 0; i <= 5; i++) {
bool res = true;
for (int j = 1; j <= 3; j++)
res &= edge[j] == v[(i + j) % 6];
for (int j = 1; j <= 4; j++) {
vector tmp(2);
tmp[v[(i + j) % 6]]++;
tmp[v[(i + j - 1) % 6]]++;
res &= a[j] == tmp;
}
if (res) ans = true;
}
sure = true;
if (ans) {
y[last]--;
if (y[0] != 0) last = 0;
else last = 1;
} else return -1;
}
}
return last;
}


作者:cz_xuyixuan

相关推荐

在这里插入图片描述

redis5.0.8 安装教程

AbstractAutoProxyCreator

Spring AOP 自动代理源码 DefaultAdvisorAutoProxyCreator

硬核ArrayList源码分析,答应我每天看一遍好么

硬核ArrayList源码分析,答应我每天看一遍好么

在这里插入图片描述

Java LinkedList 双向链表实现原理