JSOI2019R1过去了。
Day0
打板子。看白书。
晚上太热了，楼下还在打铁，睡不着。
折腾到好晚才勉强睡着。
Day1
早上好困啊。
开T1。看起来T1的60分很可做的样子？5min打完了（为后文的爆炸埋下伏笔）
开T2。emmm这什么玩意啊？？制胡窜？？？怎么像个图论？？？
大力码T2。。。一遍过样例很舒服。。
开T3。咦这怎么会有个题答啊。。。
看看第一个点。。woc这不就是个快速幂？？？写上了。。woc高精度？？？码码码。。。
好吧写完了。。。看看wa又是个什么玩意。。。
什么东西啊？？！！爆int？？？技不如人，甘拜下风
去看看2p是个什么。。咦看着和gcd挺像？？什么东西？？！呸呸呸不就是个筛素数的。。。
那。。。对了白书上有一个筛\([a,b]\)的程序！但是记不得了。。。
手推。。。哦只要取\(O(\sqrt{b})\)内的小质数就可以了？？
那。。。怎么过不了第10个点啊。。。woc竟然是\(b=10^{18}\)的？？？
那算了。
完蛋我怎么啥都做不出来了啊。。。
看看T1的100pts？不会。
看看T2的60pts？不会。
看看T3还有什么可做的部分分了。。。没有。。
好像第一个wa的点可做啊？看看随便写个能过否？
咦竟然过了？太神奇了。。
T1怎么看着像什么“线性基”？？不会不会。。
那做什么啊。。。
肝T2去？？？算了还是做T1吧。。
咦是不是可以归并搞一搞？？？
码码码。。。鈤这做法怎么假掉了。。
哦好吧就是假掉的。。。
怎么只有半个小时了啊？
还是滚去看T3了啊。。
2g到底是什么功能啊。。。
完蛋。
Day 1.5
讲题。听不懂。
看成绩。0+40+28？？？第一题怎么炸了？？？
靠我有一个unsigned竟然写成int了！！！
回想一下我当时在干嘛。。。
原来是写了个vector，然后怕老爷机鬼掉，就。。。
写了个这么玩意：
int v[N*N],cnt;这我其实能在几个时候查出来：
- 写的时候不那么吊儿郎当的，不写那么快，仔细点
- 写完测个大样例。。。即使跑不出来也要等等。。
- 最后肯定得检查！！
还有重视程度不够。
每一个字符都是分啊！！！
Day 1.75
打比赛。大众5题。我竟然卡B上半天。
技不如人，甘拜下风。竟还加了5分？？
今天晚上睡的舒服多了。
Day 2
开T1。皮配？？？劈配？？？不会是网络流吧？？？
（5min后
emmm好像网络流不能计数啊？那算了。
去开T2。这不是个状压dp吗？
码码码。。。一遍过样例很舒服。。。
去开T3吧。怎么这么小气就给16分裸暴力分啊。。。
开始学习中国东部沿海及长江沿岸地理
滚回去看T1吧。。。
怎么就给30pts暴力？？？算了想想多点分的。。。
这不是个裸dp吗？\(dp(i,j,k)\)表示第i个城市，？？阵营j人，？？派系k人？？
怎么转移啊。。。哦再搞个dp转移吗。。。
这么变态？？？好吧码码码。。。
怎么过不了大样例？？
md我是不是没取模。。。咦取模了啊？？
那。。。
（20min后
md重构代码吧。。。
好了终于过了。。。我写的什么玩意啊！
话说我每次考完出来看我考场代码都是“什么玩意啊”。。。
卡卡常。。看来是过不了80分了（捂脸
那。。再搜刮点部分分？（剥削
鈤我怎么没看见T2这个链啊？
码码码。。真简单
话说我除了暴力的部分分真用暴力以外直接用这个链做吧。。。
然后就是我多拿了10分的开心故事
好像也没法做了。。。
看看T1能不能搞个正解出来吧。。（80分也好啊。。
md什么东西啊！
@#%&…
结束了。。
Day 1.5
听讲题。。更听不懂了。。
讲到一半ztr家长发成绩单过来了。。
然后我们后半段就在研究成绩。半点都听不懂了。。（强行辩解）
wow我今天竟然卡进30名了？
50+70+16耶。。
咦怎么T2还多。。了10分？？？
复测一把发现我这个链竟然把某些弱鸡数据给跑过去了。。。
真有趣。。
总结
总体来说。。Day1渣渣，Day2还行？？？
如果我Day1不炸掉那60分我就可以买D了。。
可惜，没有如果。
Round2翻盘吧。
JSOI2019Round1Day2T2
算法1
\(n \leq 16\)。
所以果断状压dp啊。
考虑\(dp(mask)\)表示\(mask\)集合里的节点分配段之后最少总内存和。
那么转移的时候枚举现在把\(nmask\)里的点都放到同一个内存段里面。
为了在\(O(n\times 3^n)\)的时间内完成整个转移操作，
我就用了\(dfs\)转移。。。所以代码就奇丑无比（循环调用
然后注意可以用\(dfs\)序来判断\(u\)是不是\(v\)的祖先。
（话说其实我们可以预处理一下，从每一个\(v\)往上跑。。。
所以复杂度\(O(n\times 3^n)\)。
预计得分：45
实际得分：45
算法2
注意到链的部分分。
我们假设链长这样：u--1--v
所以我们看怎么找\(u\)和\(v\)。
不妨设\(u\)是深度最大的那个节点。
那u--1的路径都用过了。
剩余节点中的最深的就是\(v\)啊。
那么再看怎么分组。
理性思考一下
只要在\(u\)到根的路径上最大的和\(v\)到根的路径上最大的配，
次大的配，然后某个没了就单独一组。
想一想为什么（我才不会说我是弄了个数据看出来的呢
就酱。
然后其实不用判断这个数据是否真的是链。。
因为我也写不出来其他部分分了
结合算法1即可。
但数据奇弱无比，还多过了两个点。。。
可能就是真正的分类方案最大的真的在最深的两条链上。。
预计得分：60
实际得分：70
