翻车笔记_ Noip2005T4 等价表达式 [膜你, 栈(jian)]

大模拟总是让人做着恶心

来感受一下

Orz

懵逼的 题目

传送至 Vijos

扯淡的 题解

其实挺简单
设好运算符之间的优先级, 比如+- 是 1, */ 是 2, ^ 是3
然后设符号栈和数字栈xjb算. malao递归爆cena美滋滋
然后处理(), 遇到 ( 入栈(( 不算运算符), 遇到 ) 不入栈, 运算两个括号间的运算, 直到遇到 (
好啦程序主体就写完啦 然后就是不断的溢出和RE辣
emmmm总体来说就是a的代表数不能太大 比如虵的生日 否则溢出妥妥的…曾经试过取膜但是发现遇到减法的时候可能会出问题(一个大数可能正好是模数的倍数啥的反而比小数小)
所以a取3 这都能过数据真是水的一匹 不取膜就可以过辣

沙茶的 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <map>
#define HA (3)
#define MAXN (26 + 5)
#define OTZ (1000000007ll)
#define LL long long
const char out[MAXN] = { '0', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
using namespace std;
struct bds
{
LL ansx;
stack<LL> num;
stack<char> ys;
map<char, int> pori;
void init()
{
LL ans;
num.push(0);
ys.push('+');
int le;
le = 0;
pori['('] = 4; pori['-'] = 1; pori['+'] = 1; pori['*'] = 2; pori['/'] = 2; pori['^'] = 3; pori[')'] = 0;
ans = 0;
char srx = 0;
while(srx != '\n')
{
if (srx == ' ')
{
srx = getchar();
continue;
}
if (srx <= '9' && srx >= '0')
{
LL re = 0;
while(srx <= '9' && srx >= '0')
{
re *=10;
re += srx - '0';
srx = getchar();
}
num.push(re);
continue;
}
else if (srx == 'a')
{
num.push(HA);
}
else if (srx == '+' || srx == '-' || srx == '*' || srx == '/' || srx == '^')
{
if (ys.empty() || pori[srx] > pori[ys.top()])
{

ys.push(srx);

}
else
{
while (!ys.empty() && pori[srx] <= pori[ys.top()] && ys.top() != '(')
com();
ys.push(srx);
}
}
else if (srx == '(' || srx == ')')
{
if (srx == '(')
{
le++;
ys.push(srx);
}
else
{
if (le)
{
while(!ys.empty() && ys.top() != '(')
{
com();
}
if (!ys.empty())
ys.pop();
le--;
}
}
}
srx = getchar();
}
while(!ys.empty() && ys.top() != '(')
{
com();
}
ansx = ans = num.top();
// cout << ansx << endl;
}
void com()
{
LL y = num.top(); num.pop();
LL x = num.top(); num.pop();
LL dans;
char dqys = ys.top(); ys.pop();
switch(dqys)
{
case '+': dans = add(x, y); break;
case '-': dans = jian(x, y); break;
case '*': dans = che(x, y); break;
case '/': dans = dev(x, y); break;
case '^': dans = mpow(x, y); break;
}
num.push(dans);
}
LL add(LL x, LL y)
{
return (LL)(x + y) % OTZ;
}
LL jian(LL x, LL y)
{
return (LL)(x - y) % OTZ;
}
LL che(LL x, LL y)
{
return (LL)(x * y) % OTZ;
}
LL dev(LL x, LL y)
{
return (LL)(x / y) % OTZ;
}
LL mpow(LL x, LL y)
{
LL re = 1;
for (int i = 1; i <= y; i++)
{
re *= x;
re %= OTZ;
}
return re;
}

}a[MAXN], stda;
int n;
int main()
{
freopen("equal.in", "r", stdin);
freopen("equal.out", "w", stdout);
stda.init();
scanf("%d", &n);
getchar();
for (int i = 1; i <= n; i++)
{
a[i].init();
if (a[i].ansx == stda.ansx)
{
putchar(out[i]);
}
// puts("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}
//(8+a)^4-(8*a^3*8+2^3*a*8^3)
//a^4-4*a^3*8+6*a^2*8^2-4*a*8^3+8^4

By 终于学会删除线的 Cansult