fuzhiji

题解

/ 注册

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

L1-8 幻想乡炼金学

繁琐的模拟题，本来不打算做的，正当退缩的时候突然发现，好像实现起来代码量挺少的，就那么几个情况，于是写了一会就过了，也不算太复杂，找到了刚学算法的时候做题的那种感觉（雾），模拟大法好啊 ~~ 主要是分类讨论，用vector G[maxn]存起来每一类，括号()的全部放到一个vector，不然就下一个...

模拟

2020-05-05

2 944

糖糖别胡说，我真的不是签到题目-------前缀和（附带难度题目提高版）

对于这道题，如果按照朴素算法来说，第一反应是对于每个位置i的糖糖，处理1 ~ i-1 被消灭的糖糖有哪些，给他们标记，然后最后统计一遍，很显然，这样复杂度很高，不足以通过这道题，所以我们换种处理方法。先看m次操作，有影响的一定是，我们可以维护一个前缀和，表示第项前面有几次操作，这样做的意义是什...

线段树技巧前缀和

2020-04-20

10 1303

华华给月月准备礼物----经典二分

我们考虑朴素算法，假设Max为给出木条的最大长度，直接枚举长度 0~Max，找到符合情况的最大值即可，由于最大长度可以为1e9，复杂度最差为O(1e9n)显然不行，观察发现，如果对于裁剪出长度为x的木条最多能凑出sum根，那么裁剪x+1长度的木条，肯定不会得到sum+1根，很明显，具有单调性，我们就...

二分

2020-04-20

1 932

逆序对----找规律+快速幂 or 递推+矩阵快速幂

方法一：找规律+快速幂假设需要构成长度为n的字符串，任取其中两个元素组成1 0，那么会有种选择方法是不一样的，对于长度为n的字符串，选择一种方法后，还会剩下个字符，每个字符可以是0或1，那么就有种可能，所以可以推出答案式子因为有个取模操作，所以除法要换成乘法，因为这题的公式可以抵消，所以不需要求逆...

矩阵乘法规律快速幂递推

2020-04-15

14 803

Treepath---简单dfs or 基础dsu on tree

方法一------简单dfs：dep表示深度，lca表示最近公共祖先对于两个点u和v，u到v的路径长度是dep[u] + dep[v] - 2 x dep[lca(u,v)]很显然 2 x dep[lca(u,v)] 一定是个偶数，所以，要想路径也为偶数，那么dep[u]和dep[v]一定是同为奇...

dfs 树形结构启发式

2020-04-14

2 794

Xorto----前缀和

由于题目要求的是两个连续的区间，下文会称其为左右区间，我们可以枚举右区间的起点，不断往右扩展，每次答案加上与右区间异或和相等的左区间的个数即可。如何处理左区间，每次枚举右区间起点的时候，我们令右区间起点的前一个数为左区间的终点，往左边扫描，加入新的区间值，由于题目给的元素大小不超过1e5，可以...

STL 前缀和

2020-04-14

1 619

Accumulation Degree----基础树形dp

题意转换：假设f(x)为x节点到叶子节点的最大流量，求最大f(x):x属于1~ndp[u]表示每个节点u往儿子方向流的最大流量。对于全部不为叶子节点u，深度往下传的流量最优为dp[u]+=min(dp[u_son],flow(u,u_son))，有点类似于贪心的想法。叶子节点x为dp[x]=flow...

树形dp

2020-04-13

0 786

Running Median---优先队列or主席树

题目链接：https://ac.nowcoder.com/acm/problem/50940题解：方法1：对于动态维护中位数，可以选择使用两个优先队列，一个大优先一个小优先，并且保证大小两个优先队列的size相差不超过1即可，中位数一定会在size较大的那个队列的top位置。实时更新中位数，比大于等...

主席树优先队列

2020-04-09

0 676

城市网络——在线算法

题目链接：https://ac.nowcoder.com/acm/problem/13331来份在线查询的代码，先说这道题，在第一遍dfs求重儿子的时候，顺便处理数组dp[maxn]，其中dp[u]为从节点u到根节点1有几次购买操作，如何求答案呢？假设有两个点x和y，其中y----是x的某一级祖先...

树链剖分在线

2020-04-08

1 1130