4.20 度小满笔试编程题 AK
更新:
度小满没给面试机会
但是这编程题还是有水平的,点个赞
======================
别的楼主整理的,感谢整理题目的楼主
第一题 AC
思路
单调队列
先找出每行每个长度为b小区间的最大值,填在小区间的最右侧
再用上面的数据
纵向找出每个长度为a的小区间的 (横向小区间最大值的) 的最大值,即为滑动窗口的最大值,累加到答案中
======================另一种解释==============
先横向扫描
设的最大值
每一个格子的都求出来,这里使用单调队列,时间复杂度
在对上面的max矩阵进行纵向扫描
计算
即为每一个滑动窗口 的最大值,累加起来即为答案
也是使用单调队列求出
时间复杂度
import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; import java.util.jar.JarOutputStream; /** * @Author: Shang Huaipeng * @Date: 2020/4/20 16:23 * @Version 1.0 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); int a=sc.nextInt(); int b=sc.nextInt(); long ans=0; int hang[][]=new int[n+1][m+1]; int que[]=new int[1000+10]; int front=0; int tail=0; for(int i=1;i<=n;i++){ front=0; tail=0; for(int j=1;j<=m;j++){ while(front<tail&&(i*que[tail-1])%10<=(i*j)%10)tail--; que[tail++]=j; while(front<tail&&(j-que[front]+1>b))front++; hang[i][j]=(i*que[front])%10; } } for(int i=b;i<=m;i++){ front=0; tail=0; for(int j=1;j<=n;j++){ while(front<tail&&hang[que[tail-1]][i]<=hang[j][i])tail--; que[tail++]=j; while(front<tail&&(j-que[front]+1>a))front++; if(j>=a){ // System.out.println(i+" "+j+" "+hang[que[front]][i]); ans+=1L*hang[que[front]][i]; } } } System.out.println(ans); } }
第二题 AC
就是个单源最短路问题,图是一个有向的完全图。
你品,你细细的品
那单源最短路问题,怎么办嘛,迪杰斯特拉呗。
迪杰斯特拉+堆优化
时间复杂度(不超过 n^2)时限3000MS
用时 1700MS
import java.util.*; import java.util.jar.JarOutputStream; /** * @Author: Shang Huaipeng * @Date: 2020/4/20 16:23 * @Version 1.0 */ public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n=sc.nextInt(); int a=sc.nextInt(); int b=sc.nextInt(); int c=sc.nextInt(); int[] ai = new int[n + 1]; for(int i=1;i<=n;i++){ ai[i]=sc.nextInt(); } boolean vis[]=new boolean[n+1]; long dis[]=new long[n+1]; Arrays.fill(dis,0x3f3f3f3f3f3f3f3fL); //计算答案的最大值就是 1直接到终点 long ans=a+(n-ai[1])*1L*c; dis[1]=0; //堆优化,不懂迪杰斯特拉+堆优化的建议先学一学 PriorityQueue<Node> que = new PriorityQueue<Node>(Comparator.comparingLong(o -> o.len)); que.add(new Node(1,0)); while(!que.isEmpty()){ Node node = que.poll(); if(node.cur==n){ ans=Math.min(ans,node.len); break; } if(vis[node.cur])continue;; vis[node.cur]=true; for(int i=2;i<=n;i++){ if(vis[i])continue; int cur=node.cur; long cost=0; if(ai[cur]<i){ cost=1L*(i-ai[cur])*c; } else cost=1L*(ai[cur]-i)*b; if(dis[i]>+node.len+cost+a){//迪杰斯特拉的松弛操作 //大于最大值,就不考虑了,剪枝策略 if(node.len+cost+a>=ans)continue; dis[i]=node.len+cost+a; que.add(new Node(i,dis[i])); } } } System.out.println(ans); } static class Node{ public Node() { } public Node(int cur, long len) { this.cur = cur; this.len = len; } int cur; long len; } }#度小满笔试##度小满##笔试题目#