题目大意
题目分析
很神的一道题，朱昶宇从JOI春季合宿改编的一道题。
朱瘤：“本来这套题是给你们找信心的，不过没想到。。。”
对于子任务1，shiro可以直接将每个格子染成到目标格子的距离，每次sora沿着距离较小的点走即可。
对于子任务2，将每个格子的值染成到目标格子的距离$\bmod\,3$，走法相同。
对于子任务3，将放数看做黑白染色，我们可以将目标行以上的格子染为黑，以下的格子染为白。
对于第$x$行，因为sora可以看到三个格子，shiro只需要按三个一组，两白一黑或两黑一白染色即可把$y$左边和$y$右边的列区分开来。
但每次只能移动一步。
对于子任务4，为了加快前进速度，我们不妨让每一列表示更多的信息。
我们先使得sora移动到$x$行。
如果我们能指定一些$01$循环串，使得sora看见其中任意三个均可推导出整行信息，那我们就可以用这些$01$串来表示前进的步数。
$\lbrace0011,1100,0101,1010,1001,0110\rbrace$符合上述要求，我们不妨令其分别表示$2^i,i\in[1,6]$，便可在$\log$的时间内定位到$x$行，最多只需要$6+2=8$步。
Q：我们只能看到三个数字，如何确定其究竟是哪个循环串？如$0011$和$1100$无法区分。
A：别忘了我们除了知道这三个数字还知道横纵坐标，根据横纵坐标我们即可还原循环串。
对于第$x$行，由于会出现左右不同编码交接的位置，为了让sora一定能够识别编码（编码不会冲突），只能使用$\lbrace0011,1100,0101,1010\rbrace$四种编码，分别表示移动$\lbrace-12,12,-1,1\rbrace$步。这样我们最坏在$9+12=21$步内可以移动到目标位置。
最坏需要$8+21=29$步，可以通过所有子任务。
上述的$12$是通过测试出来的，$12$附近的值应该也可行。
编译方式
对于本机测试：
下载user.zip，将内部文件解压到程序所在目录。
打开cmd，cd到程序所在目录，输入命令：（需要保证编译目录在环境变量中）g++ -std=c++11 -O2 -Wl,--stack=6710886 grader.cpp shiro.cpp sora.cpp -o board
修改board.in，在cmd中输入命令board.exe即可获得评测结果。
对于lemon测试：
下载board.zip，将内部文件解压到lemon工作目录。
压缩文件内含有测试数据，交互库，编译命令等文件。
代码
shiro.cpp1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
using namespace std;
namespace shiro {
//declare your variables here
const int n=128,len=12;
const int M[7][4]= {
{0, 0, 0, 0},
{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 0, 1, 1},
{1, 1, 0, 0},
{1, 0, 0, 1},
{0, 1, 1, 0}
};
int map[n][n];
int Log[n];
//implement these functions
void initShiro(int caseno) {
Log[0]=-1;
for(int i=1; i<n; i++)Log[i]=Log[i>>1]+1;
}
int abs(int x) {
return x<0?-x:x;
}
void shiro(int x,int y) {
for(int j=0; j<n; j+=4) { //已达目标行
int diff=min(abs(j+3-y),abs(j-y));
if(diff<len) { //接近目标
for(int i=j; i<j+4; i+=2) {
bool v=i<y;
map[x][i]=v;
map[x][i+1]=v^1;
}
} else { //快速移动
if(j<y)copy(M[4],M[4]+4,map[x]+j);
else copy(M[3],M[3]+4,map[x]+j);
}
}
for(int i=0; i<n; i++) {
int diff=abs(i-x);
if(i==x)continue;
if((diff&1)||i==0||i==n-1) { //奇数行设立标识符
for(int j=0; j<n; j++)map[i][j]=i<x;
continue;
}
int index=Log[diff]; //偶数行设置步数
for(int j=0; j<n; j+=4)copy(M[index],M[index]+4,map[i]+j);
}
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
setFlag(i,j,map[i][j]);
}
}
sora.cpp1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
using namespace std;
namespace sora {
//declare your variables here
const int len=12;
const int M[7][4]= {
{0, 0, 0, 0},
{0, 1, 0, 1},
{1, 0, 1, 0},
{0, 0, 1, 1},
{1, 1, 0, 0},
{1, 0, 0, 1},
{0, 1, 1, 0}
};
enum direction {D,U,R,L,P};
//implement these functions
void initSora(int caseno) {}
void go(int d,int val,vector<int>& v,int& x,int& y) {
v=move(d,val);
x+=dx[d]*val;
y+=dy[d]*val;
}
int match(int* a) {
for(int i=1; i<7; i++) {
bool bj=true;
for(int j=0; j<4; j++) {
if(a[j]==-1)continue;
if(a[j]!=M[i][j])bj=false;
}
if(bj)return i;
}
return -1;
}
void sora(int x,int y,vector<int> v) {
while(!v.empty()) {
if(v[L]==v[P]&&v[R]==v[P]) { //奇数行走到偶数行
if(v[P])go(D,1);
else go(U,1);
continue;
}
int a[4],tmp=y&3;
a[(tmp+3)&3]=v[L];
a[y&3]=v[P];
a[(tmp+1)&3]=v[R];
a[(tmp+2)&3]=-1;
if(v[U]!=v[D]) { //到达目标行
if(tmp<2) {
if(a[0]^a[1]) { //慢速前进
if(a[0])go(R,1);
else go(L,1);
} else { //快速前进
if(a[0])go(R,len);
else go(L,len);
}
} else {
if(a[2]^a[3]) { //慢速前进
if(a[2])go(R,1);
else go(L,1);
} else { //快速前进
if(a[2])go(L,len);
else go(R,len);
}
}
} else go(v[U]?D:U,1<<match(a));
}
}
}
