Preface

这周一周二没事情干就只好在水课上口胡点题目了，然后今天一口气把口胡的都写了

这场感觉A~D感觉都不难，我称之为构造题大赛，不过说实话D想了挺久的，比赛时不一定写得出来

A. Ian Visits Mary

很显然当我们一次跳的\(\Delta x,\Delta y\)满足\(\gcd(\Delta x,\Delta y)=1\)时就是合法的

由于\(1\)和任意数的\(\gcd\)都是\(1\)，因此直接\((0,0)\to (1,b-1)\to (a,b)\)即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
int t,a,b;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t) scanf("%d%d",&a,&b),printf("2\n%d %d\n%d %d\n",1,b-1,a,b);
	return 0; 
}

B. Grid Reconstruction

简单构造题，首先不难发现每个点上的数是加还是减是确定的，因此我们在加的格子上放上前\(n\)大的数，在减的格子上放上前\(n\)小的数

然后考虑具体的摆放方式，首先起点和终点因为肯定都要经过所以放上最大的两个数

然后剩下的位置由于这题向下走只有一次，而且一旦向下走了之后前后的走法都是唯一的

我们把贡献的式子写出来观察一下发现就是要形如如下的构造（当\(n=6\)时）：

11 1 7 3 9 5
2 8 4 10 6 12

直接模拟填一下就好了，代码也很好写

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=100005;
int t,n,a[3][N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j,l,r; scanf("%d",&n); l=1; r=n+1;
		for (a[2][n]=2*n,a[1][1]=2*n-1,i=3;i<n+2;++i) for (j=1;j<=2;++j)
		if (i&1) a[j][i-j]=l++; else a[j][i-j]=r++;
		for (i=1;i<=2;++i) for (j=1;j<=n;++j)
		printf("%d%c",a[i][j]," \n"[j==n]);
	}
	return 0; 
}

C. Ian and Array Sorting

小清新思维题，话说为什么我每次现场打的时候C都是细节题，然后补题的时候C都是思博题

首先处理不下降的问题我们经典考虑差分，设\(d_i=a_i-a_{i-1}\)，则题目要求转化为\(\forall i\in[2,n],d_i\ge 0\)

考虑我们如果对\((i-1,i)\)用加法操作，则有\(d_{i-1}++,d_{i+1}--\)，减法的话就是\(d_{i-1}--,d_{i+1}++\)

不难发现操作不会改变\(d_i+d_{i+2}\)的和，但是由于我们可以用这个操作修改\(d_1\)和\(d_{n+1}\)，因此事实上下标和\(1\)或者\(n+1\)奇偶性相同的位置的值都可以变成任意值

因此我们发现当\(n\)为奇数时所有的位置都可以被改成任意值，因此必然有解

而当\(n\)为偶数时，所有奇数下标的位置可以被改成任意值，但偶数下标的\(d_i\)的总和是不能变的

因此只要看此时\(\sum_{i\in[2,n]\and 2|i} d_i\)是否大于等于\(0\)即可，不过要注意特判\(n=2\)的情况

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=300005;
int t,n,a[N],d[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=n;++i)
		scanf("%d",&a[i]),d[i]=a[i]-a[i-1];
		if (n&1) { puts("YES"); continue; }
		if (n==2) { puts(a[1]<=a[2]?"YES":"NO"); continue; }
		long long sum=0; for (i=2;i<=n;i+=2) sum+=d[i];
		puts(sum>=0?"YES":"NO");
	}
	return 0; 
}

D. Sum Graph

刚开始脑抽了想着构造一棵树，然后浪费了大量时间，后来发现构造一条链就很trivial了才恍然大悟

我们考虑先用两次建边操作，分别选择\(x=n+1,x=n+2\)，不难发现此时我们得到一条如下的链：

\[1\leftrightarrow n\leftrightarrow 2 \leftrightarrow n-1\leftrightarrow3\leftrightarrow n-2\leftrightarrow\cdots\leftrightarrow \lfloor \frac{n}{2}\rfloor+1 \]

不难发现如果我们确定了这条链的端点，那么通过每个点到这个端点的距离就可以确定其它点在链上的位置了

而找到端点也很simple，我们直接随便任选一个点，找出到它最远的那个点，则这个点一定是链两个端点其一

因此结合题目中要求的输出两种方案其中一个正确即可的要求，刚好可以在\(2+2(n-1)=2n\)次操作后得到答案

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
int t,n,p1[N],p2[N],lnk[N];
inline void add(CI x)
{
	printf("+ %d\n",x); fflush(stdout);
	int y; scanf("%d",&y);
}
inline int ask(CI x,CI y)
{
	printf("? %d %d\n",x,y); fflush(stdout);
	int z; scanf("%d",&z); return z;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,l,r; scanf("%d",&n); add(n+1); add(n+2);
		for (l=1,r=n,i=1;i<=n;++i) if (i&1) lnk[i]=l++; else lnk[i]=r--;
		int mx=0,id; for (i=2;i<=n;++i)
		{
			int t=ask(1,i); if (t>mx) mx=t,id=i;
		}
		for (p1[id]=1,p2[id]=n/2+1,i=1;i<=n;++i)
		if (i!=id) mx=ask(id,i),p1[i]=lnk[mx+1],p2[i]=lnk[n-mx];
		for (printf("! "),i=1;i<=n;++i) printf("%d ",p1[i]);
		for (i=1;i<=n;++i) printf("%d%c",p2[i]," \n"[i==n]);
		fflush(stdout); int t; scanf("%d",&t);
	}
	return 0; 
}

E. Between

E本质其实也是个构造，刚开始想了一大半了最后输出答案没想好，看了眼高手的实现豁然开朗

首先对于一对限制\((a_i,b_i)\)，我们可以建一条有向边\(b_i\to a_i\)表示\(a_i\)被\(b_i\)约束，即当\(b_i\)确定后才能确定\(a_i\)

很显然当我们建出图后如果有点不能被从\(1\)开始的路径访问到，说明它是unbounded的，显然无解

否则我们设\(dis_i\)表示某个点到\(1\)路径上最少经过的点的个数（\(dis_1=1\)），则数\(i\)最后一定出现了\(dis_i\)次

那么现在的难点就是怎样构造一种方案来满足题意，这里有一种很巧妙的方法

我们设所有\(S(i)=\{x|dis_x=i\}\)，然后我们考虑最终如下构造答案序列：

\[S(n)+S(n-1)+\cdots+S(3)+S(2)+S(1)+\\ S(n)+S(n-1)+\cdots+S(3)+S(2)+\\ S(n)+S(n-1)+\cdots+S(3)+\\ \cdots\\ S(n) \]

不难发现这样构造之后任意两个\(S(i)\)之间必然包含了所有\(S(i-1)\)的元素，因此肯定可以满足题设

代码实现就非常简单了

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
#define RI register int
#define CI const int&
using namespace std;
const int N=1505,INF=1e9;
int t,n,m,x,y,dis[N],mx,num; vector <int> v[N],s[N],ans; queue <int> q; bool vis[N];
inline void BFS(void)
{
	vis[1]=dis[1]=1; q.push(1);
	while (!q.empty())
	{
		int now=q.front(); q.pop(); ++num;
		for (int to:v[now]) if (!vis[to])
		vis[to]=1,dis[to]=dis[now]+1,q.push(to);
	}
	for (RI i=1;i<=n;++i) if (dis[i]!=INF) mx=max(mx,dis[i]),s[dis[i]].push_back(i);
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
		v[i].clear(),s[i].clear(),vis[i]=0;
		for (i=1;i<=m;++i) scanf("%d%d",&x,&y),v[y].push_back(x);
		if (num=mx=0,BFS(),num!=n) { puts("INFINITE"); continue; }
		for (puts("FINITE"),ans.clear(),i=1;i<=mx;++i) for (j=mx;j>=i;--j)
		for (int x:s[j]) ans.push_back(x); printf("%d\n",ans.size());
		for (int x:ans) printf("%d ",x); putchar('\n');
	}
	return 0; 
}