【算法】退役oier的重操旧业

Posted on by Nameless

前言

由于过于拙劣，离散数学老师要求我们用代码实现离散数学的一些题目，说白了就是oi题，程序设计也要求一些oi的东西。hgame2022出题人chuj也出了一道和spfa有关的题目，所以俺的oi之魂又被重新点燃。想着记录一下上大学（省二退役两年）之后新的oi进展。

但本人主要还是pwn，想跟着我搞oi那就大错特错了。

1.【2022/3/1】简单的逻辑表达式计算

题目

前置知识

二元运算符的表达式计算：建议百度一下前中后缀表达式

思路

之前做过一个四则运算的表达式计算，但是四则运算是二元的，题目有一个非运算不太好处理。当时改了很多次，和oi👴logging改了半天，全在改非运算。个人也是很满意自己对非运算的处理，大体上是没啥问题，就是卡在一些很烦人的细节上了。

首先是关于这些ABCD的未知数的处理，由于只有四个，所以博主偷懒使用了循环。但是如果遇上n个变量就不行了，只能用递归然后把生成的序列放入数组。开一个bool数组标记未知数的位置，那么在循环遍历整个算式的时候，我们就可以和经典做法一样用栈分开储存数和运算符了。

关键点

这题的关键就是对非运算的处理了。我的思路如下：

读到‘!’是只有两种情况，下一位是数字或者是括号

（1）如果！的下一位是数字，那么把数字先push然后再push一个-1
（2）如果！的下一位是‘（’，那么就把！入符号栈

相关代码：

            if(s[m]=='!') //对'!' 要特殊处理 
						{
							if(s[m+1]=='(') op.push(s[m]); 
							else 
							{
								if(s[m+1]=='A') num.push(i);
								else if(s[m+1]=='B') num.push(j);
								else if(s[m+1]=='C') num.push(k);
								else num.push(ll);
								num.push(-1);
								m++;
							}
            }

取数出来做运算：（试试!(!A))你就知道一个数之前可能不止一个-1了

int num_out()
{
	int ss=0,t;
    while(!num.empty() && num.top()==-1)
    {
		num.pop();
		ss++;
	}
	t=num.top();
	if(!num.empty()) num.pop();
	if(ss & 1) return !t;
	else return t; 
}

完整代码

#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
bool f[30000];
char s[30000];
stack<int> num;
stack<char> op; 

int num_out()
{
	int ss=0,t;
    while(!num.empty() && num.top()==-1)
    {
		num.pop();
		ss++;
	}
	t=num.top();
	if(!num.empty()) num.pop();
	if(ss & 1) return !t;
	else return t; 
}

int caculate(int a,int b, char c)
{
	if(c=='^') return (a && b);
	else if(c=='+') return (a || b);
	else if(c=='>') return ( !a || b);
	else return ((!a && !b) || (a && b));
	
}

void stack_init()
{
	while(!num.empty()) num.pop();
	while(!op.empty()) op.pop();
}

int yxj(char c)
{
	if(c=='^' || c=='+') return 4;
	else if(c=='>') return 3;
	else if(c=='-') return 2;
	return 1;
} 

int main()
{
	int n;
	cin>>n;
	if(scanf("%s",s+1)){};
	int l=strlen(s+1); 
	for(int i=1;i<=l;i++) 
	    if(s[i]>='A' && s[i]<='A'+n-1)
	       f[i]=1;
    if(n==1)
    {
        for(int i=0;i<=1;i++)

			{
				stack_init();//把栈都清空 
				for(int m=1;m<=l;m++)
				{
					if(f[m]) num.push(i); 
					
					else //如果是操作符 
					{                         
						if(s[m]=='!') //对'!' 要特殊处理 
						{ 
							if(s[m+1]=='(') op.push(s[m]); 
							else 
							{
								num.push(i);
								num.push(-1);
								m++; 
							}
						}
						else if(s[m]=='(') op.push(s[m]); //左括号直接入 
						else if(s[m]==')') //右括号的话直接计算左括号到右括号的所有值 
						{
							while(!op.empty() && op.top()!='(')
							{
								char c=op.top();
								op.pop();
								int b=num_out();
								int a=num_out();
								int res=caculate(a,b,c);
								num.push(res);
							}
							if(!op.empty()) op.pop();	
							if(!op.empty() && op.top()=='!')
							{
							   num.push(-1);
							   op.pop();	
							}
						} 
						else //如果是其它二元运算符 
						{
							if(op.empty()) op.push(s[m]) ; //如果符号栈为空那么直接入
							else 
							{
								while(!op.empty() && yxj(s[m])<=yxj(op.top()))
								{
									char c=op.top();
									op.pop();
								    int b=num_out();
								    int a=num_out();
									int res=caculate(a,b,c);
									num.push(res);
								}
								op.push(s[m]);
							}
						}
					}
				}
				
				while(!op.empty()) //如果符号栈不为空 
				{
					char c=op.top();
					op.pop();
					int b=num_out();
					int a=num_out();
					int res=caculate(a,b,c);
					num.push(res);
				}
				printf("%d %d\n",i,num_out());
			}		
	}
	
	else if(n==2)
	{
        for(int i=0;i<=1;i++)
            for(int j=0;j<=1;j++)
			{
				stack_init();//把栈都清空 
				for(int m=1;m<=l;m++)
				{
					if(f[m]) //如果是数字 
					{
					   if(s[m]=='A') num.push(i); 
					   else num.push(j); 
					}
					else //如果是操作符 
					{                         
						if(s[m]=='!') //对'!' 要特殊处理 
						{ 
							if(s[m+1]=='(') op.push(s[m]); 
							else 
							{
								if(s[m+1]=='A') num.push(i);
								else if(s[m+1]=='B') num.push(j);
								num.push(-1);
								m++;
							}
						}
						else if(s[m]=='(') op.push(s[m]); //左括号直接入 
						else if(s[m]==')') //右括号的话直接计算左括号到右括号的所有值 
						{
							while(!op.empty() && op.top()!='(')
							{
								char c=op.top();
								op.pop();
								int b=num_out();
								int a=num_out();
								int res=caculate(a,b,c);
								num.push(res);
							}
							op.pop();
							if(!op.empty() && op.top()=='!')
							{
							   num.push(-1);
							   op.pop();	
							}
						} 
						else //如果是其它二元运算符 
						{
							if(op.empty()) op.push(s[m]) ; //如果符号栈为空那么直接入
							else 
							{
								while(!op.empty() && yxj(s[m])<=yxj(op.top()))
								{
									char c=op.top();
									op.pop();
								    int b=num_out();
								    int a=num_out();
									int res=caculate(a,b,c);
									num.push(res);
								}
								op.push(s[m]);
							}
						}
					}
				}
				
				while(!op.empty()) //如果符号栈不为空 
				{
					char c=op.top();
					op.pop();
					int b=num_out();
					int a=num_out();
					int res=caculate(a,b,c);
					num.push(res);
				}
				
				if(num.top()==-1)
				{
					num.pop();
					int t=num.top();
		            num.pop();
		            num.push(!t);
				}
				printf("%d %d %d\n",i,j,num_out());
			}		
	}
	
	else if(n==3)
	{
        for(int i=0;i<=1;i++)
            for(int j=0;j<=1;j++)
                for (int k=0;k<=1;k++)
			{
				stack_init();//把栈都清空 
				for(int m=1;m<=l;m++)
				{
					if(f[m]) //如果是数字 
					{
					   if(s[m]=='A') num.push(i); 
					   else if(s[m]=='B') num.push(j);
					   else num.push(k);  
					}
					else //如果是操作符 
					{
						if(s[m]=='!') //对'!' 要特殊处理 
						{
							if(s[m+1]=='(') op.push(s[m]); 
							else 
							{
								if(s[m+1]=='A') num.push(i);
								else if(s[m+1]=='B') num.push(j);
								else if(s[m+1]=='C') num.push(k);
								num.push(-1);
								m++;
							}
						}
						else if(s[m]=='(') op.push(s[m]); //左括号直接入 
						else if(s[m]==')') //右括号的话直接计算左括号到右括号的所有值 
						{
							while(!op.empty() && op.top()!='(')
							{
								char c=op.top();
								op.pop();
								int b=num_out();
								int a=num_out();
								int res=caculate(a,b,c);
								num.push(res);
							}
							op.pop();
							if(!op.empty() && op.top()=='!')
							{
							   num.push(-1);
							   op.pop();	
							}
						} 
						else //如果是其它二元运算符 
						{
							if(op.empty()) op.push(s[m]) ; //如果符号栈为空那么直接入
							else 
							{
								while(!op.empty() && yxj(s[m])<=yxj(op.top()))
								{
									char c=op.top();
									op.pop();
								    int b=num_out();
								    int a=num_out();
									int res=caculate(a,b,c);
									num.push(res);
								}
								op.push(s[m]);
							}
						}
					}
				}
				
				while(!op.empty())
				{
					char c=op.top();
					op.pop();
					int b=num_out();
					int a=num_out();
					int res=caculate(a,b,c);
					num.push(res);
				}
			
				printf("%d %d %d %d\n",i,j,k,num_out());
			}		
	}
	
	else
	{
        for(int i=0;i<=1;i++)
            for(int j=0;j<=1;j++)
                for (int k=0;k<=1;k++)
                    for(int ll=0;ll<=1;ll++)
			{
				stack_init();//把栈都清空 
				for(int m=1;m<=l;m++)
				{
					if(f[m]) //如果是数字 
					{
					   if(s[m]=='A') num.push(i); 
					   else if(s[m]=='B') num.push(j);
					   else if(s[m]=='C') num.push(k);
					   else num.push(ll); 
					}
					else //如果是操作符 
					{
						if(s[m]=='!') //对'!' 要特殊处理 
						{
							if(s[m+1]=='(') op.push(s[m]); 
							else 
							{
								if(s[m+1]=='A') num.push(i);
								else if(s[m+1]=='B') num.push(j);
								else if(s[m+1]=='C') num.push(k);
								else num.push(ll);
								num.push(-1);
								m++;
							}
						}
						else if(s[m]=='(') op.push(s[m]); //左括号直接入 
						else if(s[m]==')') //右括号的话直接计算左括号到右括号的所有值 
						{
							while(!op.empty() && op.top()!='(')
							{
								char c=op.top();
								op.pop();
								int b=num_out();
								int a=num_out();
								int res=caculate(a,b,c);
								num.push(res);
							}
							op.pop();
							if(!op.empty() && op.top()=='!')
							{
							   num.push(-1);
							   op.pop();	
							}
						} 
						else //如果是其它二元运算符 
						{
							if(op.empty()) op.push(s[m]) ; //如果符号栈为空那么直接入
							else 
							{
								while(!op.empty() && yxj(s[m])<=yxj(op.top()))
								{
									char c=op.top();
									op.pop();
								    int b=num_out();
								    int a=num_out();
									int res=caculate(a,b,c);
									num.push(res);
								}
								op.push(s[m]);
							}
						}
					}
				}
				
				while(!op.empty())
				{
					char c=op.top();
					op.pop();
					int b=num_out();
					int a=num_out();
					int res=caculate(a,b,c);
					num.push(res);
				}
				
				printf("%d %d %d %d %d\n",i,j,k,ll,num_out());
			}		
	}
	return 0;
}

发表回复