欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

2020牛客暑期多校训练营(第五场)解题报告DEFI

程序员文章站 2022-04-02 20:42:08
题目链接:https://ac.nowcoder.com/acm/contest/5670目录D-Drop VoicingE-Bogo SortD-Drop Voicing题意:长度为n的排列,可以有两个操作。第一个是Drop-2,就是把倒数第二个位置的元素移到第一个前面:a1a2a3a4->a3a1a2a4第二个是Invert,就是把第一个位置的元素移到最后:a1a2a3a4->a2a3a4a1问你进行几段连续的Drop操作可以使得这个排列是一个递......

题目链接:https://ac.nowcoder.com/acm/contest/5670

 D-Drop Voicing

题意:长度为n的排列,可以有两个操作。

第一个是Drop-2,就是把倒数第二个位置的元素移到第一个前面:a1a2a3a4->a3a1a2a4

第二个是Invert,就是把第一个位置的元素移到最后:a1a2a3a4->a2a3a4a1

问你进行几段连续的Drop操作可以使得这个排列是一个递增排列:1,2,3,4,...,n 

2020牛客暑期多校训练营(第五场)解题报告DEFI

hint:可以将其看成一个钟表,Invert操作就是转动钟表,元素逆时针转。而Drop-2操作就是指针指向某个元素不动,其他的顺时针转,当Drop-2操作结束时,指针指向的元素固定,接下来可以随其他元素一起转动。其实就是将没在原有序排列位置的元素归位,一次只能归位一个,所以就是要求钟表上最长递增子序列长度,然后要调整的个数就是n-LIS 

AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int LIS(int *a,int n)
{
	int dp[N],len=0;
	for(int i=1;i<=n;i++)
	if(len==0||dp[len]<a[i])dp[++len]=a[i];
	else
	*(lower_bound(dp+1,dp+len+1,a[i]))=a[i];
	return len;
}
vector<int>v[N];
int main(){
    int a[N],b[N],c[N],ans=0;
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=b[i+n]=a[i];
    }
    for(int i=1;i<=n;i++){//滚动钟表n次
        int cnt=0;
        for(int j=i;j<=i+n-1;j++){
            c[++cnt]=b[j];
        }
        ans=max(ans,LIS(c,cnt));
    }
    printf("%d\n",n-ans);
    system("pause");
    return 0;
}

 E-Bogo Sort

题意:给一个长度为n的序列作为置换规则,问1,2,3,4,...,n用这个置换规则变回本身最少需要几步?

 2020牛客暑期多校训练营(第五场)解题报告DEFI

样例解读:

1 2 3 4 5 6通过{2 3 4 5 6 1}这个置换规则依次变成:

6 1 2 3 4 5

5 6 1 2 3 4 

4 5 6 1 2 3

3 4 5 6 1 2

2 3 4 5 6 1

1 2 3 4 5 6

所以最少需要6步

hint: 从一个数开始按照置换规则进行转移,在置换的过程中会形成一个环,环的循环周期就是环内的个数ci,然后求出所有ci的最小公倍数就是最少步数了,不过这里需要用到大数,题目要求对10^N次取模,其实没有这个必要,因为这个模式增长速度太快了,答案不可能超过他,所以没必要取模。

 Java代码:

import java.math.BigInteger;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] p=new int[123456];
		boolean[] vis=new boolean[123456];
		Scanner cin=new Scanner(System.in);
		int n=cin.nextInt();
		for(int i=1;i<=n;i++){
			p[i]=cin.nextInt();
		}
		BigInteger ans=BigInteger.ONE,l;
		for(int i=1;i<=n;i++){
			if(vis[i])continue;
			int len=0,t=i;
			while(!vis[t]){
				vis[t]=true;
				len++;
				t=p[t];
			}
			l=new BigInteger(String.valueOf(len));
			ans=ans.multiply(l).divide(ans.gcd(l));
		}
		System.out.println(ans);
	}

}

F-DPS

签到题。向上取整可以用ceil函数,也可以手动ceil不过要开long long 

2020牛客暑期多校训练营(第五场)解题报告DEFI

AC代码:

#include<bits/stdc++.h>
using namespace std;
int mx=-1;
void print(int x,int n){
    cout<<"+";
    for(int i=1;i<=x;i++)cout<<"-";
    cout<<"+\n|";
    for(int i=1;i<x;i++)cout<<" ";
    if(x)cout<<(mx==n?"*":" ");
    cout<<"|"<<n<<"\n+";
    for(int i=1;i<=x;i++)cout<<"-";
    cout<<"+\n";
}
int main(){
    int d[105],n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>d[i];
        mx=max(mx,d[i]);
    }
    for(int i=1;i<=n;i++){
        //print((50LL*d[i]+mx-1)/mx,d[i]);
        print(ceil(50.0*d[i]/mx),d[i]);
    }
    system("pause");
    return 0;
}

 I-Hard Math Problem

签到题。构造题,最优方案如下构造,取极限就是2/3了。 

2020牛客暑期多校训练营(第五场)解题报告DEFI

AC代码:

#include<iostream>
using namespace std;
int main(){
    double a=2.0/3;
    printf("%.6lf",a);
    return 0;
}

 

本文地址:https://blog.csdn.net/weixin_43911947/article/details/107591274

相关标签: 思维