bzoj 1096 仓库建设 -斜率优化
L公司有N个工厂，由高到底分布在一座山上。如图所示，工厂1在山顶，工厂N在山脚。由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L公司的总裁L先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是L先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由...
【bzoj4827】[Hnoi2017]礼物 FFT
题目描述我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了，他决定买一对情侣手 环，一个留给自己，一个送给她。每个手环上各有 n 个装饰物，并且每个装饰物都有一定的亮度。但是在她生日的前一天，我的室友突然发现他好像拿错了一个手环，而且已经没时间去更换它了！他只能使用一种特殊的方法，将其中一个...
BZOJ4373: 算术天才⑨与等差数列(线段树 hash?)
题意题目链接Sol正经做法不会，听lxl讲了一种很神奇的方法我们考虑如果满足条件，那么需要具备什么条件设mx为询问区间最大值，mn为询问区间最小值mx - mn = (r - l) * k区间和 = mn * len + \(\frac{n * (n - 1)}{2} k\)\(\text{立方和}...
BZOJ_2118_墨墨的等式_最短路
BZOJ_2118_墨墨的等式_最短路Description墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。Input输入的第一行包含3个正整数，分别表示N、B...
BZOJ_1003_[ZJOI2006]物流运输_最短路+dp
BZOJ_1003_[ZJOI2006]物流运输_最短路+dp题意：http://www.lydsy.com/JudgeOnline/problem.php?id=1003分析：这种一段一段的显然要用dp求。f[i]表示到第i天为止的最小花销。转移有f[i]=min{f[j-1]+cost[j][i...
[BZOJ1610] [Usaco2008 Feb] Line连线游戏 (set)
DescriptionFarmer John最近发明了一个游戏，来考验自命不凡的贝茜。游戏开始的时 候，FJ会给贝茜一块画着N (2 <= N <= 200)个不重合的点的木板，其中第i个点 的横、纵坐标分别为X_i和Y_i (-1,000 <= X_i <=1,000； -...
●BZOJ 3238 [Ahoi2013]差异
题链：http://www.lydsy.com/JudgeOnline/problem.php?id=3238题解：后缀数组套路深。问题转化为求出任意两个后缀的LCP之和在计算贡献时，各种不爽，然后就套路的从height[i]数组下手。计算出 L[i]和 R[i]，L[i]：找出排名最小(即为 L[...
bzoj4698
题解：后缀数组对所有序列差分一下公共串的长度+1就是答案了二分 扫一遍height即可,..代码：#include <bits/stdc++.h>using namespace std;const int N=,M=;int n,mn=2e9,mx=,lt,rt=2e9,mid,ans=...
2019.01.20 bzoj2238: Mst（kruskal+树链剖分）
传送门树链剖分菜题。题意简述：给一个无向图，边有边权，每次询问删一条边（对后面的询问无影响）之后的最小生成树。思路：先跑一次kruskalkruskalkruskal并把跑出来的最小生成树给链剖了。然后考虑如果没有删掉树边答案不变，如果删掉一条能够接上的就只有覆盖了这条边的路径，因此对于每条非树边都...
BZOJ2208: [Jsoi2010]连通数
bitset优化传递闭包裸题。闲得慌的话可以缩成DAG把复杂度从$O(n^3/32)$优化到$O(nm/32)$。#include<bitset>#include<cstdio>const int N=2005;std::bitset<N>g[N];char z[...
【BZOJ5417】[NOI2018]你的名字（线段树，后缀自动机）
【BZOJ5417】[NOI2018]你的名字（线段树，后缀自动机）题面BZOJ洛谷题解首先考虑\(l=1,r=|S|\)的做法，对于每次询问的\(T\)串，暴力在\(S\)串的\(SAM\)上跑，对于每个点记录其被匹配的最大长度，然后把每个被匹配到的点以及它到\(parent\)树根节点的所有节点...
【BZOJ】2101: [Usaco2010 Dec]Treasure Chest 藏宝箱（dp）
http://www.lydsy.com/JudgeOnline/problem.php?id=2101这个dp真是神思想orz设状态f[i, j]表示i～j先手所拿最大值，注意，是先手所以转移自然而然的变成f[i, j]=sum[i, j]-min(f[i+1, j], f[i, j-1])这个转...
【BZOJ】2020: [Usaco2010 Jan]Buying Feed, II （dp）
http://www.lydsy.com/JudgeOnline/problem.php?id=2020和背包差不多同样滚动数组f[j]表示当前位置j份食物的最小价值f[j]=min(f[j-l]+l*c) 1<=l<=f而且在每一步走的时候f[j]+=j然后就行了。。#include ...
【BZOJ】1649: [Usaco2006 Dec]Cow Roller Coaster（dp）
http://www.lydsy.com/JudgeOnline/problem.php?id=1649又是题解。。。设f[i][j]表示费用i长度j得到的最大乐趣f[i][end[a]]=max{f[i-cost[a][begin[a]]+w[a]} 当f[i-cost[a][begin[a]]可...
【BZOJ4034】[HAOI2015]树上操作 树链剖分+线段树
【BZOJ4034】[HAOI2015]树上操作Description有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：操作 1 ：把某个节点 x 的点权增加 a 。操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。操作 3 ：询问某个节点 x 到根...
【BZOJ】1934: [Shoi2007]Vote 善意的投票（网络流/-二分图匹配）
http://www.lydsy.com/JudgeOnline/problem.php?id=1934一开始我想到了这是求最小割，但是我认为这题二分图可做，将1的放在左边，0的放在右边，然后朋友连边，如果有冲突就相当于有1条x-y的边，求最小割也就是最大匹配即可。。可是不知道为什么就错了。#inc...
bzoj 1934: [Shoi2007]Vote 善意的投票 （最小割）
原来是赞同的连源，原来是反对的连汇，然后是朋友的就连在一起，这样最小割就是割掉违背和谐的吧type arr=record toward,next,cap:longint; end;const maxm=; maxn=;var first,col,gap,d,cur:array[..m...
【刷题】BZOJ 1934 [Shoi2007]Vote 善意的投票
Description幼儿园里有n个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿...
HDU 1029 Ignatius and the Princess IV / HYSBZ（BZOJ） 2456 mode（思维题，~~排序?~~）
HDU 1029 Ignatius and the Princess IV （思维题，排序?）Description"OK, you are not too bad, em... But you can never pass the next test." feng5166 says."I will...
bzoj 2946
Description 给出几个由小写字母构成的单词，求它们最长的公共子串的长度。任务：l 读入单词l 计算最长公共子串的长度l 输出结果Input文件的第一行是整数 n，1<=n<=5，表示单词的数量。接下来n行每行一个单词，只由小...