- 博客(118)
- 收藏
- 关注
RSS订阅原创 HDU - 6252 Subway Chasing （差分约束）
题目链接题意：现在有两个人，其中一个人比另外一个人先走x分钟，然后两个人在途中不停的聊天，要是两个人报的点一样说明该人正好在那个点，要是不一样，则在两个点中间，现在要让你求两个站之间的长度（只要满足题意就好了）。题解：这是一道差分约束的题，首先根据两个人给出点的顺序来确定一系列的不等式，再根据不等式建边，最后跑最短路。本题可以分成三种情况。情况一： a==b && ...
2019-10-24 12:11:19
290
原创 CSU1808 地铁 （最短路，好题）
题目链接题意：中文题不解释了。题解：因为再转车的过程中要另外的时间，所以我们平时那种以顶点为对象的最短路算法在这道题上面已经不适用了，在这个题当中我们要以边作为研究对象，但是用数组肯定存不下边的所有信息，这时候我们可以用链式向前星方法来存图，然后每个边都有一个对应的数字，然后以边为对象算最短路，细节看代码。#include <iostream>#include<c...
2019-10-10 15:19:33
312
原创 Gym - 101667 E How Many to Be Happy?（最小割）
题目链接题意：给一个连通无向图，对于图中的每条边，这条边可能在某一颗最小生成树上，如果在称为happy的边，否则称为unhappy的边。对于unhappy的边，总是可以删掉一些边使得它变成happy的边，设h(e)为使e变成happy最少需要删的边数，定义happy边的h值为0，让你求所有边的h值之和。题解：我们知道要是一个边没有在最小生成树里面，能对他造成影响的只有边权比它小的边（在构成...
2019-10-08 09:51:10
348
原创 CodeForces - 343D Water Tree （DFS序+线段树）
题目链接题意：现在有一棵以1为根节点的树，每个节点有一个水池，现在有三种操作。操作一：将v节点灌满水，然后他的所有子节点也将灌满水。操作二：将v节点的水抽干，然后他的所有父节点的水也将被抽干。操作三：查询某一个节点是否有水。题解：这个题看数据肯定暴力不可行，现在我们先DFS序将树结构转化成线性结构，然后对子节点的操作就直接转化成了线段树的区间操作，现在灌满水的操作已经解决了。但...
2019-10-06 12:03:25
156
原创 2018 CCPC-Final 2018 I. Cockroaches（技巧题）
题目链接题意：现在有n只虫，每只虫的位置都用一个横竖坐标表示，现在有一种杀虫剂，这种杀虫剂投放到某一点，能将所在行和列的所有虫杀死，现在让求出只投放一次杀虫剂，最多能杀多少只虫和在满足杀最多只虫的情况下，有多少种方式能杀这么多只虫。题解：因为没有给定这个坐标系到底有多大，所以肯定不能暴力枚举，首先我们考虑虫都在一行或一列的情况，肯定只有一种情况，杀n只虫，还有就是每行每列都只有一只（例如对...
2019-09-24 14:59:18
1025
1
原创 Codeforces Round #583 (Div. 1 + Div. 2) D. Treasure Island（DFS）
题目链接题意：现在有一个n*m的图，起点（1,1），终点（n,m），里面有些点能走，一些点是障碍物，现在让你把一些能走的点变成障碍物，现在让你变最少的点，使起点和终点不连通。题解：这个题最多变两个点（跟起点连接的两个点），现在我们就要考虑变更少的点的情况。现在我们直接暴力dfs，我们把走过的点全部变成障碍物，要是找到一条走到终点的路（找不到输出0），又从起点开始找，要是还能找到一条路到终点...
2019-09-12 16:09:09
143
原创 Educational Codeforces Round 72 D. Coloring Edges（拓扑判环）
题目链接题意：现在有n个点，m条有向边，现在要对这m条有向边染色，染色的要求是在一个环里面的边的颜色不能相同，现在让你求出最少要几种颜色，才能满足条件的染色。题解：首先很显然要是这个图里面连环都没有，肯定每条边都染1就行了。现在就是处理这个图里面有环的情况，要是图里面有环（题中说明没有自环），每条有向边的两个端点肯定是一个大一个小，所以要是有环的话，肯定满足有一些有向边是编号小的指向编号大...
2019-09-07 22:33:25
179
原创 Codeforces Round #582 (Div. 3) G. Path Queries（树上分块）
题目链接题意：给出一棵树，n个节点，n-1条边，每条边有自己的权值，现在有m次询问，每次询问给出一个值，现在要求出有多少对(u,v)节点（u,v节点满足之间的简单路径中的边权最大值不超过给定询问值）。题解：首先这个题我们可以先将询问离线，我们先将树上的边权按从小到大排序，排序了过后我们就能够保证当前加入的边权一定是在已加入的边权中最大的。然后我们用并查集来合并，每次合并我们将加入这条边的贡...
2019-09-03 19:30:26
357
原创 Comet OJ - Contest #9 & X Round 3 【XR-3】核心城市(树的直径，树的中心)
题目链接题意：就是在一棵树里面找一个k个节点的联通块，使不在联通块里的节点到联通块里节点的最大距离最小，这里有一道基本一样的题，但是题意写的比较清楚可以先看看Power oj 2853 小Z的糖果店。题解：这个题首先要求给出树的中心（树的直径上的中间那个点）。为什么要求这个点呢？因为这个点到其他叶子结点（离它距离最远的节点）的距离较为平均，这样就尽量使每个点到这个点的距离尽量的小，这就满足...
2019-08-27 17:12:05
187
原创 ACM 数论入门题（附代码解释）
目录51Nod - 1119 机器人走方格 V2 （费马小定理）HDU 2710 Max Factor （素数筛选）POJ2142 The Balance （扩展欧几里得）POJ 1061 青蛙的约会（扩展欧几里得）洛谷 P1069 细胞分裂（质数分解）HDU2866 Special Prime （数论）HDU 1573 X问题(中国剩余定理非互质情况)HDU 60...
2019-08-21 22:53:33
1937
原创 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
237
2
原创 Comet OJ - Contest #8 D 菜菜种菜（树状数组）
题目链接题意：现在有n个点，编号1-n，每个点都有自己的权值。现在有一些单向边。现在给出询问区间，需要求出满足在该区间内没有点能够直接到达该点的点的权值和（可能有点绕，但是中文题目问题应该不大）。题解：比赛时自己写的莫队，一直过不了，之前自己还做过类似的题，这里有一道这个题的低版型可以先看看传送门。好了，说下这道题应该怎么搞吧。首先我们要清楚，要是该点在询问区间内有点能够直接到达，说明这个...
2019-08-20 20:34:04
159
原创 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
1252
原创 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
397
原创 ACM DP入门题（附代码解释）
目录HDU 1171 Big Event in HDU（多重背包）HDU 1224 Free DIY TourHDU 1421 搬寝室HDU1069 Monkey and Banana（DAG模型）HDU1506 Largest Rectangle in a HistogramHDU 1257 最少拦截系统 （最长上升子序列）HDU 1505 City GameHD...
2019-08-15 22:33:16
1902
原创 洛谷 P3980 [NOI2008]志愿者招募（网络流-费用流）
题目链接题意：中文题不说了。题解：这个题建边非常巧妙，1连源点，n+1连汇点。然后每点之间都连一条流量为inf-a[i]，费用为0的边。然后雇佣的人起点为u，终点为v，费用为val，就连一条u到v+1，流量inf（因为可以雇佣任意多的人），费用为val的边。现在说说为啥这样建边是对的。现在我们从源点流到汇点一条流表示要雇佣一个人，所以至少要雇工作人数最多那天的人数 ，但是现在有些天并...
2019-08-15 11:34:07
208
原创 字典树，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
1681
1
原创 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
288
原创 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
596
原创 莫队，带修莫队（总结+例题）
学习了莫队，感觉这个算法是一个很玄学的的算法，分块的大小和排序方式就能决定这个算法的效率，现在就对莫队，和带修莫队做一个简单的总结。适用环境： 莫队算法使用分块的思想，可以解决一类离线区间询问问题，在使用莫队算法的时候就需要将区间询问离线（在线也可以，但是那样复杂度很高，就没有必要使用这个算法了）。算法核心： 莫队算法离线首先是按左端点分块，然后在同一个块当中区间右端点要递增（...
2019-07-28 22:06:50
1079
1
原创 HDU - 3874 Necklace（树状数组+贪心）
题目链接题意：现在有n个数，编号1-n，现在给出m次询问，每次给出一个区间[l,r]。问你该区间内数的和是多少，但是相同的数只能算一次。题解：现在我们困难的是区间内相同的数怎么只算一次，这个就可以用到贪心了，将每次询问离线，然后按询问的右区间从小到大排序。然后我们就用树状数组来维护了，因为我们是按照右区间从小到大排序的，所以我们就每次相同的，只计算最靠右的，如果在前面出现过，就先减去前面就...
2019-07-25 15:13:24
141
原创 HDU 6579 Operation（2019杭电多校第一场-线性基）
题目链接题意：现在有两种操作：操作一：输入0 l,r：表示在数组l，r区间中找出任意个数，使这些数的异或和最大。操作二：输入1 x，表示在数组末尾插入一个数x。题解：这个题用01字典树做不了，只能用线性基做。对于每个线性基，将出现位置靠右的数字尽可能地放在高位，也就是说在插入新数字的时候，要同时记录对应位置上数字的出现位置，并且在找到可以插入的位置的时候，如果新数字比位置上原来...
2019-07-23 17:06:07
444
原创 树上任意两点（距离，权值等）之和相关问题
吉首大学2019年程序设计竞赛- 滑稽树下你和我题意：给出一棵树，树上每条边给出一个权值，现在要求（distance(i,j)表示i到j节点的距离）。题解：这种题肯定不能是暴力，现在我们就可以看每条边最终要被计算多少次，这样我们只需要我们只需要更新边的贡献值就行了，看下图。现在我们来计算(u,v)之间的边的贡献值，现加入v为u的子节点（建双向边，任一点都可以为根节点，现在就假...
2019-07-15 20:39:51
2790
原创 HDU - 3887 Counting Offspring（DFS序+主席树）
题目链接You are given a tree, it’s root is p, and the node is numbered from 1 to n. Now define f(i) as the number of nodes whose number is less than i in all the succeeding nodes of node i. Now we need ...
2019-06-06 15:41:28
196
8
原创 HDU - 5692 Snacks（DFS序+线段树）
题目链接百度科技园内有nn个零食机，零食机之间通过n−1n−1条路相互连通。每个零食机都有一个值vv，表示为小度熊提供零食的价值。由于零食被频繁的消耗和补充，零食机的价值vv会时常发生变化。小度熊只能从编号为0的零食机出发，并且每个零食机至多经过一次。另外，小度熊会对某个零食机的零食有所偏爱，要求路线上必须有那个零食机。为小度熊规划一个路线，使得路线上的价值总和最大。Input...
2019-06-06 14:50:48
236
原创 SPOJ - COT Count on a tree （主席树）
题目链接You are given a tree withNnodes. The tree nodes are numbered from1toN. Each node has an integer weight.We will ask you to perform the following operation:u v k: ask for the kth minimum...
2019-05-29 20:16:48
163
原创 Codeforces Round #562 (Div. 2)（A,B,C题解）
题目链接A Circle Metro题意：现在有1-n个车站，有两个平行的轨道，一个轨道的列车是按车站的升序跑（1->n），另一个轨道是按降序跑（n->1）。现在有两个人，现在两个人分别乘两个轨道的列车，给出两个人的乘车起点和终点，问两个人中途是否能在同一个车站相遇，若列车跑到1或n还没有到两个人的终点，则又从1或n开始跑，直到到两个人的终点。题解：首先判断两个人的起点和终...
2019-05-28 12:54:54
178
原创 HDU - 4419 Colourful Rectangle （扫描线）
题目链接We use Red, Green and Blue to make new colours. See the picture below:Now give you n rectangles, the colour of them is red or green or blue. You have calculate the area of 7 different colo...
2019-05-15 20:45:13
160
原创 POJ - 2482 Stars in Your Window （扫描线）
题目链接Fleeting time does not blur my memory of you. Can it really be 4 years since I first saw you? I still remember, vividly, on the beautiful Zhuhai Campus, 4 years ago, from the moment I saw you s...
2019-05-13 10:31:19
227
原创 HDU 4578 Transformation（线段树+有技巧的懒标记下放）
题目链接Yuanfang is puzzled with the question below:There are n integers, a1, a2, …, an. The initial values of them are 0. There are four kinds of operations.Operation 1: Add c to each number bet...
2019-05-07 19:27:50
212
原创 HDU 4614 Vases and Flowers（线段树）
题目链接Alice is so popular that she can receive many flowers everyday. She has N vases numbered from 0 to N-1. When she receive some flowers, she will try to put them in the vases, one flower in one va...
2019-05-06 23:17:26
162
原创 线段树维护(最大区间和，最大子段和，最长连续上升子序列）
本文主要介绍用线段树来维护(最大区间和，最大子段和，最长连续上升子序列）的问题。HDU 1540 Tunnel Warfare（最长连续区间+单点修改）洛谷 P2894 [USACO08FEB]酒店Hotel（最长连续区间+区间修改）吉首大学2019年程序设计竞赛-白山茶与红玫瑰（最长连续区间+区间修改）SPOJ - GSS1 Can you answer these querie...
2019-05-02 02:50:09
1679
原创 POJ 3728 The merchant（倍增LCA）
题目链接DescriptionThere areNcities in a country, and there is one and only one simple path between each pair of cities. A merchant has chosen some paths and wants to earn as much money as possible ...
2019-04-24 15:19:34
167
原创 南华大学第十五届ACM程序设计竞赛(重现赛）E 免费机票（单边最短路）
题目链接题目描述 某华大学小飞中奖了！！！奖品是一张免费飞机票，唯一遗憾的是，这张飞机票有限定区间，需要从k个区间中选择其一。小飞打算高高兴兴的出去玩啦，但是，从s地出发，去往e地，可能没有直达的飞机票，可能需要转机（所有飞机线路都是无向的），小飞毕竟是个学生党，出去玩首先得考虑省钱，所以，小飞遇到麻烦了，请帮小飞计算最便宜的一条路线，小飞会很感激你的。输入描述:第...
2019-04-20 23:34:19
192
原创 POWER OJ 2812 Island（2018四川ACM：树的重心）
题目链接DescriptionRinne dreads sunlight, so she wants to find a refuge with the weakest sunlight. The place where Rinne stay now can be described as a tree with nn vertices. A tree is an undirected ...
2019-04-12 18:09:04
208
原创 Power oj 2837: 剑道万古如长夜（单调队列优化DP）
题目链接Description李淳罡正在和别人战斗，他一共有 NN 把宝剑，选择每把宝剑都要付出一定的代价。为了能够顺利的战胜敌人，在连续 MM 把宝剑中至少要有一把宝剑要被选择。请计算总共最少花费多少代价，李淳罡才能顺利的战胜敌人Input第一行一个整数 TT (T≤10)(T≤10) ，表示测试数据组数，对于每组测试 :第二行：两个整数 NN (1≤N≤2⋅106)(1≤...
2019-03-29 15:25:04
196
原创 蓝桥杯-发现环（并查集+DFS）
题目链接问题描述 小明的实验室有N台电脑，编号1~N。原本这N台电脑之间有N-1条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。 不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了BUG。 为了恢复正常传输。小明需要找到所...
2019-03-16 17:29:16
843
原创 codeforces #271D Good Substrings（hash）
题目链接You've got strings, consisting of small English letters. Some of the English letters aregood, the rest arebad.A substrings[l...r](1 ≤ l ≤ r ≤ |s|) of strings = s1s2...s|s|(where|s|i...
2019-03-10 11:26:30
462
原创 CodeForces - 633C Spy Syndrome 2—好题（hash或字典树）
题目链接After observing the results of Spy Syndrome, Yash realised the errors of his ways. He now believes that a super spy such as Siddhant can't use a cipher as basic and ancient as Caesar cipher. Aft...
2019-03-07 21:13:18
285
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人