UOJ Logo zgjkt的博客

博客

【bzoj3626】LCA

2017-03-16 13:42:49 By zgjkt

题目大意

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

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

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

阅读更多……

【GDKOI'2017'】总结与反思

2017-02-20 13:08:09 By zgjkt

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

阅读更多……

几道费用流建图方法

2017-02-14 14:00:27 By zgjkt

【bzoj1877】晨跑

题目大意

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

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

路径与路径之间不能相交


建图

每个点只能经过一次

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

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

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

源点和汇点

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

阅读更多……

【bzoj1834】网络扩容

2017-02-08 14:00:33 By zgjkt

题目大意

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

询问

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

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

阅读更多……

【poj1966】Cable TV Network

2017-02-07 13:08:00 By zgjkt

题目大意

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

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

阅读更多……

各种莫队算法

2016-12-26 14:10:07 By zgjkt

[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$

阅读更多……

【NOIP'2016'】天天爱跑步

2016-12-17 11:12:32 By zgjkt

题目大意

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

阅读更多……

关于vector

2016-12-14 14:09:51 By zgjkt
#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("");
}

此文为借鉴戳这里看原文

【NOIP'2016'】总结与反思

2016-11-21 14:06:00 By zgjkt

【bzoj2152】聪聪可可

2016-09-02 13:07:54 By zgjkt

题目大意

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

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

阅读更多……

共 63 篇博客