文章目录

Codeforces Round656 Div3 [CF1385] 题解

于 由 5+1 发布

CF Round 656

比赛链接地址

A: Three Pairwise Maximums

$\color{red}入门-模拟$

题目翻译

给你3个质数 $x,y,z$ ，和他们的算法 $x = max (a,b); y = max (a,c); z = max (b,c)$ ，请你算出 $a,b,c$ 。

做法

  1. 如果 $x=y=z$ ，直接输出3个 $x$ 因为不管怎么样，当 $x=y=z$ 的时候做 $max$ 运算时，答案一定是 $x$ 或 $y$ 或 $z$
  2. 如果 $x=y$ 而且 $x(y)$ 最大，直接输出 $x,z,z$ ($a=x, b=y=c=z$)
  3. 如果 $x=z$ 而且 $x(z)$ 最大，直接输出 $y,x,y$ ($a=y, b=x=c=y$)
  4. 如果 $y=z$ 而且 $y(z)$ 最大，直接输出 $x,x,y$ ($a=x=b=x, c=y$)
  5. 否则直接输出 NO

Code

// CF 1385 A Three Pairwise Maximums

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int t, x, y, z, a, b, c;

int main (){
    scanf ("%d", &t);
    while (t --)
    {
        scanf ("%d%d%d", &x, &y, &z);
        if (x == y && x == z)
        {
            printf ("YES\n%d %d %d\n", x, x, x);
            continue;
        }
        if (x == y && x > z)
        {
            printf ("YES\n%d %d %d\n", x, z, z);
            continue;
        }
        if (x == z && x > y)
        {
            printf ("YES\n%d %d %d\n", y, x, y);
            continue;
        }
        if (y == z && y > x)
        {
            printf ("YES\n%d %d %d\n", x, x, y);
            continue;
        }
        printf ("NO\n");
    }
    return 0;
}

B: Restore the Permutation by Merger

$\color{red}入门-模拟/统计$

题目翻译

说白了就是给你含有 $n$ 个整数的数组 $a$ ，让你去数有多少个 $x$ ，而且保留它的位置。

做法

定义一个结构体 Count ，含有 int a int pos 。

  • $Count_a$ 表示这个数
  • $Count_{pos}$ 表示这个数的位置
struct Count
{
    int a, pos;
    bool operator < (const Count &a) const
    {
        return pos < a.pos;
    }
};

bool operator < (const Count &a) const; 是一个方便 $sort$ 快排的函数。

在每次输入时将 $x$ 放进 Count 结构体里，但是由于这个题的数会重复，所以放之前还得加一个判断 if (a[x].pos == 0)

排序后按顺序输出即可。

Code

// CF 1385 B Restore the Permutation by Merger

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

struct Count
{
    int a, pos;
    bool operator < (const Count &a) const
    {
        return pos < a.pos;
    }
};

int n, t, cnt;
Count a[105];

int main ()
{
    scanf ("%d", &t);
    while (t --)
    {
        scanf ("%d", &n);
        memset (a, 0, sizeof (a));
        cnt = 0;
        for (int i = 0; i < n * 2; i ++)
        {
            int x;
            scanf ("%d", &x);
            if (a[x].pos == 0)
            {
                a[x].pos = ++ cnt;
                a[x].a = x;
            }
        }
        sort (a + 1, a + cnt + 1);
        for (int i = 1; i <= cnt; i ++)
        {
            printf ("%d ", a[i].a);
        }
        printf ("\n");
    }
    return 0;
}

C: Make It Good

$\color{orange}普及-模拟/贪心$

题目翻译

有一个操作：给你一个数列，让你把最前面或最后面尽量小的数放到新的数列里，让这个新的数列满足 $a_i=a_{i-1}$

给你一个数列，让你从前面删掉几个数使上面的操作成立。

做法

咱们试试看

4 3 3 8 4 5 2

那么删掉前面 4 个数 4 3 3 8 就能使后面的 4 5 2 成立，因为通过上面那个操作能把 4 5 2 变成 2 4 5 。

左面的是原来的序列，右面的是新产生的数列。

[4 5 2] / []
[4 5] / [2]
[5] / [2 4]
[] / [2 4 5]

2 4 5 就是什么Good数列。

其实可以把像 4 5 2 这样的数列想象成 $4<=5>=2$ 即 $a_1<=...<=a_{i-1}<=a_{i}>=a_{i+1}>=...>=a_n$

所以这题用模拟指针的方法去做比较容易。

因为这个题要从前面往后面删除数，所以应该从后面开始算。

先用一个循环去算 $a_i$ 到 $a_n$ 之间，然后再用一个循环去算 $a_i$ 到 $a_{del}$ 之间（这里的 $del$ 代指的是要删除的位置后一个位置）

所以这两个循环就是这样的

while (n > 1 && a[n - 1] >= a[n]) -- n;
while (n > 1 && a[n - 1] <= a[n]) -- n;

上面说的 $del$ 其实就是现在这两个 while 之后算出来的 $n$ 。

Code

// CF 1385 C Make It Good

#include <iostream>
#include <cstdio>
using namespace std;
int t, n, a[200005];
int main ()
{
    scanf ("%d", &t);
    while (t --)
    {
        scanf ("%d", &n);
        for (int i = 1; i <= n; i ++)
            scanf ("%d", &a[i]);
        while (n > 1 && a[n - 1] >= a[n]) -- n;
        while (n > 1 && a[n - 1] <= a[n]) -- n;
        printf ("%d\n", n - 1);
    }
    return 0;
}

写在后面的话

  • 第三题的代码比前俩题都短一些
  • 第一题还是最简单
  • 有严重的语言障碍

暂无评论

发表评论