bzoj1131: [POI2008]Sta
思路：首先先求出以1为根的答案，然后考虑由i转移到i的儿子的答案的变化，显然以son[i]为根的子树的所有结点的深度都会减一，其余的点的深度都会加一，然后就可以直接O(n)求出所有结点的答案，然后取max更新答案即可。#include<iostream>#include<cstdi...
【BZOJ 2306】 2306: [Ctsc2011]幸福路径 （倍增floyd）
2306: [Ctsc2011]幸福路径Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 912 Solved: 437Description有向图 G有n个顶点 1, 2, …, n，点i 的权值为 w(i)。现在有一只蚂蚁，从给定的起点 v0出...
【BZOJ2306】幸福路径（动态规划，倍增）
【BZOJ2306】幸福路径（动态规划，倍增）题面BZOJ题解不要求确切的值，只需要逼近显然可以通过移动\(\infty\)步来达到逼近的效果考虑每次的一步怎么移动设\(f[i][j]\)表示走\(i\)步到了\(j\)能够得到的最大权值\(f[i][v]=max(f[i-1][u])+W[v]*p...
【bzoj2306】[Ctsc2011]幸福路径 倍增Floyd
题目描述一张n个点的有向图，每个点有一个权值。一开始从点$v_0$出发沿图中的边任意移动，移动到路径上的第$i$个点输入每一行中两个数之间用一个空格隔开。 输入文件第一行包含两个正整数 n, m，分别表示 G 中顶点的个数和边的条数。 第二行包含 n个非负实数，依次表示 n个顶点权值 w(1), ...
BZOJ2306:[CTSC2011]幸福路径(倍增Floyd)
Description有向图 G有n个顶点 1, 2, …, n，点i 的权值为 w(i)。现在有一只蚂蚁，从给定的起点 v0出发，沿着图 G 的边爬行。开始时，它的体力为 1。每爬过一条边，它的体力都会下降为原来的 ρ 倍，其中ρ 是一个给定的小于1的正常数。而蚂蚁爬到某个顶点时的幸福度，是它...
BZOJ2306 [Ctsc2011]幸福路径[倍增]
这个有环的情况非常的讨厌，一开始想通过数学推等比数列的和，但是发现比较繁就不做了。然后挖掘这题性质。数据比较小，但是体力可以很接近1（恼怒），也就是说可能可以跳很多很多步。算了一下，大概跳了2e7次左右这个体力才缩到1e-14左右，这时已经几乎不会影响答案惹。也就是说，点比较少，有没有暴力做法？发现...
bzoj千题计划293：bzoj3142: [Hnoi2013]数列
http://www.lydsy.com/JudgeOnline/problem.php?id=3142如果已知数列的差分数列a[1]~a[k-1]那么这种差分方式对答案的贡献为 N-Σ a[i]，i∈[1,k-1]差分数列一共有多少种？ M^(k-1) 种所以ans=Σ (N-Σa[i]) = ...
[bzoj2157]旅游 (lct)
这个应该也算裸的模板题吧。。主要是边权的问题，对于每条边u->v，我们可以新建一个节点代替他，把边的信息弄到新的点上，就变成u->x->v了。。。当然了这样的话要防止u和v这些没用的点影响到实际的结果。。。。这个可以初始化的时候解决话说如果写链剖的话也可以用这样的姿势，就不用像以前...
bzoj1054: [HAOI2008]移动玩具
hash+bfs；要注意特殊情况。（似乎连sort。lower_bound都不用数据小直接判重了。。。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using...
秘密袭击 [BZOJ5250] [树形DP]
分析：听说正解是FFT+线段树合并，然而我并不会...我们来思考其他的方法。我们要求的是连通块第k大的和对于某一个连通块，对答案的贡献=val(Rank.K)我们不好直接算出每个连通块的Rank.K是多少但我们可以枚举一个limit for 1->w ，Σ(val(Rank.K)>=li...
BZOJ 1706
题解：倍增+floyd首先这题比较容易想到是把每个点拆点做dij但是这样复杂度是knlogn的这道题的k较大，所以不行我们考虑到每走一步，其实就是在进行一次floyd而这个可以看成矩阵乘法所以可以倍增优化这样是logk*n^3的 代码：#include <bits/stdc++.h>us...
BZOJ_3207_花神的嘲讽计划1_(Hash+主席树)
描述http://www.lydsy.com/JudgeOnline/problem.php?id=3207给出一个长度为\(n\)的串,以及\(m\)个长度为\(k\)的串,求每个长度为\(k\)的串在原串\([x,y]\)区间是否出现过.分析这道题要求对比长度为\(k\)的串,于是我们把这些串的...
bzoj1346: [Baltic2006]Coin
Description有一个国家，流通着N种面值的硬币，其中包括了1分硬币。另外，有一种面值为K分的纸币，它超过了所有硬币的面值。 有一位硬币收藏家，他想收集每一种面值的硬币样本。他家里已经有一些硬币，但是现在他只带着一张K分纸币去商店。 商店里总共有K-1种商品，价格分别为1分、2分……K-1分。...
BZOJ4408&4299[Fjoi 2016]神秘数——主席树
题目描述一个可重复数字集合S的神秘数定义为最小的不能被S的子集的和表示的正整数。例如S={1,1,1,4,13}，1 = 1 2 = 1+1 3 = 1+1+1 4 = 4 5 = 4+1 6 = 4+1+1 7 = 4+1+1+1 8无法表示为集合S的子集的和，故集合S的神秘数为8。 现给定n个正...
bzoj1578 [Usaco2009 Feb]Stock Market 股票市场
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1578【题解】由于连续买相当于每天买，第二天卖，然后再买。所以每天最后钱尽量多一定是最优的。所以对于m天，每天做一次O(n*70w)的完全背包dp即可。# include <stdio.h...
[bzoj1578][Usaco2009 Feb]Stock Market 股票市场_完全背包dp
Stock Market 股票市场 bzoj-1578 Usaco-2009 Feb题目大意：给定一个$S\times D$的大矩阵$T$，其中$T[i][j]$表示第i支股票第j天的价格。给定初始资金$M$，求最后的最大收益。注释：$1\le S\le 50$，$1\le D\le 10$，$1\...
BZOJ 1578: [Usaco2009 Feb]Stock Market 股票市场( 背包dp )
我们假设每天买完第二天就卖掉( 不卖出也可以看作是卖出后再买入 ), 这样就是变成了一个完全背包问题了, 股票价格为体积, 第二天的股票价格 - 今天股票价格为价值.... 然后就一天一天dp...---------------------------------------------------...
[BZOJ3224] [Tyvj 1728] 普通平衡树 (treap)
Description您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：1. 插入x数2. 删除x数(若有多个相同的数，因只删除一个)3. 查询x数的排名(若有多个相同的数，因输出最小的排名)4. 查询排名为x的数5. 求x的前驱(前驱定义为小于x，且最大的数)6. 求x的...
BZOJ 2200--[Usaco2011 Jan]道路和航线（最短路&拓扑排序）
2200: [Usaco2011 Jan]道路和航线Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 1128 Solved: 414[Submit][Status][Discuss]DescriptionFarmer John正在一个新的销售区域对他...
BZOJ 2242 [SDOI2011]计算器 BSGS+高速幂+EXGCD
题意:id=2242">链接方法: BSGS+高速幂+EXGCD解析:BSGS…题解同上..代码:#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#inc...