网站建设要什么证件,免费公司网页制作,自己的网站怎么做seo,php网站建设外国参考文献题目描述
明明进了中学之后#xff0c;学到了代数表达式。有一天#xff0c;他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式#xff0c;然后列出了若干选项#xff0c;每个选项也是一个代数表达式#xff0c;题目的要求是判断选项中哪些代数表达式…题目描述
明明进了中学之后学到了代数表达式。有一天他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式然后列出了若干选项每个选项也是一个代数表达式题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。
这个题目手算很麻烦因为明明对计算机编程很感兴趣所以他想是不是可以用计算机来解决这个问题。假设你是明明能完成这个任务吗
这个选择题中的每个表达式都满足下面的性质
表达式只可能包含一个变量 a。表达式中出现的数都是正整数而且都小于 1000010000。表达式中可以包括四种运算 加--减**乘^^乘幂以及小括号 (())。小括号的优先级最高其次是 ^^然后是 **最后是 和 --。 和 -- 的优先级是相同的。相同优先级的运算从左到右进行。注意运算符 --**^^ 以及小括号(()) 都是英文字符幂指数只可能是 11 到 1010 之间的正整数包括 11 和 1010。表达式内部头部或者尾部都可能有一些多余的空格。
下面是一些合理的表达式的例子
((a^1) ^ 2)^3a*aa-a((aa))9999(a-a)*a1 (a -1)^31^10^9………
输入格式
第一行给出的是题干中的表达式。
第二行是一个整数 n表示选项的个数。后面n行每行包括一个选项中的表达式。这 n 个选项的标号分别是 ,,,⋯A,B,C,D⋯
输入中的表达式的长度都不超过 5050 个字符而且保证选项中总有表达式和题干中的表达式是等价的。
输出格式
一行包括一系列选项的标号表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列而且之间没有空格。
输入输出样例
输入 #1复制
( a 1) ^2
3
(a-1)^24*a
a 1 a
a^2 2 * a * 1 1^2 10 -10 a -a输出 #1复制
AC
说明/提示
对于 30%30% 的数据表达式中只可能出现两种运算符 和 --对于其它的数据四种运算符 --**^^ 在表达式中都可能出现。对于 100%100% 的数据表达式中都可能出现小括号 (( 和 ))2≤≤262≤n≤26。
【题目来源】
NOIP 2005 提高组第四题 余观此题未生特殊代值之意徒有多项式运算之情。所以然者何变量单一形式有限假一数组以次数顺列系数则神形兼备功能俱全。遂写结构用重载。又用栈以计算。 说明白点就是直接拿个结构体用多项式每项前的系数存成一个数组来表示多项式然后通过重载运算符来支持多项式的各种运算。但这里有个问题就是a的最高次数可能远远超过10。事实上有一个测试点的数据就有
(a -6)^10^10所以多项式数组的大小不能只开到11。但这样的话这个数组岂不是要开的非常大然而既然可以用代特殊值的方法来做我以为算一下目标和结果的“较低”次数也可以管中窥豹略见一斑。即如果两个多项式在N次以内的系数都相等并且N足够大的时候也可以判定两个多项式是相等的。这里N取到100就可以过这题了也不会出现TLE的问题。这个题解之前没有考虑溢出的问题最近经过评论区提醒系数数组需要开long long。
但严格来说将系数对大数(如1e97)取模是更严谨的做法。这种做法另一个问题就是代码量比较大可能需要比较长的编码调试时间。这个思路主要优势是比较直观也容易想到。另外写的这个struct非常实用。print()稍微完善一下或者不完善因为也能看懂这已经可以用来做数学作业啦
(原题解发布于2018-09-242021-02-25更新
#includeiostream
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#includectime
#includevector
#includestack
#includestring
#define N 100
using namespace std; struct poly{long long p[N2];void clear(){memset(p, 0, sizeof(p));}poly operator (const poly b){this-clear();for (int i0; iN; i) p[i]b.p[i];return *this;}poly operator (const int b){this-clear();p[0]b;return *this;}poly operator (const poly b) const{poly c;for (int i0; iN; i){c.p[i]p[i]b.p[i];}return c;}poly operator- (const poly b) const{poly c;for (int i0; iN; i){c.p[i]p[i]-b.p[i];}return c;}poly operator* (const poly b) const {poly c;c.clear();for (int i0; iN; i){for (int j0; jN; j){if (ijN) continue;int kij;c.p[k]p[i]*b.p[j];}}return c;}poly pow(const poly b) const {//b must be an integer.int tb.p[0];poly ans; ans1;poly pas; pas(*this);while (t){if (t1) {ansans*pas;}paspas*pas;t1;}return ans;}void print(){for (int iN; i0; i--){if (p[i]0) continue;if (i!N) cout;coutp[i]a^i;}coutendl;}bool operator (const polyb) const {for (int i0; iN; i){if (p[i]!b.p[i]) return false;}return true;}};stackpoly s1;
stackchar s2;inline int f(char c){if (c^) return 3;if (c* ) return 2;if (c || c-) return 1;else return 0;
}inline void js(){poly a, b; char c;poly ans;bs1.top(); s1.pop();as1.top(); s1.pop();cs2.top(); s2.pop();if (c) ansab;if (c-) ansa-b;if (c*) ansa*b;if (c^) ansa.pow(b);s1.push(ans);
}const char L[18]0123456789-*^a();inline bool legal(char c){for (int i0; i17; i){if (cL[i]) return true; }return false;
}inline poly read(){string s;getline(cin, s);int lens.size();int judge0; bool ok1;if (s.empty()) ok0;for (int i0; ilen; i){if (s[i]() judge;if (s[i])) judge--;if (judge0) ok0;}if (judge0) ok0;if (!ok) {poly wrong; wrong.clear(); wrong.p[N1]1; return wrong;}//gets(s);bool flag0; int temp0; poly pt;poly a; a.clear(); a.p[1]1;for (int i0; ilen; i){char ns[i];if (!legal(n)) continue;if (na) {s1.push(a); continue;}if (n0 n9) {temp(temp1)(temp3)n-0; flag1; continue;}if (flag) {pttemp; s1.push(pt); temp0; flag0;}if (n() {s2.push(n); continue;}if (n)) {while (s2.top()!() js();s2.pop();continue;}while (!s2.empty() f(s2.top())f(n)) js();s2.push(n);}if (flag) {pttemp; s1.push(pt);}while (!s2.empty()) js();poly ress1.top();s1.pop();return res;//s1.top().print();
}int main(){poly aim; aimread();//aim.print();int n; scanf(%d\n, n); for (int i0; in; i){poly nowread();//now.print();if (nowaim) {char cAi; coutc;}}coutendl; return 0;
}
