复旦大学2020考研机试题-编程能力摸底试题（A-E）数据结构与算法hyacinthhome的博客-

A.斗牛

给定五个0~9范围内的整数a1,a2,a3,a4,a5。如果能从五个整数中选出三个并且这三个整数的和为10的倍数（包括0），那么这五个整数的权值即为剩下两个没被选出来的整数的和对10取余的结果，显然如果有多个三元组满 和是10的倍数，剩下两个数之和对10取余的结果都是相同的；如果选不出这样三个整数，则这五个整数的权值为-1。

现在给定T组数据，每组数据包含五个0~9范围内的整数，分别求这T组数据中五个整数的权值。

【输入格式】

第一行一个整数T(1<=T<=1000)，表示数据组数。

接下来T行，每行5个0~9的整数，表示一组数据。

【输出格式】

输出T行，每行一个整数，表示每组数据中五个整数的权值。

【样例输入】

4

1 0 0 1 0

1 0 0 8 6

3 4 5 6 7

4 5 6 7 8

【样例输出】

2

-1

-1

0

5个数里面选3个，C53也就10种，实在不行暴力也可以，当然也可以用dfs

找到那就剪枝退出。

代码：

 #include <iostream> #include <cstdio> #include <cstring> using namespace std; int num[6],all,ans; bool vis[6]; bool finding; void dfs(int now,int start); int main() {     int t;     scanf("%d",&t);     while(t--)     {         memset(vis,0,sizeof(vis));         ans=-1;         finding=false;         for(int i=1;i<=5;i++) scanf("%d",&num[i]),all+=num[i];         dfs(0,1);         printf("%dn",ans);     } } void dfs(int now,int start) {     if(finding)         return ;     if(now==3)         {             int temp1=0,temp2=0;             for(int i=1;i<=5;i++)                 if(vis[i]) temp1+=num[i];             else                 temp2+=num[i];             if(temp1%10==0)                 finding=true,ans=temp2%10;             return ;         }     for(int i=start;i<=5;i++)     {         if(vis[i]) continue;         else         {             vis[i]=true;             dfs(now+1,i+1);             vis[i]=false;         }     } } 

B.打地鼠

给定n个整数a1,a2,…,an和 一个d，你需要选出若 干个整数，使得将这些整数从小到大 排好序之后，任意两个相邻的数之差都不 小于给定的d，问最多能选多少个数出来。

【输入格式】

第一行两个整数n,d(1<=n<=10^5,0<=d<=10^9)，分别表示整数个数和相邻整数差的下界。

第二行n个整数a1,a2,…,an(1<=ai<=10^9,1<=i<=n)，表示给定的n个整数。

【输出格式】

仅 一行一个整数，表示答案。

【样例输入】

6 2

1 4 2 8 5 7

【样例输出】

3

此题是个贪心，先将输入的数字排个序，贪心寻找只要间距大于等于d那就加上去

代码：

 #include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; vector<int> object; int main() {     int n,d,ans,now,num;     while(scanf("%d%d",&n,&d)!=EOF)     {         object.clear();         now=0;         ans=1;         for(int i=0;i<n;i++)             scanf("%d",&num),object.push_back(num);         sort(object.begin(),object.end());         for(int i=1;i<object.size();i++)             {                 if(object[i]-object[now]>=d)                     ans++,now=i;             }         printf("%dn",ans);     } } 

C.排队打饭

下课了，有n位同学陆续赶到食堂进行排队打饭，其中第i位同学的到达时间为ai，打饭耗时为ti，等待时间上限为bi，即如果其在第ai+bi秒的时刻仍然没有轮到他开始打饭，那么他将离开打饭队列另寻吃饭的地 。问每位同学的开始打饭时间，或者指出其提前离开了队伍（如果这样则输出-1）。

【输入格式】

第一行一个整数n(1<=n<=10^5)，表示来打饭的同学数量。

接下来n ，每行三个整数ai,ti,bi(1<=ai,ti,bi<=10^9,1<=i<=n)，分别表 每位同学的到达时间、打

饭耗时、等待时间上限。

保证a1<a2<…<an

【输出格式】

n个整数，表 每位同学的开始打饭时间或者-1（如果该同学提前离开了队伍）。

【样例输 】

4

1 3 3

2 2 2

3 9 1

4 3 2

【样例输出】

1 4 -1 6

因为输入就是ai<a(i+1)所以都不需要排序了，直接模拟顺序处理，记录当前时间time

如果time大于这个同学最后等待时间那就输出-1，否则取time和他到达食堂时间的最大值。

模拟就可以了

代码：

 #include <iostream> #include <cstdio>  using namespace std; const int maxn=1e5+100; int a[maxn],b[maxn],c[maxn]; int main() {     int n,time;     while(scanf("%d",&n)!=EOF)     {         for(int i=1;i<=n;i++)             scanf("%d%d%d",&a[i],&b[i],&c[i]),c[i]=a[i]+c[i];         time=a[1];         for(int i=1;i<=n;i++)         {             if(i!=1)                 printf(" ");             if(time>c[i]) printf("-1");             else             {                 printf("%d",max(time,a[i]));                 time=max(time,a[i])+b[i];             }         }         printf("n");     }     return 0; } 

【样例输入】

5

2 3 5 1 4

【样例输出】

2 0 2 5 3

一开始直接建树，等到5点左右系统恢复提交tle，才想起n=1e5退化成链的时候就成O(n^2)了

后来换了个区间最值查询的方法，我用的线段树，写完的时候都不能提交了（也不知道能否ac），不过时间复杂度O(n*logn)应该差不多了

大致方法是这样的比如 5个点，2，3，5，1，4，从左往右循环，遇到2了，然后查询值为1到（2-1）的这些节点里面第一个出现的点，这里是1，那么father[1]=2,然后标记vis[1]=true;并且更新线段树，time[1]=INF，再查询(2+1)到5这里找出来是3，那么father[3]=1,然后标记vis[3]=true;接下来i=2，节点值是3，由于i点和找出来的左右节点都找出来了，所以都标记vis和更新。查询1到2 （因为节点值1和2都已经标记了，所以节点值3没有左子树），接下来找（4-5）返回了5，因为5出现在4前面，

于是father[5]=3,然后标记3和5（更新vis和更新线段树），然后i=3，值为5，查询1到4，这里1,2,3都标记过了只有4，所以father[4]=5,再查询6到5（当然是没有的，所以结点值5没有右子树），到此为止，所有点都标记了，循环后面也不会更新father了。

这个代码有误的话欢迎指出！

代码：

 #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn=1e5+100; int time[maxn]; int num[maxn]; const int INF=0x3f3f3f3f; struct Segtree {     int val; }; Segtree tree[maxn*5]; bool vis[maxn]; int father[maxn]; void build(int root,int l,int r); void update(int root,int l,int r,int index,int val); int query(int root,int l,int r,int ql,int qr); int main() {     int n;     time[0]=INF;     while(scanf("%d",&n)!=EOF)     {         for(int i=1;i<=n;i++) scanf("%d",&num[i]),time[num[i]]=i;         build(1,1,n);         memset(vis,0,sizeof(vis));         memset(father,0,sizeof(father));         for(int i=1;i<=n;i++)         {             vis[num[i]]=true;             int now1=query(1,1,n,1,num[i]-1);             int now2=query(1,1,n,num[i]+1,n);             if(now1&&!vis[now1])             father[now1]=num[i],update(1,1,n,now1,INF),vis[now1]=true;             if(now2&&!vis[now2])             father[now2]=num[i],update(1,1,n,now2,INF),vis[now2]=true;             update(1,1,n,num[i],INF);         }         for(int i=1;i<=n;i++)         {             if(i!=1) printf(" ");             printf("%d",father[i]);         }         printf("n");     }     return 0; } void build(int root,int l,int r) {     if(l==r)         tree[root].val=l;     else     {         int mid=(l+r)/2;         build(root*2,l,mid);         build(root*2+1,mid+1,r);         tree[root].val=time[tree[root*2].val]<time[tree[root*2+1].val]?tree[root*2].val:tree[root*2+1].val;     } } int query(int root,int l,int r,int ql,int qr) {     if(qr<l||ql>r)         return 0;     if(ql<=l&&qr>=r)         return tree[root].val;     int mid=(l+r)/2;     int now1=query(root*2,l,mid,ql,qr);     int now2=query(root*2+1,mid+1,r,ql,qr);     return time[now1]<time[now2]?now1:now2; } void update(int root,int l,int r,int index,int val) {     if(l==r)         time[tree[root].val]=val;     else     {         int mid=(l+r)/2;         if(index<=mid)             update(root*2,l,mid,index,val);         else             update(root*2+1,mid+1,r,index,val);         tree[root].val=time[tree[root*2].val]<time[tree[root*2+1].val]?tree[root*2].val:tree[root*2+1].val;     } } 

仅一行一个整数，表示答案。

【样例输入 】

6

1 4 2 8 5 7

【样例输出】

11

【解释】

A数组是[142857]

B数组可以是[344556]。

权值为|A_i-B_i|(1<=i<=n)之和加上(B_j-B_j+1)^2(1<=j<n)之和。

权值第 部分|A_i-B_i|(1<=i<=n)之和为：

|1-3|+|4-4|+|2-4|+|8-5|+|5-5|+|7-6|=2+0+2+3+0+1=8

权值第 部分(B_j-B_j+1)^2(1<=j<n)之和为：

(3-4)^2+(4-4)^2+(4-5)^2+(5-5)^2+(5-6)^2=1+0+1+0+1=3

所以总权值为8+3=11。

分析：

思考下，对于b数组每个值的选取对答案的贡献是什么？？其实只有前

一个把，因为贡献只不过是加上它和它前一个值的差值的平方，和它和A数组对应位置的

差值绝对值，所以咱们就维护一个now数组,now[i]表示的是当前结束的B的这个

位置值为i，那么更新就需要前一个位置的0-9种情况取最优，那么复杂度就是

O(10*10*n)，n=1e5,那么差不多1秒内了

代码：

 #include <iostream> #include <cstdio> #include <cstring> using namespace std; int tp1[10][10],tp2[10][10]; int now[10],now_temp[10];  //目前结尾为i的最小函数值，复杂度O(n*10*10)约等于1e7，差不多一秒 const int INF=0x3f3f3f3f; void init(); int main() {     int n,num;     init();     while(scanf("%d",&n)!=EOF)     {         memset(now,0,sizeof(now));         for(int i=0;i<n;i++)         {             scanf("%d",&num);             for(int j=0;j<10;j++)             {                 int temp=INF;                 for(int k=0;k<10;k++)                 {                     int tp;                     if(i)                         tp=now[k]+tp1[j][num]+tp2[j][k];                     else                         tp=now[k]+tp1[j][num];                     if(tp<temp) temp=tp;                 }                 now_temp[j]=temp;             }             for(int i=0;i<10;i++) now[i]=now_temp[i];         }         int ans=INF;         for(int i=0;i<10;i++)             ans=min(ans,now[i]);         printf("%dn",ans);     }     return 0; } void init() {     for(int i=0;i<10;i++)     for(int j=0;j<10;j++)     {         tp1[i][j]=i<j?(j-i):(i-j);         tp2[i][j]=(i-j)*(i-j);     } } 

题不算很难，细节很重要！