bistuacm 2019年第四场新生训练赛题解
题目链接:https://vjudge.net/contest/293430#overview
A
知识点:模拟
题意:给一个数组,找出其中能被k整除的最小数a[i],输出k/a[i]即可。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,i,k;
cin>>n>>k;
int a[111];
for(i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
for(i=n-1;i>-1;i--)
if(k%a[i]==0){cout<<k/a[i];return 0;}
}
B
知识点:模拟
题意:两个数组a[n]和b[n]。第一个数组只能从前往后,第二个数组只能从后往前。只能在标记1的位置上车或下车。判断是否能从位置1到位置s。
解法:首先若第一个数组1号站点为0,直接输出NO即可(因为无法上车)。然后判断若a[s]为1,则输出YES(无需换乘)。之后寻找s后是否存在a[i]和b[i]同时为1的情况,若存在则可以换乘,输出YES,否则输出NO。
#include<bits/stdc++.h>
using namespace std;
int main(){
int i,n,k;
cin>>n>>k;
int a[1111],b[1111];
for(i=1;i<=n;i++)cin>>a[i];
for(i=1;i<=n;i++)cin>>b[i];
if(a[1]==0){cout<<"NO";return 0;}
if(a[k]==1){cout<<"YES";return 0;}
if(b[k]==1){
for(i=k+1;i<=n;i++)if(a[i]&&b[i]){cout<<"YES";return 0;}
}
cout<<"NO";
}
C
知识点:数论
题意:找到第n大的连续各数字之和为k的数(计算到k为个位数为止)。
解法:对各数字求和的操作不会改变其对9求余的值(因为(10^a -10^b)mod 9=0)。因此可以认为,n%9=k那么连续各数字之和一定为k。所以直接输出(n-1)*9+k即可。
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
long long n,k;
cin>>n>>k;
cout<<9*(n-1)+k<<endl;
}
}
D
知识点:贪心/排序
题意:找到给定数组a[n]的k个子数组,保证所有子数组能组成a,且每个子数组的最大值之和最大。
解法:直接求出前k大的值即可。可以用桶或者O(n^2)模拟。区间划分直接贪心就可以了(每次选区间到极大值,最后一个极大值持续到数组结束)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
int a[11111],b[11111]={0};
int i;
for(i=0;i<n;i++)cin>>a[i];
int m=0,m1=0;
int p=k;
while(k--){
m=0;
m1=0;
for(i=0;i<n;i++){
if(!b[i]){
if(a[i]>m){
m=a[i];
m1=i;
}
}
}
b[m1]=1;
}
int cnt=1,sum=0;
for(i=0;i<n;i++)sum+=a[i]*b[i];
cout<<sum<<endl;
for(i=0;i<n;i++){
if(!b[i])cnt++;
else{
p--;
if(p)cout<<cnt<<" ";
else cout<<cnt+n-i-1;
cnt=1;
}
}
}
#include<bits/stdc++.h>
using namespace std;
int a[222222];
long long sum1[222222];
long long sum2[222222];
int main(){
int n;
long long s=0;
int i;
cin>>n;
for(i=0;i<n;i++){
cin>>a[i];
sum1[i]=s+=a[i];
}
s=0;
for(i=n-1;i>=0;i--){
sum2[i]=s+=a[i];
}
int x1=0,x2=n-1,jud=0;
while(x1<n&&x2>=0){
if(sum1[x2]==sum2[x1]&&x1>x2){cout<<sum1[x2];return 0;}
if(sum1[x2]>sum2[x1])x2--;
else x1++;
}
cout<<0;
}
F
知识点:dp
题意:给定两个数组a[n]和b[n]。在保证i<j<k且a[i]<a[j]<a[k]的情况下,求b[i]+b[j]+b[k]的最小值。
解法:用一个dp数组维护第二个数选择a[j]的情况下,前两个数之和的最小值(记为dp[j])。之后再求出对于每个dp[i]而言,dp[i]+a[k]的最小值即可。
#include<bits/stdc++.h>
using namespace std;
int a[22222];
int b[22222];
int dp[22222];
int main(){
int n,i,j;
cin>>n;
for(i=0;i<n;i++)cin>>a[i];
for(i=0;i<n;i++)cin>>b[i];
for(i=0;i<n;i++)dp[i]=999999999;
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
if(a[i]<a[j])dp[j]=min(dp[j],b[i]+b[j]);
}
}
int sum=999999999;
for(i=0;i<n-1;i++){
for(j=i+1;j<n;j++){
if(a[i]<a[j])sum=min(sum,dp[i]+b[j]);
}
}
if(sum==999999999)cout<<-1;
else cout<<sum;
}