Forever you~

题意：给一个$n$个点$m$条边的(连通)无向图，$q$个询问，每次询问给出$k$条原图中的边，问将这些边删掉后，无向图是否还是保持连通。一个图是连通的当且仅当任意两个不同的点之间存在一条路径连接他们。$N\le 100000,M\le 500000,Q\le 50000,1\le K\le 15$。 这道题实际上是bzoj 3237的加强版。 对原图随便找一个生成树出来，对非树边随机边权，树边边权则为覆盖它的所有非树边权值的异或和，那么一个边集删去后使得图不连通等价于这个边集存在一个子集的权值异或和为0。 随机是为了让边权异或和在不应该是0的情况下不为0。 正确性证明参考这篇 http://dwjshift.logdown.com/posts/2830435 时间复杂度$O(m+n+32qk)$ 1234567891011121314151617181920212223242526... Continue reading...

小清新线段树的概念是由jiry_2提出的，区别于zkw(重口味)线段树命名。这里我的理解是可以归为一类结合时间复杂度分析以及懒标记应用的非传统线段树。不过既为非传统，这类题目总体来说还是做法各异，下面就结合题目做一些分析。 入门难度1.bzoj 3211 花神游历各国区间求和，区间开根号（下取整） 因为只有开根号操作，所以最后不是1就是0，且一个数开根号次数$O(loglogC)$级别的，1e9的数最多开5次。所以就怎么暴力都行了，比如判断当前区间最大值是否是1，或者直接记录访问每个节点的次数是否达到5次，用于剪枝。时间复杂度$O(nlogn+nloglogC)$。 2.bzoj 3333 排队计划这个题其实不是很入门 有一个排列，每次修改是给一个位置x，先拿出x及之后所有小于等于a[x]的数，从小到大排序后，再放回空位中，一开始及每次操作完都要输出当前排列的逆序对数。 计算逆序对... Continue reading...

对于一类区间询问问题，如果可以离线并且可以快速合并区间信息那么就有一个非常实用的分治方法。首先我们对总区间分治下去，当前区间$[l , r]$中点为$mid$，那么我们将所有的询问分成三类，一类包括$mid$这个点，一类完全在左侧，一类完全在右侧，我们只要在当前这层解决第一类的所有询问，后两类分治下去即可。怎么快速的求呢？方法也非常简单，因为信息可以快速合并，那么我们以$mid$为界，往前处理出所有后缀信息，往后处理出所有前缀信息，对于一个跨过$mid$的询问，拿两部分拼一下就算出答案了！ 比在线算法优秀的地方在于可以优雅的去掉询问数所乘的log。 练习题目1.2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest J. Subsequence Sum Queries考虑背包dp，如果用普通的线段树，时间复杂度$... Continue reading...

问题的引入一个$n \times m$二维矩阵$A$的前缀和$S$,一般来说定义为$S_{x,y}=\sum_{i=1}^{x}\sum_{j=1}^{y}A_{i,j}$。 代码常见的写法就是用容斥加加减减： 123for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+A[[i][j]; 这是二维的情况，如果是三维或者是更高的k维，不难发现复杂度有一个$2^k$，指数爆炸了。 然而，用高维前缀和的技巧，就可以有效的将时间复杂度降下来。具体的思路是一维一维的求和。比如还是刚才二维的例子，为方便叙述，想象矩阵左上角是$(1,1)$，我们先对每行分别从左到右累加，即对每行求一维前缀和，再对每列从上到下累加，还是相同的过程，这样求出的结果就是二... Continue reading...

Lena and Queries题目链接：http://codeforces.com/contest/678/problem/F 三种操作，1.插入一个点$(x,y)$ 2.删除之前第$i$个操作插入的点 3.给一个$q$，询问在已有点中$qx+y$最大是多少 如果没有删除完全可以cdq分治然后在上凸壳上三分。有删除操作的话因为贡献不独立，所以不能cdq分治。 但是可以用上一次线段树优化建图一样的技巧，按时间来看，因为每个点的存在是一段区间，那么就可以用线段树拆成log个区间，然后把点“打”在上面（加进vector），最后对于线段树上每个区间，做凸壳然后询问就行了。每个询问会被问log次，所以时间复杂度粗略算有$O(nlog^2n)$。 12345678910111213141516171819202122232425262728293031323334353637383940414... Continue reading...

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6442 定义序列${a}=(a_0,a_1,a_2,\dots)$ 它的指数型生成函数为$g_(x)=\sum_{i=0}^{\infty}\frac{a_i}{i!}x^i$ 设$c$是一个常数 定义序列${u_c}=(c^0,c^1,c^2,\dots)$,${e_c}=(0,c^1,0,c^3,0,c^5,\dots)$ 定义两个生成函数$g_,g_$的卷积$G(x)=(g_*g_)(x)=\sum_{n=0}^{\infty}(\sum_{i+j=n}\frac{a_i}{i!}\frac{b_j}{j!})x^n$(原题面省略了阶乘，可能是写错了?) 现在给三个正整数$n,A,B$,求$G(x)=g_{u_A}*g_{e_{\sqrt{B}}}$的$x^n$前的系数乘上$n!$后... Continue reading...

有一类经典的问题，之前见过很多次了，好像某一场区域赛的热身赛里就出过：一维数轴上有$n$个炸弹，$x_i,r_i$分别表示第$i$个炸弹的位置和引爆半径，即如果引爆炸弹$i$，那么位置在$[x_i-r_i,x_i+r_i]$范围内的炸弹都会爆炸，并且引发连锁反应。然后比如询问最少引爆几个炸弹才能全部炸完。 首先一个建图思路是如果$i$能引爆$j$，那么$i$向$j$连一条边，做tarjan求强连通分量就可以知道很多信息了。但是这样暴力连边是$O(n^2)$的，需要优化。一个显然的观察是，一个点$i$的引爆范围是一段区间（这句是废话），所以是和一个区间的点连边，那么我们把炸弹按位置排序后，$1$到$n$编好号，建线段树，线段树每个点向左右儿子分别连边。如果$i$要向区间$(l,r)$所有点连边的话，就在线段树中将区间$(l,r)$分解成$O(logn)$条线段，这样就转化成了向对应的线... Continue reading...

题目链接：https://vijos.org/p/category/2014 D1T1 生活大爆炸版 石头剪刀布没想到noip还会出纯模拟 1234567891011121314151617181920212223#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[N],b[N];const int w[5][5]={{0,-1,1,1,-1},{1,0,-1,1,-1},{-1,1,0,-1,1},{-1,-1,1,0,1},{1,1,-1,-1,0}};int main(... Continue reading...

最近突然想回顾一下历年noip题目，就开个新坑吧，题解就从略了 题目链接 https://vijos.org/p/category/2013 D1T1 转圈游戏公式就$(x+m10^k)%n$，现在一眼的事情当时想了很久orz 12345678910111213141516171819202122#include<bits/stdc++.h>using namespace std;int power(int x,int n,int mod){ int ans=1; while(n) { if(n&1) ans=1LL*ans*x%mod; x=1LL*x*x%mod; n>>=1; } return ans;}int main(){... Continue reading...

问题引入题目要求解决的模型： 给定有向图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出发到达y的所有必经点构成的集合记为dom(y)，即dom(y)={x | x dom y}。 最近必经点（idom）： 节点y的必经点集合dom(y)中dfn值最大的点x是距离y最近的必经点，称为y的最近必经点。最近必经点是唯一的，因此可以记x=idom(y)。 于是可以按下面$O(V^2)$暴力求解 $pre(y)={x|(x,y)\in E}$ y的前驱节点集合 $suc(x)={y|(x,y... Continue reading...