当前位置： 移动技术网 > IT编程>开发语言>.net > 2020牛客暑期多校训练营(第五场)

2020牛客暑期多校训练营(第五场)

2020年07月26日  | 移动技术网IT编程  | 我要评论
2020牛客暑期多校训练营(第五场)(2020.7.25)D、Drop Voicing观察到若把ppp按顺时针排成一个环，每次执行第一种操作都不会改变元素的相对位置。因此在环上第一种操作可忽略不计。第二种操作对应到环上可理解为选定某元素pip_ipi​并不断按逆时针顺序和前一个元素交换。对于每个元素pip_ipi​，如果当前位置和升序排列中该元素的位置不同，只要进行一次操作就一定能保证能换到所要求的的升序排列中该元素所在的位置。所以只要枚举升序排列的起点位置，每次和给定的排列跑一遍最长公共子序列取最大值

2020牛客暑期多校训练营(第五场)(2020.7.25)

D、Drop Voicing

观察到若把pp按顺时针排成一个环，每次执行第一种操作都不会改变元素的相对位置。因此在环上第一种操作可忽略不计。第二种操作对应到环上可理解为选定某元素pip_i并不断按逆时针顺序和前一个元素交换。对于每个元素pip_i，如果当前位置和升序排列中该元素的位置不同，只要进行一次操作就一定能保证能换到所要求的的升序排列中该元素所在的位置。所以只要枚举升序排列的起点位置，每次和给定的排列跑一遍最长公共子序列取最大值，然后用长度减去最大值就是答案。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 510;
int dp[MAXN][MAXN] = {0};
int main()
{
    int n; scanf("%d", &n);
    int a[MAXN], b[MAXN];
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) b[i] = i;
    int ans = 0;
    for (int p = 1; p <= n; ++p)
    {
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j < n; ++j)
                if (a[i] == b[(p + j - 1) % n + 1]) dp[i][j + 1] = dp[i - 1][j] + 1;
                else dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i][j]);
        ans = max(ans, dp[n][n]);
    }
    printf("%d\n", n - ans);
    return 0;
}

E、Bogo sort

建一张nn个节点的图，从ii向pip_i连一条有向边。设环的大小为环中所包含的节点数，则该图中所有环大小的lcmlcm就是答案。每次置换都可以看成环中的元素向环的正向移动一位，那么当所有元素都回到原位时就是一个循环了。

要用高精。不会python，写了个C++的无高精版，交给队友转成Python。(%璇大师%)

import math
 
N = int(input())
a = []
vis = []
a.append(0)
p = list(map(int, input().split()))
 
for i in range(0, N):
    a.append(int(p[i]))
for i in range(0, N + 1):
    vis.append(0)
cycle = []
for i in range(1, N + 1):
    if vis[i] == 0:
        len = 1
        j = a[i]
        vis[i] = 1
        while j != i :
            len += 1
            vis[j] = 1
            j = a[j]
        cycle.append(len)
         
ans = 1
for i in cycle:
    ans = ans * i // math.gcd(i, ans)
 
ans = ans % (10 ** N)
print(int(ans))

F、DPS

模拟即可。

#include <bits/stdc++.h>
using namespace std;
int a[105];
int main()
{
    int n;
    scanf("%d", &n);int imax = 0;
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        imax = max(imax, a[i]);
    }
    for(int i = 0; i < n; i++)
    {
        long long s = ceil(50.0 * a[i] /imax);
        printf("+");
        for(int j = 0; j < s; j++) printf("-");
        printf("+\n");
        printf("|");
        if(a[i] == imax) {
            for (int j = 0; j < s - 1; j++) printf(" ");
            printf("*");
            printf("|");
        }
        else {
            for (int j = 0; j < s; j++) printf(" ");
            //printf("*");
            printf("|");
        }
        printf("%d\n",a[i]);
        printf("+");
        for(int j = 0; j < s; j++) printf("-");
        printf("+\n");
    }
}

I、Hard Math Problem

在2×22 \times 2的格子中，对角线上放G,EG,E能提供两格放HH的空间。考虑在无限大平面上斜着交错放置G,EG,E，那这一行斜线的上方和下方都可以放置HH。乍一看平均密度似乎是2/4=0.52/4=0.5，但实际上选择一个GG或EE，它的上方和下方一定都是HH。所以三个格子中有两个是HH，答案是2/3=0.666...2/3=0.666...

#include <bits/stdc++.h>
using namespace std;
int main()
{
    printf("%.6lf\n", (double)2 / 3);
    return 0;
}

赛后总结：

B题似乎是一个Trie树，不过还没学过，全员暴毙。知识点储备不足。

D题思路由璇大师提供。膜就完了。

E题这种题以前接触过，没有第一时间想到建图，我的锅。另外还需要储备高精板子。

F题模拟应该秒出，还是慢了。

I题思维不全面。

还是太菜了。

本文地址：https://blog.csdn.net/qq_36000896/article/details/107581513

您可能感兴趣的文章:

如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网