Codeforces Round #695 (Div. 2)

比赛地址

A （水题）

题目：

给出\(n\)个面板，每个面板初始时间相同，每过1s面板上数字会加1（数字在\(0\sim9\)循环播放）,任意时刻选择一个面板\(x\)使他的时间停止，其他的面板\(y\)会在间隔\(|x-y|\)s以后停止，问从左到右顺序组成的数字序列所对应的十进制数最大值是多少？

解析：

只要最高位最大即可，因此首先需要最高位为9，那么次高位一定得是8，再次高位并不是7,因为可以在次高位为8时停止第二个面板构成989的序列

总结：

当\(n=1\)时，只输出9
当\(n\ne1\)时，输出\(98\)其余位模十加1即可

#include<bits/stdc++.h>

using namespace std;

int main()

{

	int T;

	scanf("%d", &T);

	while (T--)

	{

		int n;

		scanf("%d", &n);

		if (n == 1)

			printf("9\n");

		else

		{

			printf("98");

			int t = 8;

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

				printf("%d", t = (t + 1) % 10);

			printf("\n");

		}

	}

}

B （暴力）

题目链接

题目：

给出一个数组\(a\)，可以改变一次数组中某一元素的值，问数列\(a\)中最小的极值点个数是多少？

解析：

对于改变任意一个数而言，能够影响到的极值点的情况也只有自己或者左右的两个数据，而为了减小极值点数量，必然是使\(a[i]=a[i-1]\mid a[i]=a[i+1]\)两种情况，
这样便可以对已经是极值点的数据进行操作，并且暴力检查两种情况下缩减极值点数目的最大值即可

注意：可以对端点值进行复制，避免在遍历过程中对端点进行特判

#include<bits/stdc++.h>

using namespace std;

const int maxn = 3e5 + 5;

int dat[maxn];

int cnt;

bool check(int i)

{

	return dat[i] > dat[i - 1] && dat[i] > dat[i + 1] || dat[i] < dat[i - 1] && dat[i] < dat[i + 1];

}

int main()

{

	int T;

	scanf("%d", &T);

	while (T--)

	{

		cnt = 0;

		int n;

		scanf("%d", &n);

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

			scanf("%d", &dat[i]);

		dat[0] = dat[1], dat[n + 1] = dat[n];

		int mx = 0;

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

		{

			if (check(i))

			{

				++cnt;

				int t = dat[i], now = 0, aa = 0;

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

					now += check(j);

				dat[i] = dat[i - 1];

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

					aa += check(j);

				mx = max(mx, now - aa);

				aa = 0;

				dat[i] = dat[i + 1];

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

					aa += check(j);

				mx = max(mx, now - aa);

				dat[i] = t;

			}

		}

		printf("%d\n", cnt - mx);

	}

}

C （贪心+思维）

题目链接

题目：

给出三个数列，每次可以从两个数列中分别挑出两个数 \(a,b\) 并从原数列中删去，并将\(a-b\)放进第一个数列，问最后剩余的一个数最大是多少（其余两个数列为空）？

解析：

两种贪心策略

每次选出某一个序列的最小值，用这个最小值减去其他序列的”所有“（保留一个）值，再用保留值减去这个所选的序列中所有的值，最后剩余数的值=其他两个序列的值之和-2*选中序列的值
分别选出两个序列中的最小值，分别用各自的最小值减去另一个序列的除最小值以外的其他值，未选中序列的“所有”（保留一个）值被两个最小值中任意一个减去都可以，然后再用保留值减去这两个最小值进行了若干次操作后的结果，最后剩余数的值=除两个选中最小值的和-选中的最小值的和

总结：

\[result=sum-2\times\min(sum_{array},min_{ai},min_{aj})
\]

注意：要开long long

#include<bits/stdc++.h>

using namespace std;

LL mn[3] = { INF,INF,INF }, sum[3], t;

LL n[3];

int main()

{

	scanf("%d%d%d", &n[0], &n[1], &n[2]);

	for (int i = 0; i < 3; ++i)

	{

		while (n[i]--)

		{

			scanf("%lld", &t);

			sum[i] += t;

			mn[i] = min(mn[i], t);

		}

	}

	printf("%lld", sum[0] + sum[1] + sum[2] - 2 * min({ mn[0] + mn[1],mn[1] + mn[2],mn[0] + mn[2],sum[0],sum[1],sum[2] }));

}

巴特西

Codeforces Round #695 (Div. 2)

A （水题）

B （暴力）

C （贪心+思维）

最新文章

热门文章