HZNU Training 5 for Zhejiang Provincial Competition 2020

 

  Solved A B C D E F G H I J
  5/11   AC     AC AC AC AC    

 


ZOJ - 4104 
- H

题意:给你一个序列,每次可以把一个元素移到最前面,问你移几次使得序列单增。

解法:偏思维, 做法比较多;

其实比较一下两个序列就好了;

HZNU Training 5 for Zhejiang Provincial Competition 2020
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int N=1e5+5;
ll a[N],b[N];
int main(){
    int n, t;
    scanf("%d",&t);
    while(t--){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),b[i]=a[i];
    sort(b+1,b+1+n);
    int cnt=n;
    for(int i=n;i>=1;i--)if(b[cnt]==a[i])cnt--;
    printf("%d\n",cnt);
    }
  return 0;
}
View Code

G - G

 HDU - 6709

题意:钓鱼,每个鱼钓的时间为ti,煮鱼的时间为k;问你怎么分配,使得时间最少;

解法:偏思维;

在ai%k的时间里,有两种选择,1.干等着,2.去捉鱼。
干等着:时间被浪费;
去钓鱼:保证桶里有鱼。
可以想一下,如果时间最少,那么锅的利用效率肯定最高,尽量不要让锅闲着。
那么每次在 ai%k 的时间里,如果手里有鱼,那么干等着就行了,反正锅里的鱼煮熟以后还能再放鱼,锅不会闲着;
如果手里没有鱼,那这段时间就要去捉鱼,因为不能锅闲着。
记录一下在煮鱼的时间里能钓的鱼为x,那么n-x条鱼就需要另外花k来钓;
那么有x条鱼,煮这这些鱼的时候干等着就行了,剩下的n-x就需要去钓其他鱼。

HZNU Training 5 for Zhejiang Provincial Competition 2020
#include<cstdio>
#include<algorithm>
#include<queue>
#define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++)
#define per(i,j,k) for(int i=(int)k;i>=(int)j;i++)
#define pb push_back
using namespace std;
typedef long long ll;
ll a[200005];
int main(){
    int n,k,t;
    scanf("%d",&t);
    while(t--){
    scanf("%d%d",&n,&k);
    ll ans=k,cnt=0;
    rep(i,1,n){
    scanf("%d",&a[i]);
    ans+=a[i]/k*k;
//    cnt+=a[i]/k;
    a[i]%=k;
    }
    sort(a+1,a+1+n);
    ll x=ans/k;
    // if(x>n)x=n;
    x=min(x,n);
    ans+=(n-x)*k;
    for(int i=1;i<=x;i++)ans+=a[i];
    printf("%lld\n",ans);
    }    
    return 0;
}
View Code

F - F

 CodeForces - 1203E 

题意:一个序列,每个数可以+1,-1,不变。但始终>0,问你最后形成的最大集合的元素个数。

做法:这题比较简单,搞错了一点,WA了几发;

贪心时先check   ai-1,ai,ai+1;

要说也能明白,

HZNU Training 5 for Zhejiang Provincial Competition 2020
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=150001;
ll a[N];
set<ll>st;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
    if(a[i]-1>0&&st.find(a[i]-1)==st.end())st.insert(a[i]-1);
    else if(a[i]>0&&st.find(a[i])==st.end())st.insert(a[i]);
    else if(a[i]+1>0&&st.find(a[i]+1)==st.end())st.insert(a[i]+1);
    }
    int ans=st.size();
    cout<<ans<<endl;
    return 0;
}
View Code

 

上一篇:String Game---The 14th Jilin Provincial Collegiate Programming Contest


下一篇:Rolling The Polygon (2018-2019 ACM-ICPC, China Multi-Provincial Collegiate Programming Contest)(The