51nod算法马拉松22总结

马拉松22总结"/>

51nod算法马拉松22总结

突然发现自己好像有几篇blog被陶冶大大拉去示众了=w=
那么就不能乱水了，好好的总结一下吧。。。

3.3

听说比赛昨天晚上开了？？？
有人秒切题2333
A一脸不可做的样子，CF原题有人做过吗？
B更是一脸不可做，期望什么的最方了。。。
C？？？？
欺负我初三刚刚会求导TAT
D？？？？
woc这次马拉松怎么这么鬼
是不是所有题的分值都被黑幕除了个2
E感觉可持久化加链剖可以搞
但之前写的可持久化链剖的空间似乎要500MB
再说了我也不觉得我写的出来。。。

然后就一直颓颓颓，毕竟还要准备中考没什么心情去想题
然后A题有了一个O(NTlogN)的想法，刚想开始打，看群发现A数据错了。。。
算了我还是不打别掉raiting了。。。
颓到了时间回去上课了。。。

3.4

早上有一场全国开放的比赛啊！好好打。。。
结果只会T1（猜结论）然后后半场一直无所事事
滚回来想马拉松
发现A题数据改了
但又听说带log不优美过不去QwQ
于是决定先想B题
B的话可以设Fi表示第一次得到i颗星的最小期望代价
那么转移的话不就是

Fi=Fi−1+minj(Cj+(1−p)(Fi−Fi−l−1)) $$F_i=F_{i-1}+min_j(C_j+(1-p)(F_i-F_{i-l-1}))$$
因为掉完星还要再回来啊。。
那么移项之后直接转移就好了
写完之后发现WA掉了几个点
一定是精度被卡了QwQ
然后换float128上
还是WA？！
然后猛然意识到没有判-1
改完之后还是WA？！
对着代码想了好久。。。
woc inf开小了
交了6次终于过了

然后想A
发现排完序之后似乎就可以贪心了
开个栈维护b，先放a，不能放之后从栈顶放b的。。。
写完之后又WA了？？？
这个是真的一脸懵逼了
最后发现自己是先加a中的数再入栈的。。
换一个顺序？！
过了！！！
呵呵呵我也是醉了
看看表5:30了
时候不早了就这样了吧，这次题这么难拿了AB应该不会掉rating了

赛后

woc还是掉了7啊TAT
十分不爽
因为后来在家里已经想出D怎么写了
只不过家里电脑配置太差写不了题（打个永夜抄都CPU100%）
C的话看过WrongAnswer的题解终于还是推出来了。。。
现在口胡一波
D可以发现把点按照最高位是0还是1分成两组，那么mst肯定是两组内分别连然后再选择两组中异或值最小的那两个点连边。
那么就分治下去，然后对其中一组建一棵trie，枚举另一组的每一个点来更新答案
最后发现点权相同的不会算23333
自己推了一波基尔霍夫矩阵也无果（navie！）
然后上网查才发现n个点的完全图的生成树的个数是 n(n−2) $n^{(n-2)}$
然后就过了，连读入优化都没写。。。
C 首先你需要会基本的微积分。。。
强行展开那个式子

∑i=0n∑j=0naiajxi+j+1−2∑i=0naixiex+e2x $$\sum_{i=0}^{n}\sum_{j=0}^{n}a_ia_jx^{i+j+1}-2\sum_{i=0}^{n}a_ix^ie^x+e^{2x}$$
最后一项常数不管他，然后暴力积分
我们知道 (xi)′=ixi−1 $$(x^i)'=ix^{i-1}$$
那么 ∫10xidx=1i+1i+1−0i+1i+1=1i+1 $$\int_0^1 x^idx={1^{i+1}\over {i+1}}-{0^{i+1}\over {i+1}}={1\over {i+1}}$$
所以前面的可以积成
∑i=0n∑j=0naiaji+j+1 $$\sum_{i=0}^{n}\sum_{j=0}^{n}{a_ia_j\over {i+j+1}}$$
但是发现 xiex $x^ie^x$不会积
没有想到可以找规律=w=
我们可以推出
((x−1)ex)′=xex $$((x-1)e^x)'=xe^x$$
((x2−2x+2)ex)′=x2ex $$((x^2-2x+2)e^x)'=x^2e^x$$
((x3−3x2+6x−6)ex)′=x3ex $$((x^3-3x^2+6x-6)e^x)'=x^3e^x$$
在推的过程中我们可以发现左边 xi $x^i$的系数乘个(n-i)就得到了 xi−1 $x^{i-1}$系数
那么我们可以归纳出 (∑i=0n(−1)n−iPn−inxiex)′=xnex $$(\sum_{i=0}^{n}(-1)^{n-i}P_n^{n-i}x^ie^x)'=x^ne^x$$
所以 ∫10xiexdx=∑j=0i(−1)i−jPi−jie−(−1)ii! $$\int_0^1x^ie^xdx=\sum_{j=0}^{i}(-1)^{i-j}P_i^{i-j}e-(-1)^ii!$$
因为我们把 00=1 $0^0=1$
这样的话原式就等于
∑i=0n∑j=0naiaji+j+1−2∑i=0nai(∑j=0i(−1)i−jPi−jie−(−1)ii!) $$\sum_{i=0}^{n}\sum_{j=0}^{n}{a_ia_j\over {i+j+1}}-2\sum_{i=0}^{n}a_i(\sum_{j=0}^{i}(-1)^{i-j}P_i^{i-j}e-(-1)^ii!)$$
求最小值
考虑偏导，就是把每个ai当做自变量，其他的aj当做常数对原式求导为0
那么我们把ai拿出来
a2i2i+1+2∑j=0,j!=inaiaji+j+1−2ai(∑j=0i(−1)i−jPi−jie−(−1)ii!) $${a_i^2\over {2i+1}}+2\sum_{j=0,j!=i}^{n}{a_ia_j\over {i+j+1}}{}-2a_i(\sum_{j=0}^{i}(-1)^{i-j}P_i^{i-j}e-(-1)^ii!)$$
求导
22i+1ai+2∑j=0,j!=inaji+j+1−2(∑j=0i(−1)i−jPi−jie−(−1)ii!)=0 $${2\over {2i+1}}a_i+2\sum_{j=0,j!=i}^{n}{a_j\over {i+j+1}}{}-2(\sum_{j=0}^{i}(-1)^{i-j}P_i^{i-j}e-(-1)^ii!)=0$$
这样我们就得到了n+1个方程，有n+1个未知数，高斯消元即可。
注意到只有常数项有e存在，也就是说所有的ai都可以表示成xe+y的形式
所以直接上就好喽~~
终于用微积分做出题来啦O(∩_∩)O~~