Codeforces Round #812 (Div. 2)

比赛的时候做出了AB，C题在比赛结束后大概十二分钟的时间解出来了。勉强算做出三道题了吧（嘎嘎掉分）。
其中B题耗费了一个多小时的时间，主要原因是在接近四十分钟的时间里读错了题，带着错误的题意去做的题。导致留给C题的时间并不长。

A题：一个规律题，大意是在一个平面坐标系中，有一些箱子，从0,0点出发，要访问所有的箱子，然后回到0,0点，坐标xy可能为负数。

这个题第一个想法就是可能和所有箱子和坐标点构造的最大矩形有关，但是没敢直接尝试。通过在稿纸上画了几个图得以验证了想法。大概十分钟的时间AC了这道题，在同分数段几乎是最快的之一

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		int x,y;
		int maxk=-999,mink=999,maxg=-999,ming=999;
		for(int i=1;i<=n;i++)
		{
			cin>>x>>y;
			maxk = max(maxk,y);
			mink = min(mink,y);
			maxg = max(maxg,x);
			ming = min(ming,x);
		}
		maxk = max(maxk,0);
		mink = min(mink,0);
		maxg = max(maxg,0);
		ming = min(ming,0);
		cout<<(maxk-mink)*2+(maxg-ming)*2<<endl;
	}
}

B题：同样是个规律题，大意是给出一个长度为n的数组，数组中可以进行一个操作：选择i和j对于(0<=i<=j<=n)使得区间内的所有数的值减少1，求出这个数组是否能在n次操作内完成使数组所有的元素为0。

最开始的理解的题意是能否使得数组为一个升序数组，Determine if for all permutations $^{†}$ $b$ of $a$ , $f (a) \leq f (b)$ is true.这一句英文没有翻译好。导致WA了四次，拿了差不多保底分

解决方法：首先操作数至少为n，因为最大的数为n，同时操作数只能为n，因为题意操作数不能超过n。
要想使得在n次内完成，那么需要数组是个升序、降序，或者先升后降。这个应该很容易就能够看出来。
具体的原因可以分开考虑。当升序和降序的时候，我们很容易可以看出来，我们可以使得n这个数所在的位置影响的范围每次减1。
先升后降的情况，最大的数n必然在两个有序段的中间，n可以在中间影响两半的区域。

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
vector<ll>ve;
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		ve.clear();
		ll n,x;
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>x;
			ve.push_back(x);
		}	
		bool yz=false,yj=false,ban=false;
		for(int i=0;i<ve.size();i++)
		{
			if(i==ve.size()-1) {
				yz = true;
			}
			if(ve[i]>ve[i+1])	break;
		}
		for(int i=0;i<ve.size();i++)
		{
			if(i==ve.size()-1) {
				yj = true;
			}
			if(ve[i]<ve[i+1])	break;
		}
		if(yz||yz)
			cout<<"YES"<<endl;
		else 
		{
			int ff = 0;
			while(ve[ff]<=ve[ff+1]&&ff<ve.size()-1)
				ff++;
			while(ve[ff]>=ve[ff+1]&&ff<ve.size()-1)
				ff++;
			if(ff==ve.size()-1)
				cout<<"YES"<<endl;
			else
				cout<<"NO"<<endl;
		}
 	}
}

C题：构造题，大意是给出一个n，求出一组0-n的全排列对于数组a[0] - a[n-1]这么一个数组中，我们需要满足a[i]+i 是某一个数的平方。如果我们无法构造这样一个数，输出-1，否则输出我们构造的这个数组，存在多个构造输出一个。

对于给定的0 - n-1，对于小的数字它的所能形成的平方数有很多，而一个大的数它能形成的平方数就很少甚至为1。
因此，我们可以倒着填数。求出一个>=n的平方数，从n-1开始填数，知道填充的范围碰到右边已经被填充的边界或者碰到n-1（整个数组的边界）。这个时候我们需要重新寻找新的满足的平方数，同时更新这个填充边界。将边界更新至i-1，这i-1可以通过代入的方法计算出来。

不满足的情况件输出-1。（通过进一步思考可以观察到n无论为什么数都可以进行构造）如果存在这个情况，可以在填数时判断sum<0时跳出，这样一定存在没有填充的位置为0，和还没有去填充的0形成重复关系。

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
const int nn = 1e5+10;
int a[nn];
bool sign[nn];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		memset(a,0,sizeof a);
		memset(sign,false,sizeof sign);
		int n;
		cin>>n;
		n--;
		int sum = 1;
		while(sum*sum<=n)
			sum++;
		if((sum-1)*(sum-1)==n)	sum--;
		
		int tempn = n;
		bool flag = true;
		for(int i=n;i>=0;i--)
		{
			while(sign[sum*sum-i]==true) sum--;
			a[sum*sum-i] = i;
			sign[sum*sum-i]=true;
			if(sum*sum-i==tempn) 
				sum--,tempn=i-1;
			
		}
	/*	memset(sign,false,sizeof sign);
		for(int i=0;i<=n;i++)
		{
			if(sign[a[i]]==true){
				flag = false ;break;
			}
			sign[a[i]] = true;
		}*/
		if(flag)
		{	
			for(int i=0;i<=n;i++)
				cout<<a[i]<<' ';
			cout<<endl;
		}else cout<<-1<<endl;
	}
}

D题：大意是有2^n个人参加比赛。顺序进行两两比赛，你可以通过2/3 * 1<<n次询问来得到最终的获胜者。
每次如果a的获胜次数大于b的获胜次数返回1，小于返回2，相等返回0。

一个交互性很强的题。我们总是可以通过两次询问排除三个人，这不难看出。在1 2 3 4中。我们可比较1和3，用胜利较多的那个比较对应的4 和 1。将获胜者放入一个单独数组，用于下次排除。

code：

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
vector<int>ve;
int ask(int a,int b)
{
	cout << "? " << a << " " << b << endl;
	int res;
	cin>>res;
	return res;
}
int main()
{
//	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		ve.clear();
		int n;
		cin>>n;
		n = 1<<n;
		for(int i=1;i<=n;i++)
			ve.push_back(i);
		while(ve.size()>1)
		{
			vector<int>ans; 
			if(ve.size()==2)
			{
				int ff = ask(ve[0],ve[1]);
				if(ff==1)
					ans.push_back(ve[0]);
				else ans.push_back(ve[1]);
			}else{
				for(int i=0;i<ve.size();i+=4)
				{
					int ff = ask(ve[i],ve[i+2]);
					if(ff==0)
					{
						int tt = ask(ve[i+1],ve[i+3]);
						if(tt==1) ans.push_back(ve[i+1]);
						else ans.push_back(ve[i+3]);
					}else if(ff==1)
					{
						int tt = ask(ve[i],ve[i+3]);
						if(tt==1) ans.push_back(ve[i]);
						else ans.push_back(ve[i+3]);
					}else 
					{
						int tt = ask(ve[i+2],ve[i+1]);
						if(tt==1) ans.push_back(ve[i+2]);
						else ans.push_back(ve[i+1]);
					}
				}
			}
			swap(ve,ans);
		}
		cout<<"! "<<ve[0]<<endl;
	}
}

搜索

标签

存档