2 SpongeBob_Y

尚未进行身份认证

暂无相关简介

等级
TA的排名 5w+

HDU - 6252 Subway Chasing (差分约束)

题目链接题意:现在有两个人,其中一个人比另外一个人先走x分钟,然后两个人在途中不停的聊天,要是两个人报的点一样说明该人正好在那个点,要是不一样,则在两个点中间,现在要让你求两个站之间的长度(只要满足题意就好了)。题解:这是一道差分约束的题,首先根据两个人给出点的顺序来确定一系列的不等式,再根据不等式建边,最后跑最短路。本题可以分成三种情况。情况一: a==b && ...

2019-10-24 12:01:35

CSU1808 地铁 (最短路,好题)

题目链接题意:中文题不解释了。题解:因为再转车的过程中要另外的时间,所以我们平时那种以顶点为对象的最短路算法在这道题上面已经不适用了,在这个题当中我们要以边作为研究对象,但是用数组肯定存不下边的所有信息,这时候我们可以用链式向前星方法来存图,然后每个边都有一个对应的数字,然后以边为对象算最短路,细节看代码。#include <iostream>#include<c...

2019-10-10 15:19:33

Gym - 101667 E How Many to Be Happy?(最小割)

题目链接题意:给一个连通无向图,对于图中的每条边,这条边可能在某一颗最小生成树上,如果在称为happy的边,否则称为unhappy的边。对于unhappy的边,总是可以删掉一些边使得它变成happy的边,设h(e)为使e变成happy最少需要删的边数,定义happy边的h值为0,让你求所有边的h值之和。题解:我们知道要是一个边没有在最小生成树里面,能对他造成影响的只有边权比它小的边(在构成...

2019-10-08 09:36:35

CodeForces - 343D Water Tree (DFS序+线段树)

题目链接题意:现在有一棵以1为根节点的树,每个节点有一个水池,现在有三种操作。操作一:将v节点灌满水,然后他的所有子节点也将灌满水。操作二:将v节点的水抽干,然后他的所有父节点的水也将被抽干。操作三:查询某一个节点是否有水。题解:这个题看数据肯定暴力不可行,现在我们先DFS序将树结构转化成线性结构,然后对子节点的操作就直接转化成了线段树的区间操作,现在灌满水的操作已经解决了。但...

2019-10-06 11:53:52

2018 CCPC-Final 2018 I. Cockroaches(技巧题)

题目链接题意:现在有n只虫,每只虫的位置都用一个横竖坐标表示,现在有一种杀虫剂,这种杀虫剂投放到某一点,能将所在行和列的所有虫杀死,现在让求出只投放一次杀虫剂,最多能杀多少只虫和在满足杀最多只虫的情况下,有多少种方式能杀这么多只虫。题解:因为没有给定这个坐标系到底有多大,所以肯定不能暴力枚举,首先我们考虑虫都在一行或一列的情况,肯定只有一种情况,杀n只虫,还有就是每行每列都只有一只(例如对...

2019-09-24 14:43:25

Codeforces Round #583 (Div. 1 + Div. 2) D. Treasure Island(DFS)

题目链接题意:现在有一个n*m的图,起点(1,1),终点(n,m),里面有些点能走,一些点是障碍物,现在让你把一些能走的点变成障碍物,现在让你变最少的点,使起点和终点不连通。题解:这个题最多变两个点(跟起点连接的两个点),现在我们就要考虑变更少的点的情况。现在我们直接暴力dfs,我们把走过的点全部变成障碍物,要是找到一条走到终点的路(找不到输出0),又从起点开始找,要是还能找到一条路到终点...

2019-09-12 16:02:41

Educational Codeforces Round 72 D. Coloring Edges(拓扑判环)

题目链接题意:现在有n个点,m条有向边,现在要对这m条有向边染色,染色的要求是在一个环里面的边的颜色不能相同,现在让你求出最少要几种颜色,才能满足条件的染色。题解:首先很显然要是这个图里面连环都没有,肯定每条边都染1就行了。现在就是处理这个图里面有环的情况,要是图里面有环(题中说明没有自环),每条有向边的两个端点肯定是一个大一个小,所以要是有环的话,肯定满足有一些有向边是编号小的指向编号大...

2019-09-07 22:27:32

Codeforces Round #582 (Div. 3) G. Path Queries(树上分块)

题目链接题意:给出一棵树,n个节点,n-1条边,每条边有自己的权值,现在有m次询问,每次询问给出一个值,现在要求出有多少对(u,v)节点(u,v节点满足之间的简单路径中的边权最大值不超过给定询问值)。题解:首先这个题我们可以先将询问离线,我们先将树上的边权按从小到大排序,排序了过后我们就能够保证当前加入的边权一定是在已加入的边权中最大的。然后我们用并查集来合并,每次合并我们将加入这条边的贡...

2019-09-03 19:30:26

Comet OJ - Contest #9 & X Round 3 【XR-3】核心城市(树的直径,树的中心)

题目链接题意:就是在一棵树里面找一个k个节点的联通块,使不在联通块里的节点到联通块里节点的最大距离最小,这里有一道基本一样的题,但是题意写的比较清楚可以先看看Power oj 2853 小Z的糖果店。题解:这个题首先要求给出树的中心(树的直径上的中间那个点)。为什么要求这个点呢?因为这个点到其他叶子结点(离它距离最远的节点)的距离较为平均,这样就尽量使每个点到这个点的距离尽量的小,这就满足...

2019-08-27 17:12:05

ACM 数论入门题(附代码解释)

目录51Nod-1119机器人走方格V2(费马小定理)HDU2710MaxFactor(素数筛选)POJ2142TheBalance(扩展欧几里得)POJ1061青蛙的约会(扩展欧几里得)洛谷P1069细胞分裂(质数分解)HDU2866SpecialPrime(数论)HDU1573X问题(中国剩余定理非互质情况)HDU60...

2019-08-21 22:53:33

Codeforces Round #580 (Div. 2) D. Shortest Cycle(Floyd找最小环或DFS)

题目链接题解:现在有n个数,要是a[i]&a[j](i≠j)不等于0的话i跟j之间有一条边,现在让你求出这n个点里面的最小环,要是没有最小环则输出-1。题解:首先我们明白&操作是在二进制下,某一个都是1,&操作该位才是1,现在我们就提前处理出来,0-64位每位都多少有在该位是1,要是有3个数在某一位都是1,那不用说这三个数肯定是构成环了,直接输出3。否则我们直接Fl...

2019-08-20 21:10:33

Comet OJ - Contest #8 D 菜菜种菜(树状数组)

题目链接题意:现在有n个点,编号1-n,每个点都有自己的权值。现在有一些单向边。现在给出询问区间,需要求出满足在该区间内没有点能够直接到达该点的点的权值和(可能有点绕,但是中文题目问题应该不大)。题解:比赛时自己写的莫队,一直过不了,之前自己还做过类似的题,这里有一道这个题的低版型可以先看看传送门。好了,说下这道题应该怎么搞吧。首先我们要清楚,要是该点在询问区间内有点能够直接到达,说明这个...

2019-08-20 20:34:04

ACM 图论入门题(附代码解释)

目录HDU 1869 六度分离HDU 1874 畅通工程续 (最短路)HDU 3339 In Action (最短路+01背包)HDU 1162 Eddy's picture(prime算法)HDU 1863 畅通工程 (最小生成树)HDU 1301 Jungle Roads (最小生成树)POJ 3522 Slim Span (最小生成树)HDU 1102 Co...

2019-08-16 22:50:35

ACM 线段树,树状数组入门题(附代码解释)

如果是初学者建议先看看这篇博客,写的很不错传送门目录HDU 1166 敌兵布阵(线段树)HDU 1698 Just a Hook(线段树)POJ 3468 A Simple Problem with Integers(线段树区间修改+求和)HDU 1540 Tunnel Warfare(最长连续区间+单点修改)洛谷 P3372 【模板】线段树 1洛谷 P3373 【模板...

2019-08-15 23:00:50

ACM DP入门题(附代码解释)

目录HDU1171BigEventinHDU(多重背包)HDU1224FreeDIYTourHDU1421搬寝室HDU1069MonkeyandBanana(DAG模型)HDU1506LargestRectangleinaHistogramHDU1257最少拦截系统(最长上升子序列)HDU1505CityGameHD...

2019-08-15 22:33:16

洛谷 P3980 [NOI2008]志愿者招募(网络流-费用流)

题目链接题意:中文题不说了。题解:这个题建边非常巧妙,1连源点,n+1连汇点。然后每点之间都连一条流量为inf-a[i],费用为0的边。然后雇佣的人起点为u,终点为v,费用为val,就连一条u到v+1,流量inf(因为可以雇佣任意多的人),费用为val的边。现在说说为啥这样建边是对的。现在我们从源点流到汇点一条流表示要雇佣一个人,所以至少要雇工作人数最多那天的人数 ,但是现在有些天并...

2019-08-15 11:34:07

字典树,01字典树,可持续化01字典树(总结+例题)

目录字典树01字典树 字典树例题:power oj 2390: 查单词HDU 1671 Phone ListHDU 1004Let the Balloon RiseHDU 1075 What Are You Talking About HDU 4287 Intelligent IME HDU 1247 Hat’s W...

2019-08-11 23:22:19

ACM递推求解入门题(附代码解释)

目录HDU2048 神、上帝以及老天爷(错排公式)HDU2047 阿牛的EOF牛肉串HDU2045 不容易系列之(3)—— LELE的RPG难题HDU2563 统计问题HDU2046 骨牌铺方格HDU 2050 折线分割平面HDU 2709 SumsetsHDU 1098 Ignatius's puzzleHDU2048 神、上帝以及老天爷(错排公式)题解...

2019-08-11 12:13:21

ACM BFS,DFS入门题(附代码解释)

目录HDU 1312 Red and Black(BFS)HDU1372 Knight Moves(BFS)HDU2717 Catch That Cow(BFS)HDU 1241 Oil Deposits(DFS)HDU - 1181 变形课(DFS)HDU 1312 Red and Black(BFS)题意:从‘@’点出发,问能到达的最多的点有多少,‘#’不可经过...

2019-08-11 12:12:44

莫队,带修莫队(总结+例题)

学习了莫队,感觉这个算法是一个很玄学的的算法,分块的大小和排序方式就能决定这个算法的效率,现在就对莫队,和带修莫队做一个简单的总结。适用环境: 莫队算法使用分块的思想,可以解决一类离线区间询问问题,在使用莫队算法的时候就需要将区间询问离线(在线也可以,但是那样复杂度很高,就没有必要使用这个算法了)。算法核心: 莫队算法离线首先是按左端点分块,然后在同一个块当中区间右端点要递增(...

2019-07-28 22:06:50

查看更多

勋章 我的勋章
  • GitHub
    GitHub
    绑定GitHub第三方账户获取
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。