pinkyHead's blog

一 这学期终于结束了，感觉时间过的真快呀，日子就这么不知不觉的一天天溜走… 怎么说呢，感觉还是有些遗憾吧，cf至今仍然没有上橙，甚至还掉了不少分。 这学期的期末可真是太折磨了，两周学完了一学期的内容，快要累死了。 平时课全翘了，可是感觉自己并没有把这些时间利用好，还是拿去打游戏刷视频了，挺惭愧的。 期末考试还发生了意外，考模电的时候没带计算器，然后还因此挂科了…当然自己没认真学才是主要原因吧 前两天因为准备校赛还没有去参加专业实习的讲座，不知道会不会又挂一门小学期的实习课。 五一的时候，去图书馆自习回来，淋了雨然后又熬夜到三点补cf的题，第二天头晕的不行，然后经常复发，直到现在都经常头晕。是真的恼火，也不清楚什么时候才能好 感觉自己的生活一团乱麻，我就像是万青在歌里描绘的那个董二千先生：四体不勤，五谷不分，文不能测字，武不能防身。前已无通路，后不见归途 二 暑假开始了，目前一个人打了4场多校，完全是一直被虐的状态，太菜了。 基础知识差的太多了，训练方向也有问题，一前就一直补cf的div1&2，感觉这些题目和区域赛比起来，虽然思维难度没差太多，但是对知识点的考察简直就是小打小 ...

这次选拔赛前前后后打了一周，总共七场，每天下午1：30-6：30，是ACM赛制的单人赛，选拔rating总分的前六名。最后我总积分排名第四进队了，也算是有惊无险叭 打算等测控实习和专业实习补完再把这一周的题都补一补，然后写个题解啥的。这里就先挖个坑，两三周过后再来填 Day0 今天热身赛，不会计分，索性在宿舍睡了一下午，就没去教室打比赛。才考完试，太累人了…醒了之后，看了眼题。看到有个题目就一个人过了，就去写了写，没想到居然没写出来，后面才发现这只是个线段树…算错时间复杂度了 Day1 心心念念的选拔赛终于正式开始了，说实话还挺激动的。因为校赛rank3，然后蓝桥还有个A组国一，我觉得自己的实力进个校队应该不难。索性就做得随性一点，一上来就开A题，结果想了个假贪心去做这个不算简单的树形DP题…然后写了三个题后又跟错了榜，明明不会网络流的板子，却像个伞兵一样卡E题卡了两个小时 其实B题并不算难，下来花了1h也补掉了，可惜考试的时候看都没看…K题考试时也没有看，记得最后过的人也挺多的，一个比较简单的构造题叭，不过补题的时候反而第一时间没太想到正解QAQ 第一天就这么稀里糊涂的结束了，猛 ...

一 说真的，对于我这样的没有时间性的人而言，大学是真的读起来很累，无处不在的过程考核简直要命，也许我这种小镇做题家还是只适合参加考试吧 这学期的跑操只跑了20次，本来想着体育不重要，扣点分无所谓，没想到网球期末的专项测试如此之难，我甚至很有可能会挂科…本来是对打的项目，我居然刚好成为了人数为奇数的班里没有搭档的那一个，真是倒霉。这周五就要考试了，而我已经练了几天，累得半死，可惜还是收效甚微。 周三下午又要考马原，背书我可是最不在行了…可能又要熬夜了。 二 这两天和同学和学长又聊起了保研的事，看他们一个个90+，甚至94+的人为了自己在专业中的排位心急如焚，再看看自己可怜又可笑的均分，说实话，真的很失落。 回顾自己大学这两年来，一个人迷迷糊糊的走在算法竞赛这条路上，逃课去图书馆抢带插座的位置，即使第二天早八也依然坚持打codeforces，好像一副很努力的样子，但事实上，我只是在自欺欺人罢了。很多时候，我一天也没有写一两道题，逃课得来的时间，也只是拿去打游戏刷b站罢了。 三 前段时间，无意中又翻到了hzwer学长的退役博客，我居然看哭了。我脑子里一遍遍回想起当时高中短暂而苦乐交加的 ...

普通莫队 算法简介 对于序列上的区间询问问题，如果能O(1)O(1)O(1)内从[l,r][l,r][l,r]扩展得到[l−1,r][l-1,r][l−1,r]，[l+1,r][l+1,r][l+1,r]，[l,r−1][l,r-1][l,r−1]，[l,r+1][l,r+1][l,r+1]的答案，那么可以在O(nn)O(n\sqrt{n})O(nn​)内求出所有询问的答案。 对于区间[l,r][l,r][l,r]，以 lll 所在的块的编号为第一关键字，rrr 的大小为第二关键字从小到大排序。对于每个块的第一个区间我们在 o(n)o(n)o(n) 内暴力求解，然后再暴力转移。 引例 首先看一个例子感受一下 有一个长度为 nnn 的序列 。现在给出 mmm 个询问，每次给出两个数 ，从编号在 lll 到 &r& 之间的数中随机选出两个不同的数，求两个数相等的概率。 首先按照简介中介绍的方法对这 mmm 个区间排序，设选择相同颜色的方案数为 ansansans,col[i]col[i]col[i] 表示当前区间颜色 iii 出现了多少次，且新加入或新删掉的元素颜色为 ...

这场是真的搞人心态…居然卡在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 ...

回顾 机房的电脑居然是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=1n​Si​∣=∑i​∣Si​ ...

概率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) ...

模板 洛谷 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 ...

最近感觉越学越菜了… 一 蓝桥大题就出了两个，填空题就对了三个。大题里一个博弈，一个DP，全都差一点出，欸。感觉DP还是做太少了，本来DP状态都想好了，写法也明确了，就是具体写式子的时候出差错，菜的一匹。填空题更啥b，下午回去把错的题代码重写了一下，结果居然就和标准答案一样了，都搞不懂当时我是咋写错的。最后一个状压我也没写，当时写了个暴力跑不出来就跳了，如果知道第一时间反应过来是dp也能做的吧，欸。 二 天梯赛也是难顶，三个多小时，断线重连了十次 第一个题看都没看。第二个贪心还没想到，还以为这道题是Trie+DP（因为才补了一道Trie上矩阵快速幂加速DP的题）。其实写暴力也能过，但暴力写错了，忘记了首尾连接处要重合起来。 前面也是，字符串和STL的两道题卡了贼久…字符串相关的库函数不会用，map的hash也不会写 最后两百分草草收场，L3爆零了… 三 是怎么回事呢，明明每天都在做着自己喜欢的事情，明明每天都有一点进步，但是结果却是这样不尽如人意。 最近的cf一场没落，甚至还开了许多virtual contest。但我的rating居然不增返降，欸。 逐渐发现自己的实力其实并没有 ...