pinkyHead's blog

ICPC2020南京站 C.Certain Scientific Railgun 这道题算是个挺巧妙的构造题吧，可以对原图进行若干次对称变换，这样就可以固定住决策，从而极大地简化了代码量 然而简化之后还是很折磨 决策分为两种情况，首先只向左走，然后再上下；或者向左走后再向右，然后上下走。 按照题解的做法维护四个set就行了接下来这道题需要的就只是亿点点细节 注意一下，有可能最优解只是上下走，要注意特判，或者交换一下X，Y轴再算一次。我这里的做法是增加了一个坐标为(0,0)(0,0)(0,0)的点，这样能保证在X轴上能“移动一次”（即使这时候的花费为0），从而包含了只上下走的情况。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104 ...

9.02 训练赛传送门 Problem I. Minimum Diameter Spanning Tree 这道题需要一定的前置知识，比如这篇博客 当明白图的绝对中心这个概念后，这道题就迎刃而解了。 注意理解上述博客中的折线最低点的求解过程。因为都是斜率为1的折线，所以可以通过简单的推导得到最低点与折线的关系式，进而求解。然后最后找点则根据中心点的位置bfs即可，注意中心点可能在某条线段的端点上，所以这种情况下要特判。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair ...

一 这学期终于结束了，感觉时间过的真快呀，日子就这么不知不觉的一天天溜走… 怎么说呢，感觉还是有些遗憾吧，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) ...