CTSC 2018 游记
浮尘ii
·
·
个人记录
APIO 2018游记由于题目保密规定，过几天再更。
day0 5.6 报到
赶火车去北京。下午到了以后去试机，然而并没有试机，在北京八十中里面乱逛。
据同学说机子特别快，100w次std::set的insert只用了特别短的时间（具体数字记不清了
第二天要考试，晚上睡得比较早。然而某bot第二天军训晚上还弄到两三点，这个我先记着。
day1 5.7 比赛一
早饭点了一个肉夹馍就没了？？？好在听说考场会发吃的。于是考场发了一瓶矿泉水，两个士力架以及一个面包。
T1 假面 faceless
题目大意
给定n个数a_1,a_2,...,a_n(a_i\in[1,m])，有两种操作：
\quad$1. 给定$u,v,i$，若有$p=\frac{u}{v}$的概率将第$i$个数$-1
所有操作完成后，还需要求出最后每个数的期望，对$998244353$取模。
$n\le200, Q\le 2\times10^5,C\le10^3,m\le100,id_i$互不相同$(1\le i\le k)$，
其中$Q$为总操作数，$C$为第二种操作数。
##### 分析
对于操作1，我们令$F[i][j]$表示第$i$个数为$j$的概率，则$F[i][0]=F[i][0]+p\cdot F[i][1], F[i][j]=(1-p)\cdot F[i][j]+p\cdot F[i][j+1](0<j\le a_i)$，则最后第$i$个数的答案即为$\sum_{j=0}^{a_i}{j\cdot F[i][j]}
对于操作2，对于id_i，答案为P(i)\cdot\sum_{j=0}^{k-1}{\frac{1}{j+1}\cdot P_i(j)}，其中P_i(j)表示除a_{id_i}以外，恰好有k个数非0的概率，P(i)表示a_{id_i}非0的概率.
$G[i][j]$表示前$i$个数恰好有$j$个非$0$的概率，则$G[i][j]=(1-P[i])\cdot G[i][j]+P[i]\cdot G[i][j-1]$.
考虑加上除$a_{id_i}$以外的限制，有如下方法：
- 题解做法：推出$P_i(j)$与$P_{i+1}(j)$的关系，$O(1)$转移，时间复杂度$O(Cn^2)
- CDQ分治：考虑问题即求解除去一个物品的背包，可以使用CDQ分治，时间复杂度O(Cn^2\log n)
- 松松松：考虑将前缀背包和后缀背包分别求出，在a_{id_i}处只需要合并i-1前缀的背包和i+1后缀的背包，时间复杂度O(Cn^3)，由于常数较小，再注意一下常数问题，考场上以5.8s压线通过此题。
据LCA说有O(Cn\log n)的神仙做法，然而并没有人写。
T2 暴力写挂 wronganswer
题目大意
给定两棵树，求\max\{depth(x)+depth(y)-depth(LCA(x,y))-depth'(LCA'(x,y))\}(1\le x,y \le n)，其中depth(i)表示1到i的距离，带'的表示在第二棵树中。
n\le366666
分析
并不会，写了个O(1)LCA，枚举x,y，O(n^2)拿到了45pts(n\le 12345)。
据说爬山/贪心能拿到高分甚至满分……
然而并没有去WC，所以并不知道这些事情。
T3 青蕈领主 green
题目大意
定义一个长度为m的整数序列是连续的，当且仅当这个序列中最大值与最小值的差\le m-1。
给定L_i(1\le i\le n)表示以i为右端点的最长连续区间的长度，求有多少种1~n的排列满足给定的L_i。
多组数据，答案对998244353取模。
T\le100,n\le5\times10^4
分析
并不会，写了个O(T\cdot n!\cdot n^2)，拿到10pts(n\le10,T=1)。
考场傻了，对于另外的10pts(n\le10, T\le100)，直接把每个排列的L_i弄出来然后hash或者map就好了，复杂度O(n!\cdot n^2 \cdot f(n))，f(n)表示查询L_i的复杂度。然而这个10pts并没有拿。
另外，通过打表找规律发现，对于L_i=i的情况，答案即为2^{n-1}，于是又拿到5pts
于是day1 100+45+15=160
day2 5.8 答辩
-
时间复杂度不及是不是更优。
-
莫队算法是什么。
-
要让初学者看懂论文。
下午人工智能专题一个是mix lab一个是360网络安全实验室。并没有太在意听。不过八十中貌似是360挂牌的网络安全实验室基地？并没有怎么宣传360的产品，挺切合主题。
day3 5.9 比赛二
分到了415机房考试，前一天听说有提交答案题，感觉药丸，毕竟没有做过提交答案题。
T1 混合果汁 juice
题目大意
有n种果汁，每一种果汁有美味度d_i和单价p_i元/L，以及限制l_i表示最多往一一瓶混合果汁中加入l_i升此种果汁。
一瓶混合果汁的美味度定义为所有参与混合果汁的美味度的最小值。
$n,m\le10^5
分析
很明显想到可以二分答案，二分答案k后将di\ge k的果汁拿出来，从价格最小的开始往里加，看加入L_j升后的价格是否\le g_j，并调整二分上下界。判断价格可以使用以价格作为下标的线段树，查询时在线段树上二分即可。复杂度O(n^2\log^2 n)（分析复杂度时假设n,m同阶，下同）
考虑能否放在一起二分，发现可以，于是使用整体二分即可。
或者每次二分不再重构线段树，而是先建立可持久化线段树，然后二分答案后直接在可持久化线段树上二分。
时间复杂度O(n\log^2n)。
T2 字典树 trie
题目大意
给定一棵n个结点的trie树，每个转移边为数字0~9或者','，满足对于每一个从根到叶子的路径，所表示的字符串都可以看成由','分隔开的递增的十进制整数序列。
现在m条边上的字符不确定，请你找到一种字典序最小的填法使得这个trie树满足题目要求。
分析
并不会，直接在trie上DFS，对于每一个不确定的位置，贪心的字典序从小到大填。时间复杂度O(11^m\cdot n)。
期望得分0pts，然而实际测试时通过了20pts(n \le 80, m\le 8)。
T3 组合数问题 placement
题目大意我也不知道，因为没读完就直接随了n个[1,k]上的数开始退火/爬山（先退一遍火，在退火的答案上进行多次爬山）了。
一开始simulator运行不了，监考过来帮我加了权限。
chmod +x simulator
好在这个simulator会把答案输出到res.txt，直接读进来退火/爬山就好了。
拿到了10+10+3+2+2+10+3+3+10+10=63pts
于是day2 100+20+63=183pts
中午吃完饭就来考场门口等成绩，然而发现CCF NOI科学委员会全部跑到了我们考场，感觉事情不太妙。
然后群里就开始说514考场的监考说程序丢了。WTF？本机评测程序还能弄丢？
果然，后来老师让我们去礼堂，说这里下午先不评测了。
晚上闭幕式之后，CCF留下来了85个人，说我们成绩拿不到了，让我们明天补测。说什么不会亏待我们，要相信CCF NOI科学委员会能很好地解决这件事。
day4 5.10 比赛三（补测）
拿到题目一看，和昨天的题目一样的？？？
好吧，那就开始写吧，昨天的经验告诉我，最后一题退火/爬山需要很长时间，于是就先码了T3，放在后台慢慢跑。
于是T3就多了9pts(10+10+10+2+2+10+5+3+10+10=72pts)
别的题目没动。
于是day3 100+20+72=192pts
不过据说考场别的人都是几十分几十分的加。
颁奖日 5.14
前一天看到成绩了，放在一起排名是42，不过如果分开按比例排名可能就没有金牌了。
最终CCF给出的方法是排除85人后划分成绩线，并且85人照样拿牌，而且适当的提高了获奖比例。
最后还是拿到了金牌。
不过当天晚上在我校杂话墙上被挂得莫名其妙。