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>
using namespace std;
typedef long long ll;
const int N=1005,M=2e5+5,INF=1e9;
int get_num(){
	int num = 0;
	char c;
	bool flag = false;
	while((c = getchar()) == ' ' || c ==
 2019-02-13 09:33:40 |  0 Comments  |  最短路 差分约束系统

[转载]差分约束系统详细讲解

差分约束系统

一、何为差分约束系统:
差分约束系统(system of difference constraints),是求解关于一组变数的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成,其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即,差分约束系统是求解关于一组变量的特殊不等式组的方法。
通俗一点地说,差分约束系统就是一些不等式的组,而我们的目标是通过给定的约束不等式组求出最大值或者最小值或者差分约束系统是否有解。
比如:


二、差分约束系统的求解:
差分约束系统可以转化为图论来解决,对应于上面的不等式组,如果要求出x3-x0的最大值的话,叠加不等式可以推导出x3-x0<=7,最大值即为7,我们可以通过建立一个图,包含6个顶点,对每个xj-xi<=bk,建立一条i到j的有向边,权值为bk。通过求出这个图的x0到x3的最短路可以知道也为7,这是巧合吗?并不是。
之所以差分约束系统可以通过图论的最短路来解,是因为xj-xi<=bk,会发现它类似最短路中的三角不等式d[v] <=d[u]+w[u,v],即d[v]-d[u]<=w[u,v]。而求取最大值的过程类似于最短路算法中的松弛过程。
三角不等式:(在此引用大牛的博客)
B - A <= c     (1)
C - B <= a     (2)
C - A <= b     (3)
 如果要求C-A的最大值,可以知道max(C-A)= min(b,a+c),而这正对应了下图中C到A的最短路。


因此,对三角不等式加以推广,变量n个,不等式m个,要求xn-x1的最大值,便就是求取建图后的最短路。
同样地,如果要求取差分约束系统中xn-x1的最小值,便是求取建图后的最长路。最长路可以通过spfa求出来,只需要改下松弛的方向即可,即if(d[v] < d[u] + dist(u,v)) d[v] = d[u] + dist(u,v)。当然我们可以把图中所有的边权取负,求取最短路,两者是等价的。
最长路求解算法证明如下:
http://www.cnblogs.com/g0feng/archive/2012/09/13/2683880.html
最后一点,建图后不一定存在最短路/最长路,因为可能存在无限减小/增大的负环/正环,题

Title - Artist
0:00