2020牛客多校第五场DEI题解

F. DPS

签到。题意为将给定的数据用横向条形图画出来。

I. Hard Math Problem

题意

$n \times m$ 的网格，每个网格可以放置H、G、E中的一种，要求H旁边必须至少相邻一个G和E，求 当区域趋于无穷大时最大的放置H的数量。

解题思路

最开始想的交叉放置，这样最大利用率趋近 $\frac{1}{2}$ ，之后的思路是所有的区块都按照3*3放置，利用率是 $\frac{5}{9}$ 。但这两种方法都WA了。
正确思路：利用率达到最大时，每个G和E都被旁边的四个H利用，那么理想状态下，G:E:H=1:1:4，即结果为 $\frac{2}{3}$ 。

/*
GHHGHHGHHGHH
HHEHHEHHEHHE
HGHHGHHGHHGH
EHHEHHEHHEHH
*/

E. Bogo Sort

题意

有一个 $1 \sim n$ 的某个排列，给定一个变换序列p[i]，每次替换时将数组中每个元素a[i]替换成a[p[i]]。问最多替换多少次可以将原数组排列成 $1 \sim n$ 的顺序排列。

解题思路

求出每个数环的长度，结果则为环的长度的最小公倍数。结果用python表示，C++用不好会炸。

def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

def lcm(a, b):
    return (a//gcd(a, b)*b) % (10**n)

vis = [0]*200005
n = int(input())
num = [int(n) for n in input().split()]
cir = []
ans = 1
for j in num:
    if(vis[j] != 0):
        continue
    cir.clear()
    while(vis[j] == 0):
        vis[j] = 1
        cir.append(j)
        j = num[j-1]
    ans = lcm(ans, len(cir))
print(ans)

D. Drop Voicing

题意

有两种操作：
Drop-2: 把右数第二个数移至最左边。
Invert：环形旋转整个序列一位。
每一步可以进行单个操作任意次，求至少多少次后可以将原数组排列成 $1 \sim n$ 的顺序排列。

解题思路

网上有个题解思路写得很清楚。

花费1即连续的①相当于可以把倒数第二个往前移任意个位置。那么我们可以花费1经连续的①把倒数第二个往前的若干个数移到最前面，然后花费0经②把该的若干个数又移到最后面，所以可以等价于花费1可以把最后一个数移到前面任意两个数之间。

既然可以旋转任意多次，那么，多次Drop-2等价于将一个元素移至任意位置，多次Invert等价于旋转序列任意位。所以这道题即是求整个环形序列的最大上升子序列长度，结果就是n-ans。

// rotate函数用法
rotate(数组首地址, 旋转后数组首地址, 数组末地址);

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;

int dp[maxn], a[maxn];
int ans, n;

int fun(int n) {
    for(int i=0;i<=n;i++) dp[i]=1;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<i;j++) {
            if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1); 
        }
    }
    return dp[n];
} 

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) {
        ans = max(ans, fun(n));
        rotate(a+1,a+2,a+n+1);
    }
    printf("%d\n", n-ans);
}