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...
BZOJ 2242: [SDOI2011]计算器( 快速幂 + 扩展欧几里德 + BSGS )
没什么好说的...---------------------------------------------------------------------#include<cstdio>#include<cmath>#include<map>using name...
BZOJ 2242 [SDOI2011]计算器（快速幂+Exgcd+BSGS）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=2242【题目大意】给出T和K 对于K=1,计算 Y^Z Mod P 的值 对于K=2,计算满足 xy≡ Z ( mod P ) 的最小非负整数 对...
bzoj 2242 [SDOI2011]计算器——BSGS模板
题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2242第一道BSGS！咳咳，我到底改了些什么？……感觉和自己的第一版写的差不多……可能是long long还有%C的位置的缘故？不过挺欣赏这个板子的。把它记下来好了。其讲解：https://bl...
【卡特兰数】BZOJ1485: [HNOI2009]有趣的数列
Description我们称一个长度为2n的数列是有趣的，当且仅当该数列满足以下三个条件：(1)它是从1到2n共2n个整数的一个排列{ai}；(2)所有的奇数项满足a1<a3<…<a2n-1，所有的偶数项满足a2<a4<…<a2n；(3)任意相邻的两项a2i-1与...
【BZOJ-2864】战火星空 计算几何 + 最大流
2864: 战火星空Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 33 Solved: 14[Submit][Status][Discuss]Description从APIO回来之后，XX便迷上了“战火星空”这个游戏。原版战火星空中，有一架小飞机和...
BZOJ 3294: [Cqoi2011]放棋子
3294: [Cqoi2011]放棋子Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 628 Solved: 238[Submit][Status][Discuss]DescriptionInput输入第一行为两个整数n, m, c，即行数、列数和棋...