/2020/11/ zh-CN 个人博客，（曾经）基本只放题解，现在随便写点啥了吧（ Sun, 08 Nov 2020 08:49:58 +0800 Sun, 08 Nov 2020 08:49:58 +0800 /archives/291/ /archives/291/ Sun, 08 Nov 2020 08:49:58 +0800 admin # Day 0 这个比赛在周中举办就非常不友好，有若干事情要忙，傍晚才能出发。然后因为出发的略晚没赶上火车，在路上改签才赶上（然后这班晚 15 分钟出发的车晚一个小时到）（为啥要改签只晚 15 分钟出发的车呢？因为没有更晚的动车 or 高铁了）。 到酒店后，看了会番，然后睡觉。 # Day 1 早饭还不错。 到了现场，发现这比赛是专门新修了一栋楼。然后酒店到这栋楼的路上，两边全是网络安全宣传周的各种标语。赛场所在的房间也特别酷炫，颇有一种《亲爱的，热爱的》里面的感觉了。  此图是队友拍摄，由于没有保存，只能去微信缓存截图，所以清晰度较低。 比赛有四道 AD 题和若干 RW 题。RW 题大概就是对真实世界里的东西进行 pwn，然后上台去演示 exp。AD 题和 DEFCON 的模式差不多，是提交 patch 的形式。 我粗略的看了看这些 RW，发现可能也就一道比较可做，不过也打算在晚上再做，现在做 AD 比较划算。 第一道 AD（没记错的话）是个简单的 pwn，不过我也还是不太会，只能帮着看看。 （后来具体干了啥也不太记得清了，总之第一天基本也没干什么，就随便看了看，有的题倒是花了不少功夫看，但是也没看出什么东西） 第一天最后，放了一道 sort。我看了看，发现非常适合我来做。 题目给了一个 binary，内置了一个虚拟机，然后内置了一段代码，我只能 patch 这段代码。执行的时候，他会把内置的代码和别人发来的代码一起跑，然后需要做到的功能是排序一个长为 100 的数组。谁用的指令数少就赢了。 如果我去打别人，我赢了，我就有攻击分。如果我比所有别人打我的都厉害，我就有防御分。这其实是用 AD 的形式搞了个 KoH。 对于这道题，显然可以有若干种排序方法，并且我感觉都不难实现。 回到酒店，吃过饭，我先逆出了虚拟机的 opcode，然后写了个汇编器。 然后就是写若干种排序了。由于以为这题会给流量，为了防止别人抄做法，我特意写了多种所需时间不同的算法，然后打算用刚好比别人优一点的做法去打。具体来说，我写了插入排序、冒泡排序、快排等多种算法，并且在里面还加入了一些劣化。 快排里面，我发现长度为 2 或 3 的时候很慢，于是也加了特判，快速处理。 写完这些，也已经三点过快四点了，于是我去睡觉了。 # Day 2 第二天，经过询问主办方，我得知其实不会给流量，那么可以直接用最优的算法打了。 比赛正式开始了，我打出去却发现，这个优化的快排只能打过 30 个队，还有一个队比我优。 于是我开始了费劲的优化。我把长度为 4 到 9 都加上了特判（暴搜决策树，或者暴搜快排决策树，或者暴搜快排状态，总之可以比裸循环的快排快不少），结果最后还是只能优化 20% 左右，但是那个队比我快 30%。 在某一次上厕所时，我突然想到，可以基数排序（桶排序）。回来之后立刻实现了一个，发现确实能行，而且很快。于是搞了个桶排序，终于反超了。 最后，我进一步优化了桶排序的实现，然后适当减小了桶的个数，然后把每个桶內部改成之前的优化冒泡排序，达到了非常小的指令数（其实也就是比那个队再快 20% 的水平）。这个第一名一直保持到了最后。 剩下的时间，帮着看了看别的题，不过也没啥实际贡献吧。。 晚上是个莫名其妙的活动，“高新之夜”，实际上就是一群人蹦迪。  我当时只是听说有免费酒水，于是就去了，不过虽然没蹭到酒水，倒是面到了几个群友。比如青少年组的 hasu 和李大哥。（当然还有某个北大队的队员） 顺便我还在这个网络安全科技馆中拍到了不少好图：  真·网络安全演练  共 筑 网 络 长城 # Day 3 看前三名决斗，以及颁奖。 这个决斗过程其实没啥好看的，因为我们也接触不到题。 颁奖的话，主持人念了个比较怪的强网宣言：  然后颁完奖，回学校。顺便晚上去和光光和 O 等人去桃李地下吃了顿。 ]]> 0 /archives/291/#comments /feed/archives/291/