day -2 & -1

别人停课两周，我停课两天。

day 0

两三年没坐飞机了吧。
机长的操作真是稳，落地刹车急转弯，一位老兄的手机都滑掉了。

帝都超级热啊。挥汗如雨。
被拦在 THU 门口，保安尽职尽责。

晚上背模板，十一点半睡觉。

day 1

爆炸的一天从此开始。

上午

作为一个酱油选手（dalao们可以右上角退出），遇到了很多锅。
迟到半小时，发现是 Windows 的电脑。（注：正式选手是 Ubuntu）
i7-4790，16G，R7 240 居然奇卡无比。

第一题 求区间 LIS，$n\le 10^5,q\le 10^7,a_i\le 10^3$ ，强制在线，1G，10s。
第一次见到这么毒瘤的范围。想到平时的单调队列二分求法，只有30pt。
直觉觉得和 $a_i$ 有关。
猜想可持久化单调队列，搞不出。
猜想两个LIS合并，发现合并一次O(1000)，爆炸。
猜想O(1)回答询问，没思路。
至此，比赛已经过了两个半小时。 是的，我太菜了。

退回到最基本的 dp，考虑如何在 LIS 的末尾接上一个数，条件是 $k<j$ 且 $a[k]<a[j]$ 。
设 dp[i][j] 表示 满足 LIS 长度为 i，最后一位是 a[j] 的串，最靠右（解决 LIS 不唯一的问题）的起始位置。
外层循环 j，内层循环 i，转移需要知道 LIS 长度为 i-1，最后一位满足 $k<j$ 且 $a[k]<a[j]$ 的 dp[i-1][k] 的最大值。显然 LIS 长度≤1000。考虑给每个 LIS 长度 i 建一个树状数组，下标是 a[j]，值是 dp[i][j] 。不断取 max，转移就显然了。

dp[i][j]=query(i-1,a[j]-1);
update(i,a[j],dp[i][j]);
dp[i][j]=max(dp[i][j],dp[i][j-1]);

询问的时候二分，找到 dp[x][ri]≥li 的最大的x即可。
吐槽一下强制在线的方式，迭代值爆int。

第二题 字符串题。没时间了，暴力分也不多，跳过。

第三题 好评！人工智障！
有史以来做过最有趣的提交答案题。
你需要猜想什么输入运行 ./ai 后能够输出样例。10个点的数据，每个点有4种难度，挑一个就行。
下发的文件是 Ubuntu 的，Windows 又出锅了。等着管理员把 win 版本的 ai.exe发过来。

然后遇到了换行符问题。ai.exe 显示的行数不对。

凉凉。本机答案正确，上传发生SPJ ERROR。
由于时间不够，后面的数据还没做来得及下去。本来多个二三十分没问题。
rating估计前70吧。爆炸。

下午

subway好吃！

听吴建平教授、吴文虎教授、王逸松同学讲话。
王逸松同学：“……，不是体现在你的代码能跑多快。”

然后逛清华园。
清华真是大。但它的美不是体现在气势宏大，而是在细节处宛如苏州园林的美。
水木清华，荷塘月色。

day 2

上午

今天没有遇到锅。
第三题
拿到题先看提答。
题意：给出若干个 $?\times ?$ 的小方块，将它们拼成一个大方块。小方块可以旋转，方块之间可以有空隙。利用率越高得分越高。同时要求拼出的大方块有一边的边长满足 $L\le x\le R$ ，否则另外扣分。输出大方块剪成小方块的方案。

第一个点的方案提示很明显，就是手玩输出方案比较麻烦。
第三个点 L=R=2 ，同时所有小方块有一边边长是 1。做背包即可。（有一个 1×2的方块要竖着放）
别的一眼看不出。通解好难打，暂时跳过。

第一题
题面和洛谷5月月赛太极剑类似。所有的连边只在奇数点之间，偶数点之间可以发出能量。但是切断一条连边需要一定的能量，求切断所有连边所需的最小总能量，并输出一种方案。

出题人本来想令所有连边切断能量都等于 1，那就是月赛原题了 QwQ。出题人本来还不知道月赛这回事。
当时在做月赛的时候就在想，可以用差分约束，但是数据范围大，过不了。题解给了一种线性方法，但是没看懂。可惜对考试题不适用。
考试题的范围 $n\le 2000$ 是可以用差分约束的。果断开始建图，交上去 WA 了好几次，后来发现建边错了。

第二题
题意：一个点有 Ri 只红色史莱姆，Gi 只绿色史莱姆。所有史莱姆互不相同。给出一棵以 1 为根的树。每次从 1 出发，不能走回头路，到叶子时停止。在每个点收集且只能收集 1 只史莱姆。求分别收集到 0~n 只史莱姆的方案数。不同的史莱姆算不同的方案。

一看就是 FFT 之类的东西，是个卷积。可我就是不会。背板子有什么用？又不会用。
打完 dp 滚粗。

下午

讲题。

d1t1 dp。34人AC
d1t2 AC自动机上乱搞。
d1t3 平均得分30+。数据点记不清了。有求定积分，定位，行列式……第九个点好评，但是女主出锅了。出题者：如何评价 THUSC 2018？ - 赵金昊的回答 - 知乎

d2t1 差分约束系统。震惊！仅 10 人有分，1 人AC。个人觉得这题还算简单。
d2t2 长链剖分，分治 NTT。震惊！这是全场平均分最高的题。
d2t3 模拟退火跑数小时。

day 3

由于是酱油选手，也就没有什么面试之类的东西了。
下午听讲座，学长讲清华的学生活动。

最后，恭喜 rank1 的司机获得无条件一本资格。这次只签了十来个一本。

最后

以上就是含糊便当为你收集整理的THUSC2018 观光记day -2 & -1day 0day 1day 2day 3的全部内容，希望文章能够帮你解决THUSC2018 观光记day -2 & -1day 0day 1day 2day 3所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。