Forever you~
首页
归档
分类
标签
关于
bzoj 3569 DZY Loves Chinese II
题意:给一个nnn个点mmm条边的(连通)无向图,qqq个询问,每次询问给出kkk条原图中的边,问将这些边删掉后,无向图是否还是保持连通。一个图是连通的当且仅当任意两个不同的点之间存在一条路径连接他们。N≤100000,M≤500000,Q≤50000,1≤K≤15N\le 100000,M\le 500000,Q\le 50000,1\le K\le 15N≤100000,M≤500000,Q≤
2019-02-18
散装题解
随机化
小清新线段树
小清新线段树的概念是由jiry_2提出的,区别于zkw(重口味)线段树命名。这里我的理解是可以归为一类结合时间复杂度分析以及懒标记应用的非传统线段树。不过既为非传统,这类题目总体来说还是做法各异,下面就结合题目做一些分析。 入门难度 1.bzoj 3211 花神游历各国 区间求和,区间开根号(下取整) 因为只有开根号操作,所以最后不是1就是0,且一个数开根号次数O(loglogC)O(log
2018-11-08
算法学习
线段树
时间复杂度
一类区间分治技巧
对于一类区间询问问题,如果可以离线并且可以快速合并区间信息那么就有一个非常实用的分治方法。首先我们对总区间分治下去,当前区间[l,r][l , r][l,r]中点为midmidmid,那么我们将所有的询问分成三类,一类包括midmidmid这个点,一类完全在左侧,一类完全在右侧,我们只要在当前这层解决第一类的所有询问,后两类分治下去即可。怎么快速的求呢?方法也非常简单,因为信息可以快速合并,那么我
2018-10-30
算法学习
分治
高维前缀和
问题的引入 一个n×mn \times mn×m二维矩阵AAA的前缀和SSS,一般来说定义为Sx,y=∑i=1x∑j=1yAi,jS_{x,y}=\sum_{i=1}^{x}\sum_{j=1}^{y}A_{i,j}Sx,y=∑i=1x∑j=1yAi,j。 代码常见的写法就是用容斥加加减减: for(int i=1;i<=n;++i) for(int j=1;j<=m
2018-10-29
算法学习
线段树优化凸壳
Lena and Queries 题目链接:http://codeforces.com/contest/678/problem/F 三种操作,1.插入一个点(x,y)(x,y)(x,y) 2.删除之前第iii个操作插入的点 3.给一个qqq,询问在已有点中qx+yqx+yqx+y最大是多少 如果没有删除完全可以cdq分治然后在上凸壳上三分。有删除操作的话因为贡献不独立,所以不能cdq分治。 但是
2018-10-09
算法学习
线段树
2018 CCPC网络赛 GuGu Convolution
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6442 定义序列{a}=(a0,a1,a2,… )\{a\}=(a_0,a_1,a_2,\dots){a}=(a0,a1,a2,…) 它的指数型生成函数为g{a}(x)=∑i=0∞aii!xig_{\{a\}}(x)=\sum_{i=0}^{\infty}\frac{a_i}{i!}x^ig{a}
2018-10-08
散装题解
生成函数
线段树优化建图
有一类经典的问题,之前见过很多次了,好像某一场区域赛的热身赛里就出过:一维数轴上有nnn个炸弹,xi,rix_i,r_ixi,ri分别表示第iii个炸弹的位置和引爆半径,即如果引爆炸弹iii,那么位置在[xi−ri,xi+ri][x_i-r_i,x_i+r_i][xi−ri,xi+ri]范围内的炸弹都会爆炸,并且引发连锁反应。然后比如询问最少引爆几个炸弹才能全部炸完。 首先一个建图思路
2018-09-30
算法学习
线段树
NOIP 2014
题目链接:https://vijos.org/p/category/2014 D1T1 生活大爆炸版 石头剪刀布 没想到noip还会出纯模拟 #include<bits/stdc++.h> using namespace std; #define N 205 #define rep(i,l,r) for(int i=l;i<=r;++i) int n,na,nb; int a[
2018-09-28
散装题解
noip
NOIP 2013
最近突然想回顾一下历年noip题目,就开个新坑吧,题解就从略了 题目链接 https://vijos.org/p/category/2013 D1T1 转圈游戏 公式就(x+m10k)%n(x+m10^k)\%n(x+m10k)%n,现在一眼的事情当时想了很久orz #include<bits/stdc++.h> using namespace std; int power(int
2018-09-26
散装题解
noip
Dominator Tree
问题引入 题目要求解决的模型: 给定有向图G(可能有环)和图中的一个点r,对于G中的任意一个点x,求从r到x的路径上(可能有很多条)必须经过的点集。 Flow Graph:若有向图G中存在一点r,从r出发可到达G中所有的点,则称G是Flow Graph,记为(G,r)。 必经点(dom):若在(G,r)中从r到y的路径一定经过点x,则称x是从r到达y的必经点,记为x dom y。 从r出发到达
2018-09-14
算法学习
图论
1
2
3
4
搜索
×
关键词