[POJ1144][BZOJ2730]tarjan求割点
求割点一种显然的n^2做法:枚举每个点,去掉该点连出的边,然后判断整个图是否联通用tarjan求割点:分情况讨论如果是root的话,其为割点当且仅当下方有两棵及以上的子树其他情况设当前节点为u,一个儿子节点为v存在low[v]>=dfn[u],也就是说其儿子节点v能连到的最前面的点都在u的下面...
BZOJ 4763
有毒第一开始一直RE,我就把dfs改成了bfs结果一直TLE,自己造的数据要跑8s因为 lxl 等人讲随机 $\sqrt{n}$ 个点作为关键点就可以了但是我把随机改成深度有关就AC了,而且那组数据跑了200ms#pragma GCC optimize(3)#include<bits/stdc...
[BZOJ3751] [NOIP2014] 解方程 (数学)
Description已知多项式方程:$a_0+a_1*x+a_2*x^2+...+a_n*x^n=0$求这个方程在[1,m]内的整数解(n和m均为正整数)。Input第一行包含2个整数n、m,每两个整数之间用一个空格隔开。接下来的n+1行每行包含一个整数,依次为a0,a1,a2,...,an。Ou...
bzoj1412
比较裸的最小割注意狼和羊的领地可以通过空地相连 const inf=; dx:array[..] of integer=(,,,-); dy:array[..] of integer=(-,,,); type node=record next,point,flo...
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...