Solution - CF7E Defining Macros

Posted on Edited on

原题链接CF7E Defining Macros

这个黑题感觉好像不是很黑

1.理解题意

输入 n 个 #define 语句，然后给一个表达式，让你判断该表达式是不是 ‘Suspicious’ 的。 ‘Suspicious’ 的定义是某一个 #define 定义的东西被拆开来了。

如：

1
2
3
#define haha ha+ha
#define p haha-haha
p

这是 ‘Suspicious’ 的，因为第二个haha被拆开了。本来是：

1
2
3
 (ha+ha)-(ha+ha)
= ha+ha - ha-ha

现在是：

1
ha+ha-ha+ha

2.思路

对于一个表达式，在括号外面的最低级的运算符就是该表达式的优先级。比如说 (x+y)∗z/p( x + y ) * z / p 的优先级就是 $ * $ 或者 $ / $ 。

我们把全在运算符括号里面（或者没有运算符）的表达式记为 00 级， ++ 或者 −- 为 11 级， ∗* 或 // 为 22 级。

不难发现， 00 级的表达式是不可能被拆分的。

11 级的表达式的前面有 ∗* 或 // 或 −- 会被干掉 或者 后面有 ∗* 或 // 会被干掉。

22 级的表达式的前面有 // 才会被干掉。

注意：这里的“有”指直接相邻。

所以我们可以先 预处理出所有表达式的优先级 ，然后我们惊奇地发现，所有表达式之间的调用关系为 一张有向无环图！

所以我们可以从调用方到被调用方都连上边，然后愉快地DFS 。

然后就好了。

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
#include<cstdio>
#include<string>
#include<map>
#include<vector>
using namespace std;
const int N=110;
inline bool isCH(char ch){ return ch>='A'&&ch<='Z'||ch>='a'&&ch<='z'; }//判断是否为字母 
inline int read()//输入一个数字 
{
	int num=0;char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch<='9'&&ch>='0') num=(num<<1)+(num<<3)+(ch^48),ch=getchar();
	return num;
}
inline void getdef()//把没用的#define过掉 
{
	char ch=getchar();
	while (ch!='#') ch=getchar();
	while (ch!='d') ch=getchar();
	while (ch>='a'&&ch<='z') ch=getchar();
	return;
}
inline string getS()//输入一个连续的字母串 
{
	char ch=getchar();string s="";
	while (ch==' ') ch=getchar();
	while (ch!=' ')	s+=ch,ch=getchar();
	return s;
}
inline string getL()//输入整行 
{
	char ch=getchar();string s="";
	while (ch!='\n'&&ch!=EOF)
	{
		if (ch!=' ') s+=ch;//去除空格 
		ch=getchar();
	}
	return s;
}
inline void put(string s){ for(int i=0;i<s.length();++i)putchar(s[i]);puts(""); }//输出一个字符串（供调试用） 

//以上为手写输入输出 

int n;//n
string op;//最后的表达式 
string A[N],B[N];//#define A B
map<string,int> mp;//记录A是几号表达式 
int C[N];//分级：0完全整体  1+-  2*/ 
vector<int> G[N];//图：G[i][j] 表示i的第j个调用点 
vector<char> L[N],R[N];//图：L[i][j] 表示i的第j个调用点左边的符号, R是右边的 
bool vis[N];//有没有到过该节点 
bool safe[N];//该节点是否安全 
inline void Dfs(int cur)//DFS
{
	for (int i=0;i<G[cur].size();++i)//遍历所有子节点 
	{
		int to=G[cur][i];char le=L[cur][i],ri=R[cur][i];//to指向的点，le左边的符号，ri右边的符号 
		if (!vis[to])//如果没有去过这个点就往下走 
		{
			vis[to]=1;
			Dfs(to);
		}
		if (C[to]==1)//如果子节点级别为1 
			if (le=='*'||le=='/'||le=='-'||ri=='*'||ri=='/')
				safe[cur]=0;//如果前面有*/-或后面有*/那当前节点不安全 
		else if (C[to]==2)//如果级别为2 
			if (le=='/') safe[cur]=0;//前面有/不安全 
		safe[cur]&=safe[to];//只要有一个子节点不安全就坏事 
	}
	return;
}
int main()
{
	n=read();//输入 
	for (int i=1;i<=n;++i)
	{
		getdef();//去除#define 
		A[i]=getS();//读入A 
		B[i]=getL();//读入B 
		mp[A[i]]=i;//记录A的编号 
		int inb=0;//在第几层括号 
		for (int j=0;j<B[i].length();++j)
		{
			if (B[i][j]=='(') ++inb;//如果遇到左括号加深一层 
			else if (B[i][j]==')') --inb;//如果遇到有括号降一层 
			else if (inb==0)//如果在最外层 
			{
				if (B[i][j]=='+'||B[i][j]=='-') C[i]=1;//如果是+-，那么是1级 
				else if (!C[i]&&(B[i][j]=='*'||B[i][j]=='/')) C[i]=2;//如果是*/，那么是2级 
			}//同时有+-和*/算+- 
		}//不然默认是0级 
	}
	//我不知道这算不算一个点，在C++中前面的#define也可以调用后面的#define 
	for (int i=1;i<=n;++i)
	{
		for (int j=0;j<B[i].length();++j) 
		{//找子表达式 
			if (!isCH(B[i][j])) continue; //表达式全是字母，所以不是字母就continue
			string s="";int now=0;
			int k=j;//从j往后找 
			while (k<B[i].length()&&isCH(B[i][k])) s+=B[i][k],++k;
			if (mp[s])//如果找出的字串是定义过的，那就连边 
			{
				L[i].push_back(j?B[i][j-1]:'#');//防止越界随便搞了一个字符 
				R[i].push_back(k<B[i].length()?B[i][k]:'#');//L和R分别是左边的运算符和右边的运算符 
				G[i].push_back(mp[s]);//像该节点连边 
			}
			j=k;
		}
		safe[i]=1;//初始设safe为1 
	}
	for (int i=1;i<=n;++i)
		if (!vis[i]) vis[i]=1,Dfs(i);//如果没有去过就DFS 
	op=getL();//输入最后的表达式 
	for (int j=0;j<op.length();++j)
	{//和之前那个循环很像（我是复制的） 
		if (!isCH(op[j])) continue;
		string s="";int now=0;
		int k=j;
		while (k<op.length()&&isCH(op[k])) s+=op[k],++k;
		if (mp[s])//同上 
		{
			if (!safe[mp[s]])//如果这个子表达式本生就不安全，直接输出 
			{
				puts("Suspicious");
				return 0;
			}
			else if (C[mp[s]]==2&&j&&op[j-1]=='/')//如果该表达式为2级，左边是/，也不安全 
			{
				puts("Suspicious");
				return 0;
			}
			else if (C[mp[s]]==1
				  &&(j&&(op[j-1]=='/'||op[j-1]=='*'||op[j-1]=='-')
				   ||k<op.length()&&(op[k]=='/'||op[k]=='*')))
			{//同上，如果表达式为1级，左边是/*-或右边是/*就不安全 
				puts("Suspicious");
				return 0;
			}
		}
		j=k;
	}
	puts("OK");//经历了以上一切还活着，输出OK 
	return 0;
}