shyyhs

分类

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38) 题解(330)

/ 注册

TA的专栏 440篇文章 0人订阅

415篇文章 3901人学习

AtCoder思维大提升

6篇文章 753人学习

kuangbin专题记录

0篇文章 0人学习

牛客每日一题推介(裙子计划~)

19篇文章 848人学习

全部文章（共469篇）

树状数组来自专栏

数据结构了,作为一个从来没有学过数据结构的萌新.认真的更下树状数组.什么是树状数组?就是利用二进制的存储方式进行的一个数据结构.线段树是二叉树进行存储,而树状数组是用lowbit进行存储.https://www.cnblogs.com/xenny/p/9739600.html 这博客不错,我也不说了...

树状数组

2020-07-15

3 593

食物链来自专栏

建图种类并查集即可 #include <bits/stdc++.h> using namespace std; const int N=5e4+5; int fa[N],d[N]; int ask(int x) { if(fa[x]!=x) { int r...

并查集

2020-07-15

1 662

奇偶游戏来自专栏

各种找矛盾的题..下面用种比较好的算法写吧,不用扩展域,权值并查集.怎么权值查并集呢?首先和上个题目一样,用一个d[x]表示x到根节点的距离.假如距离为偶数就表示同一面.奇数就表示对立面. #include <bits/stdc++.h> using namespace std; con...

并查集

2020-07-15

1 1085

贝伦卡斯泰露来自专栏

因为儿子需要,所以又更一篇水题题解.很容易想到爆搜2^40复杂度直接搜,当然也可以合并分别处理2堆,但是我觉得这题剪枝完全不必要.所以一发爆搜+剪枝就过了.剪枝就是必须保证前面的搜到的答案必要一致.emm没了 #include <bits/stdc++.h> using namespac...

dfs

2020-07-14

9 842

银河英雄传说来自专栏

又是查并集..没啥好说的...qaq大概是查并集+、差分思想吧?d[x]表示我x点到root的距离,然后sz[x]表示x集合的大小.显然root到root的距离为0.我们考虑两个集合合并,显然,我们第一个集合的d[root]设为sz[2].sz[2]的大小又要+sz[1].然后我们第二次查询时,就是...

并查集

2020-07-14

1 625

程序自动分析来自专栏

并查集,忘了.自己写也可以写出来,wow.. #include <bits/stdc++.h> using namespace std; const int N=1e6+5; unordered_map<int,int>fa; struct vv{ int l,r,p;...

并查集

2020-07-14

2 629

格鲁吉亚和鲍勃来自专栏

这题可以完全转化为台阶博弈.就看你会不会转化了.//下面讲讲怎么转化,不会台阶博弈的,就...我们可以把我们可以两个棋子之间中的空隙看成台阶的石子数,向左移看成石子往下传递石子.然后就是台阶博弈了?下面讲讲台阶博弈怎么做?台阶博弈是这样的: 现在，有一个n级台阶的楼梯，每级台阶上都有若干个石子，其中...

博弈论

2020-07-14

1 575

魔法珠来自专栏

sg函数ε唉,令人自闭的东西.考虑有向图建边(sg函数mex定义只是针对0?...不是很懂ε唉)对于每个局面单独考虑,计算出它能转移的状态,然后根据sg^和为0判定游戏胜负.代码如下: #include <bits/stdc++.h> using namespace std; const...

博弈论

2020-07-14

1 678

换教室来自专栏

简要的证明一下floyd算法的正确性.想必大家都做过旅行商问题(状态压缩).floyd就是暴力枚举了每个点的对整幅图的贡献.然后就是讲下这个题,这个题是个概率dp,因为要求最小.首先得明确dp所表示的含义.我们令f[i][j][0/1]表示我们学到了第i门课,我们用了j次机会,第j次的时候用了/没用...

floyd dp

2020-07-13

3 620

放弃测试来自专栏

一个简单的算法,0/1分数规划.具体就是二分. 分子是一些ai的和,分母是一些bi的和.假定我的值是满足要求且要扩大.那我们很容易得出ai-bi*x>=0. 那么就是我们按ai-bi*x排个序,删掉k个小的即可.#include <bits/stdc++.h> using name...

0/1分数规划

2020-07-13

3 1010