美团2021校招技术综合-后台方向在线考试
不一样的逆序数
时问限制:3000MS
内存限制:589824KB
题目描述:
小团最丘对逆序数（将一个数字逐位逆序，例如1234的逆序数为4321）特别感兴趣。但是又觉得普通的逆序教问题有点太乏味
了。于是他想出了一个新的定义：如果一个数的4倍恰好是它的逆序数，那么称这两个数是新定义下的逆序对。
接下来给定一正整数n，问:不超过n的正整数中有多少对新定义下的逆序对?
输入格式
单组输入。输入一个整数n,n<1e7。
输出描述
第一行输出在不超过n的前提下有多少对逆序数，接下来每一行输出一对逆序数，以空格分隔。如果有多组逆序数，按照第一个数升序输出。
如果没有一对逆序数则直接输出0即可。
样例输入 10000
样例输出 1 2178 8712
思路：注意到本题的时间是3s，并且数据上限为1e7，用枚举法即可。这边提供一些优化思路：
A.首先如果一个数x和它的4倍互为逆序数，设x共有m位，则x*4<10^m(即互为逆序数的两个数的位数一定相同)。
B.采用生成的策略，由于有着4倍和逆序数的关系，我们可以知道，可以由一部分推知另一部分。以2178为例，我们首先设置两个指针L,R，L指向最高位，R指向最低为，每次产生的进位为c，开始的时候，L指向2，R指向8，c=0，8*4+c=32，产生进位3，而32%10==2，于是本次匹配成功，c=3，指针各向内移动一位，L指向1，R指向7，c=3，7*4+c=31，31%10==1，匹配成功。由此我们只需要枚举一半即可，再注意一下边界即可，当然还要考虑有没有可能位数是奇数的情况辣。不过注意本题给的时间，不要给自己找麻烦，。。=m=
#include<bits/stdc++.h>
using namespace std;bool match(int i,int j){int rever=0;while(j){rever=rever*10+j%10;j/=10;}return i==rever;
}int main(){int n,count=0;vector<int> ans; cin>>n;for(int i=1;i<=n;++i){if(match(i,i*4)){++count;ans.push_back(i);}}cout<<count<<endl;for(auto x:ans){cout<<x<<" "<<4*x<<endl;}return 0;
}
小团的旅行线路
时问限制:3000MS
内存限制:589824KB
题目描述:
小团是一个旅游爱好者，快要过春节了，他想统计一下，在过去的一年中他进行过几次旅行，于是他打开了美团app的订单记
录，记录显示了他的购买车票的记录。记录是按时间顺序给出的，已知一次旅行的线路一定是一个闭环，即起点和终点是同一
个地点。因此当每找到一段闭合的行程，即认为完成了一次旅行。数据保证不会出现不在闭环路径中的数据。
请你在小团的购票记录中统计出他全年共进行了多少次旅行？
输入描述
输入第一行包含一个正整数n，表示小团的购票记录数量。(1<=n<=10000)
接下来有n行，每行是两个长度不超过10的仅由小写字母组成的字符果S_a、S_b，表示购买了一张从S_a到S_b的车票。
输出描述
辅出仅包含一个整数。表示小团的旅行次数。
样例输入 6 beijing nanjing nanjing guangzhou guangzhou shanghai shanghai beijing fuzhou beijing beijing fuzhou
样例输出 2
思路：每一次旅行都是一个新起点，当重新回到这个起点的时候认为完成了一次旅行，统计次数即可。题意表示数据保证在旅行过程中的每一段，当前段的起点是上一段的终点。
#include<bits/stdc++.h>
using namespace std;int main(){int n,ans=0;string S_a,S_b,start="";unordered_set<string>::iterator iter;cin>>n;while(n--){cin>>S_a>>S_b;if(start==""){start=S_a;}if(S_b==start){++ans;start="";}}cout<<ans;
}
小团的配送团队
时问限制:3000MS
内存限制:589824KB
题目描述:
小团是美团外卖的区域配送负责人，众所周知，外卖小哥一般都会同时配送若干单，小团在接单时希望把同一个小区的单子放
在一起，然后由一名骑手统一配送。但是由于订单叠在一超的，所以，他归类订单时只能知道新订单和已有的某个订单的小
区是相同的，他觉得这样太麻烦了，所以希望你帮他写一个程序解决这个问题。
即给出若干个形如a b的关系，表示a号订单和b号订单是同一个小区的，请你把同一个小区的订单按照编号顺序排序，并分行
输出，优先输出最小的订单编号较小的小区订单集合。订单的编号是1到n。(可能存在同时出现a b和b a这样的关系，也有可能出
现a a这样的关系。
输入描述
输入第一行是两个正整改n、m，表示接变的订单数量和已知的关系数量。(1<=n,m<=10000)
接下来有m行，每行两个正整数a和b，表示a号订单和b号订单属于同一个小区(1<=a,b<=n):
输出描述
输出第一行包含—个整数x，表示这些订单共来目x个不同的小区。 接下来的输出包含x行，每行表示输出若干个订单编号，表示这些订单属于同一个小区，按照订单编号升序输出。优先输出最小的订单编号较小的小区。
样例输入 5 5 1 2 2 2 3 1 4 2 1 5
样例输出 1 1 2 3 4 5
思路：抽象题意后本题就是考察并查集，套模板即可。
#include<bits/stdc++.h>
using namespace std;int Rank[10010],Fa[10010];int Find(int x){if(Fa[x]==x)return x;return Fa[x]=Find(Fa[x]);
}void Union(int a,int b){//事实上在路径压缩的过程中Rank会变 int A=Find(a),B=Find(b);if(A!=B){if(Rank[A]>Rank[B]){Rank[A]++;Fa[B]=A;}else{Rank[B]++;Fa[A]=B;}}
}int main(){int n,m,i,a,b;vector<int> parties;cin>>n>>m;for(i=1;i<=n;++i){Fa[i]=i;Rank[i]=1;}for(i=1;i<=m;++i){cin>>a>>b;Union(a,b); }for(i=1;i<=n;++i){if(Fa[i]==i)parties.push_back(i);}cout<<parties.size()<<endl;for(auto part:parties){for(i=1;i<=n;++i){if(Fa[i]==part){cout<<i<<" ";}}cout<<endl;}
}
小团的车辆调度
时间限制: 400M5
内存限制: 655360K
小团是美团汽车租售公司的调度师，某个时刻A和B两地都向该公司提交了租车的订单，分别需要a和b辆汽车。此时，公司的所
有车辆都在外运营，通过北斗定位可以得到所有车辆的位置。小团分别计算了每辆车前往A地和B地完成订单的利润。作为一名精明的调度师，当然是想让公司的利润最大化了。 请你帮他分别选择a辆车完成A地任务，选择b辆车完成B地任务。使限公司获利量大每辆车最多只能完成一地的任备。
输入描述 输入第一行包含三个整数n,a,b。分别表示公司的车辆数量和A，B两地订单所需数量，保证a+b<=n.(1<=n<=2000)
接下来有m行，每行两个正整数x、y，分别表示该车完成A地任务的B地任务的利润。
输出描述 输出仅包含一个正整数，表示公司最大获得的利润和。
样例输入
5 2 2
4 2 3 3 5 4 5 3 1 5
样例输出 18
思路：要求将n辆车分配a辆至A，分配b辆至B，能够获得的利润。对于第i辆车来说，可以分配至A，可以分配至B，也可以不考虑它，分析后可以发现，这是一个背包问题。设dp[i][j][k]表示第i辆车，则可以得到转移方程如下： dp[i][[j][k]=max{dp[i-1][j-1][k]+A[i],dp[i-1][j][k-1]+B[i],dp[i-1][j][k]}; 同时考虑合法状态，则可知对于每一个合法状态dp[i][j][k]，则必定会有i>=j+k，故转移前需要考虑是否可以转移。
#include<bits/stdc++.h>
using namespace std;int dp[110][110][110];
int A[110],B[110];int main(){int n,a,b,i,j,k;cin>>n>>a>>b;for(i=1;i<=n;++i){cin>>A[i]>>B[i];}for(i=1;i<=n;++i){dp[i][1][0]=A[i];dp[i][0][1]=B[i];for(j=1;j<=n;++j){for(k=1;k+j<=i;++k){dp[i][j][k]=max(dp[i-1][j-1][k]+A[i],dp[i-1][j][k-1]+B[i]);if(i-1>=j+k)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);}}}cout<<dp[n][a][b];
}
优化：本题开三维数组的空间要求非常大， 可以采用滚动数组的方式。
#include<bits/stdc++.h>
using namespace std;int dp[2][1010][1010];
int A[1010],B[1010];int main(){int n,a,b,i,j,k;cin>>n>>a>>b;for(i=1;i<=n;++i){cin>>A[i]>>B[i];}for(i=1;i<=n;++i){dp[(i&1)^1][1][0]=A[i];dp[(i&1)^1][0][1]=B[i];for(j=1;j<=n;++j){for(k=1;k+j<=i;++k){dp[(i&1)^1][j][k]=max(dp[((i-1)&1)^1][j-1][k]+A[i],dp[((i-1)&1)^1][j][k-1]+B[i]);if(i-1>=j+k)dp[(i&1)^1][j][k]=max(dp[(i&1)^1][j][k],dp[((i-1)&1)^1][j][k]);}}}cout<<dp[(n&1)^1][a][b];
}
第五题：考试的学长口述的=-=，没有具体题目，这边给出抽象描述。
输入n、m，n表示装饰物种的最高价格，m表示装饰物的个数，且装饰物序列满足，后者的价格必须是前者的倍数(倍数从1倍开始)，也就是说，必须保证前后倍数的情况下，最右边的装饰物的价格必须保证<=n，求安排满足这种要求的装饰物序列的数量，结果对1e9+7取模。
思路：动态规划。dp[i][[j]表示第i个物品，价格为j时，前i个物品能构成的序列种数。于是我们可以推知：
#include<bits/stdc++.h>
using namespace std;int dp[2010][2010];
const int Mod=1e9+7;int main(){int n,m,i,j,k,ans=0;cin>>m>>n;//最高价格m 个数n for(j=1;j<=m;++j){dp[1][j]=1;}for(i=1;i<n;++i){for(j=1;j<=m;++j){for(k=1;k*j<=m;++k){dp[i+1][k*j]=(dp[i][j]+dp[i+1][k*j])%Mod;}}}for(j=1;j<=m;++j){ans=(ans+dp[n][j])%Mod;}cout<<ans;
}