为帮助大家能在6月18日的比赛中有一个更好的成绩，我会将蓝桥杯官网上的历届决赛题目的四类语言题解都发出来。希望能对大家的成绩有所帮助。
今年的最大目标就是能为【一亿技术人】创造更高的价值。
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
C++
#include<stdio.h> #include<algorithm> #define N 100010 #define x first #define y second using namespace std; typedef pair<int,int> PIT; PIT req[N]; int ans[N]; int main() { int n,m; int i,j; int top; int p,q; int k,l,r; while(scanf("%d %d",&n,&m)==2) { top = 0; for(i=0;i<m;i++) { scanf("%d %d",&p,&q); if(!p) // 操作0 { while(top && req[top].x == 0) // 如果出现连续的0操作，则记录最大的操作范围 q = max(q,req[top--].y); while(top >= 2 && req[top-1].y <= q) // 如果当前操作的范围比上一次的操作范围大，则把上一次的0和1操作删除 top -= 2; req[++top] = {0,q}; // 保存最优的操作 } else if(top) //操作1 && 操作0已经进行过，因为第一个操作是1的话无意义 { while(top && req[top].x == 1) //如果是连续的1操作，则记录最大的操作范围 q = min(q,req[top--].y) ; // 因为是给后缀排序，q越小，操作的范围越大 while(top >= 2 && req[top-1].y >= q) top -= 2; req[++top] = {1,q}; } } k = n; l = 1; r = n; for(i=1;i<=top;i++) { if(req[i].x == 0) // 操作0 { while(l <= r && r > req[i].y) ans[r--] = k--; } else // 操作1 { while(l <= r && l < req[i].y) ans[l++] = k--; } if(l > r) break; } if(top % 2) // 操作1 { while(l <= r) ans[l++] = k--; } else // 操作0 { while(l <= r) ans[r--] = k--; } for(i=1;i<=n;i++) { printf("%d ",ans[i]); } printf("\n"); } return 0; }
C
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #define x first #define y second typedef struct{ int x; int y; }PII; const int N = 100010; int main() { int n, m; PII stk[N]; int ans[N]; int i , j ; scanf("%d%d", &n, &m); int top = 0; while (m -- ) { int p, q; scanf("%d%d", &p, &q); if (!p)//操作1 { while (top && stk[top].x == 0) q = fmax(q, stk[top -- ].y);//出现连续的操作1，我们取最大 while (top >= 2 && stk[top - 1].y <= q) //如果当前的操作1比上一次的操作1范围大，则将上一次操作1和操作2删除 top -= 2; PII num; num.x = 0; num.y = q; stk[ ++ top] = num;//存本次最佳操作 } else if (top)//操作2 &&且操作1已经进行过（操作二第一个用没效果） { while (top && stk[top].x == 1) q = fmin(q, stk[top -- ].y); while (top >= 2 && stk[top - 1].y >= q) top -= 2; PII num; num.x = 1; num.y = q; stk[ ++ top] = num; } } int k = n, l = 1, r = n; for (i = 1; i <= top; i ++ ) { if (stk[i].x == 0)//如果是操作1 while (r > stk[i].y && l <= r) ans[r -- ] = k -- ;//移动r值 ，并赋值 else while (l < stk[i].y && l <= r) ans[l ++ ] = k -- ; if (l > r) break; } if (top % 2) while (l <= r) ans[l ++ ] = k -- ; else while (l <= r) ans[r -- ] = k -- ; for (i = 1; i <= n; i ++ ) printf("%d ", ans[i]); return 0; }
Java
import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintStream; import java.io.PrintWriter; import java.io.StreamTokenizer; public class Main { public static void main(String[]args) throws IOException{ int n=in(); int m=in(); int[]sta=new int[m]; int cnt=0; while(m-->0){ int op=in(); int mid=in(); {//维护栈 if(op==0){ if(cnt%2!=op)//如果要放入的指令与栈中最后一个指令类型相同 { if(cnt-1>=0&&sta[cnt-1]<=mid)cnt--;//则进行第一轮比较，如果当前更大则弹出最后一个 else continue;//否则直接舍去当前指令，进入下一层循环 } while(cnt-2>=0&&sta[cnt-2]<=mid) cnt-=2;//循环弹出 }else{ if(cnt%2!=op)//如果要放入的指令与栈中最后一个指令类型相同 { if(cnt-1>=0&&sta[cnt-1]>=mid)cnt--;//则进行第一轮比较，如果当前更小则弹出最后一个 else continue;//否则直接舍去当前指令，进入下一层循环 } while(cnt-2>=0&&sta[cnt-2]>=mid) cnt-=2;//循环弹出 } sta[cnt++]=mid;//压入栈 } } int l=1; int r=n; int[] ans=new int[n+1]; //x从大到小，从外到内填数字 int x=n; for(int i=0;i<cnt;i++){ int mid=sta[i]; if(i%2==1){ mid=Math.min(r, mid); while(l<mid)ans[l++]=x--; } else { mid=Math.max(l, mid); while(r>mid)ans[r--]=x--; } if(r-l<1)break; } if(l<=r) if(cnt%2==1) { while(l<=r)ans[l++]=x--; }else { while(l<=r)ans[r--]=x--; } out.print(ans[1]); for(int i=2;i<=n;i++) { out.print(" "+ans[i]); } out.println(); out.flush(); } static StreamTokenizer in=new StreamTokenizer (new BufferedReader(new InputStreamReader(System.in))); static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); static int in() throws IOException{ in.nextToken(); return(int)in.nval; } }
Python
# -*- coding: utf-8 -*- read = lambda tp: map(tp, input().split()) def solve(): n, m = read(int) ops = [] for _ in range(m): p, q = read(int) if not p: while ops and ops[-1][0] == 0: q = max(ops.pop()[1], q) while len(ops) >= 2 and ops[-2][1] <= q: ops.pop(), ops.pop() ops.append([0, q]) elif ops: while ops and ops[-1][0] == 1: q = min(ops.pop()[1], q) while len(ops) >= 2 and ops[-2][1] >= q: ops.pop(), ops.pop() ops.append([1, q]) ans = [0] * (n + 1) k, l, r = n, 1, n for p, q in ops: if not p: while l <= r and r > q: ans[r] = k r -= 1 k -= 1 else: while l <= r and l < q: ans[l] = k l += 1 k -= 1 if l > r: break if len(ops) % 2: while l <= r: ans[l] = k l += 1 k -= 1 else: while l <= r: ans[r] = k r -= 1 k -= 1 print(*ans[1:], sep=' ') if __name__ == '__main__': while True: try: solve() except EOFError: break
