CF #618 div.2

序

闲来无事，打场CF,本人蒟蒻，考场A了前三道，第四有解答

正文

T1 Non-zero

是道水题。。。。

给你一个序列a。要求你输出最少的操作次数使这个序列的累和与累乘都不为0；

一次操作指给\(a_i\)+1.

我们的想法是先给每个零的+1，检查此时和是否为0，若为0，+1，否则直接输出答案

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int Maxn=101;

int t,n,s,a[Maxn],sum;

int main() {

//	freopen("a.in","r",stdin);

	t=read();

	while(t--){

		n=read();s=0;sum=0;

		for(int i=1;i<=n;i++){

			a[i]=read();

			sum+=a[i];

		}

		for(int i=1;i<=n;i++) if(a[i]==0) s++,sum++,a[i]++;//��֤ a[i]��Ϊ0

		if(sum!=0) printf("%d\n",s);

		else printf("%d\n",s+1);

	}

	return 0;

}

我把快读删了。。。有-的

T2 Assigning to Classes

我们注意到，差值事实上是两个数之差，而这两个数都为子数组中的中位数，所以这两个数\(a\),\(b\)，不妨设\(a>b\) ,从而，\(a \ge p_{k+1}\),而\(b \le p_{k}\), 这是显然的。

从而，最小值之差即为\(p_{k+1}-p_{k}\),这是可以取到的

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int Maxn=2*1e5+111;

int t,a[Maxn],n;

int main() {

//	freopen("a.in","r",stdin);

	t=read();

	while(t--){

		n=read();

		for(int i=1;i<=2*n;i++) a[i]=read();

		sort(a+1,a+1+2*n);

		printf("%d\n",a[n+1]-a[n]);

	}

	return 0;

}

T3 Anu Has a Function

我们注意到，事实上对于\(f(i,j)<i\),从而进一步的讨论，把每一个数分解为二进制，如果这些数而二进制的某位上1的个数超过1，则这一位的答案一定为0，所以我们只需要从最高位开始扫，扫到某一位只有一个一即可

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int Maxn=1e5+111;

int r[50],a[Maxn],n;

bool s[Maxn][50];

int main() {

//	freopen("a.in","r",stdin);

	n=read();

	for(int i=1;i<=n;i++) {

		a[i]=read();

		int k=a[i];

		for(int j=0;k>0;j++){

			if(k&1) s[i][j]=1,r[j]++;

			k>>=1;

		}

	}

	int u=0;bool flag=1;

	for(int j=50;j>=0&&flag;j--)

		if(r[j]==1)

			for(int i=1;i<=n;i++)

				if(s[i][j]){

					u=i;

					flag=0;

					break;

				}

	if(u!=0) printf("%d",a[u]);

	for(int i=1;i<=n;i++) if(i!=u) printf(" %d",a[i]);

	return 0;

}

T4 Aerodynamic

我们可以推出再若在\(P(x_0,y_0)\)中有两点\((x_1,y_1)\),和\((0,0)\),则必有\(P(x_0-x_1,y_0-y_1)\) 包含两点\((0,0)\),\((-x_1,-y_)\),从而我们可以得到T一定是中心对称的，只要我们检查P是否具有中心对称性即可

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int Maxn=1e5+111;

double x[Maxn],y[Maxn];

int n;

int main() {

//	freopen("a.in","r",stdin);

	n=read();

	if(n&1){

		printf("No");

		return 0;

	}

	for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);

	x[n+1]=(x[1]+x[n/2+1])/2;y[n+1]=(y[1]+y[n/2+1])/2;n/=2;

	for(int i=2;i<=n;i++)

		if(x[2*n+1]!=((x[i]+x[i+n])/2)||y[2*n+1]!=((y[i]+y[i+n])/2)){

			printf("No");

			return 0;

		}

	printf("YES");

	return 0;

}

嵬

蒟蒻终能变为神犇

巴特西

CF #618 div.2

序

正文

T1 Non-zero

T2 Assigning to Classes

T3 Anu Has a Function

T4 Aerodynamic

嵬

最新文章

热门文章