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)

/ 注册

全部文章（共200篇）

AtCoder Beginner Contest 120 解题报告

为啥最近都没有arc啊... A - Favorite Sound #include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include &l...

2019-03-03

0 0

LuoguP2161 [SHOI2009]会场预约

题目地址题目链接题解用fhqtreap对区间进行维护。可以注意到的是，对于当前存在的预约，他们一定是升序排列的（有重叠的都被删了）。那么就可以用按照位置分裂的fhqtreap搞了（预约无论按l还是按r都必定是升序的）。每次插入一个区间的时候，就直接找出互不重叠的前驱和后继，那...

2019-03-03

0 497

fhqtreap初探

介绍 fhqtreap为利用分裂和合并来满足平衡树的性质，不需要旋转操作的一种平衡树。并且利用函数式编程可以极大的简化代码量。（题目是抄唐神的来着）核心操作（均为按位置分裂合并） struct fhq { int lc, rc, siz, rnd, val; ...

2019-03-03

0 446

LuoguP5221 Product

题目地址题目链接题解注，下方\((i,j)\)均指\(gcd(i,j)\)，以及证明过程有一定的跳步，请确保自己会莫比乌斯反演的基本套路。介绍本题的\(O(n)\)和\(O(n\sqrt{n})\)做法，本题还有\(O(nlogn)\)做法，需要用到欧拉函数，或者是从质因子角度考虑也...

2019-03-02

0 671

BZOJ1951: [Sdoi2010]古代猪文

Description “在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关心……” ——选自猪王国民歌很久很久以前，在山的那边海的那边的某片风水宝地曾经存在过一个猪王国。猪王国地理位置偏僻，实施的是适应当时社会的自给自足的庄...

2019-02-24

0 616

牛客OI周赛7-普及组解题报告

出题人好评。评测机差评。 A 救救喵咪二位偏序。如果数据范围大的话直接树状数组，不过才1000就\(O(n^2)\)暴力就ok了。 #include <bits/stdc++.h> struct Node { int x, y; }a[1010]; int main...

2019-02-23

0 445

LuoguP2680 运输计划

题目地址题目链接题解二分答案，那么大于答案的路径都需要有一条公共边，maxlen-val>=二分出来的x。val是边权。考虑树剖，对每条大于答案的路径都+1（线段树里），枚举边，如果（线段树中的）值==大于答案的边数，那么对他们取max。复杂度\(O((nlognlogn+...

2019-02-16

0 725

AtCoder Beginner Contest 118 解题报告

A - B +/- A #include <bits/stdc++.h> int main() { int a, b; std::cin >> a >> b; b % a ? std::cout << b - a : std::cou...

2019-02-16

0 576

BZOJ5479: tree

Description 给出一棵树，根节点为1 给出两个集合，集合由树上节点组成从两个集合分别选出一个元素，求其LCA 问LCA的最大深度是多少 Input 第一行给出数据组数T 对于每组数据第一行给出N，M，代表树的节点个数及询问次数接下来N-1行，每行两个正整数u,v,表...

2019-02-14

0 420

LuoguP1041 传染病控制

题目地址题目链接题解这里讲一个非正解——贪心+随机化。贪心的想法是什么？我们dfs一遍处理出每个节点子树内的节点数量，记为\(siz\)。贪心的砍掉\(siz\)最大的那个子树，在树的形态比较正常的情况下是可以得到最优解的。如何hack掉这种贪心？构造一条链，在中间的地方放一个...

2019-02-13

0 434