2020牛客暑期多校训练营(第五场)解题报告DEFI
题目链接:https://ac.nowcoder.com/acm/contest/5670
D-Drop Voicing
题意:长度为n的排列,可以有两个操作。
第一个是Drop-2,就是把倒数第二个位置的元素移到第一个前面:a1a2a3a4->a3a1a2a4
第二个是Invert,就是把第一个位置的元素移到最后:a1a2a3a4->a2a3a4a1
问你进行几段连续的Drop操作可以使得这个排列是一个递增排列:1,2,3,4,...,n
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用这个置换规则变回本身最少需要几步?
样例解读:
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
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了。
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
上一篇: 2021年度十大网络用语发布
下一篇: 微信能直接打开淘宝抖音链接了
推荐阅读
-
2020牛客暑期多校训练营(第四场)——Basic Gcd Problem
-
2020牛客暑期多校训练营(第五场)
-
2020牛客暑期多校训练营(第九场) The Flee Plan of Groundhog
-
2020暑期牛客多校训练营第九场(K)The Flee Plan of Groundhog(lca,树形dp)
-
2020牛客暑期多校训练营(第二场)Cover the Tree
-
2020牛客暑期多校训练营(第一场)H-Minimum-cost Flow
-
2020牛客暑期多校 第一场 F Infinite String Comparision(字符串)
-
Harmony Pairs 2020牛客暑期多校训练营(第六场)
-
2020牛客暑期多校训练营(第五场)解题报告DEFI
-
I 1 or 2 2020牛客暑期多校第一场