cf1206解题报告
- A
- B
- C
- D
- E，F

cf1206解题报告

A

模拟

#include <bits/stdc++.h>

using namespace std;

int n,m,a[1010],b[12910];

int dsr[1111];

int main() {

	scanf("%d",&n);

	for(int i=1;i<=n;++i) scanf("%d",&a[i]),dsr[a[i]]=1;

	scanf("%d",&m);

	for(int j=1;j<=m;++j) scanf("%d",&b[j]),dsr[b[j]]=1;

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

		for(int j=1;j<=m;++j) {

			if(!dsr[a[i]+b[j]]) {

				cout<<a[i]<<" "<<b[j];

				return 0;

			}

		}

	}

	return 0;

}

B

普及dp,其实不用开数组

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int _=2e5+7;

ll n,a[_],b[_],f[_][2];

int main() {

	cin>>n;

	for(ll i=1,x;i<=n;++i) {

		cin>>x;

		a[i]=abs(x-1),b[i]=abs(x+1);

	}

	f[0][1]=100000000000000000LL;

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

		f[i][0]=min(f[i-1][0]+a[i],f[i-1][1]+b[i]);

		f[i][1]=min(f[i-1][1]+a[i],f[i-1][0]+b[i]);

	}

	cout<<f[n][0];

	return 0;

}

C

贪心，套路，构造

互相差1，那i和i+n+1就是相差1的。

根据样例可以这样构造。

\(a[1]=1,a[n+1]=2;\)

\(a[2]=2n,a[n+2]=2n-1;\)

\(a[3]=3,a[n+3]=4;\)

\(a[4]=2n-2,a[n+4]=2n-3;\)

\(…………\)

无解瞎猜偶数，很套路

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int _=2e5+7;

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

int main() {

	scanf("%d",&n);

	if(n%2==0) return puts("NO"),0;

	int l=1,r=n*2;

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

		if(i&1) {

			a[i]=l;

			++l;

			b[i]=l;

			++l;

		} else {

			a[i]=r;

			--r;

			b[i]=r;

			--r;

		}

	}

	printf("YES\n");

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

	for(int i=1;i<=n;++i) printf("%d ",b[i]);

	return 0;

}

D

这个题很容易想歪呀。

二进制的x位为1的数的个数有3个及其以上。

答案就是3，且没有比他再小的ans了。

首先先去掉没用的0。

剩下的数如果大于120的话，必定有上述情况。

因为每一个数至少包含一位。

然后范围缩小到100了。

暴力Floyd找最小环，学到了。

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int n,ans,dis[207][207],g[207][207];

std::vector<ll> a;

int main() {

	scanf("%d",&n);

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

		ll x;cin>>x;

		if(x) a.push_back(x);

	}

	n=a.size();

	if(n>=130) return puts("3"),0;

	memset(dis,0x3f,sizeof(dis));

	memset(g,0x3f,sizeof(g));

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

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

			dis[i][j]=g[i][j]=233;

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

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

			if(i==j) continue;

			if(a[i-1]&a[j-1]) dis[i][j]=g[i][j]=1;

		}

	}

	ans=200;

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

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

			for(int j=i+1;j<k;++j)

				ans=min(ans,dis[i][j]+g[j][k]+g[k][i]);

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

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

				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

	}

	if(ans==200) ans=-1;

	printf("%d\n",ans);

	return 0;

}

E，F

看见交互题就烦，虽然不是不能做。

算了，咕咕了。

巴特西

cf1206解题报告

cf1206解题报告

A

B

C

D

E，F

最新文章

热门文章