题目大意

给出一棵$n$个节点的有根树，编号为$0$到$n-1$，根节点为$0$

询问$m$次，每次询问给出区间$[l,r]$和节点编号$z$，求$$\sum_{l\leqslant i\leqslant r}deep[lca(i,z)]$$

每个答案对$201314$取模输出

阅读更多……

这是$ZGJ$升上高中之后，考得很好的一次比赛，虽然也有很多遗憾

阅读更多……

【bzoj1877】晨跑

题目大意

给出有$n$个点$m$条边的带权图

要求找到最多的(起点到终点)路径数且使总费用尽量少

路径与路径之间不能相交

建图

每个点只能经过一次

拆点，容量为$1$，费用为$0$

每条边有边权，且使得边权和最小

容量为$+∞$,费用为边权

源点和汇点

点$1$和点$n$可以经过多次，因此不用开超级源和超级汇，直接取点$1$和点$n$分别作为源点和汇点

阅读更多……

题目大意

给定一张$n$个点$m$条边的有向图，每条边都有一个容量$c$和一个扩容费用$w$（这里扩容费用是指将容量扩大$1$所需的费用）

询问

1. 在不扩容的情况下，$1$到$n$的最大流

2. 将$1$到$n$的最大流增加$k$所需的最小扩容费用

阅读更多……

题目大意

给出一个有$n$个点$m$条边的无向图

求至少要删掉几个点，使得新图存在两个点无法联通

阅读更多……

[bzoj2648]小$Z$的袜子——普通莫队

题目大意

给出一个有$n$个数的数列$A:a_1,a_2,a_3\dots a_n$，询问$m$次

每次询问给出一个区间$[l,r]$，询问区间$[l,r]$内抽到一对数值相等的数的概率大小

数据范围

$n,m\leqslant 50000$，$1\leqslant l< r\leqslant n$，$a_i\leqslant n$

题解

不妨设区间$[l,r]$里元素个数为$len$，显然，抽一对数的情况总数为$C_{len}^2$

同时区间里只有$k$种数值，每种数值对应的元素有$s_1,s_2\dots s_k$个，抽一对数值相等的数的情况总数为$C_{s_1}^2+C_{s_2}^2+\dots C_{s_k}^2$

则答案为$$\frac{C_{s_1}^2+C_{s_2}^2+\dots C_{s_k}^2}{C_{len}^2}=\frac{s_1(s_1-1)+s_2(s_2-1)+\dots s_k(s_k-1)}{len(len-1)}=\frac{s_1^2+s_2^2+\dots s_k^2-len}{len(len-1)}$$

那么现在问题简化为，如何即时地统计所有的$s_1,s_2\dots s_k$

这个时候引入一个东西，莫队算法，是莫涛前几年提出的算法，适用于解决离线区间查询问题

Question Ⅰ：这个算法怎么用啊？

假设已经得到了区间$[l,r]$需要统计的信息，可以在常数级别的时间内转移到区间$[l-1,r]$、区间$[l+1,r]$、区间$[l,r-1]$、区间$[l,r+1]$

那么可以在$O(n\sqrt n)$的时间复杂度求得所有答案

Question Ⅱ：这个时间复杂度？

我们可以调整一下处理每个查询的顺序，保证最优的顺序之下转移区间

将$n$个数分成$\sqrt n$块

按区间排序，以左端点所在块内为第一关键字，右端点为第二关键字，进行排序

然后按这个排序直接暴力，复杂度分析是这样的：

1. $i$与$i+1$在同一块内，$r$单调递增，所以$r$是$O(n)$的，由于有$\sqrt n$块，所以这一部分时间复杂度是$n\sqrt n$

2. $i$与$i+1$跨越一块，$r$最多变化$n$，由于有$\sqrt n$块，所以这一部分时间复杂度是$n\sqrt n$

3. $i$与$i+1$在同一块内，$l$变化不超过$\sqrt n$，跨越一块也不会超过$\sqrt n \times 2$

由于有$m$次询问（和$n$同级），所以时间复杂度是$n\sqrt n$

阅读更多……

题目大意

有$m$条路径在一棵有$n$个节点的树上，问每个点恰为多少条路径起点出发$w_i$长度处

阅读更多……

#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;

vector <int> a;
inline bool cmp(int a,int b){return a>b;}

int main(){

    a.push_back(1);//向队尾插入一个元素 
    printf("%d\n",a[0]);//从零开始计数 
    puts("");

    a.push_back(2); 
    int k=1000;
    a.push_back(k);
    for(int j=0;j<=2;j++) printf("%d\n",a[j]); 
    puts("");

    a.insert(a.begin()+2,3);//在第三个元素后边插入元素 
    vector <int>::iterator i;//第一次使用迭代器访问元素 
    for(i=a.begin();i!=a.end();i++) printf("%d\n",*i); 
    puts("");

    for(i=a.begin();i!=a.end();i++) *i+=1,printf("%d\n",*i); 
    puts("");

    a.erase(a.begin()+2);//删除第三个元素 
    for(i=a.begin();i!=a.end();i++) printf("%d\n",*i);
    puts("");

    int size=a.size();//得到元素个数 
    printf("%d\n",size); 
    puts("");

    sort(a.begin(),a.end(),cmp);//排序所有元素 
    for(i=a.begin();i!=a.end();i++) printf("%d\n",*i);  
    puts("");

    a.clear();//删除所有元素 
    printf("%d\n",a.size());
    puts("");
}

此文为借鉴戳这里看原文

$ZGJ$傻傻的参加了第一次$NOIP$提高组

阅读更多……

题目大意

给出一棵有$n$个节点的无根树

若两个点路径上边的边权和是$3$的倍数，求这样的点对个数

阅读更多……