hysbz专题
HYSBZ 1012 最大数maxnumber
思路：在单调队列不更新列首，因为查询区间大小不确定，所以不能保证下次是否还用到它 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define N 222222#define ll long longint que[N];ll m,d;ll a[N];int cnt;ch
HYSBZ - 2243染色——树链剖分+线段树建树技巧
【题目描述】 HYSBZ - 2243染色 【题目分析】 我一直没有看清楚题，以为求的是路径上出现颜色的种类，然后就写了一个区间染色的线段树进行维护，过样例的时候才发现题读错了，人家要求的是路径上出现的颜色段，所以颜色的种类不重要，重要的是每一段每一段。理所当然，我们应该用线段树维护所在区间有多少段。但是左右区间上传的时候如果边界颜色相同（左节点的右边界和右节点的左边界），那么区间个数应该减一。
HYSBZ 3674: 可持久化并查集加强版——主席树+并查集
Description： 自从zkysb出了可持久化并查集后…… hzwer:乱写能AC，暴力踩标程 KuribohG：我不路径压缩就过了！ ndsf：暴力就可以轻松虐！ zky:…… n个集合 m个操作 操作： 1 a b 合并a,b所在集合 2 k 回到第k次操作之后的状态(查询算作操作) 3 a b 询问a,b是否属于同一集合，是则输出1否则输出0 请注意本题采用强制在
XOR和路径 （HYSBZ - 2337 ，高斯消元解后效性 DP）
一.题目链接： HYSBZ-2337 二.题目大意： 给一张无向边权图，在每个节点都会等概率地选择一条边，求 1 ~ n 路径的权值异或和的期望值. 三.分析： 由于是异或，不妨按答案的二进制位逐位考虑. 假设当前考虑第 i 位 设 dp[u] 表示 u ~ n 路径的权值异或和二进制第 i 位的期望值. 设 v 是与顶点 u 相关联的顶点集合，de[u] 表示 u 的度, wi(
树的同构（HYSBZ - 4337，树的哈希）
一.题目链接： HYSBZ-4337 二.题目大意： 输出 m 棵树的同构运算等价类. 三.分析： 貌似是个模板题... 原来这就叫做树的哈希，感觉好水啊... 详见代码. 四.代码实现： #include <bits/stdc++.h>using namespace std;typedef unsigned long long ull;const int M = (int)5
SPOJ-DQUERY HYSBZ 1878 HH的项链 (线段树/树状数组/莫队/主席树)
1878: [SDOI2009]HH的项链 Time Limit: 4 Sec Memory Limit: 64 MB Description HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步 完后，他都会随意取出一 段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此他的项链变得越来越长。有一天，他突然提出了一 个问题：某一段贝壳中，包含了多
HYSBZ-2660最多的方案-齐肯多夫定理+dp
最多的方案 HYSBZ - 2660 现在给一个正整数 n，它可以写成一些斐波那契数的和的形式。如果我们要求不同的方案中不能有相同的斐波那契数，那么对一个 n 最多可以写出多少种方案呢？ 考虑将数n分解成齐肯多夫形式，然后拆分成段逐位向下分解，显然每一段的贡献是坐标差/2向下取整。因为可能会出现段之间的0影响实际分解情况，所以用dp记录一下每个位置有没有分解。 递推式： #include
HYSBZ - 1798 Seq 维护序列seq 线段树lazy标记
传送门 这道题属实是线段树的道比刷题，又加又乘的，当然还可能会有乘除，阶乘等等可能的情况。 对于这道题，主要的一个就是怎么记录lazy标记，首先的话一个数组是肯定不行的，设乘的为lazy，加的为add。 每次我们更新时，要用lazy数组去更新add数组。 关键是pushdown的时候注意一下，下放的时候比较复杂。 代码如下： #include<stdio.h>#include<str
树上操作 HYSBZ - 4034
https://www.lydsy.com/JudgeOnline/problem.php?id=4034 在树链剖分后形成的dfs序 和普通的dfs序性质一样 一颗子树在dfs序列中仍然是连续的 因为树剖之后虽然先走重链 但还是要走完当前子树后才会递归返回 然后进入其他子树 #include <bits/stdc++.h>using namespace std;#define ll lo
染色 HYSBZ - 2243
https://www.lydsy.com/JudgeOnline/problem.php?id=2243 树链剖分加区间合并 每个节点维护最左边和最右边的颜色以及当前区间的总段数 最难处理的地方在于一条链会被剖分成很多小段 需要将衔接部分处理好 #include <bits/stdc++.h>using namespace std;struct node1{int v;int next;
self 同类分布 HYSBZ - 1799
https://www.lydsy.com/JudgeOnline/problem.php?id=1799 枚举各位数字之和 然后数位DP 将数值对所枚举的数字之和取模 #include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long ll;const int
HYSBZ - 3530 数数 【DP+AC自动机】
点我传送到题目！！！ 题意： 给定一个数n，和m个数字构成的字符串，求1-n范围内不包含m个字符串中任何一个的数的个数？n的长度不超过1200，m不超过500。 解题思路： 这题可以用ac自动机来求是否包含字串，dp[i][j]表示第i位在ac机中状态为j的答案数。某一状态是否为匹配状态可以在AC机建立fail路径时建立预处理出来。 解题代码： #include<iostream>#
A Horrible Poem （HYSBZ - 2795，字符串哈希 + 枚举最小循环节小技巧~）
一.题目链接： HYSBZ-2795 二.题目大意： 给一个长度为 n 的字符串，q 次询问，每次问 s[l...r] 的最小循环节. 三.分析： 技巧一：字符串 s[l, r] 具有循环节 k 等价于 s[l, r - k] == s[l + k, r]. 技巧二：线性筛中预处理出每个数的最小质因子，可 进行质因数分解. 技巧三：字符串的最小循环节可通过对字符串长
HYSBZ 1588 营业额统计 伸展树
题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1588 题意:每次查找集合中一个key对于给定的tmp满足 |tmp-key|最小,将tmp加入集合 维护每次的最小差值 第一道伸展树题,大神的模板很好用 代码: #include <bits/stdc++.h>#define sf scanf#define pf printf
齿轮 HYSBZ - 4602
现有一个传动系统，包含了N个组合齿轮和M个链条。每一个链条连接了两个组合齿轮u和v，并提供了一个传动比x : y。即如果只考虑这两个组合齿轮，编号为u的齿轮转动x圈，编号为v的齿轮会转动y圈。传动比为正表示若编号 为u的齿轮顺时针转动，则编号为v的齿轮也顺时针转动。传动比为负表示若编号为u的齿轮顺时针转动，则编号为v 的齿轮会逆时针转动。若不同链条的传动比不相容，则有些齿轮无法转动。我们希
HYSBZ - 1001 狼抓兔子 （网络流板子）
HYSBZ - 1001 狼抓兔子 （网络流板子） 现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到，但抓兔子还是比较在行的， 而且现在的兔子还比较笨，它们只有两个窝，现在你做为狼王，面对下面这样一个网格的地形： 左上角点为(1,1),右下角点为(N,M)(上图中N=4,M=5).有以下三种类型的道路 1:(x,y)<>(x+1,y) 2:(x,y)<>(x,y+1) 3:(x,y