P1054 等价表达式
题目描述
明明进了中学之后,学到了代数表达式。有一天,他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。
这个题目手算很麻烦,因为明明对计算机编程很感兴趣,所以他想是不是可以用计算机来解决这个问题。假设你是明明,能完成这个任务吗?
这个选择题中的每个表达式都满足下面的性质:
1. 表达式只可能包含一个变量‘a’。 2. 表达式中出现的数都是正整数,而且都小于10000。 3. 表达式中可以包括四种运算‘+’(加),‘-’(减),‘’(乘),‘’(乘幂),以及小括号‘(’,‘)’。小括号的优先级最高,其次是‘’,然后是‘’,最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。(注意:运算符‘+’,‘-’,‘*’,‘^’以及小括号‘(’,‘)’都是英文字符) 4. 幂指数只可能是1到10之间的正整数(包括1和10)。 5. 表达式内部,头部或者尾部都可能有一些多余的空格。
下面是一些合理的表达式的例子:
((a^1) ^ 2)^3,aa+a-a,((a+a)),9999+(a-a)a,1 + (a -1)3,110^9……
输入输出格式
输入格式:
输入文件的第一行给出的是题干中的表达式。
第二行是一个整数n(2 <= n <= 26),表示选项的个数。后面n行,每行包括一个选项中的表达式。这n个选项的标号分别是A,B,C,D……
输入中的表达式的长度都不超过50个字符,而且保证选项中总有表达式和题干中的表达式是等价的。
输出格式:
输出文件包括一行,这一行包括一系列选项的标号,表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列,而且之间没有空格。
写完这道题我真想吐血十升。。。
写完这道题我真想吐血十升。。。
写完这道题我真想吐血十升。。。
两个点:
- 完美算法不好写,提供一些质数作为a的值代入计算即可
- 中缀表达式转后(前)缀表达式。
- 中缀表达式转后缀表达式
栈s1存数字或运算符,s2存运算符
从左至右扫描
数字进s1
运算符讨论
若s2栈顶优先级小于进来的,我们认为是合法的(想想为什么等于不行)
否则弹出s2到s1直到合法
括号要多一些判断
非完美算法的细节:
- 为了避免爆ll,要mod一个大质数。
质数不能太大,不然依旧会爆
也不能太小,不然负数模会出问题
(幸运数字1000000007)
不能每一步都膜,会很慢
a的取值要小,否则很可能要出问题
a的数量不能多不能少,否则很可能会出问题
总结:非完美算法要在看脸的基础上,多想想
code:
// luogu-judger-enable-o2
#include <cstdio>
#include <cstring>
#include <stack>
#define ll long long
using namespace std;
int n;
ll last[15],now[15];
int is[260];
ll pre[5]={5,7,11,2,3};
ll mod=1000000007;
char C[60];
void init()
{
for(int i='0';i<='9';i++)
is[i]=1;
is[int('(')]=2;
is[int('+')]=3;
is[int('-')]=3;
is[int('*')]=4;
is[int('^')]=5;
is[int(')')]=6;
is[int('a')]=7;
}
int cnt;
void read()
{
char c=getchar();
while(!is[c]) c=getchar();
cnt=-1;
while(c!='\r')
{
if(is[c])
C[++cnt]=c;
c=getchar();
}
}
struct node
{
int k;//符号1还是数字0
ll c;//数学或者AS码
node(){}
node(int k,ll c)
{
this->k=k;
this->c=c;
}
};
ll get_pow(ll n1,ll n2)
{
ll nn=1;
while(n2)
{
nn=nn*n1;
if(nn>=mod)
nn%=mod;
n2--;
}
return nn;
}
stack <node > s1,s2;
bool get(char *now,int cnt,int flag)
{
while(!s1.empty()) s1.pop();
while(!s2.empty()) s2.pop();
for(int k=0;k<=4;k++)
{
for(int i=0;i<=cnt;i++)
{
ll x=0;
char c=*(now+i);
if(is[c]==1)
{
while(is[c]==1&&i<=cnt) {x=x*10+c-'0';i++;c=*(now+i);}
node tt(0,x);
s1.push(tt);
i--;
}
else if(is[c]==7)
{
node tt(0,pre[k]);
s1.push(tt);
}
else if(is[c]==6)
{
while(!s2.empty())
{
if(s2.top().k&&is[s2.top().c]==2)
break;
s1.push(s2.top());
s2.pop();
}
if(s2.empty())
return false;
else
s2.pop();
}
else
{
node tt(1,c);
while(!s2.empty()&&is[s2.top().c]>=is[c]&&s2.top().c!='('&&c!='(')
{
s1.push(s2.top());
s2.pop();
}
s2.push(tt);
}
}
while(!s2.empty())
{
if(is[s2.top().c]==2)
return false;
s1.push(s2.top());
s2.pop();
}
while(!s1.empty())
{
s2.push(s1.top());
//printf("%d ",s1.top().c);
s1.pop();
}
//printf("\n");
while(!s2.empty())
{
node tt=s2.top();
s2.pop();
if(tt.k)
{
ll t1=s1.top().c;
s1.pop();
ll t2=s1.top().c;
s1.pop();
ll t3;
if(char(tt.c)=='+')
t3=t1+t2;
else if(char(tt.c)=='-')
t3=t2-t1;
else if(is[tt.c]==4)
{
t3=t2*t1;
if(t3>=mod)
t3%=mod;
}
else if(is[tt.c]==5)
t3=get_pow(t2,t1);
tt.c=t3;
tt.k=0;
s1.push(tt);
}
else
s1.push(tt);
}
int ttt=s1.top().c%mod;
if(flag)
last[k]=s1.top().c%mod;
else if(last[k]!=ttt)
return false;
s1.pop();
}
return true;
}
int main()
{
init();
read();
get(C,cnt,1);
char c=getchar();
n=0;
while(!is[c]) c=getchar();
while(c!='\r') {n=n*10+c-'0';c=getchar();}
for(int i=0;i<n;i++)
{
read();
if(get(C,cnt,0))
printf("%c",char(i+'A'));
}
return 0;
}
2018.4.29
洛谷 P1054 等价表达式 解题报告的更多相关文章
-
洛谷 P1054 等价表达式
洛谷 P1054 等价表达式 题目描述 明明进了中学之后,学到了代数表达式.有一天,他碰到一个很麻烦的选择题.这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式, ...
-
洛谷P1054 等价表达式
P1054 等价表达式 题目描述 明明进了中学之后,学到了代数表达式.有一天,他碰到一个很麻烦的选择题.这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的 ...
-
[NOIP2005] 提高组 洛谷P1054 等价表达式
题目描述 明明进了中学之后,学到了代数表达式.有一天,他碰到一个很麻烦的选择题.这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的要求是判断选项中哪些代数 ...
-
洛谷 P1783 海滩防御 解题报告
P1783 海滩防御 题目描述 WLP同学最近迷上了一款网络联机对战游戏(终于知道为毛JOHNKRAM每天刷洛谷效率那么低了),但是他却为了这个游戏很苦恼,因为他在海边的造船厂和仓库总是被敌方派人偷袭 ...
-
洛谷 P4597 序列sequence 解题报告
P4597 序列sequence 题目背景 原题\(\tt{cf13c}\)数据加强版 题目描述 给定一个序列,每次操作可以把某个数\(+1\)或\(-1\).要求把序列变成非降数列.而且要求修改后的 ...
-
洛谷1087 FBI树 解题报告
洛谷1087 FBI树 本题地址:http://www.luogu.org/problem/show?pid=1087 题目描述 我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全 ...
-
NOIP2005 等价表达式 解题报告
明明进了中学之后,学到了代数表达式.有一天,他碰到一个很麻烦的选择题.这个题目的题干中首先给出了一个代数表达式,然后列出了若干选项,每个选项也是一个代数表达式,题目的要求是判断选项中哪些代数表达式是和 ...
-
洛谷 [CQOI2015]选数 解题报告
[CQOI2015]选数 题目描述 我们知道,从区间\([L,H]\)(\(L\)和\(H\)为整数)中选取\(N\)个整数,总共有\((H-L+1)^N\)种方案. 小\(z\)很好奇这样选出的数的 ...
-
洛谷 P2444 [POI2000]病毒 解题报告
P2444 [POI2000]病毒 题目描述 二进制病毒审查委员会最近发现了如下的规律:某些确定的二进制串是病毒的代码.如果某段代码中不存在任何一段病毒代码,那么我们就称这段代码是安全的.现在委员会已 ...
随机推荐
-
HDU 4251 --- 主席树(划分树是正解)
题意:查询区间中位数 思路:模板题,相当于区间第K大的数,主席树可以水过,但划分树是正解.但还没搞明白划分树,先上模板 #include <iostream> #include <c ...
-
SDUT 2893-B(DP || 记忆化搜索)
B Time Limit: 1000ms Memory limit: 65536K 有疑问?点这里^_^ 题目描写叙述 有n块地板排成一条直线,从左到右编号为1,2,3. . . n-1,n,每 ...
-
LPCTSTR
LPCTSTR类型: L表示long指针 这是为了兼容Windows 3.1等16位操作系统遗留下来的,在win32中以及其他的32位操作系统中, long指针和near指针及far修饰符都是为了兼容 ...
-
AI学习---特征工程【特征抽取、特征预处理、特征降维】
学习框架 特征工程(Feature Engineering) 数据和特征决定了机器学习的上限,而模型和算法只是逼近这个上限而已 什么是特征工程: 帮助我们使得算法性能更好发挥性能而已 sklearn主 ...
-
[svc]linux紧急情况处理
如何判断 Linux 服务器是否被入侵? w-last-history top-lsof-strace netstat CPU利用率很高 800%爆了 netstat find 文件 查/etc/rc ...
-
写入与读取第三方的 cookie - P3P: CP=";CAO PSA OUR";
应用的场景是这样: 在 a.com 页面显示一个 来自b.com的一张图片 a.com/test.html 的内容: <img src=b.com/a.jpg> 但需求是,当用户访问 b. ...
-
pyinstaller打包pyqt文件(转)
pyinstaller打包pyqt文件 https://www.cnblogs.com/dcb3688/p/4211390.html 打包pyqt文件 如何将pyqt生成exe的二进制文件呢,p ...
-
【渗透测试学习平台】 web for pentester -5.代码执行
Example 1 http://192.168.106.154/codeexec/example1.php?name=".system('uname -a');// Example 2 h ...
-
Java File文件操作 创建文件\目录,删除文件\目录
Java手册 java.io 类 File java.lang.Object java.io.File 所有已实现的接口: Serializable, Comparable<File> p ...
-
20145327 实验四 Andoid开发基础
20145327 实验四 Andoid开发基础 安装Android Studio 安装过程出现未找到SDK的错误,只需在打开界面找到右下角的设置按钮,将路径设置为如下就可以运行.(默认安装路径) 设计 ...