2019-03-12 17:13:37 |  0 Comments  |  线段树 扫描线

hdu 1542 Atlantis 扫描线:矩形面积并


题目大意

给出矩形的左下端点和右上端点的坐标,求所有的矩形的面积的并。


题解

求矩形面积并是扫描线的基础经典问题。这篇blog是借助这个来介绍初步入门扫描线。

扫描线,顾名思义,就是一条上下扫描或者左右扫描的虚拟的自主创造的线。

在扫描线扫描到一条线段的时候,就进行操作。而这种操作常常是利用线段树这种数据结构来进行存储的。

在矩形面积的并这一个问题中,我们可以这样去把要计算的总的面积分为这样几个部分来看:

(图来自于别人的博客,实在是不想自己画图了QAQ)

我们可以看到,这个图就是按照扫描线来分区计算面积的。

我们每一次找到一条扫描线,就要维护当前在这条扫描线上(当然这里扫描线是向上扫的)所有的线段的覆盖总长(覆盖部分不再重复计算)。

然后我们用两条扫描线的高度差去乘前一条扫面先上的所有线段的覆盖总长,就是这两条扫描线与矩形围成的面积并。

对于扫描线的顺序,只需要把矩形的上下边去离散化排序以下就可以了。

于是我们剩下的任务就是维护当前扫描线上的线段覆盖总长。

由于x坐标可能会很大,我们一样要对x进行离散化,并且记录离散化后的元素对应的离散化前的元素。

然后我们可以类比前缀和的方式:

对于每一个矩形的下边,我们设这里的标记为+1,对于每一个矩形的上边,我们设这里的标记为-1

这里的标记就可以使用线段树来维护了(但是这里的标记并不需要下放,也不需要向上更新,这里的标记是用于记录这段区间线段是否被覆盖的)。

于是我们在线段树中维护两个变量,一个表示这段区间表示的线段是否被完全覆盖,另一个表示这段区间被覆盖的线段的总长。

在求被覆盖线段总长时,要分两种情况进行讨论:

1.当前区间表示的线段被完全覆盖:区间被覆盖的线段总长即为这段区间表示的线段总长。

2.当前区间表示的线段未被完全覆盖:当前区间被覆盖的线段的总长=其左区间被覆盖的线段的总长+其右区间被覆盖的线段的总长。

我们是一边更新一边统计答案,统计答案只需要每次答案加上总区间被覆盖的线段总长×两条扫描线之间的高度差。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;
struct node
{
    double x1, x2, y1, y2; int id;
    node(double X1 = 0, double Y1 = 0, double X2 = 0, do
 2019-03-12 09:15:43 |  0 Comments  |  单调队列

POJ2823 Sliding Window 单调队列维护

题解

经典的单调队列维护。

单调队列可以在O(n)的时间内完成当前查找区间的最大值最小值的维护。

具体实现:

使用双端队列方便元素进出。元素保存的不是数而是数的位置,因为此题涉及到不在区间内的元素的删除,所以我们应该保存书的位置。

两个单调队列都要在遍历时,都要弹出当前不在查找区间内的元素。我们可以保证,如果要弹出,那么这个元素一定在队列的最开头。

第一个单调队列维护区间最小值,如果当前位置上的数比单调队列中的最后一个元素位置上的数大,则删除单调队列末尾位置的元素,一直到队列为空或者队列末尾元素位置的数比当前位置的数小,然后将当前位置编号加入队列。

第二个单调队列维护区间最大值,类比第一个单调队列。

记得循环的时候就保存答案。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num << 3) + (num << 1) + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e6+5;
int n,k;
int a[maxn];
dequeq1;
dequeq2;
int ans1[maxn];
int ans2[maxn];
int main(){
    n = get_num();
    k = get_num();
    for(int i = 1;i <= n;++i){
        a[i] = get_num();
    }
    for(int i = 1;i
 2019-03-06 18:08:45 |  0 Comments  |  模拟

CCF-CSP201812-2小明放学

题目背景

  汉东省政法大学附属中学所在的光明区最近实施了名为“智慧光明”的智慧城市项目。具体到交通领域,通过“智慧光明”终端,可以看到光明区所有红绿灯此时此刻的状态。小明的学校也安装了“智慧光明”终端,小明想利用这个终端给出的信息,估算自己放学回到家的时间。

问题描述

  一次放学的时候,小明已经规划好了自己回家的路线,并且能够预测经过各个路段的时间。同时,小明通过学校里安装的“智慧光明”终端,看到了出发时刻路上经过的所有红绿灯的指示状态。请帮忙计算小明此次回家所需要的时间。

输入格式

  输入的第一行包含空格分隔的三个正整数 r、y、g,表示红绿灯的设置。这三个数均不超过 10^6。
  输入的第二行包含一个正整数 n,表示小明总共经过的道路段数和路过的红绿灯数目。
  接下来的 n 行,每行包含空格分隔的两个整数 k、t。k=0 表示经过了一段道路,将会耗时 t 秒,此处 t 不超过 10^6;k=1、2、3 时,分别表示出发时刻,此处的红绿灯状态是红灯、黄灯、绿灯,且倒计时显示牌上显示的数字是 t,此处 t 分别不会超过 r、y、g。

输出格式

  输出一个数字,表示此次小明放学回家所用的时间。

样例输入

30 3 30
8
0 10
1 5
0 11
2 2
0 6
0 3
3 10
0 3

样例输出

46

样例说明

  小明先经过第一段路,用时 10 秒。第一盏红绿灯出发时是红灯,还剩 5 秒;小明到达路口时,这个红绿灯已经变为绿灯,不用等待直接通过。接下来经过第二段路,用时 11 秒。第二盏红绿灯出发时是黄灯,还剩两秒;小明到达路口时,这个红绿灯已经变为红灯,还剩 11 秒。接下来经过第三、第四段路,用时 9 秒。第三盏红绿灯出发时是绿灯,还剩 10 秒;小明到达路口时,这个红绿灯已经变为红灯,还剩两秒。接下来经过最后一段路,用时 3 秒。共计 10+11+11+9+2+3 = 46 秒。

评测用例规模与约定

  前 6 个测试点保证 n ≤ 10^3。
  所有测试点保证 n ≤ 10^5。

题解

这就是个水题……只要注意倒计时和从当前颜色灯开始亮起过的时间的区别就行了,剩下的就是一个一个的简单处理。
至于为什么写这道题……
因为我去年CSP的时候就是因为这道题崩了才没过……想想当时自己真的sb
注意开long long

代码

#include <bits/stdc++.h>
using names
 2019-02-27 23:53:01 |  0 Comments  |  树状数组

BZOJ 1537 POI2005 AUT-The Bus 二维偏序问题

由于格式问题,这道题的题面就不往这里放了,给一个洛谷的链接吧:

[POI2005]AUT-The Bus

题解

这道题有中文题意,没有BZOJ权限号的可以去洛谷上搜到这道题。
首先会想到DP,但是一看这个数据范围也太大了,离散化后也没法做二维DP。
但是离散化也是要的,不然10的9次方的数据谁顶得住啊。
考虑这是一个二维偏序问题。一般的二维偏序都是找比当前物品的两个值都小的问题,而这道题并不是,这道题要做的是维护最大前缀和。
首先按照y排序并且离散化每个车站的y坐标,然后再按照x排序,使用树状数组维护最大前缀和即可(当然线段树应该也是可以的,只不过会比树状数组麻烦一点)。注意这里的树状数组不是维护的前缀和,而是维护前缀和的最大值。所以update操作和query操作里并不是求和,而是取最大值。


代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e5+5;
struct point{
    int x,y,k;
}p[maxn];
bool cmp1(point a,point b){
    return a.y < b.y;
}
bool cmp2(point a,point b){
    if(a.x == b.x)return a.y < b.y;
    return a.x < b.x;
}
int lowbit(int x){
    return x & (-x);
}
int c[maxn];
int n,m,k,cnt;
void update(int x,int d){
    while(x <= 
 2019-02-27 00:17:20 |  0 Comments  |  并查集

HDU-5441 Travel 贪心+加权并查集

Descrpition

Jack likes to travel around the world, but he doesn’t like to wait. Now, he is traveling in the Undirected Kingdom. There are n cities and m bidirectional roads connecting the cities. Jack hates waiting too long on the bus, but he can rest at every city. Jack can only stand staying on the bus for a limited time and will go berserk after that. Assuming you know the time it takes to go from one city to another and that the time Jack can stand staying on a bus is x minutes, how many pairs of city (a,b) are there that Jack can travel from city a to b without going berserk?

Input

The first line contains one integer T,T≤5 , which represents the number of test case.

For each test case, the first line consists of three integers n,m and q where n≤20000,m≤100000,q≤5000 . The Undirected Kingdom has n cities and m bidirectional roads, and there are q queries.

Each of the following m lines consists of three integers a,b and d where a,b∈{1,...,n} and d≤100000 . It takes Jack d minutes to trav

 2019-02-26 20:08:10 |  0 Comments  |  最短路

HDU - 5876 Sparse Graph 补图最短路(使用两个set的做法)

题目大意

给出图G,求图G的补图H对于源点S的单源最短路


题解

这道题目就是稍微考虑一下就可以了。同样是一个BFS的写法,只不过这次的BFS要求不能使用图中给出的边,我们要求的是补图的最短路,就要用非原图的所有边。
这样我们可以使用两个set,其中过一个记录当前会被更新的点,另一个记录还没有被更新过的点。具体实现看代码,不好解释。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
sets1;
sets2;
const int maxn = 2e5+5;
struct edge{
    int to,next;
}e[maxn];
int h[maxn];
int dis[maxn];
int T,n,m,S,u,v,cnt;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (((num<<2)+num)<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
void init(){
    for(int i = 1;i <= n;++i){
        h[i] = -1;
        dis[i] = -1;
    }
    cnt = 0;
}
void add(int u,int v){
    e[cnt].to = v;
    e[cnt].next = h[u];h[u] = cnt++;
    return;
}
void BFS(int s){
    for(int i = 1;i <=
 2019-02-26 18:14:48 |  0 Comments  |  topsort

HDU - 4948 Kingdom 拓扑排序

Description

Teacher Mai has a kingdom consisting of n cities. He has planned the transportation of the kingdom. Every pair of cities has exactly a one-way road.

He wants develop this kingdom from one city to one city.

Teacher Mai now is considering developing the city w. And he hopes that for every city u he has developed, there is a one-way road from u to w, or there are two one-way roads from u to v, and from v to w, where city v has been developed before.

He gives you the map of the kingdom. Hope you can give a proper order to develop this kingdom.

Input

There are multiple test cases, terminated by a line "0".

For each test case, the first line contains an integer n (1<=n<=500).

The following are n lines, the i-th line contains a string consisting of n characters. If the j-th characters is 1, there is a one-way road from city i to city j.

Cities are labelled from 1.

Output

If there is no solution just output "-1". Otherwise output n integers representing the order to develop this kingdom.

Sampl

 2019-02-24 16:33:29 |  0 Comments  |  网络流 费用流 最大流

HDU5352 MZL's City

Description

MZL is an active girl who has her own country.

Her big country has N cities numbered from 1 to N.She has controled the country for so long and she only remebered that there was a big earthquake M years ago,which made all the roads between the cities destroyed and all the city became broken.She also remebered that exactly one of the following things happened every recent M years:

1.She rebuild some cities that are connected with X directly and indirectly.Notice that if a city was rebuilt that it will never be broken again.

2.There is a bidirectional road between city X and city Y built.

3.There is a earthquake happened and some roads were destroyed.

She forgot the exactly cities that were rebuilt,but she only knew that no more than K cities were rebuilt in one year.Now she only want to know the maximal number of cities that could be rebuilt.At the same time she want you to tell her the smallest lexicographically plan under the best answer.Notice that 8 2 1 is smaller than 10 0 1.

I

 2019-02-14 10:43:38 |  0 Comments  |  网络流 最小割 最短路

BUPT校内训练 & HDU 5294 最短路&最小割

Description

Innocent Wu follows Dumb Zhang into a ancient tomb. Innocent Wu’s at the entrance of the tomb while Dumb Zhang’s at the end of it. The tomb is made up of many chambers, the total number is N. And there are M channels connecting the chambers. Innocent Wu wants to catch up Dumb Zhang to find out the answers of some questions, however, it’s Dumb Zhang’s intention to keep Innocent Wu in the dark, to do which he has to stop Innocent Wu from getting him. Only via the original shortest ways from the entrance to the end of the tomb costs the minimum time, and that’s the only chance Innocent Wu can catch Dumb Zhang.
Unfortunately, Dumb Zhang masters the art of becoming invisible(奇门遁甲) and tricks devices of this tomb, he can cut off the connections between chambers by using them. Dumb Zhang wanders how many channels at least he has to cut to stop Innocent Wu. And Innocent Wu wants to know after how many channels at most Dumb Zhang cut off Innocent Wu still has the chance to catch Dumb

 2019-02-14 09:39:19 |  0 Comments  |  网络流 费用流

BZOJ 1937 Mst最小生成树

Description

Input

第一行为N、M,其中 表示顶点的数目, 表示边的数目。顶点的编号为1、2、3、……、N-1、N。接下来的M行,每行三个整数Ui,Vi,Wi,表示顶点Ui与Vi之间有一条边,其权值为Wi。所有的边在输入中会且仅会出现一次。再接着N-1行,每行两个整数Xi、Yi,表示顶点Xi与Yi之间的边是T的一条边。

Output

输出最小权值

Sample Input

6 9
1 2 2
1 3 2
2 3 3
3 4 3
1 5 1
2 6 3
4 5 4
4 6 7
5 6 6
1 3
2 3
3 4
4 5
4 6

Sample Output

8

【样例说明】 边(4,6)的权由7修改为3,代价为4
边(1,2)的权由2修改为3,代价为1
边(1,5)的权由1修改为4,代价为3
所以总代价为4+1+3=8
修改方案不唯一。

HINT

1<=n<=50,1<=m<=800,1<=wi<=1000
n-->点数..m-->边数..wi--->边权


题解

这道题的题意是要求修改一些边的权值使得给出的树成为这个图的最小生成树,求最小代价。
注意到我们只可能增大非树边,减小树边。

那么对于一个树边ii和一个可能影响到最小生成树的非树边jj,我们一定要满足如下条件:
widiwj+djwi−di≤wj+dj
移项,即
wiwjdi+djwi−wj≤di+dj
其中d表示我们对于边的改动值(一定非负)
这样就可以转化成二分图最小顶标和来做。
我们把边看成点,两原边边权之差作为新点之间的边权,跑一边KM或者最小费用最大流就可以了。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int N=1005,M=2e5
Title - Artist
0:00