拼多多后端笔试题解 2023.3.12 附源码

T1 100/100

没啥好说的家人们

// 100 points
#include <bits/stdc++.h>
#define int long long
#define sc(a) scanf("%lld",&a)
#define pr(a) printf("%lld",a)
#define re(i,a,b) for(int i=a;i<=b;++i)
using namespace std;

string s,ss;

signed main() {
	cin>>s;
	int cnt=0;
	for(auto i:s) {
		if(isalpha(i)) {
			re(j,1,cnt) ss+=i;
			cnt=0;
		} else {
			cnt*=10;
			cnt+=(i-'0');
		}
	}
	cout<<ss;
	return 0;
}

T2 100/100

思路题，答案只跟1有关，消掉所有的1，其他全部一次解决

// 100 points
#include <bits/stdc++.h>
#define int long long
#define sc(a) scanf("%lld",&a)
#define pr(a) printf("%lld",a)
#define re(i,a,b) for(int i=a;i<=b;++i)
using namespace std;

int t,n;
int a[205];

void gao() {
	re(i,1,n) sc(a[i]);
	sort(a+1,a+1+n);
	int cnt=0;
	re(i,1,n) if(a[i]==1) ++cnt;
	int ans=cnt/2;
	if(cnt%2==1) --cnt;
	ans+=n-cnt;
	pr(ans);
	puts("");
}

signed main() {
	sc(t),sc(n);
	while(t--) gao();
	return 0;
}

T3 65/100

带权二分图匹配模板题，KM算法，把abc三类点扩展成300个点跑匹配即可，但是我实在背不住模板，写了个dfs溜了

// 65 points
#include <bits/stdc++.h>
#define int long long
#define sc(a) scanf("%lld",&a)
#define pr(a) printf("%lld",a)
#define re(i,a,b) for(int i=a;i<=b;++i)
using namespace std;

int n;
int mp[105][3];
char s[5];
int cnt[3],val[3];

int ans=0x3f3f3f3f;
int sum=0;
int pos=-1;

void dfs(int i) {
	if(sum>ans) return;
	pos=max(pos,i);
	if(i==n+1) {
		ans=min(ans,sum);
		return;
	}
	re(j,0,2)
		if(mp[i][j]&&cnt[j]>0) {
			--cnt[j];
			sum+=val[j];
			dfs(i+1);
			++cnt[j];
			sum-=val[j];
		}
}

signed main() {
	sc(n);
	re(i,1,n) {
		scanf("%s",s);
		re(j,0,strlen(s)-1) {
			if(s[j]=='A') mp[i][0]=1;
			else if(s[j]=='B') mp[i][1]=1;
			else if(s[j]=='C') mp[i][2]=1;
		}
	}
	re(i,0,2) sc(cnt[i]),sc(val[i]);
	dfs(1);
	if(ans!=0x3f3f3f3f) {
		puts("YES");
		pr(ans);
	}
	else {
		puts("NO");
		pr(pos-1);
	}
	return 0;
}

T4 100/100

平均数很简单，中位数的话要找一个动态有序且支持重复的数据结构，自然想到cpp的mutiset，在插入时维护一下中位数指针位置即可，关键代码在37-46行

// 100 points
#include <bits/stdc++.h>
#define int long long
#define sc(a) scanf("%lld",&a)
#define pr(a) printf("%lld",a)
#define re(i,a,b) for(int i=a;i<=b;++i)
using namespace std;

int n;
int a[200005];
int avg[200005];
int mid[200005];
multiset<int> s;

int gao(int a,int b) {
	double d=(double)a/b;
	int f=floor(d);
	if(d-f>0.4999999) return f+1;
	return f;
}

signed main() {
	sc(n);
	re(i,1,n) sc(a[i]);
	double sum=0;
	re(i,1,n) {
		sum+=a[i];
		avg[i]=gao(sum,i);
	}
	mid[1]=a[1],s.insert(a[1]);
	if(n>=2) mid[2]=gao(a[1]+a[2],2),s.insert(a[2]);
	auto p=s.begin();
	++p;
	re(i,3,n) {
		s.insert(a[i]);
		if(a[i]>=*p&&i%2==0) ++p;
		if(a[i]<*p&&i%2==1) --p;
		if(i%2==1) {
			mid[i]=*p;
		} else {
			auto q=p;
			--p;
			mid[i]=gao(*p+(*q),2);
			// if(i==5) cout<<*p<<' '<<*q<<endl;
			++p;
		}
	}
	re(i,1,n) pr(avg[i]),printf(" ");
	puts("");
	re(i,1,n) pr(mid[i]),printf(" ");
	return 0;
}