Fatalzyc的博客

转载 树链剖分笔记（一）-------初识树链剖分

写在前面首先，在学树链剖分之前最好先把 LCA、树形DP、DFS序 这三个知识点学了emm还有必备的 链式前向星、线段树 也要先学了。如果这三个知识点没掌握好的话，树链剖分难以理解也是当然的。树链剖分树链剖分 就是对一棵树分成几条链，把树形变为线性，减少处理难度需要处理的问题：将树从x到y结点最短路径上所有节点的值都加上z求树从x到y结点最短路径上所有节点的值之和将以x为根节点的子树内所有节点值都...

转载 P3708 koishi的数学题

原创 P3092 [USACO13NOV]没有找零No Change

题目描述Farmer John is at the market to purchase supplies for his farm. He has in his pocket K coins (1 <= K <= 16), each with value in the range 1..100,000,000. FJ would like to make a sequence o...

原创 P3478 [POI2008]STA-Station

考虑直接对于每个点计算一次 时间复杂度O(n2)显然无法接受 所以，考虑只进行一次DFS在通过递推求解 如果已经知道根节点的答案的话 那么，他的儿子节点很容易的可以递推出来： Ans[son]=Ans[father]+n−2∗size[son] 有点利用树链剖分的思想，其实就是dfs1// luogu-judger-enable-o2#include <cstdio&g...

转载 斐波那契数列定理们

斐波那契数列定理1gcd(f[i],f[i+1])=1gcd(f[i],f[i+1])=1 利用辗转相减法 证明： gcd(f[i],f[i+1])gcd(f[i],f[i+1]) =gcd(f[i+1]−f[i],f[i])=gcd(f[i+1]−f[i],f[i]) =gcd(f[i−1],f[i])=gcd(f[i−1],f[i]) =….=…. =gcd(f[1],f[2...

原创 NOIP 2016 换教室 DP

DP 很好想： 首先，考虑对于所有的教室与道路，地图本身是存在最短路的，我们先用floyd求出任意两点之间的最短距离。其次，针对所有事件可能发生的情况：1.当前的课不换的情况：(1)上一节课也没换；(2)上一节课换了—-成功or不成功；2.当前的课换的情况：(1)当前课成功换了：a.上一节课换了—-上一节课成功or不成功b.上一节课没换；(2)当前的课换了失败...

原创 2017 NOIP 子串

定义状态 f[i][j][k][0/1] 表示字符串 A 的前 i 个字符和字符串 B 的前 j 个字符用了 k 个子串，第四维为 1 表示 A 字符串的第 i 个字符必须被选出，为 0 表示 A 字符串的第 i 个字符不能被选出。那么很容易得出转移：1、对于任意一个 0<=i<=n,f[i][0][0][0]=1 。2、f[i][j][k][0]=f[i−1][j][k]...

原创 bzoj 绝世好题

Description给定一个长度为n的数列ai，求ai的子序列bi的最长长度，满足bi&bi-1!=0(2<=i<=len)。 Input输入文件共2行。 第一行包括一个整数n。 第二行包括n个整数，第i个整数表示ai。 Output输出文件共一行。 包括一个整数，表示子序列bi的最长长度。 Sample Input31 2 3 Sample...

原创 P1533 可怜的狗狗 平衡树

题目背景 小卡由于公务需要出差，将新家中的狗狗们托付给朋友嘉嘉，但是嘉嘉是一个很懒的人，他才没那么多时间帮小卡喂狗狗。题目描述 小卡家有N只狗，由于品种、年龄不同，每一只狗都有一个不同的漂亮值。漂亮值与漂亮的程度成反比（漂亮值越低越漂亮），吃饭时，狗狗们会按顺序站成一排等着主人给食物。可是嘉嘉真的很懒，他才不肯喂这么多狗呢，这多浪费时间啊，于是他每次就只给第i只到第j只狗中第k漂亮的狗...

转载 [TJOI2007]线段

转载：https://www.cnblogs.com/qdscwyy/p/7953758.html（主要是偷懒）题目描述在一个 n*n 的平面上，在每一行中有一条线段，第 i 行的线段的左端点是(i, L(i))，右端点是(i, R(i))，其中 1 ≤ L(i) ≤ R(i) ≤ n。你从(1, 1)点出发，要求沿途走过所有的线段，最终到达(n, n)点，且所走的路程长度要尽量短。更具体一些说，...

原创 P3871 [TJOI2010]中位数

最近在学splay,一看要求中位数，就上一个单点修改splay吧 顺便安利一发splay写的极好（还行）的博客https://blog.csdn.net/zj_js_zxb/article/details/80258824#include <cstdio>#include <iostream>#include <cmath>using namespace ...

原创 bzoj 2208

暴力+BFS 水过#include<iostream>#include<cstdio>#include<cstring>const int N=2000+5;inline int read(){ int f=1,x=0; char c=getchar(); while (c<'0'||c>'9'){if (c=='-') f=-1;c=...

转载 NOIP2017模拟赛10.02

A. 「NOIP2017模拟赛10.02」电阻 个人认为是思维题。第一题其实很简单，而且很有意思。 对于每个电阻我们不是串联进去，就是并联进去。 如果a>ba>b，那么我们肯定是串联进去比较好，所需达到的阻值abab变成了a−bba−bb，如果发现a<ba<b，那么我们只能选择并联，我们知道1R=1R1+1R2+1R3+...+1Rk1R=1R1+1R2+1R3+...+1...

原创 HNOI2008 GT考试 BZOJ1009 洛谷P3193

此题主要思路是dp，但dp有多种写法。我们用f[i][j]表示现在已经有i个数字了，而且最后j个数字是不幸数字前j个数字。（保证不包含不吉利序列） 为了防止dp的意义出现歧义，我们让对于同一个状态j要竟可能大； 比如 1212是不幸数字，那么551212是f[6][4]; 这样的话我们可以发现f[0][0]=1; ans=f[n][k] ，k∈[0，m-1] ∪Z（若k=m，那么已经形成一个不吉利...

原创 BZOJ P1899 [ZJOI2005]午餐DP+贪心

看到有两队人马在吃饭，再看看数据范围，题目应该属于贪心+DP.贪心：以吃饭时间，从大到小排序，为什么是正确的呢？我们可以假设只有一个队时只有两个人甲乙；         打饭时间      吃饭时间   甲     X                 Y   乙     Z                 Y+k（k>0）如果甲先打，哪么tot（总时间）=X+Z+Y+k(因为Y+k>k...