为帮助大家能在6月18日的比赛中有一个更好的成绩,我会将蓝桥杯官网上的历届决赛题目的四类语言题解都发出来。希望能对大家的成绩有所帮助。
今年的最大目标就是能为【一亿技术人】创造更高的价值。
资源限制
内存限制:256.0MB C/C++时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s
#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;
}
#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;
}
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;
}
}
# -*- 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