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篇）

题解 | 天天爱跑步

本blog有所有部分分的解法 Description 小c同学认为跑步非常有趣,于是决定制作一款叫做《天天爱跑步》的游戏。天天爱跑步是一个养成类游戏,需要玩家每天按时上线,完成打卡任务。这个游戏的地图可以看作一一棵包含 N个结点和N-1 条边的树, 每条边连接两个结点,且任意两个结点存在一条路径互...

线段树差分桶树链剖分

2019-09-03

0 914

题解 | 绿豆蛙的归宿

有向无环图是个很好的性质。因为期望dp都是逆推，所以可以建反图，然后在反图上拓扑排序来递推。设表示点到终点的期望路径长度，有,为点的度数。答案为 #include <bits/stdc++.h> using namespace std; const int N = 100010; d...

概率期望

2019-09-03

0 554

题解 | Rainbow的信号

选取的概率为，选取的概率为分别考虑三种运算并按位考虑，考虑第位：对于的情况显然贡献为，为第位为的数的个数。（三种运算的情况都一样）对于和，记录前面连续的个数，那么当前位置作为右端点，对期望的贡献为对于和，记录前面第一个有的位置，那么当前位置作为右端点，对期望的贡献为对于和，记录前缀和，并维护和两个桶...

概率期望

2019-09-03

0 605

题解 | mayan游戏题解

搜索+大模拟。不过思路明确后还是可以写的。搜索树每一层代表移动了几次。每次枚举移动哪个位置，以及可以写个两个函数，一个来处理每一列的下降（移动或消除），第二个将每次可消的方块标记出来，然后再次下降（注意一次移动可能会导致多次消除，所以得重复判断），以及每次要记得把原数组copy了以便回溯。复杂度上界...

2019-09-02

0 625

题解 | SuperMemo题解

能整合的操作大部分都整合了...所以这是个毒瘤题（码农题），不过维修序列貌似比这题更恐怖。这题要求资瓷区间加，区间反转，区间旋转（其实就是从中间断开然后左右交换位置），单点插入，单点删除，区间查询最小值。这些都能用fhqtreap解决。区间加（和线段树），区间反转（^=1，交换左右子树）都打标记就行...

2019-09-02

0 629

题解 | 作诗题解

和蒲公英差不多的套路，预处理整块的答案，查询的时候分类讨论，如果一个数在整段中是偶数次，在中间的整块是奇数次那么，在整段是奇数次在中间的整块是偶数次就。效率是。必须O2+优秀的块的大小才可以卡过去。注意不要用memset，每次处理过后for一遍清空就好，memset是对整个数组清空. #includ...

2019-09-02

0 565

题解 | 蚯蚓题解

很有意思的一道题。对于每秒的增长，因为是个定值，所以显然可以打标记处理，记录每只蚯蚓被切断的时间，那么这只增长量就是，可以利用一个堆来维护当前的最大长度，那么可以做到，这样子已经可以通过5分了（卡常卡的好一点就85）。这题最有意思的地方就是按题目规则切出来的蚯蚓都是有单调性的。对于当前切出来的两只蚯...

归并排序单调性堆贪心

2019-09-02

0 653

题解 | relays 题解

考虑先离散化，那么点的个数只会有个最多。于是复杂度里面就可以有一个.考虑构造矩阵表示经过一条边的最短路，那么就会是输入进来的边。那么表示经过条边的最短路，则有;然后就可以处理出次方的所有矩阵，然后得到最终矩阵的答案了。这个算法叫做倍增floyd #include <cstdio> #i...

矩阵快速幂 floyd

2019-09-02

0 603

题解 | BLO 题解

很巧妙的一道题。对于一个点，如果它不是割点，那么去掉之后，它的答案一定是2*(n-1)(图的连通性没有改变)。如果这个点是割点，那么割掉之后会形成（设它有t个儿子）至多t+2个联通块（t个儿子，它本身，剩下的部分）。那么对于答案的贡献就是。另外注意中间值爆 #include <bits/std...

tarjan

2019-09-02

0 512

题解|创世纪题解

这道题的边连起来的话是个基环树森林的样子(i往a[i]连边)，先考虑如果是个树怎么做，设f[i][0/1]表示节点i不选和选可投放的最大节点数量，则（因为一定要有至少一个子节点不选以限制当前节点）。可以先连的有向边，拓扑排序找出每个基环树里面的环，然后断掉环上的一条边来实现这个过程（在这之前重新建一...

基环树单调队列树形dp

2019-09-02

0 593