constbh-CSDN博客

原创【无标题】

LRU的实现#include<queue>#include<iostream>#include<list>#include<unordered_map>using namespace std;class LRUCache {public: list<pair<int,int> >que; unordered_map<int, list<pair<int,int> >::ite

2022-04-26 16:42:00 112

原创【无标题】

岛屿数量#include<iostream>using namespace std;class Solution {public: int vis[305][305]; void dfs(int i,int j,int l,int w,vector<vector<char>>& grid) { if (i<0||i>=l || j<0||j>=w) return ; if (vis[

2022-04-26 16:09:44 102

重新排列日志文件#include<iostream>#include<vector>#include<string>using namespace std;bool cmp(const string a,const string b) { int aNumberCount = 0; string tmpa = ""; string tmpb = ""; string titleA = ""; string titleB =

2022-04-26 15:59:35 155

原创 leetcode Median of Two Sorted Arrays python

对于两个已排序的数组，在o(n+m)的时间内就可以按序存储在一个大数组里面，这里学习python语法，记录代码．class Solution: def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int]

2018-02-01 19:08:21 295

原创 leetcode　Longest Substring Without Repeating Characters　python

学习ｐｙｔｈｏｎ语法，用ｐｙ写发尺取学习了ｐｔｈｏｎ中的ｍａｐ要注意特判空字符串class Solution: def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ dict = {}

2018-01-31 10:06:17 182

原创 codeforces913C(贪心)

退役了好久没写题，今天晚上睡不着写一发．这题仔细一想其实不难，按照每个位的性价比排序，然后安最便宜的枚举，然后假设比当前位低的位不用，只需要买这一位就行（二进制就这样，而且题目说可以比给定的值大），更新答案．一发ＡＣ　，中间因为变量定义出了问题，调了一会儿#include#includeusing namespace std;const int maxn = 35;typede

2018-01-21 23:49:04 359

原创 hdu4435(思维)

There are n cities in M^3's empire. M^3 owns a palace and a car and the palace resides in city 1. One day, she wants to travel around all the cities from her palace and finally back to her home. Howev

2017-11-28 11:07:52 235

原创 vijos1094(差分约束系统)

描述给出一有向图，图中每条边都被标上了关系运算符‘’,‘=’。现在要给图中每个顶点标上一个大于等于0,小于等于k的某个整数使所有边上的符号得到满足。若存在这样的k，则求最小的k，若任何k都无法满足则输出NO。例如下表中最小的k为2。结点1>结点2结点2>结点3结点2>结点4结点3=结点4如果存在这样的k，输出最小的k值；否则输出‘NO’。格式输入格式共二行，

2017-11-21 21:27:49 259

原创 codeforces892C

昨天晚上写这个题综测挂了，没有特判全是１的情况．/************************************************************************* > File Name: cf3.cpp > Author: > Mail: > Created Time: 2017年11月18日星期六 09时55分17秒 ***********

2017-11-18 10:12:04 402

原创 newcoder世界上最可爱的珂朵莉

题目描述我永远喜欢珂朵莉~！有两个长为n的序列a[i]与b[i] 你可以把任意不多于x个a序列中的数变成y 你可以把所有序列b中的数减去一个非负数t 你可以把a序列和b序列分别任意打乱要求对于1 满足a[i] >= b[i] 求t的最小值输入描述:第一行三个数n,x,y之后一行n个数表示a序列之后一行n个数表示b序列输出描述:一

2017-11-17 21:21:28 702

原创 newcoder猴子吃香蕉

题目描述有n只猴子，第i只猴子每过xi小时会连续吃香蕉yi小时。猴子从第二次开始每次休息结束后这只猴子连续吃香蕉的时间会增加zi小时。给定n只猴子，每一只的xi，yi，zi，以及时间t，求在前t小时中，所有猴子共吃了多少小时。对于一只猴子来说是这样的：从第1小时开始：休息xi小时( 1 -> xi ) 吃yi小时( xi + 1 -> xi + yi )

2017-11-17 21:18:32 442

原创 codeforces888E（折半二分）

把序列分为前一半和后一半，然后壮压得出两部分数字可以得到的所有和，存在两个vector里，然后枚举第一个vector中的数字，二分查找第二部分满足条件的最大值，然后更新最大值。#include#include#includeusing namespace std;typedef long long ll;vectorg1,g2;ll num[40],t[40];int main(

2017-11-12 20:21:36 405

原创热爱工作的蒜蒜（带限制最短路）

众所周知，蒜蒜是一名热爱工作的好员工，他觉得时间就是金钱，做事情总是争分夺秒。这天晚上，蒜蒜一个人去吃晚饭。不巧的是，吃完饭以后就开始下雨了，蒜蒜并没有带雨伞出来。但是蒜蒜热爱工作，工作使他快乐，他要尽快赶回去写代码。蒜蒜的公司在中关村，中关村这边地形复杂，有很多天桥、地下通道和马路交错在一起。其中，地下通道是可以避雨的，天桥和马路都没办法避。可以把中关村抽象成为 nnn 个点的地

2017-10-25 21:05:19 326

原创 uvalive5713(次小生成树)

先求出最小生成树，然后n^2枚举两个点，在两个点之间连一条边，就形成了一个环，然后求出两点间人数的和除以那个环在树上的边的最大边，更新最大值．求最大权值边可以用熟练剖分．复杂度n^2logn．#include #include #include #include#include using namespace std;#define Del(a,b) memset(a,b,size

2017-10-22 11:36:43 281

原创 vijos1412(第k优背包)

求第Ｋ优的背包．然后选前Ｋ大的价值求和/************************************************************************* > File Name: vijos1059.cpp > Author: > Mail: > Created Time: 2017年10月16日星期一 10时33分45秒 **********

2017-10-16 11:31:44 227

原创 vijos1843（货车运输）

每个货车可以运输的最大货物量就是起点到终点的某一条路径上的最小权值，为了使运输量最大，那就是选一条路使得这条路上的最小权值边最大。于是想到最大生成树，然后就是树上查询两点之间路径上的最小值，熟练剖分可以解。#include #include #include #include using namespace std;#define Del(a,b) memset(a,b,size

2017-10-14 19:43:28 328 1

原创 poj3867(2-sat)

题目大意：给了N个点和M条边，每个点的权值可以是0可以是1，M条边有一个边权和一个操作，问是否存在一个点权赋值方式，满足m条边的两个端点的权值通过该边的操作和该边的权值相等。挑战上经典的2-sat问题。列出一个真值表，看着建图就行了。#include#include#include#includeusing namespace std;con

2017-10-11 19:38:29 236

原创 hdu3622（二分&2-sat）

二分答案，若距离冲突（dist【i】【j】代码来自匡斌/*HDU 3622题意:给n对炸弹可以放置的位置(每个位置为一个二维平面上的点),每次放置炸弹是时只能选择这一对中的其中一个点,每个炸弹爆炸的范围半径都一样,控制爆炸的半径使得所有的爆炸范围都不相交(可以相切),求解这个最大半径. 首先二分最大半径值,然后2-sat构图判断其可行性,对于每两队位置(u,

2017-10-09 20:55:46 189

原创 codeforces730J（费用流）

每个人与源点连一条边，流量是1，费用为0.每个人与编程队那个点连一条边，流量是p，费用为-a[i];每个人与运动队那个点连一条边，流量是s，费用为-b[i];编程队与运动队向汇点连一条边，流量分别为，p，s。费用为0；最大值就是最小费用的取反。然后遍历边数组，流量不为0 的边并且起点是1-n的，终点是运动队就是运动队的人，是编程队就是编程队的人。#include#inc

2017-10-09 16:49:58 302

原创 codeforces 869E(哈希&二维树状数组)

把每个子矩阵哈希一下，增加操作就是树状数组加，删除就是减，然后判断连通时就是判断两个点的hash值是否相等。#include#include#include#includeusing namespace std;int n,m,q;long long tree[2505][2505];typedef pair P;map,long long>mp;int lowbit(int

2017-10-09 16:46:34 336

原创 poj3169(差分约束系统)

题目大意：一些母牛按序号排成一条直线。有两种要求，A和B距离不得超过X，还有一种是C和D距离不得少于Y，问可能的最大距离。如果没有输出-1，如果可以随便排输出-2，否则输出最大的距离。推出公式：b-a然后spfa#include#include#include#includeusing namespace std;int n;const int maxn = 1000+

2017-10-09 12:23:52 215

原创 poj1724(带限制的最短路)

题意：一个人要从1点到N点，有m条边可以走，走每条边要花一些钱，这个人只有k的钱，问花的钱不多于K且能到N的最短路。spfa解决最短路，不过dist数组要加一维，dist【i】【j】表示从1走到了i花了j钱的最短路。感觉这时候就是个bfs#include#include#include#includeusing namespace std;int n,k;struct no

2017-10-08 19:52:10 1677

原创 hdu5242(贪心&记忆化搜索)

先跑一遍dfs处理出每个点到跟能获得的最大值。然后按照这个值排序，按照这个顺序再去跑第二遍dfs算出这个点到跟的价值，用过的点直接返回0，把结果保存在数组里，再次排序，取前K个就是答案。#include#include#include#includeusing namespace std;const int maxn = 100000+10;vectorG[maxn];stru

2017-10-02 17:21:18 252

原创 hdu5543（01背包）

带限制条件的01背包dp【i】【k】表示i体积是放在漏出的金条的个数为k时获得的最大价值。#include#include#includeusing namespace std;typedef long long ll;const int maxn = 1000+10;int vo[maxn],va[maxn];ll dp[maxn*4][3];int main(){

2017-10-01 10:24:07 310

原创 hdu4283（区间DP）

dp[i][j]表示从第i个人到第j个人这段区间的最小花费（是只考虑这j-i+1个人，不需要考虑前面有多少人）那么对于dp[i][j]的第i个人，就有可能第1个上场，也可以第j-i+1个上场。考虑第K个上场,即在i+1之后的K-1个人是率先上场的，那么就出现了一个子问题 dp[i+1][i+k-1]表示在第i个人之前上场的,对于第i个人，由于是第k个上场的，那么屌丝值便是a[i]*(k-1),其余

2017-09-29 19:15:14 223

原创 hdu3530（单调队列）

题意：有整数的序列。您的任务是找到满足以下条件的最长子序列：子序列的最大元素与最小元素之间的差值不小于m且不大于k。维护两个单调队列，一个最大，一个最小，然后根据两个队列队首元素的差值剔除队首元素。然后更新最大长度。答案的初始值要为0，为1则wa，因为当一个元素时，最大，最小都是他，有可能不满足大于M的情况。#include#include#includeusing

2017-09-28 22:08:17 424

原创 hdu（HDU5945）单调队列优化DP

#include#include#includeusing namespace std;const int maxn = 1000000+10;int dp[maxn];int q[maxn];int main(){ int cases,x,k,t; scanf("%d",&cases); while(cases--) { memse

2017-09-27 16:27:58 260

原创 hdu 2844(多重背包)

题意：一个人有一些硬币，给定了硬币的价值和数量，问他能组成多少种和。明显的多重背包 #include #include using namespace std; int d[100000+10],n,m; int w[105],c[105]; int vis[100000+10]; void zeroonepack(int w,i

2017-09-22 17:30:09 187

原创 lightoj1348（树链剖分&线段树）

常规树链剖分题，把点权哈希到数组中，用线段树维护。#include#include#includeusing namespace std;const int N = 30000+10;int dep[N],siz[N],fa[N],id[N],son[N],val[N],top[N],num;vectorv[N];void dfs1(int u, int f, int d) {

2017-09-22 15:28:47 265

原创 spoj371（费用流）

一个比较直观的想法是每个盒子 i 作为一个点。若 Ai > 1 则连边(s, i, Ai-1, 0)；若Ai = 0 则连边(i, t, 1, 0)。对任意两个盒子 i, j，若 Ai > 1 并且 Aj = 0，连边(i, j, ∞, min(|i - j|, n - |i - j|))。求一次最小费用流即为结果。但是这样构图复杂度会很高，边数会达到 O(N^2)，不够聪明。更加简洁

2017-09-22 11:46:30 203

原创 Hoj2739

【题目大意】带权有向图上的中国邮路问题：一名邮递员需要经过每条有向边至少一次，最后回到出发点，一条边多次经过权值要累加，问最小总权值是多少。（2 1 【建模方法】若原图的基图不连通，或者存在某个点的入度或出度为 0 则无解。统计所有点的入度出度之差 Di，对于 Di > 0 的点，加边(s, i, Di, 0)；对于 Di 0)；对原图中的每条边(i, j)，在网络中加

2017-09-21 16:43:19 291

原创 poj3680(费用流)

经典构图题。先将所有区间端点离散化到整数 1..M，另加源 s=0，汇 t=M+1；对每个点 i (0 ai’, bi’分别表示 ai, bi 离散化后对应的数值。求一次最小费用流再取反即为结果#include#include#include#includeusing namespace std;#define INF 0x3f3f3f3fconst int maxn

2017-09-21 16:42:13 288

原创 poj1815(最小割点集)

【题目大意】现代社会人们都靠电话通信。A 与 B 能通信当且仅当 A 知道 B 的电话号或者 A知道 C 的电话号且 C 与 B 能通信。若 A 知道 B 的电话号，那么 B 也知道 A 的电话号。然而不好的事情总是会发生在某些人身上，比如他的电话本丢了，同时他又换了电话号，导致他跟所有人失去了联系。现在给定 N 个人之间的通信关系以及特定的两个人 S 和 T，问最少几个人发生

2017-09-19 23:30:57 814

原创 BZOJ1036

树链剖分的板子题，初学先存一波板子，代码来自点击打开，感谢。#include #include #include #include using namespace std;const int N = 30005;int dep[N], fa[N], son[N], sz[N], top[N], id[N], idx, val[N];int first[N], nexts[N

2017-09-18 21:25:44 324

原创 918知道了几个新的概念

最小支配集：对于图G=（V，E）来说，最小支配集指的是从V中尽量取少的点组成一个集合，使得V中剩余的点都与取出来的点有边相连。设V1是图G的一个支配集，则对于图中的任意一个顶点u，要么属于集合V1，要么与V1中的点相邻。在V1中去除任何一个元素后V1不在是支配集，则V是图G的最小支配集。最小点覆盖：对于图G=（V，E）来说，最小点覆盖指的是从V中取尽量少的点组成一个集合，使得E中所有边

2017-09-18 16:36:55 374

原创 hoj2713（最小点权覆盖）

经典的最大点权独立集问题。转化为最小点权覆盖集：先将网格黑白染色，从源点到每个黑点有一条边，从每个白点到汇点有一条边，容量均为相应宝石的价值。每个黑点向与其相邻的四个白点连边，容量为∞。设最小割为 ans，结果即为∑Cij – ans#include#include#includeusing namespace std;typedef int cap_type;#de

2017-09-18 16:34:41 471

原创 hdu3887（dfs序）

问你对于每个节点，它的子树上标号比它小的点有多少个子树的问题，dfs序可以很轻松的解决，因为点在它的子树上，所以在线段树中，必定在它的两个时间戳的区间之间，所以我们只需要从小到大考虑，它的区间里有多少个点已经放了，然后再把它放进去。很容易的解决了#include#include#includeusing namespace std;const int maxn = 10000

2017-09-15 10:48:00 436

原创 SGU326(最大流)

同样，所有和球队 1 相关的比赛全让球队 1 赢，如果此时仍有某支球队胜利的场数大于球队 1，则已经不可能满足要求。按如下方法建图：所有小组内的比赛 i（不包括与球队 1 相关的比赛）作为一个点并加边(s, i, num[i])，每支球队（不包括球队 1）作为一个点并加边(j, t, wins[1]-wins[i])，每场比赛向与其关联的两支球队 u, v 连边(i, u, ∞),

2017-09-13 17:14:33 404

原创 poj3281（最大流）

【建模方法】此题的建模方法比较有开创性。以往一般都是左边一个点集表示供应并与源相连，右边一个点集表示需求并与汇相连。现在不同了，供应有两种资源，需求仍只有一个群体，怎么办？其实只要仔细思考一下最大流的建模原理，此题的构图也不是那么难想。最大流的正确性依赖于它的每一条 s-t 流都与一种实际方案一一对应。那么此题也需要用 s-t 流将一头牛和它喜欢的食物和饮料“串”起来，而食

2017-09-13 11:35:42 305

原创 hdu6201(无向图最长路)

设置一个虚拟起点和虚拟终点，每个点与起点间一条负边，值为这个点书的价值的相反数（代表买书花钱），每个点与终点连一条正边，值为这个点的书的价格（代表卖书赚钱）。然后按照图中给的边建无向边，权值为负（代表路费）。然后就是跑最长路，spfa改一下松弛条件就行#include#include#include#includeusing namespace std;const int maxn

2017-09-12 21:26:14 2262 1

MFC程序设计-画图板

空空如也