Xsbl模拟赛相关

在10/23推出,其实只是作为验题人,由Fop_zz提供题目。从题目来讲,相比我以前出的正常多了,不过平均分还是偏低不少,在120~130。

但是,考虑到版权问题(?),这里不细谈题目,原题分别是CF5D、CSA Server Hacking、CSA Growing Trees,T1和T2都有较大的实现难度。这次文档的样式基本上都是我写的,用了不少模板,但也有很多有趣的事实:

  • 在PDF中插入动画(Server Hacking)
  • 首次使用Beamer作为题解演示文稿,并同时提供文档版的题解
  • 插入大量图片,主要来自原题和Fop_zz手绘图像
  • 使用Overleaf在线合作编辑LaTeX文档
  • 使用VeraCrypt跨平台加密方案

PDF插入动画

问题

在搬题的时候,我们突然发现,https://csacademy.com/contest/archive/task/server-hacking/上有一个动画。开始我们以为它只是个GIF之类的,但是稍加观察,就发现它似乎每次的方案都是不同的。于是我们大胆猜想:应该是用js随机解然后绘制的。这很正常,毕竟CSA的样例解释都很神奇,它提供的三个在线工具用于画图、画坐标系和对比两个文件,不仅使用方便,而且能嵌入到题面中。我们都很想把这么有趣的内容放到题面里。

尝试

一开始,我认为可以把HTML转为PDF,但似乎没有解决方案。而且,我也没办法把那个动画扒下来,因为没有swwind的帮助。Fop_zz提出了备用方案:让动画多跑几次,截成GIF放进PDF,或者甚至直接放在目录下。我也很想就此罢休,但是终究不甘心。

发现移植的难度不低于重写的难度,那就去重写吧。查阅资料发现,现在的PDF都是支持js的,所以理论上是支持动画的。不过对于PDF阅读器的限制很大,常见的只有Adobe Reader和Foxit可以,浏览器之类的根本不可能。在这篇文章中,先介绍了插入GIF的方法,看起来很简单,只要用animate宏包,再把GIF拆成一帧帧的就可以了。这样把GIF丢进PDF容易实现,但是显然空间会极大地浪费。

接着,文章也就此指出更高级的使用,用LaTeX的绘图工具来绘图,类似存矢量图。这听起来很不错,然而我根本不会任何绘图方式,更重要的是,这个命令并没有提供完整的语言接口。也就是说,随机是不可能的,它只能顺序播放。

理论方案

我还是不甘心,找到了更高级的文档,也就是animate宏包的文档。首先它指出是Flash的替代品,所以现在的PDF也是可以嵌入Flash的,不过怎么能用垃圾Flash呢?这个插件的缺点是浪费空间。

文档中有一个前面没有提到的选项——时间线(timeline)文件,这个文件每行有4个字段,最吸引我的是最后一列,是js代码。这意味着利用时间线文件直接插入js代码是可能的。当然理论上用Acrobat也可以,但显然没有正版,而且会很复杂,说不定和LaTeX不容易兼容。

那么具体怎么实现方块的移动呢?虽然可以放js,但毕竟不是HTML,你又没有对象可以操作。我想到了一种简单的替代方案:把所有可能的图都保存,然后构建一个有向图转移状态,并循环播放。同一阶段的状态,直接等概率随机选择一个。这样理论上就可以实现要求的功能了。

原型

实现显然更加耗费时间。由于工程量比较大,按照我的习惯,得先试一下原型来确定可行性。这很简单,我直接在动画里随便截了两个状态。不过问题很快暴露:这样截取的位置和大小不完全相同,导致播放时“背景”也移动了,这是后期需要解决的问题。

时间线的前三个字段,容易发现前两个空着,第三个直接填上标号就行了,这里不是重点。对于我这种js基本不熟悉的人,要写嵌入式的js基本不可能,所以我们需要另一个API文档

为了能在时间线中访问动画,需要在插入处指定label,比如我日常用test,然后用anim['test']anim.test来访问接口。最重要的一个属性就是frameNum,可以直接指定跳转到时间线中的位置(也就是行数,不一定要与实际的帧对应)。至于随机,只能用Math.random(),和垃圾VB一样,也是返回[0,1)[0,1)之间的随机数。咨询swwind后得知,js并不区分浮点数和整数,所以用分数区分就好了,例如有3个状态就用

然而事情并没有那么简单。修改frameNum后动画会立即切换,没有任何停顿,也就是原来设定的帧率直接作废。这不麻烦,我们for(i=1;i<=1e5;i++);延时一下不就好了吗?可惜它是单线程的,这么做循环长了Reader直接卡住,短了切换的时间极不稳定。那么就用sleep吧,然而swwind说根本没有这样的函数,只能用异步。

可以在浏览器甚至vscode的开发者选项的控制台中做实验,使用setTimeout函数会立即返回,并且在指定时间后会调用回调函数。但把这个直接写到时间线里根本没有用。原来在API文档中指出,嵌入式js与普通环境下不同。要用app.setTimeOut!要知道C家族的语言都是大小写敏感的。而且这个API传入的也不是一个回调函数,而是一个表达式!不过其实这种写法在animate宏包的文档中也提到过,只是我没仔细看……

这样基本上就完成了,但还有一个令人崩溃的问题:动画播放一段时间之后会随机停止,而且还和设置的超时时间反相关。我没有找到任何解决方案,只好决定把原先的1fps改成2fps,这样通常能播放十多帧。

批处理

接下来比较复杂的问题就是截图了,经过统计共有25帧。这些帧中边框的位置必须完全一致,才能看起来比较正常。我的方法是先全屏截图,顺便编一下号,然后用ImageMagick裁剪,可能ffmpeg也可以。至于裁剪的坐标,打开画图并放大,可以在状态栏中看到。而且根据我的经验,坐标最好是4的倍数。

这样基本就完成了,这里再放上时间线文件。

timeline.txt
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
::0:{app.setTimeOut("anim['test'].frameNum=1",500);}
::1:{app.setTimeOut("anim['test'].frameNum=Math.random()>2/3?2:Math.random()>1/3?3:4",500);}
::2:{app.setTimeOut("anim['test'].frameNum=Math.random()>2/3?5:Math.random()>1/3?6:7",500);}
::3:{app.setTimeOut("anim['test'].frameNum=Math.random()>2/3?6:Math.random()>1/3?7:8",500);}
::4:{app.setTimeOut("anim['test'].frameNum=Math.random()>1/2?7:8",500);}
::5:{app.setTimeOut("anim['test'].frameNum=Math.random()>1/2?9:10",500);}
::6:{app.setTimeOut("anim['test'].frameNum=Math.random()>2/3?9:Math.random()>1/3?10:11",500);}
::7:{app.setTimeOut("anim['test'].frameNum=Math.random()>2/3?10:Math.random()>1/3?11:12",500);}
::8:{app.setTimeOut("anim['test'].frameNum=Math.random()>1/2?11:12",500);}
::9:{app.setTimeOut("anim['test'].frameNum=13",500);}
::10:{app.setTimeOut("anim['test'].frameNum=Math.random()>1/2?13:14",500);}
::11:{app.setTimeOut("anim['test'].frameNum=Math.random()>2/3?13:Math.random()>1/3?14:15",500);}
::12:{app.setTimeOut("anim['test'].frameNum=Math.random()>1/2?14:15",500);}
::13:{app.setTimeOut("anim['test'].frameNum=16",500);}
::14:{app.setTimeOut("anim['test'].frameNum=Math.random()>1/2?16:17",500);}
::15:{app.setTimeOut("anim['test'].frameNum=Math.random()>1/2?16:17",500);}
::16:{app.setTimeOut("anim['test'].frameNum=Math.random()>2/3?18:Math.random()>1/3?19:20",500);}
::17:{app.setTimeOut("anim['test'].frameNum=Math.random()>1/2?19:20",500);}
::18:{app.setTimeOut("anim['test'].frameNum=Math.random()>2/3?21:Math.random()>1/3?22:23",500);}
::19:{app.setTimeOut("anim['test'].frameNum=Math.random()>2/3?22:Math.random()>1/3?23:24",500);}
::20:{app.setTimeOut("anim['test'].frameNum=Math.random()>1/2?23:24",500);}
::21:{app.setTimeOut("anim['test'].frameNum=0",500);}
::22:{app.setTimeOut("anim['test'].frameNum=0",500);}
::23:{app.setTimeOut("anim['test'].frameNum=0",500);}
::24:{app.setTimeOut("anim['test'].frameNum=0",500);}

Beamer

以前一直觉得写Beamer很麻烦,但其实还行。建议的步骤是先写完文档,然后适当手动分页就可以改成幻灯片了。下面是一个简单的模板。

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
\documentclass{beamer}

\usepackage{ctex}

\mode<presentation>{
% list of themes
%\usetheme{default}
%\usetheme{AnnArbor}
%\usetheme{Antibes}
%\usetheme{Bergen}
%\usetheme{Berkeley}
%\usetheme{Berlin}
%\usetheme{Boadilla}
%\usetheme{CambridgeUS}
%\usetheme{Copenhagen}
%\usetheme{Darmstadt}
%\usetheme{Dresden}
\usetheme{Frankfurt}
%\usetheme{Goettingen}
%\usetheme{Hannover}
%\usetheme{Ilmenau}
%\usetheme{JuanLesPins}
%\usetheme{Luebeck}
%\usetheme{Madrid}
%\usetheme{Malmoe}
%\usetheme{Marburg}
%\usetheme{Montpellier}
%\usetheme{PaloAlto}
%\usetheme{Pittsburgh}
%\usetheme{Rochester}
%\usetheme{Singapore}
%\usetheme{Szeged}
%\usetheme{Warsaw}

% list of colors
%\usecolortheme{albatross}
%\usecolortheme{beaver}
%\usecolortheme{beetle}
%\usecolortheme{crane}
%\usecolortheme{dolphin}
%\usecolortheme{dove}
%\usecolortheme{fly}
%\usecolortheme{lily}
%\usecolortheme{orchid}
%\usecolortheme{rose}
%\usecolortheme{seagull}
%\usecolortheme{seahorse}
%\usecolortheme{whale}
\usecolortheme{wolverine}
}
\title{Test}
\author{zhzh2001}
\date{}

\begin{document}
\frame{\maketitle}
\section{A}
\begin{frame}
\frametitle{Overview}
A is a simple problem... \\~\\
A new paragraph...
\end{frame}
% ...
\end{document}

可以修改beamer的主题和主题色,专门有网站可以预览,也可以自己一个一个编译尝试。frame表示页,既有命令形式,用于写少量内容;又有环境形式,一般用环境。

beamer中的段落间是没有空隙的,所以一般在段间写上\\~\\,相当于一个空段。另外,根据我的个人偏好,认为主题的sectionsubsection的标题太小,所以就不用,而是直接在每页里手动加上对应的节标题作为页标题。这感觉不太优美,但暂时没有好的方法。

也有一些第三方主题,我没有试过。

Overleaf的使用

我们知道,一般用的LaTeX发行版是TeX Live或MikTeX(主要是Windows),前者我一般下载完整镜像安装,或者装软件包;后者则只安装核心,宏包在需要时在线下载安装。因此TeX Live是很费空间的,MikTeX好一些,但很多时候需要Internet。这两种发行版在固定的地方安装一下还能接受,但部署不方便,不适合移动。即使有portable,但也不方便(其实是我没装好过)。

于是就有了在线编辑平台,Overleaf就是比较流行的。除了无需配置环境,Overleaf免费版还支持与1个人合作,以及24小时内的版本控制。其实我最早用的是ShareLaTeX,只是现在被Overleaf收购了,被包装成Overleaf v2。

Overleaf用起来很方便,一般只要把本地的源文件直接复制上去,再上传相关文件,就能编译通过了。Overleaf用的应该是*nix,所以会比MikTeX编译的文件大不少。

VeraCrypt

为了在学校编辑足够的安全性,我考虑使用加密工具,Windows自带的功能并不靠谱。一开始我用的是不知哪里看来的Cryptomator,创建一个加密的磁盘并挂载,界面极其简洁。问题是它好像是通过网络磁盘的形式提供的,CCR好像稍微一来就会TLE,可能是性能太差了。而且只有AUR提供。

然后我机智地想到了用VHD+Bitlocker,在学校玩了一周,挺好用的,只是没有锁定功能,非得用命令解决。然而拿到家里我就傻眼了,因为Linux下怎么查看?貌似有支持Bitlocker读写的东西,但再加上VHD,还是太麻烦了,也不是原生的。

于是我决定找一个原生的跨平台加密方案,找到了VeraCrypt。VeraCrypt的前身是TrueCrypt,已经停止支持。而VeraCrypt有活跃更新,而且无需AUR,也不存在任何性能问题。只是建议的密钥长度大于20位,我不得不改huami.py,Windows版是支持32位完整密钥的。它还支持密钥文件之类的奇怪操作,我也不想试。