shyyhs

题解

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

/ 注册

全部文章 / 题解（共329篇）

奇偶游戏来自专栏

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

并查集

2020-07-15

1 1086

贝伦卡斯泰露来自专栏

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

dfs

2020-07-14

9 845

银河英雄传说来自专栏

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

并查集

2020-07-14

1 626

程序自动分析来自专栏

并查集,忘了.自己写也可以写出来,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 633

格鲁吉亚和鲍勃来自专栏

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

博弈论

2020-07-14

1 577

魔法珠来自专栏

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

博弈论

2020-07-14

1 679

换教室来自专栏

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

floyd dp

2020-07-13

3 622

放弃测试来自专栏

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

0/1分数规划

2020-07-13

3 1012

异或来自专栏

水题?不解释.代码如下: #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N=2e5+5; ll vis[N],d[N],a[N],cnt=0,n,m,ins[100],ans=0;...

线性基

2020-07-12

3 635

小部件厂来自专栏

有些题你写多了或许就不觉得麻烦了,但是这题是我三天前拖欠的,一直不敢写..ε=唉,我对于100+的纯代码都有一种莫名的恐惧感.其实每个题也就那么几个过程.这题是用高斯消元解异或同余方程.并没有重点要讲的地方.代码如下: #include <bits/stdc++.h> using nam...

高斯消元

2020-07-12

2 653