3 千杯湖底沙.

尚未进行身份认证

我要认证

退役了。 OI就到此为止吧。 呃我又回来了

等级
TA的排名 3w+

注意点

关于C++STLmapC++STLmapC++STLmap 如果一个元素没有在映射中出现过,那么它的初值是不确定的, 不能通过判断它的初值来判断它是否被赋值过。比如定义一个数到boolboolbool型的映射,如果没有出现过map[1]map[1]map[1],那么我们不能通过判断map[1]==0map[1]==0map[1]==0来判断数字111是否过。...

2020-10-30 19:16:11

Luogu P4552 IncDec Sequence 题解

题目描述给定一个长度为nnn的数列a1,a2,a3,…,ana_1, a_2, a_3,…,a_na1​,a2​,a3​,…,an​每次可以选择一个区间[L,R][L,R][L,R],使这个区间内的所有数都+1+1+1或者−1-1−1。请问至少需要多少次操作才能使数列中所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。提交地址洛谷提交地址Contest Hunter 提交地址分析这道题用差分做。对于原数列,求出它的差分数列bib_ibi​。我们现在要做的事情就是:把差分数列b

2020-10-29 17:00:19

回归刷题记录(停更)

看到之前发过的博客还是费用流和点双边双问题,感慨良多呀。10.15中午洛谷P1226 【模板】快速幂快速幂代码:int power (int a, int b, int p) { int ans = 1 % p; for (; b; b >>= 1) { if (b & 1) ans = (long long)ans * a % p; a = (long long)a * a % p; } return ans;}这里引用一下高中时代膜拜的大佬之一syq大佬的

2020-10-15 13:03:15

回归

我回来了!!!2020/9/13 西电开学2020/9/21 重拾C++目标大概是参加 CTF 和 ACM 并拿到满意的成绩吧。

2020-09-23 22:03:20

分块算法坑点

分清楚iii代表的意义。solution:用k来枚举块不要iii在枚举块的时候还套p[i]p[i]p[i], 不要iii在枚举数的时候不套p[i]p[i]p[i]。在维护累加和的时候,delta记号记得乘上数量。solution:特别检查一下吧…...

2018-09-05 21:18:51

【haoi2009】毛毛虫

题面题目描述 对于一棵树,我们可以将某条链和与该链相连的边抽出来,看上去就象成一个毛毛虫,点数越多,毛毛虫就越大。例如下图左边的树,抽出一部分就变成了右边的一个毛毛虫了。 输入格式 第一行两个整数N,M,分别表示树中结点个数和树的边数。 接下来M行,每行两个整数a, b表示点a和点 b有边连接(a, b≤N)。你可以假定没有一对相同的(a, b)会出现一次以上。 输出格式 一个...

2018-08-31 10:39:06

bzoj 1718: [Usaco2006 Jan] Redundant Paths 分离的路径

题面题目描述 In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the rest of the herd are forced to cross near the Tree of Rott...

2018-08-23 08:56:22

hdoj3394 railway

题面题目描述 有一个公园有n个景点,这n个景点由m条无向道路连接而成。 公园的管理员准备规划一一些形成回路的参观路线。如果一条道路被多条参观路线公用,那么这条路是冲突的;如果一条道路没在任何一个回路内,那么这条路是多余的道路。 问分别有多少条有冲突的路和多余的路 输入格式 包括多组数据 每组数据第一行2个整数n,m 接下来m行,每行2个整数x,y,表示从x到y有一条无向边。 输入...

2018-08-23 08:49:47

Tarjan算法——边双和点双

边双连通分量边双连通图:如果一个无向连通图中,没有割边,那么这个无向连通图就是一个边双连通图。一个无向图的极大边双连通子图就是它的其中一个边双连通分量。 我们要解释下这里“极大”的概念:如果一个连通子图G1G1G1是边双,那么不存在一个原图的子图G2G2G2既满足G1∈G2G1∈G2G1\in G2又满足G2是边双G2是边双G2是边双。边双的“极大”不是指整个图范围内的最大,而是所有...

2018-08-23 08:37:56

poj 3694 network

题目大意给一张无向连通图,然后给q个操作,每个操作都会在某两个点xy之间连边,问每一个操作之后还有几座桥。题解先用tarjan求边双,缩点求新图。 先让ans=割边条数 然后对于每一个操作(x,y) 如果他们在同一个边双里,答案不变。 如果不在同一个边双,那么求出他们边双的lca=LCA(block[x],block[y]); x和y两个点分别向父亲跳,直到到lca。途径全部...

2018-08-17 20:23:40

Tarjan算法——割点与割边

tarjan算法中的一些要素dfn[i]代表时间戳,是访问该节点的时间。low[i]代表追溯值。是该节点以及它的子树通过非搜索树边能追溯的dfn值最小的祖先的dfn值。割点割点的概念就是:在一张无向图中,去掉某一个点,这个图将会分裂成多个连通子图。我们知道一个点不是割点,当前仅当这个点在至少一个简单环上。 我们还可以知道,不在搜索树上的边一定是一个点连到它的祖先的。而不是连到...

2018-08-10 21:20:55

bzoj 2730 [HNOI2012]矿场搭建

题面Description 煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。 Input 输入文件有若干组数据,每组数...

2018-08-02 11:27:13

[网络流24题]负载平衡问题 (费用流)

题目描述G公司n个沿铁路运输线环形排列的仓库,每个仓库存储的货物数量不等。如何用最少搬运量可以使n 个仓库的库存数量相同。搬运货物时,只能在相邻的仓库之间搬运。 输入输出格式 输入格式: 文件的第1 行中有1 个正整数 n ,表示有 n 个仓库。第 2 行中有 n 个正整数,表示 n 个仓库的库存量。 输出格式: 输出最少搬运量。题解很明显,题目中要求运送的货物最少,我们...

2018-07-28 15:55:43

poj3422 卡卡的矩阵旅行(费用流)

题意做过过河卒(一取方格数)、传纸条(二取方格数),我们这里来安利K取方格数。 也就是给出一个方阵,大小为n×nn×nn\times n 每一个格子都有一个权值。 我们需要从左上角到右下角取nnn条路径。每一条路径都会取掉当前方格内的数。多条路径通过同一个位置的话,这个位置的数只取一次。 要求最大化k条路径取到的数之和。题解由于每一个点的数只能被取一次,但是可以被走过多次。...

2018-07-21 18:42:42

网络流小结

网络流建模建模的条件是根据限制性条件连边。 对于每条边的限制性条件用容量来限制; 对于每个点的限制性条件用拆点之后连自边来限制。网络流算法EK算法 Dinic算法 二分图的匈牙利算法 EK+SPFA费用流算法 ZKW费用流(等待填坑)写网络流的注意点数组大小问题邻接表从0开始,头结点数组填满-1.调不出来了就重敲。区分算法建模很重要!!!...

2018-07-21 14:38:47

费用流模板——EK+SPFA实现的最小费用最大流

算法原理用两个字的高度概括——贪心~ 用一句话的概括:每一次通过spfa找到花费最小的可行流,然后进行增广,直到残量网络中,源点不能达到汇点。 其实还是通过代码理解比较好。code这里1是源点,n是汇点。 每次的读入四个数:有向边的两个结点+容量+费用#include<bits/stdc++.h>using namespace std;inline i...

2018-07-21 09:54:12

bzoj1711 [Usaco2007 Open]Dingin吃饭 poj3281 Dining

题面Description 农夫JOHN为牛们做了很好的食品,但是牛吃饭很挑食. 每一头牛只喜欢吃一些食品和饮料而别的一概不吃.虽然他不一定能把所有牛喂饱,他还是想让尽可能多的牛吃到他们喜欢的食品和饮料. 农夫JOHN做了F(1<=F<=100)F(1<=F<=100)F (1 D(1<=D<=100)D(1<=D<=100)D (1 N(1&...

2018-07-14 13:59:32

奶牛的聚会(最大流)

题面题目描述 N(3<=N<=200)头奶牛要办一个新年晚会。每头牛都会烧几道菜。一共有D(5<=D<=100)道不同的菜肴。每道菜都可以用一个1到D之间的数来表示。 晚会的主办者希望能尽量多的菜肴被带到晚会,但是每道菜的数目又给出了限制。每头奶牛可以带K(1<=K<=5)道菜,但是必须是各不相同的(例如,一头牛不能带三块馅饼,但是可以带上一块馅饼,一份面...

2018-07-14 09:38:18

bzoj1693 Asteroids(二分图最小顶点覆盖)

题目大意n * n矩阵有K个点,第i个点的坐标为(Xi,Yi)。每次可以把某行或者某列删掉。问至少需要多少次可以把K个点都删掉。 (n≤500n≤500n\leq 500)题解每一行每一列都建点,然后对于每一个坐标(Xi.Yi)(Xi.Yi)(X_i.Y_i)都建一条从Xi到YiXi到YiX_i到Y_i容量为1的边。 然后就是二分图的最小顶点覆盖了。 可以证明最小顶点覆盖=最小割...

2018-07-13 20:15:35

POJ1149 养猪(最大流)

题面(来源于HLOJ)题目描述 尼克在一家养猪场工作,这家养猪场共有M间锁起来的猪舍,由于猪舍的钥匙都给了客户,所以尼克没有办法打开这些猪舍,客户们从早上开始一个接一个来购买生猪,他们到达后首先用手中的钥匙打开他所能打开的全部猪舍,然后从中选取他要买的生猪,尼克可以在此期间将打开的猪舍中的猪调整到其它开着的猪舍中,每个猪舍能存放的猪的数量是没有任何限制的。买完猪后客户会将他打开的猪舍关上。 ...

2018-07-13 16:02:36

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。