Codeforces Round #695 (Div. 2)
Codeforces Round #695 (Div. 2)
A. Wizard of Orz
B. Hills And Valleys
C. Three Bags
D. Sum of Paths
E. Distinctive Roots in a Tree
A. Wizard of Orz
B. Hills And Valleys
C. Three Bags
D. Sum of Paths
E. Distinctive Roots in a Tree
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] }));
}
版权声明：本文为DreamW1ngs原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。