henry_y

题解

A-学习笔记(10) A-游记/杂谈(2) B-题库-51nod(2) B-题库-AtCoder(7) B-题库-BZOJ(48) B-题库-CodeForces(5) B-题库-HDU(5) B-题库-LibreOJ(7) B-题库-Luogu(16) B-题库-POJ(1) B-题库-牛客网(8) C-博客园美化(1) C-比赛记录及刷题计划(2) 动态规划-DP(12) 图论-网络流(1) 图论·最短路(3) 字符串-hash(1) 字符串-KMP(1) 字符串-Trie(2) 思想-分块(4) 思想-前缀和(1) 数据结构及算法-单调队列(4) 数据结构及算法-堆(2) 数据结构及算法-树链剖分(2) 数论-其他(3) 数论-博弈论(1) 数论-数论分块(1) 数论-欧拉函数(1) 数论-莫比乌斯反演(1) 数论·筛法(4) 未归档(3) 深度优先搜索-dfs(1) 贪心(1)

/ 注册

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

题解 | Island题解

基环树直径的板子。但是dfs会爆栈...所以最后改成了bfs。还是一个很考验码力的板子。首先基环树的直径显然有两种情况，在不进入环的情况下在一个子树内，这直接dp求就好了。第二种是一个子树中的链+环上一段+另外一个子树中的链。按这两种情况分类讨论即可。对于这种情况，可以在先求第一种情况的同时把子树中...

基环树单调队列树形dp

2019-09-02

0 605

题解|装备购买题解

真正意义上的线性基...在关于向量加法和标量乘法的线性空间中的线性基。题目的意思就是要构造一个价格最低的基底。对于同个线性空间它的基底的位数不会变，那么要费用最低，可以按费用排序然后依次加入线性基判定是否可行。关于证明，设该线性空间中的向量为，线性基中的向量为，若存在满足，，而A_k是费用最低的一个...

线性基线性代数

2019-09-02

0 629

题解 | xor 题解

首先有个显然的结论：图中所有环的xor和都可以取到（考虑从1走过去绕一圈回来，那么过去那段路的xor和就抵消了），dfs处理出所有的环（这个可以通过记录in_edge然后利用返祖边找环，在搜索树上维护前缀和即可），扔进线性基中，然后随便选一条1到n的路径，在线性基取max即可。考虑证明正确性：如果从...

线性基图论贪心

2019-09-02

0 672

题解｜新nim游戏题解

做法：线性基+贪心先手必胜。游戏的结论是所有数的和不为则先手胜。因为自己可以取一次来修改局面，对手也可以取一次来修改局面，那么现在的目标就变成了取走最少的石头堆，让剩下的石头没有一个非空子集的和为。而线性基刚好满足这一性质。所以问题就变成了构造一个线性基，使其包含的石子数最多。这个将石子降序插入线...

线性基贪心

2019-09-02

0 547

题解|程序自动分析题解

Solution 很容易就能一眼并查集吧...提供一个简便且好写的方法，利用了哈希的思想。但是太大了。顺理成章想到离散化这是对的但是离散化好麻烦啊所以我们拿一个大质数来一下吧比如某神奇的八位质数？ #include <bits/stdc++.h> using namespace...

2019-09-02

2 784

题解 | 蒲公英题解

因为太菜所以只会的做法就是那种要用二分的，并不会clj那种不带log的做法首先数的值域为1e9肯定要离散化一下因为数最多有40000个所以开40000个vector，存一下每个数出现的位置预处理出每个以块的端点为左右端点的区间的众数，这种区间一共有O(block^2)个，所以可以用O(n*b...

二分蒲公英分块

2019-09-02

0 566

题解 | 换教室题解

题目地址 https://www.luogu.org/problem/P1850 题解这题的转移其实挺好想的但是方程特别长...真的特别长...首先设表示当前在第个位置，申请了次，当前这次申请了/没申请，为当前被安排的课室位置，为可申请的课室位置，为申请通过的概率，表示到的最短路。直接一遍求出来...

noip 换教室

2019-09-02

0 623