pinkyHead's blog

算法简介 给出若干个元素，其中每个元素非真即假。然后再给出若干个包含这些元素的命题，要求找出这些元素的可能取值，使得所有给出的命题成立。 问题的初始模型网上都已经讲的很清楚了，具体可以参考传送门。这里我只会放一些本人在的学习过程中踩过的坑 Tarjan 缩点 一般来说，2-SAT 的模型所建出来的图都是对称的。这里的对称该如何理解呢？ 给出两个元素A，B。那么如果A，B不能共存，那么A->B’,B->A’。即如果选了A，那么只能选B’;如果选了B，那么只能选A’。所以如果能由X推出Y，那么就能从Y’推出X’，这就是所谓的"对称"。 先使用 tarjan 算法跑一边强连通分量，如果存在一个元素X能推出元素X’,那么说明X’也能推出X，所以一定会导致矛盾产生，那么问题一定无解。 如果问题有解，那么我们就反向拓扑排序，依次选择排序过程中遇到的点。由于求强连通分量的时候利用了栈，这就是一个天然的反向拓扑排序的结构，所以选择最先进栈的强连通分量就行了。 至于为什么需要反向拓扑排序，其实博主也不能严格证明出它的正确性，这个需要自己感性理解。首先可以先自己推算一下 ...

ICPC网络赛#2021第二场 题解传送门 H.Set 对于这种咋一看不知从何入手的题目，可以想想能否“乱搞”，即利用某种极端的条件或者这个题目某种特殊的性质入手研究整个问题。 这里需要知道一个东西，叫做Union bound,然后我们可以计算出随机选一组解为非法解的概率的上界，结果惊人地小，于是我们可以直接使用random_shuffle构造一组答案，问题就解决了 123456789101112131415161718192021222324252627282930#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int>pii;typedef double db;const int maxn=1e5+5;const ll mod=998244353;const double eps=1e-10;int r,k;vector<int>vec[300];int main(){ int T=1;//scanf("%d& ...

ICPC2020上海站 题解传送门 E.The Journey of Geor Autumn 这道题看似复杂，其实就是个很直观的递推。乍一看貌似无从下手，但是可以从最小数的放置方式入手，从而实现递推求解。注意这里递推的方式，可以手算一下，还是很好化简的。 12345678910111213141516171819202122232425262728293031323334353637#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int>pii;typedef double db;const int maxn=1e7+5;const ll mod=998244353;const double eps=1e-10;int n,k;ll f[maxn];ll fac[maxn],infac[maxn];ll quick_p(ll x,ll y){ ll res=1; while(y){ if(y&1)res*=x,res ...

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 ...