牛客练习赛87

A

题意：

备注：

思路：

排个序，每次把最后的两个相加，加k次之后输出中位数即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define js 
typedef long long ll;
#define o(x) cout<<#x<<" : "<<x<<endl
const int N=2000010;
ll a[N];

int main(){
    int T;
    cin>>T;
    while(T--){
        int n,k;
        cin>>n>>k;
        memset(a,0,sizeof a);
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        sort(a+1,a+n+1);
        for(int i=n-1,j=0;j<k;j++,i--){
            a[i]=a[i]+a[i+1];
        }
        n-=k;
        cout<<a[(n+1)/2]<<endl;
    }
}

B

题意：

给出长度为 的序列a1,a2,...,an{a_1,a_2,...,a_n}a1,a2,...,an，有多少对不同的整数对满足al,al+1,...,ar{k} x$ ?

思路：

比赛的时候真以为是主席树了，只过了50样例，然而并没有去观察题目的性质，这里看了一篇别人跟官方题解不一样的做法。

我们把小于 x 的数都记为 1 ；大于x的数都记为0，这样我们就可以采用前缀和计算出有多少个数比x小，所以我们查找这样的区间，

,,我们 从x的位置pos向右开始遍历，查找的个数，这个可以用map计数,查找。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200020;
#define int ll
int a[N],n,m,k,b[N];
map<ll,ll> mp;


signed main(){
    int x,pos=0;
    cin>>n>>x>>k;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        if(a[i]==x) pos=i;
        if(a[i]<=x) b[i]=1;
        else b[i] = 0; 
    }
    mp[0]++;
    for(int i=1;i<=n;i++){
        b[i]=b[i-1]+b[i];
        if(i<pos) mp[b[i]]++;
    }
    ll cnt=0;
    for(int i=pos;i<=n;i++){
        cnt+=mp[b[i]-k];
    }
    cout<<cnt<<endl;
    return 0;
}

C

记忆化搜索，

待补

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
unordered_map<ll,int>f;
vector<ll>v6,v9;
int F(ll n)
{
    if(n==0||f[n]) return f[n];
    f[n]=inf;
    int pos=upper_bound(v6.begin(),v6.end(),n)-v6.begin()-1;
    if(pos>=0)
        f[n]=min(f[n],F(n-v6[pos])+1);
    pos=upper_bound(v9.begin(),v9.end(),n)-v9.begin()-1;
    if(pos>=0)
        f[n]=min(f[n],F(n-v9[pos])+1);
    pos--;
    if(pos>=0)
        f[n]=min(f[n],F(n-v9[pos])+1);
    if(n<=5) f[n]=min(f[n],F(n-1)+1);
    return f[n];
}
int main()
{
    for(ll x=6;x<=1000000000000ll;x*=6) v6.push_back(x);
    for(ll x=9;x<=1000000000000ll;x*=9) v9.push_back(x);
    int t;scanf("%d",&t);
    while(t--)
    {
        ll n;scanf("%lld",&n);
        printf("%d\n",F(n));
    }
}