• 赛后总结
  • A - Non-zero
  • B - Non-zero
  • C - Anu Has a Function
  • D - Aerodynamic

鸽了n次之后的题解blog 这次比赛除了以前一直都在做比赛的学长们也来了许多同届的同学。

赛后总结

• 鸽了这么久的题解。。本来想在之后的感想里面写的，还是先在这里写一些吧。

经过了三个月的训练，自己也从只能A题到能开D题。本来这次比赛D题有机会交的，只奈自己手速太慢，做AB题就明显比有经验的学长交题慢了很多，导致自己D题只留了20分钟。这次比赛感觉AB题太水了，到了C题就难度陡升，花了一个多小时才做完。最后开D题发现居然比C题简单。。真是令人窒息的操作。不过后来凌晨三点出分居然Rank.2000还加了12分hhhhh……说点别的；寒假天天刷题到现在，虽然现在才发现自己很多基础算法之前学的不扎实，但是也在努力的填坑。现在的感觉就是算法竞赛，算法是其次。。最重要还是思维。不多废话了，以后也要坚持多写题解，15号之前一定要上蓝名！！加油，奥利给！！！！

A - Non-zero

• 题意: 有一数组，每次操作可以对该数组中任意一元素值+1，请问需要多少次操作才能使数组元素之和与之积不为 0 。

• 思路:

  1. 因为之积不能为0，所以输入的元素不能为0,故记录输入0的个数。
  2. 因为之和不能为0，所以判断相加是否为0，为0就输出0的个数+1。

int main()
{
	IOS;
	int T;
	cin >> T;
	while (T--)
	{
		int n;
		cin >> n;
		int q = 0, ans = 0;
		int temp;
		for (int i = 0; i < n; i++)
		{
			cin >> temp;
			if (temp == 0)
			{
				q++;
			}
			ans += temp;
		}
		if (ans + q == 0)
			cout << q + 1 << endl;
		else
			cout << q << endl;
	}
	return 0;
}

B - Non-zero

• 题意: 给定n，下面列出2n个元素的数组，然后将这2n个数分成两组，每组元素个数都是奇数个，两组元素个数可以不相等，所有元素都要被分配而且只能分到一个数组里，问怎么分配使这两个数组的中位数存在最小绝对值差。

• 思路: 将2n数组进行排序，下标编号是0~n-1，则两个数组最小中位数差的绝对值最小就是下标为n-1的元素减下标为n的元素的绝对值就是答案

int main()
{
	IOS;
	int T;
	vector<int> s;
	cin >> T;
	while (T--)
	{
		int n;
		cin >> n;
		int temp;
		for (int i = 0; i < 2 * n; i++)
		{
			cin >> temp;
			s.push_back(temp);
		}
		sort(s.begin(), s.end());
		int ans = s[n] - s[n - 1];
		if (ans < 0)
			ans *= -1;
		cout << ans << endl;
		s.clear();
	}
	return 0;
}

C - Anu Has a Function

• 题意: 给定一个数组，按照题目要求的算法函数f求出最大元素值，循环 f(f(…f(f(a1,a2),a3),…an−1),an) 直到算出最后一位元素值，问怎么排序原数组可以使这样求出的最后一位元素值最大。

• 思路:

1. 我们知道一个数（这里讨论正整数）都是以32位的二进制来表示的，比如11就是00000000000000000000000000001011 验证一下：从右边开始算：1 *2^0 + 1 * 2^1 + 0 * 2 ^ 2 + 1 * 2^ 3 = 1 + 2 +0 +8 =11(前面的好多0都可以不用算了），这道题目就是尽可能将高位（靠左边的）的0变成1，我们知道按位或 “|” 运算符就是取两者的最大并集，如0|0=0；1|0=1；1|1=1。

2. 我们可以开辟一个数组来存储32位上每位出现1的次数，然后从最高位开始遍历，如果这个位的1只有一次，我们把它调到最前面来运算，因为这样子我们可以最大上补齐32位码上空缺的1使新的元素尽可能最大，至于后面的数，顺便排序，因为他们位上有1已经对能等到最大元素值没有什么帮助了。

3. 由于当时AC的代码过于狗屎 于是用官方题解的思路回炉重造了一下

ll ans[55],a[100005],vis[100005];

int main()
{
	int n,i,j;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		vis[i]=1;
		for(j=0;j<=31;j++)
		{
			if((a[i] >> j)&1==1)
				ans[j]++;
		}
	} 
	for(i=31;i>=0;i--)
	{
		if(ans[i]-1==0)
		{
			for(j=1;j<=n;j++)
			{
				if((a[j] >> i)&1==1)
				{
					vis[j]=2;
					cout<<a[j]<<' ';
					break;
				}		
			}
			for(j=1;j<=n;j++)
				if(vis[j]==1)
					cout<<a[j]<<' ';
			return 0;
		}
	}
	for(j=1;j<=n;j++) cout<<a[j]<<' ';
	cout<<endl;
	return 0; 
}

D - Aerodynamic

• 题意: 给你n个点，将这n个点依次连线形成一个图形，问该图形是否中心对称。

• 思路:

  1. 写题解时心态又炸一次。。。真不该先做C啊 这题难度绝对是和AB一个水平- -
  2. 由于题目是逆时针给出n个点，所以先判断n是不是奇数，是奇数就输出no（当时就是这个特判没调试出来），否则只要枚举 点[i] 和 点[i+n/2] 的中点有没有变化就可以了（当时我都写出这个了啊啊啊）。

int n, a[100005], b[100005];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i] >> b[i];
	if (n % 2 == 1)
	{
		cout << "NO";
		return 0;
	}
	for (int i = 1; i <= n / 2; i++)
	{
		if (a[i] + a[n / 2 + i] != a[1] + a[n / 2 + 1] || b[i] + b[n / 2 + i] != b[1] + b[n / 2 + 1])
		{
			cout << "NO";
			return 0;
		}
	}
	cout << "YES";
}