A. Non-zero

题意

给出一段含有 $n$ 个数的序列 $a$ ,可以对其中任何数加一,问最少操作多少次让每一个数和序列和都不为0。


思路

输入的时候如果输入的是 $0$ 就将答案加一,最后如果序列和为 $0$ 的话答案加一。


代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

int t,n,sum,p,ans;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		sum=ans=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&p);
			if(p==0)
			{
				ans++;
				sum+=1;
			}
			else sum+=p;
		}
		if(sum==0) printf("%d\n",ans+1);
		else printf("%d\n",ans);
	}
}

B. Assigning to Classes

题意

将 $2n$ 个数分成个奇数序列,问两个奇数序列的中位数之差最小为多少。


思路

直接就将序列排序然后输出中间两个数之差即可。


代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

const int maxn = 100005;
int t,n,a[maxn<<1];
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		int p=n<<1;
		for(int i=1;i<=p;i++)
		{
			scanf("%d",&a[i]);
		}
		sort(a+1,a+1+p);
		printf("%d\n",abs(a[n]-a[n+1]));
	}
	return 0;
}

C. Anu Has a Function

题意

给出函数 $f: f(x,y)=(x|y)-y $ ,给出序列 $a$,序列 $a$ 中含有 $n$ 个数,可以表示为$[a_1,a_2\cdots,a_n ]$ ,定义 $x=f(f(…f(f(a_1,a_2),a_3),…a_{n-1}),a_n)$ ,你可以对序列 $a$ 中元素进行重排,求使得 $x$ 最大的序列 $a$ 。如果有多种情况,输出一种即可。

思路

  • 第一种思路是因为 $f(x,y)=(x|y)-y$ ,我们可以发现对于经过这样的运算之后,如果 $x$ 的某一位是1,如果 $y$ 的相应位是0,那么运算出来的 $f(x,y)$ 对应位就是1,如果 $y$ 对应位是1,那么运算出来就是0。那么对于 $x$ 的计算过程中的每一位这个规律都是适应的。因此我们只需要将位数从高到低依次扫一遍,如果这个位数为1的情况在序列所有元素中只出现了一次,那么就将唯一出现1的那个数放到第一位即可。

  • 第二种思路 $$ \because f(x,y)=(x|y) - y {\Longleftrightarrow} f(x,y) = x&({\sim} y) \therefore x=(a_1)&({\sim}a_2)&({\sim} a_3){\cdots}({\sim}a_n) $$ 我们发现后面其实都是可交换的,所以第一个只有第一个是起决定作用的,那么我们就可以处理一个前缀和后缀的 and 数组,这样我们就可以 $O(1)$ 的计算出后面那部分,然后遍历序列 $a$ 找到最合适的 $a_1$。

代码实现

第一种思路

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

const int maxn=100005;
int n,a[maxn],maxk;
int cnt;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		maxk=max(maxk,a[i]);
	}
	int p=1,k=0;
	while(p<=maxk)
	{
		k++;
		p<<=1;
	}
	for(int i=k;i>=0;i--)
	{
		cnt=0;
		for(int j=1;j<=n;j++)
		{
			if(a[j]&(1<<i))
			{
				cnt++;
				if(cnt==1) swap(a[j],a[1]);
			}
		}
//		printf("%d %d\n",i,cnt);
		if(cnt==1)
		{
			for(int j=1;j<=n;j++)
			{
				printf("%d ",a[j]);
			}
			return 0;
		}
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d ",a[i]);
	}
	return 0;
}

第二种思路

#include<cstdio>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iostream>

using namespace std;

const int maxn=100005;
int n,a[maxn];
int ans;
int pre[maxn],suf[maxn]; //pre is prefix,suf is suffix
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i]=~a[i];
		if(i==1) pre[i]=a[i];
		else pre[i]=pre[i-1]&a[i];
	}
	suf[n]=a[n];
	for(int i=n-1;i>=1;i--)
	{
		suf[i]=suf[i+1]&a[i];
	}
	for(int i=1;i<=n;i++)
	{
		int p=a[i];
		p=~a[i];
		if(i==1)
		{
			int now=suf[i+1]&p;
			ans=max(ans,now);
		}
		else if(i==n)
		{
			int now=pre[i-1]&p;
			if(now>ans)
			{
				swap(a[i],a[1]);
				ans=now;
			}
		}
		else 
		{
			int now=pre[i-1]&suf[i+1]&p;
			if(now>ans)
			{
				swap(a[i],a[1]);
				ans=now;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		printf("%d ",~a[i]);
	}
	return 0;
}

D. Aerodynamic

题意

给定一个凸多边形 $P$ 的所有顶点,可以将凸多边形沿向量 $(x,y)$ 平移,我们定义多边形 $T$ 是所有 $P$ 平移到与原点有交点后所构成的点集所形成的图形(我知道这句话有点绕,我实在是解释不明白,实在不行康康原题吧)。那么问这个 $T$ 是否是和 $P$ 相似的,如果是输出YES,不是输出NO。


思路

就是判断这个图形是不是中心对称图形就行了,证明还不会,暂且放一下,会了再写QAQ..


代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>

using namespace std;

const int maxn=100005;
int n;
int x[maxn],y[maxn];
bool check()
{
	int p=n/2;
//	printf("%d",p);
	int x1=x[1]+x[1+p];
	int y1=y[1]+y[1+p];
	for(int i=2;i<=p;i++)
	{
		if(x1!=x[i]+x[i+p]||y1!=y[i]+y[i+p])
		{
			return false;
		}
	}
	return true;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x[i],&y[i]);
	}
	if(n&1)
	{
		printf("NO");
	}
	else
	{
		if(check())
		{
			printf("YES");
		}
		else printf("NO");
	}
	return 0;
}