Mr.K 018

Java和C这样的成熟的语言语法其实很复杂，但是词法部分其实还算简单，因为无非就关键字/运算符/常量/标识符这么几大类，再往下分也不是词法分析能干的事情。所以这些语言的词法分析任务不难，写一个DFA，然后遍历一遍输入的程序就完了 实际上调库的话也是得自己定义出词法的确切定义的，flex和antlr能做的只是帮你搭一个DFA，没了。这也是为什么这里允许调库，但是要给出相应库使用的脚本

没事 执此flex/bison/antlr4，微笑面对词法分析器，java是大便（

不是parser，lexer就行 parser预计是2，不过工作量太大了，我不知道要不要出

第19期来力！ 照例是个模拟题，这一期敲样例输出可把我累坏了（ 有工具专门做这件事没错，所以用了工具的要贴出所有源代码（包括工具的输入脚本等）哦 虽然写了1，但是估计不会有2，因为我估计2的工作量就太大了，不符合我们的初衷。不过这道题还好。 第19期 冰系魔法1 传说在某个异世界里是存在元素的，也存在元素魔法。有一次，那个世界的来客向我们展示了一种那个世界的冰系魔法： public class Artia{ public static void main(String[] argv){ System.out.println("Artia's Ice Magic"); } } MrK-018发现，这段魔法的咒语好像可以分解成一个个的单词，好像还能给单词分类。不过，手动把它们一个个摘出来也太麻烦了，还是写一个程序自动区分出魔法咒语里的单词吧。 输入 一段Java源代码冰系魔法咒语。保证符合语法规范。 输出 对每个单词，输出其单词序号、原文和单词类别。格式参考输出样例。 样例输入 package artia; import java.util.*; public class Artia{ char ch = 'a'; String str = "Artia's Ice magic"; public static void main(String[] argv){ double d = 10.25+1; System.out.println(str); return; } } 样例输出 Token 1: 'package', 'package' Token 2: 'artia', identifier Token 3: ';', ';' Token 4: 'import', 'import' Token 5: 'java', identifier Token 6: '.', '.' Token 7: 'util', identifier Token 8: '.', '.' Token 9: '*', '*' Token 10: ';', ';' Token 11: 'public', 'public' Token 12: 'class', 'class' Token 13: 'Artia', identifier Token 14: '{', '{' Token 15: 'char', 'char' Token 16: 'ch', identifier Token 17: '=', '=' Token 18: '\'a\'', character Token 19: ';', ';' Token 20: 'String', identifier Token 21: 'str', identifier Token 22: '=', '=' Token 23: '"Artia\'s Ice magic"', string Token 24: ';', ';' Token 25: 'public', 'public' Token 26: 'static', 'static' Token 27: 'void', 'void' Token 28: 'main', identifier Token 29: '(', '(' Token 30: 'String', identifier Token 31: '[', '[' Token 32: ']', ']' Token 33: 'argv', identifier Token 34: ')', ')' Token 35: '{', '{' Token 36: 'double', 'double' Token 37: 'd', identifier Token 38: '=', '=' Token 39: '10.25', floating Token 40: '+', '+' Token 41: '1', integer Token 42: ';', ';' Token 43: 'System', identifier Token 44: '.', '.' Token 45: 'out', identifier Token 46: '.', '.' Token 47: 'println', identifier Token 48: '(', '(' Token 49: 'str', identifier Token 50: ')',')' Token 51: ';', ';' Token 52: 'return', 'return' Token 53: ';', ';' Token 54: '}', '}' Token 55: '}', '}' Token 56: <EOF>, <EOF>

终点没开之前是墙，而且不允许停（那样就太没意思了（笑）） 而且，这个DFS是没法找到最短路径的，会导致有些能yes的例输出no

第18期来啦！ 第18期 汉化组的吃人陷阱1 MrK-019有一次不小心暴露了自己会中日英三语和视频剪辑的事实，现在某个汉化组已经布下了天罗地网，只要时机一到就要把他收入囊中，调教成无情的汉化机器！ 已知汉化组布下的天罗地网是一种格子迷宫，只有一个出口。迷宫大概是这样的： ###### #K...# ####.# #S...# ###### 如图所示，图上标为#的地方都是墙，标.的地方都是可以走的部分。MrK-019初始所在的地方也是可以走的部分。MrK-019一秒可以走一格。出口只在某一秒开放，平时都是不能走的墙；如果MrK-019在出口开放的那一秒到达出口，他就能逃脱汉化组的吃人陷阱，否则就会被抓住吃掉（指调教成无情的汉化机器）。同时，由于汉化组的人就在后面穷追不舍，MrK-019必须不停地移动才行！ MrK-019能不能从汉化组的吃人陷阱里逃出来呢？ 输入 第一行是三个整数m,n,s，分别表示迷宫的长和宽，以及出口在第几秒开放。 接下来是一个m*n的字符矩阵，表示汉化组设下的迷宫。格式见题干和输入样例。 输出 如果MrK-019能逃出来，就输出一行Yes，否则输出一行No。 样例输入1 5 6 8 ###### #K...# ####.# #S...# ###### 样例输出1 Yes 样例输入2 5 6 9 ###### #K...# ####.# #S...# ###### 样例输出2 No

今天呢，今天决定来一道丧心病狂的题目！ 来看题： 第17期. 这不是一个丧心病狂的题目 题目描述： 输入中每行以十进制形式给出一个整数N ()，输出该数字在英文中的表达。 英文中数字的表达遵循如下规则： 1.0-19分别直接以如下的单词进行表达： { "zero","one","two","three", "four","five","six","seven", "eight","nine","ten","eleven", "twelve","thirteen","fourteen","fifteen", "sixteen","seventeen","eighteen","nineteen" }; 2.20-99，用一个单词或两个单词连接进行表达。若能被10整除则直接用一个单词进行表达: { "twenty","thirty","forty","fifty", "sixty","seventy","eighty","ninety" }; 若不能被10整除，则将十位和个位用连字符连接。如23在英文中的表达为"twenty-three"。 3. 100-999，先表示百位，再表示十位和个位，并以and连接。如123在英文中的表达为"one hundred and twenty-three" 4.对于不小于1000的数字，从右向左，每三位将数字划分一次。对于每一部分，先直接表示，然后加上对应的单位。如果一部分的三个数字都是0则直接省略。如12,345在英文中的表达为"twelve thousand three hundred and forty-five" 从高位到低位，每部分的单位分别为 { "billion",//10^9 "million",//10^6 "thousand",//10^3 ""//1, needs to add nothing }; 输入： 多组用例，以EOF结束。每行以十进制形式给出一个整数N () 输出： 对于每个输入的整数，输出一行，为该数字在英文中的表达。 输出中不允许开头，结尾或单词之间出现任何多余的空格（' '）或连字符（'-'）。 召唤阵： @yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui @摸鱼奇才咖啡喵

我刚才看了下，好像Linux也有做这事的API，貌似是mmap

十进制和十六进制之间反复横跳√

关于第四步优化，可以参考MSDN上的介绍： https://docs.microsoft.com/en-us/windows/win32/memory/creating-a-file-mapping-object 真的就是字面意义上的，像访问数组一样访问文件内容……

召唤 @yhz012 这个题我觉得就是那种很狗的题。 做之前：？？？这也能做？ 做之后：？？？就这？ 解这个题需要对数独终局的两条引理： 引理1. 任意给定数独的第一行，可以构造出至少一个合法的数独终局。（实际上某一行即可，这里为了简便，就说是第一行） 怎么构造呢？可以像这样构造： 1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 3 4 5 6 7 8 9 1 5 6 7 8 9 1 2 3 4 8 9 1 2 3 4 5 6 7 3 4 5 6 7 8 9 1 2 6 7 8 9 1 2 3 4 5 9 1 2 3 4 5 6 7 8 可以看出，这么构造过之后每一行、每一列、每一个九宫格之内1-9都恰好出现了一次。 这样的话，由于左上角的值不能变，剩下八个数能产生8!=40,320种排列。到这里还不够两百万，为了达到我们二百万终局的目标，我们还需要引理2. 引理2. 任给一个合理的数独终局，重新排列这个终局的前三行，所得终局仍然相同；对中间三行和后三行也成立。 举个例子：把上例中的第4行和第6行交换，得到的数独终局仍然合法；或者说，把7，8，9行重新排列成9，8，7行，得到的新数独终局仍然成立。 由于第一行有限制，它只好继续呆在第一行，因此前三行有2种排法；中间三行和后三行没什么限制，分别可以产生6种排法。 这样的话，任给一个数独终局，我们能构造出2*6*6=72个数独终局（包括给的那个终局）。 并用引理1和引理2，我们就能用这样的很简单的操作构造出多达72*40,320=2,903,040种不同的数独终局！ 事实上，中间三行和后三行是可以整体交换的，这样可以构造出的数独终局数量还能再加倍。不过我们只要两百万种，不这么交换也够用了。 这样，我们就给出了能过掉normal的算法。当然，这个算法稍微做一点优化（主要是磁盘IO方面的），也是可以过掉hard和extreme难度的。实际上如果这个算法都过不掉的话，很难想象还有什么算法能过掉了，毕竟这道题输出量是非常大的…… 算法大意如下： 1. 首先构造出初始的第一行：从1排到9，然后把需要在左上角的那个数换过去。 2. 对第一行剩下8个数进行全排列，对每一个排列进行下述操作： 2.1 按照引理1提供的方法填满其余的格子； 2.2 按照引理2排列各行，输出之，直到输出数量够为止。 最后再说一下怎么就优化吧。这一部分其实不是算法本身关注的重点，不过还是简单说一下。 首先按照上面算法直接写，用C++的输入输出库的话，可以搞定normal难度，但是hard难度是跑不通的。 第一步优化：扔掉所有C++输入输出方法，改用C语言的输出函数。这比C++的同样方法快得多。（所以说这里的优化都是一些无聊的小细节） 第二步优化：不要每输出一个数字就调用一次C语言输出函数，而是每输出一次数独调用一次。这样可以大幅减少函数调用的次数。（无聊细节+1）到此可以过掉hard难度。 第三步优化：其实交换两行的时候，不用整个一起交换的。可以记录一个“行索引表”，对行的交换只在索引表上进行。这需要对算法进行一些修改。 第四步优化：连C语言的输入输出函数都扔掉，而是直接用Windows的API。Windows的文件映射功能可以让程序可以像访问内存一样访问文件，进一步提高了磁盘的利用效率。这样，extreme难度也可以过掉了。 相比算法本身来说，这个优化过程就显得平凡很多了。而且在OJ平台上也没有Windows API可以调用不是么（笑

真的有那么魔鬼的嘛？（笑 而且三角函数还好吧，我这里难题都是解析几何和导数……

不会的不会的，不会那么机械无趣的 在思考要不要给第二个提示，不过这个提示给出来跟直接告诉题解也没区别了（

少侠，你已经接近答案了✓

这个题跟别的题不一样，这个题更像猜谜（笑 给个提示：注意到这个两百万的数据大小是远远小于可以构造出的全部数独终局数量的，所以说可以找一些有特定规律的……

不是的哟（笑

第16期到了！ 出题人偷偷地告诉各位，这个题之所以放在这里，是因为它没有看上去那么难哦…… 召唤阵： @yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui @摸鱼奇才咖啡喵 第16期 数独终局 各位应该都了解数独。数独的目标是从指定的状态出发，设法解出一个合理的数独终局——即数独棋盘的九行、九列和九个九宫格中，1-9这九个数字都恰出现一次。今天的任务并非给数独求解，而是从空的数独棋盘开始，“从无到有”地生成出数独终局。 并且，我们要生成出许多数独终局，左上角的数字还要求一样。 输入 只有一组测试用例。一行两个整数a和n，分别表示数独终局左上角的数字，和要求给出的数独终局数量。保证1<=a<=9, 1<=n<=2,000,000。 输出 输出所有的数独终局，两个数独终局间空一行。数独终局的形式如下： 123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678 不要输出到标准输出流中。请输出到文件result.txt。 时间限制 用C或C++编制的程序，时间限制分为三级： easy：无时间限制 normal：120秒 hard：30秒 extreme：20秒（仅Windows） 想要挑战extreme难度？试试Windows的文件映射相关API，或者换用固态硬盘没错，氪金使人变强 ------ 虽然有四个模式，但是本题有意思的点都在easy模式和normal模式之间，剩下两个难度都是解决“如何科学地和硬盘打交道”这样的无聊的编程小问题。因此，只考虑算法的话，挑战normal模式就可以了。 各位加油！

这个题这么做意外的也可以？ hard难度应该不能这么做，这个题本来是个数据结构题来着

已经出到第15期啦！下一期难道就需要两位数了吗？！ 时间过得好快啊。 今天这道题想做出来不难，但是想要跑得快（西方记者：？）的话，需要一点知识和技巧才行。 召唤阵： @yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui @摸鱼奇才咖啡喵 第15期 给绳子染色 有一根绳子，我们要把它涂上各种颜色用来装饰。可以把绳子想象成一段一段的，一共有n段，每次涂色都会涂连续的若干段。比如，先把第1段到第10段涂成红的，仔把第5段到第20段涂成绿的，再把第3段到第7段涂成白的，等等。不用在乎每种颜色都叫什么，我们用一个数字来表示颜色。 涂了一段时间颜色之后，涂色的人也搞不清楚绳子被涂成啥样了。现在他想问问你，指定的两个段之间（包含这两个段），有多少种不同的颜色？ 输入 输入有多行，请读取到文件尾。 第一行是绳子的总长度n和颜色的种数k。接下来若干行，每行可能有两种情况： p x y c，表示从第x段到第y段（含x, y），涂上第c种颜色； q x y，表示询问第x段和第y段（含x, y）之间的颜色种数。 输出 对每个询问输出一行一个整数，表示颜色种数。 难度选择 本题分为两种难度：easy和hard。在easy模式中，保证任意两次涂上的颜色不相同；在hard模式中则可能会相同。

基本上就是这样的。这道题的关键就在于大力的作用看上去是加攻击力，但实质是沉默对面一回合 这个题其实是2019BIT校赛的一道题，我拿不到题面于是就另编了一个

不算，这一点可以放心 A上去之前喝一吨大力也不占回合的（察觉）

我超勇的！

前两天事情有点多，（连电脑都没时间开），于是鸽了一天x 召唤阵： @yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui @摸鱼奇才咖啡喵 第14期 【大力】出奇迹 这是一个很老套的故事：有一个回合制的RPG游戏，里面有一个可以拿装备/道具/塞尔逵公主的副本，副本里有若干怪物，想要拿到奖励就得把怪物一一打倒才行。我们的主人公K018打算下这个副本。这个B非常勇，他决定不带回血的药也不练回复技能，就硬莽。他出发之前掂量了一下自己的斤两，觉得就这么莽多半是直接凉凉。但是已经说过不带药和回复技能了，怎么办呢？ 他思来想去，决定找天桥的某位“药剂供应商”买一点【大力】。这位天桥药剂供应商向他保证：只要吃一份【大力】，下次攻击的伤害就能超级加倍！听了这话我们的主人公K018激动地当场买下了他能买下的全部【大力】，然后就准备下副本了。 已知K018的血量H和攻击伤害D，每一个怪物的血量L_i和攻击伤害K_i，以及我们主人公K018持有的【大力】数量。 主人公每吃下一份【大力】，下一次攻击的伤害就增加D。例如某次攻击前他一口气吃下了10份【大力】，那么这次攻击他就能打出11D的伤害！不过，如果下次攻击前没有继续吃【大力】的话，那仍然只能打出D的伤害。当然，怪物不会蠢到去天桥买【大力】，所以怪物是没有的。同时，由于K018非常勇，所以跟怪物交手时总是他先出手。 我们的主人公K018觉得他彳亍了。各位算算看，他真的彳亍吗？ 输入 第一行有三个整数H, D, m和n。H表示K018的血量，D表示K018的攻击伤害，m表示他持有【大力】的份数，n表示怪物数量。 接下来n行，每行两个整数L_i和K_i，分别表示第i个怪物的血量和攻击伤害。 提示：主角和怪物是轮流攻击的直到有一方被打倒为止。主角一次只面对一个怪物。 输出 如果K018能做到在被打倒（血量小于等于0）前打倒所有怪物，就输出一行“彳亍”，否则输出一行“不彳亍”。 有一说一，只吃一份【大力】攻击伤害确实能翻倍，天桥卖大力的倒也没说假话

考虑一个想法：决定弃用一个已使用的道路，无非是将原有的最小生成树砍成两半，找一条边接上即可

第13期—— 本题来源：HDU4126，题意复述如下： 现有n个据点，两两之间连有道路。现在要在一些道路上驻扎守卫，使得任意两个据点之间都可以或者直接或者间接地传递消息（消息只能在有守卫驻扎的道路上才能传递，否则会丢失或者被截获）。已知每条道路需要的守卫数量。 现在得到情报，有一条道路上会发生游击队袭扰，受到影响的道路需要增派守卫来保障消息的安全传递。当然，也可以不再用这条道路，换用其他的道路驻扎守卫。现在尚不清楚游击队具体会在哪条道路上进行袭扰，只能大致圈定可能发生袭扰的范围。同时，我们知道如果在某个地方发生了袭扰时需要增派的守卫数目。如前所述，游击队袭扰同时只会发生在一条道路上。 现在已知每条道路所需的守卫数量和游击队可能的袭扰情况（多种可能，每种都会注明发生的道路和需增派的兵力。同一条道路上的袭扰所需的增派兵力时可能不同的，它们视为不同的可能性）。问，在每种情况下所需的最少守卫数量是多少？ 召唤阵： @yhz012 @inuisanaa @ZERC @随性而为 @NianRuoshui @摸鱼奇才咖啡喵