Codeforces_Round#721_div2
这场是真的搞人心态…居然卡在B题,最后一分钟才过B2,人麻了
不过这次的题目质量还是挺高的,蛮有意思的一场div2
本场传送门
A
1234567891011121314151617181920#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=2e5+10;int main(){ int T;scanf("%d",&T); while(T--){ int n;scanf("%d",&n); int p=0; for(int i=0;i<=n;i++){ if((1<<i)>n){ p=i-1;break; } } printf("%d\n",(1<<p)-1); } return 0;}
B1&B2
yys ...
XJTU校赛#2021游记
回顾
机房的电脑居然是32位的,着实是搞人心态,vscode配好了居然没法编译…
五一开始感冒到现在都没好,前一天晚上还加重了QAQ,考试的时候头晕又犯了,不过还好挺住了,也算是有惊无险吧。
说实话挺忐忑的,害怕自己打得不好,但是比赛开始后就没啥感觉了,还是挺平静的然而刚开始还是太激动了,A题因为没保存就提交挂了一发
最后的J题,idea一下子就出了,但是debug整整花了快两个半小时…先是用map结果TLE,然后又发现线段树的区间上限写错了,结果改了还是WA。本来都想放弃了,花了一个小时才发现原来是贪心的时候漏了一个判断条件…
最后在封榜十多分钟之后成功AC,算是松了一口气。
最终排名rank3,也算是一个不错的结果了吧。
总结
这一场下来暴露的问题还是挺多的,码力还是不太行,J题这么简单居然写了3个多小时。然后还有就是算法的积累也不够多,图论学的太差。希望以后继续努力吧。
这次校赛好像并没有进行校队的选拔白高兴一场,今年的选拔仍然是依据小学期的ACM培训,
距离上一次小学期已经一年了,希望今年我的进步能弥补去年的遗憾吧。
容斥原理
容斥原理的定义
设U中有n种不同的属性,第i种属性为PiP_{i}Pi,拥有属性PiP_iPi的元素构成集合SiS_iSi,则有
∣⋃i=1nSi∣=∑i∣Si∣−∑i<j∣Si∩Sj∣+∑i<j<k∣Si∩Sj∩Sk∣−⋯+(−1)m−1∑ai<ai+1∣⋂i=1mSai∣+⋯+(−1)n−1∣S1∩⋯∩Sn∣\left|\bigcup_{i=1}^{n} S_{i}\right|= \sum_{i}\left|S_{i}\right|-\sum_{i<j}\left|S_{i} \cap S_{j}\right|+\sum_{i<j<k}\left|S_{i} \cap S_{j} \cap S_{k}\right|-\cdots +(-1)^{m-1} \sum_{a_{i}<a_{i+1}}\left|\bigcap_{i=1}^{m} S_{a_{i}}\right|+\cdots+(-1)^{n-1}\left|S_{1} \cap \cdots \cap S_{n}\right|∣⋃i=1nSi∣=∑i∣Si ...
概率DP
概率DP
期望DP
「NOIP2016」换教室
又是一道当年没做过现在来补票的NOIP题目
定义DP状态为fi,j,0/1f_{i, j, 0 / 1}fi,j,0/1,其中i表示在第i个时间段,连同当前时间段总共用了j次换教室的机会,在这个时间段换(1)或者不换教室(0)的最小期望路程和。答案就是max{fn,i,0,fn,i,1},i∈[0,m]\max \left\{f_{n, i, 0}, f_{n, i, 1}\right\}, i \in[0, m]max{fn,i,0,fn,i,1},i∈[0,m]
如果当前阶段不换教室
fi,j,0=min(fi−1,j,0+wci−1,ci,fi−1,j,1+wdi−1,ci⋅pi−1+wci−1,ci⋅(1−pi−1))f_{i, j, 0}=\min \left(f_{i-1, j, 0}+w_{c_{i-1}, c_{i}}, f_{i-1, j, 1}+w_{d_{i-1}, c_{i}} \cdot p_{i-1}+w_{c_{i-1}, c_{i}} \cdot\left(1-p_{i-1}\right) ...
动态DP
模板
洛谷 P4719 【模板】动态 DP
因为要动态维护树上的DP方程,所以很容易想到利用树链剖分进行优化。进而考虑使用重链的性质来化简DP过程的复杂度。这里将重链和轻链的对DP的贡献分开考虑,从而使用广义矩阵乘法,使DP过程得以在线段树上实现。
证明广义矩阵乘法的结合律
因为max,+,*都满足结合律和交换律,并且*对+有分配律,+对max也有分配律。我们将max和+分别看成*和+,和证明普通矩阵乘法的方法一样,把计算的每一项都展开即可。然后可发现对于矩阵A,B,CA,B,CA,B,C做广义矩阵乘法,满足(AB)C=A(BC)(AB)C=A(BC)(AB)C=A(BC)
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410 ...
蓝桥杯&CCCC天梯赛#2021——总结
最近感觉越学越菜了…
一
蓝桥大题就出了两个,填空题就对了三个。大题里一个博弈,一个DP,全都差一点出,欸。感觉DP还是做太少了,本来DP状态都想好了,写法也明确了,就是具体写式子的时候出差错,菜的一匹。填空题更啥b,下午回去把错的题代码重写了一下,结果居然就和标准答案一样了,都搞不懂当时我是咋写错的。最后一个状压我也没写,当时写了个暴力跑不出来就跳了,如果知道第一时间反应过来是dp也能做的吧,欸。
二
天梯赛也是难顶,三个多小时,断线重连了十次
第一个题看都没看。第二个贪心还没想到,还以为这道题是Trie+DP(因为才补了一道Trie上矩阵快速幂加速DP的题)。其实写暴力也能过,但暴力写错了,忘记了首尾连接处要重合起来。
前面也是,字符串和STL的两道题卡了贼久…字符串相关的库函数不会用,map的hash也不会写
最后两百分草草收场,L3爆零了…
三
是怎么回事呢,明明每天都在做着自己喜欢的事情,明明每天都有一点进步,但是结果却是这样不尽如人意。
最近的cf一场没落,甚至还开了许多virtual contest。但我的rating居然不增返降,欸。
逐渐发现自己的实力其实并没有 ...
树链剖分
重链剖分
概述
由于重链剖分时,从根节点到叶子节点经过的重链数量必定小于等于lognlognlogn这一量级,故可以通过对每一条重链进行维护和求解得到最终答案。
只要经过了重链的某一个节点,就算是经过了该重链
一般来说,可以结合线段树维护dfs序,再通过类似于找LCA的方式向上跳,只不过这里向上跳是跳到该重链最上面的端点。然后在跳的过程中利用线段树对经过的每一条重链进行查询,对于每一次查询在log2nlog^2 nlog2n的复杂度求出答案。
例题
「SDOI2014」旅行
由于有多个不同类型的点,对于每个种类的点我们都要开一颗线段树。但是由于点的种类能达到10510^5105之多,故不能像以往那样每次都直接建立出一个大小为nlognnlognnlogn的线段树。这里在建树时,我们只能一个一个地加点,并且加点时只需要开辟根节点到该节点这条路径上的点即可(每次要存储lognlognlogn个点)。
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950 ...
Berlekamp_Massey 算法
问题模型
给定一个有n个元素的数列a,其中第i个元素是aia_iai 。
求一个较短或最短的数列b,假设b有m个元素,那么要求满足∀m<i≤n,ai=∑j=1mai−jbj\forall m<i\leq n, a_i = \sum_{j=1}^m a_{i-j} b_j∀m<i≤n,ai=∑j=1mai−jbj
要求在O(n2)O(n^2)O(n2)的时间复杂度内解决此问题
Berlekamp_Massey
假设递推式经过c次更新,第i次更新后递推式为R[i]R[i]R[i]。初始时,定义R[0]R[0]R[0]为空。
假设当前递推式的长度为m,这时候考虑用递推式去算a[i]a[i]a[i]是否成立
设deltai=ai−∑j=1mai−jR[c][j]delta_i = a_i - \sum_{j=1}^m a_{i-j} R[c][j]deltai=ai−∑j=1mai−jR[c][j]
如果deltai=0delta_i=0deltai=0,那么R[c]R[c]R[c]依然合法,不用修改
否则,设failc=ifail_c=ifailc ...
论把博客部署到服务器时踩过的坑
因为服务器到期,已经好久好久没有更新博客了,哭了
阿里云太奇葩了,学生优惠只能买一年的服务器,但是续费的话就没优惠了 😦
但是更扯的是,虽然续费没有优惠,但是买新的服务器却还是可以的有优惠的不得不说这政策是真的啥b
所以又花了一番功夫才又把数据搬到这个新的服务器上面,期间又遇到了一些奇奇怪怪的坑。还是总结一下叭,希望以后换的时候就没这么恼火了
教程
带你跳过各种坑,一次性把 Hexo 博客部署到自己的服务器
大致内容就是这些,下面是一些需要注意的地方
注意熟悉vim的使用方法,例如进入编辑模式(按’i‘),退出(’按esc‘),保存并退出(按’:wq’),退出不保存(按’:q!’)
阿里云会默认占用80端口,所以会导致nginx运行不了,这时候要先执行命令杀死占用80端口的进程
1sudo fuser -k 80/tcp
修改nginx的配置文件时,一定要注意把要修改的内容前面的’#‘删去(不然就相当于把它注释掉了,所以就会改了个寂寞我就是这里卡了好久,眼睛瞎没看到user root前面有个#,麻了)
如果重置了服务器,这时候本地的连接可能会出问题(没出现连接 ...
大二·上
回顾
总的来说,这一学期过得还是挺惬意的。
想翘的课就翘,作业也是想做才做,实在不行就抄了了事。虽然最后期末考试栽了,但也算是意料之中吧。
经过一年半的大学生活,慢慢地成“老油条”了,并不会像刚开始那样各种不适应,心态什么的慢慢地调整过来了一些,也算是找到了自己的状态。
这学期找了位电吉他老师,感觉有人带着确实比自学轻松多了(笑)。老师也是玩乐队的呢,不知道我未来两年多的大学生活,是否也会有机会去组个乐队啥的。如果真的有这回事了,也许也是ICPC拿金之后了叭(又一个flag)。
现在的我,似乎比以前坚定了不少,又不知不觉又成长了许多呢。
目标
这学期开始渐渐明晰了自己的人生方向,有了努力的目标。但是不论是练琴还是准备算法竞赛,我投入的时间和精力还不是很多,还是有些过于悠闲了。
希望这学期能坚持下去,每一天都不白废掉。周末或者平时没事的话,多去去图书馆;一周还是要多锻炼几次,不要天天宅在宿舍。
今年五月就是校赛了,在这里再立个flag(这个flag我是认真的),我要拿全校的rank1,拭目以待吧!