宁波镇海蛟川书院 卢啸尘 ID: Ruchiose 一族分析类编译问题 宁波镇海蛟川书院 卢啸尘 ID: Ruchiose

Q&A Q: 你谁啊？ A: 一个来自农村学校的颓狗。 Q: 这个PPT模板怎么感觉什么地方见过？ A: 没错，去年某个“即将退IOI役Jinpai的酱油Da选手Ye”用过， 不会用TEXBEAMER的我就直接拉了。 24.11.2018

Q&A Q: 这个课是干什么的？ A: 这个课是讲分析类编译问题。指的是那些输入是一段高级 程序源代码，但是目标并非执行代码，而是在语义的方面分 析代码的性质的题目。 课件中有一大半的篇幅在讲一个题的做法，然后剩下一小半 就是在这个题目的基础上魔改。 Q: 听这个课对提高OI竞赛水平有什么帮助？ A: 没有帮助。我们知道，曾经有名为“会toptree的省选都 挂了”的论断（@apia）。可是尼萌都会去学toptree。 24.11.2018

Q&A Q: 会考吗？ A: 考了的话寄刀片小分队加我一个。 Q: 那么这种问题的意义何在？ 24.11.2018

举个栗子 下面给出的例题可以说是万恶之源。 做了这个题以后我整个人就都不对了。 然后整个人都不对的我就来用这个题报社了。 24.11.2018

万恶之源 The 11th Zhejiang Provincial Collegiate Programming Contest Problem K: Unreachable Statement 24.11.2018

被吊打的感觉 24.11.2018

被吊打的感觉 半个机房开了个黑然后被单挑的lyrically爷干掉，你们感受一 下。 12题和11题，差距就在K题。 24.11.2018

看样例识题意 out in Unreachable statement at line 6, column 13 function gao() { if (x <= 5) print a else { if (x < 3) print b else print c } print d function zaigao() { if(x>100) print LongVariable if(x<=15) print hello print world print lol out Unreachable statement at line 6, column 13 Unreachable statement at line 19, column 9 24.11.2018

Unreachable Statement 你是宏Macro硬Hard公司的一个程序猿。 你正在写一种叫做C Flat的语言的编译器。 找出所有不可能被执行到的语句。 输入代码总长在2MB以内。 24.11.2018

C Flat语言 Flat是降调符号，长得像b一样的那个。 正如b所指出的，C Flat是C的一个弱化版。 一个C Flat程序由若干个function组成。 每个function的格式是function 函数名() {一堆语句} 语句有三种，“print 变量”，“if (表达式) 语句 [else 语句]”和 "{一堆语句}" print是一个用来卖萌的语句。 表达式只有三种，true，false和“变量名 二元算符 非负常量 ”。二元算符包括四种不等号。 所有变量为int类型。没有变量声明。 24.11.2018

不能被执行到的语句 比如这货： function tooyoungtoosimple() { if (a >= 2333) 这里的print makeAbigNEWS和print shenmegui都是不可 能被执行到的。 输出两个语句第一个字符的位置(7,7)和(10,7) function tooyoungtoosimple() { if (a >= 2333) if (a >= 233) print a else print makeAbigNEWS if (false) print shenmegui } 24.11.2018

其他要求 不输出处在不可达代码内的不可达代码。 比如这货： function AMarioSeaman(){ 三个不可达语句是：第二个if，第三个if和print。 后面两个语句被套在第一个里面所以只输出(2,14)。 function AMarioSeaman(){ if (false) if (false) if (false) print amarioseaman } 24.11.2018

摔 这种输入文件怎么读入啊！ 读都读不进来有木有！ 24.11.2018

关于读入 尼萌都会写读入优化吧。 当需要读入数目在10^6级别的整数时，常常使用getchar来 代替scanf。 具体地，重复读入字符直到遇到第一个digit，然后重复读入 字符直到遇到第一个非digit。中间遇到的所有digit构成了下 一个读入的整数。 把读入优化改一改，就变成了所谓的词法分析器。 24.11.2018

词法分析器 词法分析器是编译器的第一个部分。它接受一个字符串（源 代码），输出一个词素表。 （这里的定义已经按照简化实现的方向进行修改） 如，输入"function gao() {if (a > 1) print a}"，输出 {"function", "gao", "(", ")", "{", "if", "(", "a", ">", "1", ")", "print", "a", "}"}。 24.11.2018

词法分析器 在现代，编译器中的词法分析器通常被实现为语法分析器的 一个子过程。 这就是说，语法分析器在需要的时候调用一次词法分析器， 每次，词法分析器返回输入流中的下一个词素。 如，前例中，第一次调用函数返回字符串"function"，第二 次调用返回字符串"gao"。以此类推。 下面当提到词法分析器的时候，指的就是这种返回下一个词 素的过程。 24.11.2018

词法分析器 在本题中，所需的词法分析器的一种实现是这样的。 首先读入字符直到第一个非空白字符。 如果是字母：读入字符直到遇到非字母字符。 如果是数字：读入字符直到遇到非数字字符。 如果是"(){}"中的某个字符：返回这个字符。 如果是"<>"中的某个字符：如果下一个字符是等号，读入等 号。否则返回这个字符。 通过设置一个char的缓冲区实现“检查下一个字符”而不 “读入”它。 24.11.2018

好了我会做了 既然已经读入进来了那么就使劲码就可以了。 不用讲了不用讲了。 这么想然后马上去码的话就可能会像我一样连挂三发。 你没有学会游泳就会不知所措。 所以下面还是要教尼游泳。 24.11.2018

下一步 第二步是语法分析。 语法分析通常基于预测分析法。分为递归式和非递归式。 如果不基于预测分析的话隔三岔五就要回溯。 尼萌感受一下那样的效率。 24.11.2018

递归下降分析方法 递归向下语法分析器由一系列子过程构成。 每个非终结符号对应了分析程序中的一个分析过程。 以以下文法为例： EXPR ::= TERM REXPR REXPR ::= ε | + TERM REXPR | - TERM REXPR TERM ::= integer | (EXPR) （这个是消除了左递归以后的描述带括号加减法表达式的文 法） 24.11.2018

递归下降分析方法 string nxtLexeme(); // 检查输入流中下一个词素 string getLexeme(); // 读取输入流中下一个词素 // 以上是词法分析器 bool isInteger(string lexeme); // 检查给定词素是否描述了一个整数 void Match(string s) { if (nxtLexeme() != s) throw "Syntax Error"; getLexeme(); } void EXPR() TERM(); REXPR(); void REXPR() if (nxtLexeme() == "+") {Match("+"); TERM(); REXPR(); return;} if (nxtLexeme() == "-") {Match("-"); TERM(); REXPR(); return;} void TERM() if (nxtLexeme() == "(") {Match("("); EXPR(); Match(")");} if (!isInteger(getLexeme())) throw "Syntax Error"; 24.11.2018

LL(1)文法 在以上文段中，在分析一个非终结符号时我们只检查了下面 的一个语素。这是由消除左递归以后此文法的LL(1)性决定的。 LL(1)性是如此定义的：考虑每一个非终结符号。若该符号不 可推导出ε，则该符号串各变换规则串的FIRST互不相交；若 该符号可推导出ε，则该符号串各变换规则的FIRST，以及该 符号的NEXT集合互不相交，同时可以推导出ε的产生式唯一 （这是为了保证无二义）。 24.11.2018

FIRST集合 FIRST(符号串)为此符号串推导出的所有串的首语素所构成的 集合。 一个符号串α[1..n]的FIRST为α[1..i]的FIRST集合之并，其中 α[i]是n或第一个不可推导出ε的符号。终结符号的FIRST集合 为由它自己一个元素构成的集合。非终结符号的FIRST集合为 所有变换规则串的FIRST之并。在消除了左递归以后，FIRST集 合可以无死循环地递归求出。 如： FIRST(EXPR) = {(, integer} FIRST(TERM) = {(, integer} FIRST(REXPR) = {+, -} FIRST(+ TERM) = FIRST(+) = {+} 24.11.2018

NEXT集合 NEXT(非终结符号)是该符号的后面一个非终结符号的取值范 围。检查所有的生成规则P::=α[1..n]，若α[i]为非终结符号， 将NEXT(α[i])并上FIRST(α[i+1..n])。若α[i+1..n]可推导出ε将 NEXT(α[i])并上NEXT(P)。特别的，NEXT(初始符号)中有串尾 标志$符号。 重复以上过程直至不再有新的变化。 如： NEXT(EXPR) = NEXT(REXPR) = {$, )} NEXT(TERM) = {$, ), +, -} 24.11.2018

LL(1)文法→预测分析 如果某个文法是LL(1)的，则我们可以按照以下方式为其构建 递归下降预测分析器。 对于每一个非终结符号，检查下一个语素是否在某个变换规 则的FIRST集合中。若存在，应用此变换规则。 如果不在任何一个FIRST集合中，而又没有可推导出ε的产生 式的话，宣称语法错误。若有，默认应用那个产生式。注 意，在这里利用此符号的NEXT集合是没有意义的。考虑以下 文法： S::=aAb|bAa; A::=ε|c 则当上下文中，S应用的是第一条变换规则时，A的后文可以 确定为b。因此若下一个语素是a时，由于NEXT(A)包含a就 断言A应用ε是不恰当的。应当在不考虑NEXT的前提下假设A 应用ε规则，在过程A()结束后，其调用者过程S()调用 match("a")时再抛出语法错误。 24.11.2018

将一般的文法转化为LL(1)文法 现在我们已经能够为一个LL(1)文法构建递归下降的文法分析 器。 但是并非所有文法都是LL(1)的。 24.11.2018

消除左递归 考虑以下文法： S ::= integer | S + integer 将其写成以下形式。 S ::= integer RS RS ::= ε | + integer RS 此为消除左递归。 在实践中这样的形式通常用S()中的一个while循环代替。 24.11.2018

提取左公因式 考虑以下文法： A ::= ad | Bc B ::= aA | bB A的两个产生式的FIRST都有a。 将A展开：A ::= ad | aAc | bBc 提取a：A ::= aC | bBc c是如此定义的：C ::= d | Ac。 这样就得到了一个无左公因式文法： A ::= aC | bBc C ::= d | Ac 容易看出它是LL(1)的。 24.11.2018

另一个例子 考虑以下文法（这个文法描述了条件分歧语句的嵌套）： STATMT ::= { BLOCK } STATMT ::= if EXPR then STATMT STATMT ::= if EXPR then STATMT else STATMT 第二、三个产生式的FIRST集合均为{if}。所以此文法非 LL(1)。 但是可以通过增加一个非终结符号来消除它。 STATMT ::= if EXPR then STATMT AFTTHEN AFTTHEN ::= ε | else STATMT 这个文法就是LL(1)的了，吗？ 24.11.2018

约定法 有二义的文法不可能是LL(1)的！ 大家应该注意到上面的文法是二义的。它没有处理else的归 属问题。具体的，AFTTHEN的NEXT中和产生式的FIRST中都 有else，同时AFTTHEN可以推导出ε。 实践中对于else的处理并非在文法的层次上进行的。通常是 在分析器中进行约定。 尼不是有两种选项，ε（把else传给上层）和else STATMT （把else直接匹配掉）吗？ 我规定每个else和最近的未匹配then搭配，不让你选ε不就 无二义了吗？ 24.11.2018

非递归的预测分析 现在问题来了，递归式虽然写起来方便但是要用系统栈。 交上去以后可能会爆栈（我曾经在膜你题中出过45W对花括 号这样的数据）。当然支持开栈的话当场A给你看。（窝出 《rpg》时一开始就是非递归的然后std在hdu爆栈了） 所以对于比较大的输入要使用人工栈。也就是所谓非递归预 测分析。 就是用一个栈保存当前的非终结符号串中尚未处理的部分。 考虑以下文法： A ::= aC | bBc，为初始符号 B ::= aA | bB C ::= d | Ac 和以下输入：abbaadcc 24.11.2018

示例 流：abbaadcc。符号：A。栈为符号串中粗体部分，以下 同。 读入a。适用A ::= aC。符号：aC。 读入b。适用C ::= Ac，A ::= bBc。符号：abBcc。 读入b。适用B ::= bB。符号：abbBcc。 读入a。适用B ::= aA。符号：abbaAcc。 读入a。适用A ::= aC。符号：abbaaCcc。 读入d。适用C ::= d。符号：abbaadcc。 读入c。栈顶终结符号已匹配。符号：abbaadcc。 读入c。栈顶终结符号已匹配。符号：abbaadcc。匹配终 了。 总的来说就是每步根据栈顶符号和流的头符号决定变换。若 栈顶是非终结符，根据预测分析规则在栈顶修改符号。若栈 顶是终结符，试着匹配之。 24.11.2018

回到题目 考虑到本题的数据规模在2M，这里使用非递归预测分析法。 在下面的介绍中你将会发现，这个分析器和之前提到的非递 归预测分析器不太一样，栈中只有程序结构方面的符号，并 且我还将语义有关的分析也写到同一个分析器中了。 考察文法： STATMT ::= { BLOCK } STATMT ::= print var_name STATMT ::= if (EXPR) STATMT AFTTHEN AFTTHEN ::= ε | else STATMT BLOCK ::= ε | STATMT BLOCK EXPR ::= var_name OPRT constant OPRT ::= < | <= | > | >= 24.11.2018

EXPR和OPRT EXPR和OPRT只在一处（if中）出现，容易识别。 将EXPR当成一个终结符expr在需要处理expr处调用以下过 程即可。 void readExpr() { if (!isVarName(getLexeme())) throw "Syntax Error"; if (nxtLexeme() == ")") // true/false return; if (!isOperator(getLexeme())) throw "Syntax Error"; if (!isConstant(getLexeme())) throw "Syntax Error"; } 24.11.2018

表达式的语义 注意到这道题的要求并非仅仅对源程序进行语法分析。 因此源程序文段的语义也是必要的。 因此readExpr()应当被定义为有返回值的函数。 pair<string,pair<u32,u32> > readExpr() // pair定义了下界和上界 { string a, b, c; if (!isVarName(a = getLexeme())) throw "Syntax Error"; if (nxtLexeme() == ")") // true/false return (a == "true") ? ALWAYS_TRUE : ALWAYS_FALSE; if (!isOperator(b = getLexeme())) throw "Syntax Error"; if (!isConstant(c = getLexeme())) throw "Syntax Error"; u32 _c = to_IU(c); if ((b == ">") && (_c == MAXU32)) return ALWAYS_FALSE; if ((b == "<") && (_c == 0)) return ALWAYS_FALSE; if ((b == ">=") && (_c == 0)) return ALWAYS_TRUE; if ((b == "<=") && (_c == MAXU32)) return ALWAYS_TRUE; if (b == ">") return MP(a, MP(_c + 1, MAXU32)); if (b == ">=") return MP(a, MP(_c, MAXU32)); if (b == "<") return MP(a, MP(0, _c - 1)); if (b == "<=") return MP(a, MP(0, _c)); } 24.11.2018

表达式的语义的反面 ALWAYS_TRUE和ALWAYS_FALSE这两个 pair<string,pair<u32,u32>>型常量被用来表示必真和必假。 标识符不会以':'开头，因此这里定义它们为<":true",<0,0>> 和<":false",<0,0>>。 当一个pair<string,pair<u32,u32>>的first不以':'为其开头时， 它就描述了这个if...then对原来变量值的一条约束：first变量 的取值范围在second.first..second.second。 然而除了if...then还有else。这就要求我们为每个 pair<string,pair<u32,u32>>定义其反面。 pair<string,pair<u32,u32> > NOT(pair<string,pair<u32,u32> > x) { if (x == ALWAYS_TRUE) return ALWAYS_FALSE; if (x == ALWAYS_FALSE) return ALWAYS_TRUE; if (x.second.first == 0) return MP(x.first, MP(x.second.second + 1, MAXU32)); return MP(x.first, MP(0, x.second.first - 1)); } 24.11.2018

if语句的语义动作 我们分析一个if语句： if (EXPR) smth_1 [else smth_2] 要想访问到smth_1，变量必须满足约束readExpr()，要想访 问到smth_2，变量必须满足约束NOT(readExpr())。 我们考虑当从左到右扫描代码时会发生什么事。 最初发现了if。根据后面跟着的EXPR计算出约束readExpr()。 在读入右圆括号后readExpr()开始生效。在读入一个STATMT 以后readExpr()失效。之后检查下面一个符号是否是else， 如果是的话NOT(readExpr())生效，并且它在读入一个 STATMT以后失效。 24.11.2018

分析语义用数据结构 这里，我们需要支持两种操作，加入一条约束或删除最后一 条加入的尚未删除的约束。并且支持随时查询所有约束是否 矛盾。 由于约束的栈性质，我们可以简单地用 map<string,vector<pair<u32,u32> > >来实现，设置计数 器cnt来计量当前有多少个变量取值范围为空加上有多少个 false。 当cnt从0变成1时输出光标当前位置。 24.11.2018

实现 int isConflict(pair<u32,u32> X); // 1 if empty. pair<u32,u32> operator * (pair<u32,u32> a, pair<u32,u32> b); namespace Rez // Restriction { map<string,vector<pair<u32,u32> > > A; vector<string> Recent; int cnt; void Init() {A.clear(); Recent.clear(); cnt = 0;} void push(pair<string,pair<u32,u32> > X) Recent.push_back(X.first); if (X == ALWAYS_TRUE) return; if (X == ALWAYS_FALSE) {cnt++; return;} if (!A.count(X.first)) A[X.first].push_back(MP(0, MAXU32)); cnt -= isConflict(A[X.first].back()); A[X.first].push_back(A[X.first].back() * X.second); cnt += isConflict(A[X.first].back()); } void pop() string BACK = Recent.back(); Recent.pop_back(); if (BACK == ":true") return; if (BACK == ":false") {cnt--; return;} cnt -= isConflict(A[BACK].back()); A[BACK].pop_back(); cnt += isConflict(A[BACK].back()); bool OK() {return cnt == 0;} 24.11.2018

程序结构分析的实现 非终结符号STATMT, BLOCK, AFTTHEN是和程序结构相关的 符号。 根据之前所说的，我们需要在if结束时引入撤销修改这一语义 动作，因此在栈中进一步引入ENDIF符号。 我们用栈P描述当前程序的结构，用栈Q保存语义动作。 24.11.2018

初始值 最初，将function、function_name、(、)、{读入丢掉。 向栈P中压入BLOCK符号。这个符号的意思是当前语句处于 某个块中，等待一个}，类似于非递归语法分析器中的"}"符号。 栈Q为空。 24.11.2018

当栈顶为BLOCK时 栈顶为BLOCK时，相当于当前正在分析一个非终止符号 BLOCK。读入一系列语句直至右花括号，NEXT(BLOCK)中 的唯一元素。 当栈顶为BLOCK时，检查下一个语素。若为"}"，则说明应当 应用BLOCK ::= ε规则。读入"}"，弹出P中的BLOCK。 否则，说明接下来是一个语句，应当应用BLOCK ::= STATMT BLOCK规则。向P中压入STATMT符号。 24.11.2018

当栈顶为STATMT时 栈顶为STATMT时，说明分析器马上要开始分析一个语句。 检查下一个语素： 若为"{"，则说明这个语句是一个块语句。即应用STATMT ::= { BLOCK }规则。读入"{"，从P弹出STATMT，压入BLOCK符 号。 若为"print"，则说明这个语句是一个谜之卖萌语句。即应用 STATMT ::= print var_name规则。读入两个语素，从P弹出 STATMT。 若为"if"，则说明这个语句是一个条件分歧语句。即应用 STATMT ::= if (EXPR) STATMT AFTTHEN。记录a = readExpr()并一直读到")"后。将a压入栈Q。调用 Rez::Push(a)，然后如果Rez::OK()从true变成了false，输出 此时的光标位置。从P弹出顶端的STATMT，先后将ENDIF, AFTTHEN, STATMT压入栈中。 24.11.2018

当栈顶为AFTTHEN时 这个时候，分析器处理了一个if的then部分，正要开始处理 else部分。 首要任务是检查else语句是否存在。根据每个else和最近 then匹配的约定，只要下一个语素是"else"就认为它是这个if 的else。 如果是"else"，则应用AFTTHEN ::= else STATMT。读入语素 else，将Q栈顶的a换成它的反面NOT(a)，调用Rez::pop() 弹出then的约束。调用Rez::push(Q.top())（即NOT(a)）， 同样若Rez::OK()开始变成false，输出光标位置。从P弹出 AFTTHEN，压入STATMT。 否则此if无else。应用AFTTHEN ::= ε。弹出AFTTHEN。 24.11.2018

当栈顶为ENDIF时 此时，分析程序完成了对一个if的分析——要么此if有else并 且分析程序已经完成了对此else后接语句的分析。 此时，Q的栈顶的约束就是此if残留在Rez中的约束。ENDIF 符号的工作就是消除这个残留约束。 弹出ENDIF，弹出Q栈顶的约束，调用Rez::pop()。 24.11.2018

AC 这道题目就这么解决了。 可喜可贺可喜可贺。 本来下面几张幻灯片还贴了代码，不过窝知道你们都看不清 楚所以就不贴了。 24.11.2018

欢迎秒题 我们发现只要把Unreachable Statement中的那个辅助数 据结构换一换就能出成别的题目。 下面两个题目就是这么造出来的。其中辅助数据结构部分的 难度都是联赛级别的。因此欢迎来秒。 24.11.2018

ZCC Loves RPG HDU 4874。 2014多校训练赛第2场C题。 出题人是我。 现场0人A，计划通。（然后结束以后2小时就被秒了） 24.11.2018

题面 ZCC在打游戏。 ZCC有一个游戏角色，它有N个属性Ai，每个属性的取值范围都是全体非负整 数。由于ZCC患有强迫症，如果一段编号连续，符号为正的属性值之和＞K， ZCC会爆炸（?）。 游戏有剧情线路。在某些位置根据某个属性值的不同会进入不同的路线，在某 些位置可以看CG。ZCC希望知道在自己不爆炸的前提下自己能看到多少种CG。 （当然ZCC可以把这个游戏打若干遍。） 游戏的剧本以类似C++语言的方式给出： game(n, k) <块> 定义了整个剧本，n是属性数目, k是ZCC的限制； cg(p1); 说明在某个位置出现了某一张CG，编号为p1。 if (a[p1] >= p2) <语句或块>; [else <语句或块>;]说明了根据p1属性 是否大于等于p2，进入不同的路线。 else属于最近的那个if。 输入保证符合语法，但是空格和换行分布不一定满足上面的说明。 24.11.2018

秒题时间 24.11.2018

此处的辅助数据结构—— 在Unreachable Statement的基础上，本题还要求支持单 点修改和查询最大非零子段和。 使用线段树即可。 24.11.2018

ZCC Loves AVG 校内膜你赛题。 出题人是我。 现场0人A，计划通。 24.11.2018

题面 ZCC在制作一个文字冒险游戏。 ZCC的游戏中有若干个角色，它们分属两个阵营，分别是有爱的爱（AI）军团和黑暗的死妖灵（410）军团。 ZCC尚未决定每个角色属于哪个军团。ZCC认为所有的角色都属于同一个军团也是可以接受的。 在游戏的开头，玩家可以决定每个角色是属于那个军团。这将影响游戏的路线。 具体地，在剧本的某些地方，会根据以下情况产生分支： 1.某角色是否属于某一个军团； 2.某两个角色是否属于同一军团。 在游戏的某些位置ZCC放置了CG。现在游戏完工了，为了减少压缩包的大小，ZCC将去掉那些不会被看到的CG 。你需要指出一个游戏中哪些CG不会被看到。 我们将用类似于C++代码的方式来描述这个剧本。 在这个剧本中，每个角色属于的军团是由一个与该角色同名的布尔型变量表示（true若为爱军团，false若 为死妖灵军团）。保证没有角色的名字是保留字。 在这个剧本中有以下语句： game() <块> 定义了整个剧本。 cg(name); 说明在某个位置出现了某一张CG，名称为字符串name。 if (var1 == var2) 或 if (var1 != var2) 或 if (var1) 或 if (!var1) <语句或块> [else <语句 或块>] 说明了根据①②名为var1和var2的角色是否属于同一/不同军团③名为var1的角色是否属于爱军团 ④名为var2的角色是否属于死妖灵军团，剧情将产生分歧。 else属于最近的那个if。 输入保证符合语法，但是空格和换行的分布不一定如上所示。 24.11.2018

秒题时间 24.11.2018

此处的辅助数据结构—— 本题要求支持维护一系列点的所属集合（集合共两种），陈 述有A,B在同一集合和A,B在不同集合两种。 用并查集解决。我知道你们都会做可持久化并查集。 不过这里不需要可持久化，撤销的操作不会再被用到。 所以只需要按秩合并+用栈记录每次push时连了哪条边。 数据比较难出所以不按秩合并大概也没关系？ 24.11.2018

脑洞时间 用分析类编译问题这个外壳可以搞出撤销修改时间的栈性 质。 有些难搞的东西有了栈性质就好搞了。 我们还能搞出点什么？ 24.11.2018

脑洞之一 变量只有实变量x和y。 if的格式只有ax+by+c>=0。 24.11.2018

解 有栈性质的动态半平面交问题。 用splay维护凸包的两个凸壳，每次二分出分割位置然后把凸 包分裂开来。 分裂开来的两个凸包一个属于then一个属于else。endif以 后再并起来。 24.11.2018

脑洞之二 如果ZCC Loves AVG中的各变量不是bool而是int能不能 做？ 题意：加边删边，是否存在长为1的环。 我会暴力。 24.11.2018

脑洞之三 加上循环语句能不能做？ 窝连暴力都不会了。 如果语句功能太强，复杂度至少跟字面值的规模有关，而非 代码长度。比如有了取模运算以后我们就可以定义素数了， 然后就可以做一些奇怪的事了。 24.11.2018

欢迎更多脑洞 24.11.2018

非分析类编译问题 “分析类编译问题好无聊啊。” 只是改一改辅助数据结构就变成新题，两百多行代码修改的 也就是那么几十行。 尼萌可以来写一写非分析类编译问题。 也就是模拟类编译问题辣。 Rujia Liu's Present 5的Mini-Lua系列欢迎你。 第一题写词法分析器 第二题写单语句解释 第三题解释代码段，循环什么的全都有 据说std有30K。 24.11.2018

不插旗就不会死 在大型比赛前写这种奇怪的长代码题很不jiry。 尼萌就当我今天讲了个笑话吧。今天是愚人节啊。 24.11.2018

祝大家省选顺利 FIN.