pinkyHead's blog

小记 同样作为强连通分量相关的算法，tarjan算法似乎要出名得多，实际上我也是两天前才知道还有个叫Kosaraju的算法。后者与前者的理论复杂度其实是一样的，而且实际情况应用中前者甚至会稍快一些。但是Kosaraju算法有着tarjan所没有的优势——Kosaraju可以与bitset相结合，从而能够在极为优秀的复杂度内解决一些稠密图内的问题。 算法流程 首先对图进行第一遍dfs，并把遍历到的点压入栈中。值得注意的是，这里的压栈要写在dfs函数的最后，即在一个节点及其后继完全访问完毕后再压栈操作。 对这个图求反，即把所有边反向。然后在这个反图上跑dfs。注意这里跑dfs时，选取上一步中栈顶的元素作为起点。一次dfs中遇到的所有点，都属于同一个强连通分量，并且标记他们，注意在dfs过程中，不能访问已经标记过的点。如果dfs结束，那么再次从栈顶取一个未被标记的元素，以它为起点继续在反图上跑dfs，如此往复，直到栈为空。 算法结束，所有的强连通分量已求出。 123456789101112131415161718192021222324252627282930313233343536 ...

ICPC#2020澳门站 C.Club Assignment 挺小清新的一个构造题。要尽量使得高位能有1，如果无法避免有的异或值高位为0的话，那么就继续递归地往下讨论，并且这一位不同的数字之间的相对位置关系对答案就不会产生影响了。 模拟赛的过程中没写完，下来花了1个多小时一遍AC了，还是挺爽的。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134#include<bits/stdc++.h>using namespace std;typede ...

二分图最大匹配 图的匹配，即由一组没有公共端点的不是圈的边构成的集合，我们这里需要使得这个集合尽可能大，即寻找二分图的最大匹配 这里需要先了解两个定义： 交错路：给定图G的一个匹配M，如果一条路径的边交替出现在M中和不出现在M中，我们称之为一条M-交错路径 增广路（增广轨）：如果一条M-交错路径，它的两个端点都不与M中的边关联，我们称这条路径叫做M-增广路径 匈牙利算法 该算法本质上就是不停地找增广路并更新答案，复杂度为O(nm)O(nm)O(nm)。 算法的正确性证明可以看这里 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960struct augment_path { vector<vector<int> > g; vector<int> pa; // 匹配 vector<int> pb; vector<int> vis; ...

算法简介 给出若干个元素，其中每个元素非真即假。然后再给出若干个包含这些元素的命题，要求找出这些元素的可能取值，使得所有给出的命题成立。 问题的初始模型网上都已经讲的很清楚了，具体可以参考传送门。这里我只会放一些本人在的学习过程中踩过的坑 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 第一天就这么稀里糊涂的结束了，猛 ...