220126总结

~~所以今天怎么上来就模拟赛~~

今日运势

~~然而我AK乐~~

~~然而今天是RE的一天（~~

模拟赛

今天的OIer：人生苦短，我用python（逃
一共交了26次，其中T3交了13次~~模拟赛的描述是“准确率”~~

表达式括号匹配（stack）

之前做过，本来想抢个第一个切掉但是手慢了QAQ

就比第一慢了12秒！比第二慢了不到5秒！！然后就第三个切掉了

因为只有圆括号，所以不开栈直接拿p模拟其实就行
括弧匹配检验（check）

因为有多种括号所以就开了个栈

左括号就入栈，右括号如果和栈顶括号同类的话就弹出
字符串匹配问题（strs）

【问题描述】

字符串只含有括号(),[],<>,{}，判断输入的字符串中括号是否匹配。如果括号有相互包含的形式，从内到外必须是<>,(),[],{}。例如，输入[()]，输出YES；而输入([]),([)])都应该输出NO

【输入格式】

第一行为一个整数n，表示以下有n个由括号组成的字符串。接下来的n行，每行都是一个由括号组成的长度不超过255的字符串。

【输出格式】

n行，每行都是YES或NO

非常离谱一直RE

之前是比较的字符，后来改成比较对应的数值来判断是否合格
计算（clac）

求表达式的值。（”/“用整数除法）

【输入格式】1行的1个算式

【输出格式】表达式的值

【样例输入】1+(3+2)*(7^2+6*9)

【样例输出】258

【数据范围】100%的数据满足：算式长度$\leqslant 30$，其中所有数据在$2^{31}-1$的范围内

这题可以说很恶心了

~~我觉得我堆出来了一座shit山~~

~~完了T4堆的shit山被发现了（变量名字：ppp，pppp；函数名：popp，topp……）~~

我的做法是先把中缀表达式专程后缀表达式再求值

重点就在转换（转换还是一道蓝题来着~~有时间把这道蓝题给过了~~）

转换出来后缀表达式拿栈计算就行
中缀表达式值（expr）

这道题拿T4代码改一下读入可以过3个点

固输NO可以过2个点

而且这五个点互不相同

~~人品检测——随机数大法计划通！虽然我最后没用随机数就是了~~

其实是在T4代码的基础上，添加一个判断函数

经过测试，括号应该是保证能匹配的

需要判断的是运算符的数量与运算数的数量关系

当然这在后缀表达式转换成中缀表达式之后也非常好办

前、中、后缀表达式

定义

顾名思义，前缀表达式就是~~缀在前面的表达式~~运算符在运算数前面的表达式

中、后缀表达式同理。
计算

前缀表达式一般用递归计算（遇上操作符就操作后两个数）

中缀表达式是人算（bushi

后缀表达式是用栈来算

互相转换

中缀转后缀

方法：遇到数字就输出，遇到操作符时，比较其与符号栈栈顶元素运算优先级，若栈顶元素优先级低则入栈，若栈顶元素优先级高于等于当前操作符，那么栈顶元素出栈，直到栈顶元素优先级低于当前操作符后，当前操作符入栈。
如果遇上括号，左括号直接入栈，遇上右括号需要将符号栈里面的栈顶元素依次弹出，直到遇到左括号为止。再将左括号出栈。
这里的输出/出栈，既可以指直接输出，也可以指暂时存储起来（存储可以用结构体，因为同时存在char和int型数据

//这段代码太恶心了我有空重写一下
//要是用到多于1个栈最好用STL的stack而不是手动模拟（手动模拟一个栈就需要配套三个函数）
#include<bits/stdc++.h>
using namespace std;

int st_[50];
int pppp = 0;
void popp(){pppp--;}
int topp(){return st_[pppp-1];}
void pushh(int a){st_[pppp++] = a;}

int ppp = 0;
char yunsuanfuS[50];
int p = 1;
struct DDD{
	int mo;
	int dt;
	char f;
}A[50];

void pop(){
	A[ppp].f = yunsuanfuS[p-1];
	A[ppp].mo = 0;
	ppp++;
	if(p == 0) return;
	p--;
}
void push(char f){yunsuanfuS[p++] = f;}
char top(){return yunsuanfuS[p-1];}

int level(char c){
	if(c == '+' || c == '-') return 1;
	if(c == '*' || c == '/') return 2;
	if(c == '^') return 3;
	if(c == '(') return -1;
	return -2;
}
bool cmp(char c){
	int t1 = 0;
	int t2 = 0;
	t1 = level(c);
	t2 = level(top());
	return t1>t2;
}
int yunsuan(int a,int b,char s){
	switch(s){
		case '+':{return a+b;break;}
		case '-':{return a-b;break;}
		case '*':{return a*b;break;}
		case '/':{return a/b;break;}
		case '^':{return pow(a,b);break;}
	}
}

int main(){
	char s[50];
	scanf("%s",s);
	yunsuanfuS[0] = ' ';
	int d = 0;
	for(int i = 0;i<strlen(s);i++){
		if(isdigit(s[i])){
			d++;
			if(i == strlen(s)-1){
				int dt = 0;
				for(int j = 0;j<1;j++){
					dt = dt + (s[i-j] - '0') * pow(10,j);
				}
				A[ppp].dt = dt;
				A[ppp].mo = 1;
				ppp++;
			}
		}else{
			if(d != 0){
				int dt = 0;
				for(int j = 0;j<d;j++){
					dt = dt + (s[i-j-1] - '0') * pow(10,j);
				}
				A[ppp].dt = dt;
				A[ppp].mo = 1;
				ppp++;
				d = 0;
			}
			char c = s[i];
			if(c == ')'){
				while(top()!='(') pop();
				p--;
			}
			else if(c == '('){
				push(c);
			}
			else if(cmp(c)) push(c);
			else{
				while(!cmp(c) && top()!='(') pop();
				push(c);
			}
			
		}
	}
	while(p!=1) pop();
	int r = 0;
	for(int i = 0;i<ppp;i++){
		if(A[i].mo){
			printf("%d ",A[i].dt);
			pushh(A[i].dt);
		}else{
			printf("%c ",A[i].f);
			int v = topp();
			popp();
			int u = topp();
			popp();
			
			pushh(yunsuan(u,v,A[i].f));
		}
	}
	return 0;
}

单调队列

就是元素严格单调的队列（
可以用来求区间最值

#include<bits/stdc++.h>
using namespace std;

const int M = 1000005;
int n,w;
int A[M],Q[M],ID[M];

void minquery(){
    int st = 0;
    int ed = 0;
    for(int i = 1;i<=w;i++){
        while(st<ed && Q[ed]>A[i]) ed--;
        ed++;
        Q[ed] = A[i];
        ID[ed] = i;
    }
    for(int i = w+1;i<=n;i++){
        while(st<ed && ID[st+1]<i-w) st++;
        printf("%d ",Q[st+1]);
        while(st<ed && Q[ed]>A[i]) ed--;
        ed++;
        Q[ed] = A[i];
        ID[ed] = i;
    }
    while(st<ed && ID[st+1]<n+1-w) st++;
    printf("%d\n",Q[st+1]);
}
void maxquery(){
    int st = 0;
    int ed = 0;
    for(int i = 1;i<=w;i++){
        while(st<ed && Q[ed]<A[i]) ed--;
        ed++;
        Q[ed] = A[i];
        ID[ed] = i;
    }
    for(int i = w+1;i<=n;i++){
        while(st<ed && ID[st+1]<i-w) st++;
        printf("%d ",Q[st+1]);
        while(st<ed && Q[ed]<A[i]) ed--;
        ed++;
        Q[ed] = A[i];
        ID[ed] = i;
    }
    while(st<ed && ID[st+1]<n+1-w) st++;
    printf("%d\n",Q[st+1]);
}
int main(){
    scanf("%d%d",&n,&w);
    for(int i = 1;i<=n;i++){
        scanf("%d",&A[i]);
    }
    minquery();
    maxquery();
    return 0;
}

今日代码