8.31 拼多多笔试

第一题

其实应该写应该while就行了，但是一开始写匈牙利做二分图匹配炸了，就写的有点崩

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10005;
int n,m,k,T;
int a[maxn],b[maxn];
int vis[maxn],match[maxn];
int main() {
    cin>>T;
    while(T--) {
        int ans1=0,ans2=0;
        cin>>n>>m>>k;
        for(int i=0;i<n;i++){cin>>a[i];}
        for(int i=0;i<m;i++){cin>>b[i];}
        sort(a,a+n);sort(b,b+m);
        int a1=0,b1=0;
        while(a1<n && b1<m) {
            if(b[b1]-k<=a[a1] && a[al]<=b[b1]+k) {
                b1++,a1++;
                ans1 ++;
            }
            else if(b[b1]-k>a[a1] ) a1++;
            else if(a[al]<b[b1]+k) b1++;
        }
        while(a2<n && b2<m) {
            if(a[a2]-k<=b[b2] && b[b2]<=a[a2]+k) {
                b2++,a2++;
                ans2 ++;
            }
            else if(a[a2]-k>b[b2]) b2++;
            else if(b[b2]>a[a2]+k)a2++;        
        }
        printf("%d\n",max(ans1,ans2));
    }

    return 0;
}

第二题

排序就不找了

第三题

推出来边长L的正方形需要2*L^2+2*L，然后懒得倒推，估计之后的部分数字不大

就直接模拟完事了。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10005;
int T;
#define ll long long
ll n;
int main() {
    cin>>T;
    while(T--) {
        cin>>n;
        if(n<4){
            printf("0\n");
            continue;
        }
        ll L = sqrt(n/2)-1;
        ll ans =  L*L;
        n -= 2*(L+1)*L;
        while(n>0) {
            if(n>=3)ans++,n-=3;
            else break;
            if(n>=2*L-2){
                ans +=L-1;
                n-=2ll*L-2;
            }
            else {
                ans+=n/2;break;
            }
            if(n>=3)ans++,n-=3;
            else break;
            if(n>=2*L){
                ans +=L;
                n-=2ll*L;
                L++;
            }
            else {
                ans+=n/2;break;
            }
        }
        printf("%lld\n",ans);
    }
    return 0 ;
}

第四题

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10005;
int T,n,a[maxn];
int f(int l,int r) {
    if(l==r)return 1;
    int minn = 1e9;
    for(int i=l;i<=r;i++)minn = min(minn,a[i]);
    for(int i=l;i<=r;i++)a[i]-=minn;
    int ans1 = minn ,lc=l,rc=l;
    while(lc<=r) {
        if(a[lc]==0)lc++;
        else {
            rc = lc;
            while(rc<=r &&a[rc]!=0)rc++;
            rc -- ;
            ans1+=f(lc,rc);
            lc = rc+1;
        }
    }
   // printf("L%d R%d %d %d\n",l,r,ans1,r-l+1);
    return min(ans1,r-l+1);
}
int main() {
    cin>>T;
    while(T--) {
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        int ans = f(1,n);
        printf("%d\n",ans);
    }

    return  0;
}

#拼多多笔试##拼多多##笔经#