AtCoder Regular Contest 142

A题不用说，C题之后不会。。。

B - Unbalanced Squares

大意：

构造一个n阶矩阵（元素从1~n^2），对于矩阵中的每一个元素，它周围的元素中大于它的数目和小于它的数目不能相等。

思路：
想了二十多分钟才有的思路。。。脑子是越来越不行了。

我的思路：

如果直接按从小到大的顺序做矩阵的话：

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

很明显是不行的。但是仔细观察一下，如果对每一行的元素改变一下顺序的话，可能是有希望的（总比全部重新构造好）。第一行和最后一行的每一个元素都是满足条件的。对于中间行的一些元素，如果它在边缘的话，下面两个元素是比它小的，上面两个元素是比它大的，那么旁边的元素无论是多少，都不会让这个元素不满足条件，所以两边的元素可以任意摆。剩余中间的，由于上面和下面的元素一样多，所以它两边的两个元素必须同时比它大或者同时比它小。

然后就可以随便试试了。

发现 a a+2 a+1 a+4 a+3 a+6 a+5...这个序列是ok的。

那么按规律填进去就可以了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define begin ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll n,t;
ll k;
void solve()
{
	cin>>n;
	if(n%2==1)
	{
		ll cnt=1;
		for(int i=1;i<=n;++i)
		{
			ll p=1+n*(i-1);
			if(i==1||i==n)
			{
				ll cnt=0;
				for(int j=1;j<=n;++j) cout<<p+(cnt++)<<' ';
				cout<<endl;
				continue;
			}
			cout<<p<<' ';
			ll cnt=1;
			for(int j=1;j<=(n-1)/2;++j)
			{
				cout<<p+(cnt)+1<<' '<<p+cnt<<' ';
				cnt+=2;
			}
			cout<<endl;
		}
		return;
	}
	else if(n%2==0)
	{
		ll cnt=1;
		for(int i=1;i<=n;++i)
		{
			ll p=1+n*(i-1);
			if(i==1||i==n)
			{
				ll cnt=0;
				for(int j=1;j<=n;++j) cout<<p+(cnt++)<<' ';
				cout<<endl;
				continue;
			}
			cout<<p<<' ';
			ll cnt=1;
			for(int j=1;j<=n/2-1;++j)
			{
				cout<<p+(cnt)+1<<' '<<p+cnt<<' ';
				cnt+=2;
			}
			cout<<p+cnt;
			cout<<endl;
		}
		return;
	}
	return;
}
int main()
{begin
	solve();
	return 0;
}

C - Tree Queries 

大意：

一道交互题（因为问问题的格式不对白瞎两发，shit。。。）

有一个n个节点的树。可以问不超过n*2个问题，每个问题可以问任意两个节点的距离（除了问1 ，2的距离）。

然后让你求1，2的距离。

思路：
既然可以问那么多问题，本着不要白不要的原则，就先把所有节点到1和2的距离都问出来，这样只需要2*n-4个问题。

然后分两种情况

1，2的距离为1：

看看是否有到1的距离为1且到2的距离为2的点，有的话标记f1，如果有到2的距离为1且到1的距离为2的点，就标记f2.

如果f1,f2都被标记了，有两种情况： 

那么只要对两个点询问一次距离，如果不是1的话，就可以说明1，2的距离为1了。

另外 ，如果f1，f2只有一个被标记了，也可以说明1，2的距离为1（自行理解）

 

对于剩余的大部分情况（1，2距离！=1）

只要对所有到1的距离为1的点求出它们到2的距离的最小值，加上一就可以了。

所以整体最多只要2*n-3次询问就能解决问题了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define ser ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const ll N=110;
ll n;
ll dis[N];
ll p[N];
ll k;
void solve()
{
	std::cin>>n;
	memset(p,0x3f,sizeof p);
	memset(dis,0x3f,sizeof dis);
	//cout<<"HBK"<<endl;
	for(int i=3;i<=n;++i)
	{
		std::cout<<"? "<<i<<" "<<2<<endl;
		std::cin>>k;
		dis[i]=k;
	}
	for(int i=3;i<=n;++i)
	{
		std::cout<<"? "<<i<<" "<<1<<endl;
		std::cin>>k;
		p[i]=k;
	}
	ll f1=0,f2=0;
	for(int i=3;i<=n;++i){
		if(p[i]==1&&dis[i]==2) f1=i;
		if(p[i]==2&&dis[i]==1) f2=i;
	}
	if(f1&&f2)
	{
		std::cout<<"? "<<f1<<' '<<f2<<endl;
		//cout<<"sdddddd"<<endl;
		std::cin>>k;
		if(k==1);
		else
		{
			cout<<"! "<<1<<endl;
			return;
		}
	}
	if((f2&&!f1)||(f1&&!f2))
	{
		cout<<"! "<<1<<endl;
		return;
	}
	ll ans=10000;
	for(int i=3;i<=n;++i)
	{
		if(p[i]==1)
		{
			ans=min(ans,dis[i]);
		}
	}
	std::cout<<"! "<<ans+1;
}
int main()
{//ser
	solve();
	return 0;
}