构造一个 的矩阵,满足元素 。
次询问,每次给出一条 只能向下向右走的路径上的元素的和,你需要保证矩阵对于这 次询问路径都能唯一确定。
,。
观察到我们只要知道偶数行在哪里,就可以得知整条路径,所以不妨考虑构造一个奇数行均为 ,偶数行均不为 的矩阵。
考虑偶数行的取值,显然可以考虑二进制拆位,给每一个处于偶数行的位置都分配一个 的权值。
考虑 的取值,由于不能向左走,所以不同行的 可以有重复的。第一行显然必须是 ,第二行则可以是 因为不能向左走。所以第 行开头的 最小可以取第 行从左往右数第 个 。
这样我们一共用了 个 , 时用了 个 ,,构造满足限制。
不难发现这样构造之后若路径的权值和为 ,则 的二进制序列(低位在前高位在后) 中连续的 对应在同一偶数行中走,特判 的奇偶性输出方案即可。
代码如下:
#include <iostream>
#include <cstdio>
using namespace std;
const int S=30,BS=500;
int n,q;
long long a[S][S];
int main()
{
scanf("%d",&n);
int cnt=0;
for(int i=2;i<=n;i+=2)
{
long long mul=1<<i-2;
for(int j=1;j<=n;j++) a[i][j]=mul,mul<<=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) printf("%lld ",a[i][j]);
printf("\n");
fflush(stdout);
}
scanf("%d",&q);
while(q--)
{
long long sm;
scanf("%lld",&sm);
int lim=n+(n/2-1)*2-!(n&1);
int x=1,y=1;
for(int i=-1;i<=lim;i++)
{
printf("%d %d\n",x,y);
fflush(stdout);
if((i>=0&&(sm>>i&1))&&!(sm>>i+1&1)) x++;
else if((1<0||!(sm>>i&1))&&(sm>>i+1&1)) x++;
else y++;
}
}
return 0;
}