BZOJ3566 : [SHOI2014]概率充电器
选个根把无根树转化成有根树，设f[i]表示i不通电的概率则答案为对于枚举树根root进行DP后1-f[root]的和直接算是O(n^2)的，但是n有500000，所以不能过。对于这样一棵以1为根的树，求出它的欧拉遍历序为1->2->5->2->6->2->1-&g...
【bzoj3160】万径人踪灭 FFT
题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3160我是一个傻叉 微笑脸 #include<bits/stdc++.h> #define inf 1000000000 #define ll long long #define N ...
Bzoj3160：万径人踪灭
题面BzojSol求不连续回文子序列的个数\(ans=\)回文子序列个数-连续回文子序列个数即回文子序列个数-回文子串个数后面直接\(Manacher\)就好了考虑前面的枚举对称轴，设\(f[i]\)表示对称轴\(i\)两边相同字符的对数那么最终答案就是\(\sum 2^{f[i]}-1\)考虑求\...
【BZOJ3160】万径人踪灭（FFT，Manacher）
【BZOJ3160】万径人踪灭（FFT，Manacher）题面BZOJ题解很容易想到就是满足条件的子序列个数减去回文子串的个数吧。。。至于满足条件的子序列我们可以依次枚举对称轴如果知道关于这个位置对称的位置的组数就很容易算了（直接\(2^k-1\)）而关于这个位置对称是什么东西？\(s[x-i]=s...
BZOJ3160【万径人踪灭】 【FFT】
。。恩 打了四五遍 不会也背出来了。。BZOJ3160 【听说时限紧？转C++的优势么？】上AC代码 fft /*Problem: 3160 User: cyz666 Language: C++ Result: Accepted Time:1992 ms Me...
[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\)树根节点的所有节点...