请_坚持思考-CSDN博客

原创 Codeforces Round #402 (Div. 2) C:Dishonest Sellers

Codeforces Round #402 (Div. 2) C:Dishonest Sellers #include #include #include #include #include #include using namespace std;#define MAXN 200010static int N,K,ans,A[MAXN],B[MAXN];int main

2017-02-26 20:00:50 324

原创 Codeforces Round #401 (Div. 2)C. Alyona and Spreadsheet

Codeforces Round #401 (Div. 2)C. Alyona and Spreadsheet看代码一种新的思想 dp 以每行#includeusing namespace std;const int MAXN=100010;int n,m,a[MAXN],last[MAXN],h[MAXN],k;int main(){ scanf("%d%d"

2017-02-24 20:41:30 225

原创 hdu1281+坐标构图+二分匹配

hdu1281+坐标构图+二分匹配这道题主要就是构图思想之前的A题也是一样的但是没想明白为什么这样构图是正确的虽然说现在也没真正想清楚但是也能够进一步理解解题思路是以x 和 y轴建立二分图 x和y分别代表两个集合如果一个点可以放车那么x,y连一条边因为是坐标的垂直方向和水平方向不能有车所以这个坐标x，y连一条边，这样就可以排除车相互攻击的可能性代表可以放东西

2017-02-24 17:06:38 301

原创 poj1236 有线图的强连通分量 tarjan算法判断

poj1236 有线图的强连通分量 tarjan算法判断/*/*总结：这道题开始做的时候思路是正确的，但是我是把它当成无线图处理了但是这道题是有向图，有向图的连通判断是tarjan算法和kosaraju算法判断几个强连通分量无向图就是判断判断是否连通，一般有两种方法判断无向图1；并查集2；搜索，bfs,dfs；这道题判断强连通分量，然后是缩点，将一个强连通分量变成一个点，那么就变

2017-02-17 18:08:54 401

原创 hdu 4009 小树形图

hdu 4009 小树形图这道题用到图论的一些思维方法那就是增加超级源点超级源点到其他所有点的权值是其他点打井的花费这样的话就很好表示哪一户打井如果打井就选择相应边进行了做题时的错误：1；以为打井的深度是任意深度的其实是固定的c 原文的误解让这道题增加了难度2；写代码时总是忘记变量的匹配了函数返回值的匹配还有就是n值忘记改导致run time erro

2017-02-10 18:02:20 284

原创次小生成树 poj1679

次小生成树 poj1679遇到一道需要思考的题，所以把他写下来，见代码注释#include#include#include//什么是最小生成树？简单说就是第二小的树，这个第二小不一定是总权值第二小，也可能和MST一样的#include//题目：判断最小生成树是否唯一 #include //开始的时候用的另一种枚举但是有个细节没处理掉就错了 #include//最小生成树运用

2017-02-04 22:42:53 232

原创 Beaver's Calculator coderforces 70A1 蓝桥杯

Beaver's Calculator coderforces 70A1 这道题贪心思路简单但是方法对于我来说比较巧了题解看源码#include#includeusing namespace std;struct type{long x,y,z;}p[300000];bool cmp(type x,type y){ if (x.x==y.x) ret

2017-02-02 21:02:50 970

原创 floyd 算法带输出路劲

//floyd 算法带输出路劲#include#include#define inf 0xFFFFFFFusing namespace std;const int maxn=100005;int n,dp[maxn][maxn],path[maxn][maxn];//floyd算法利用的是动态规划的思想。//也是可以求解矩阵的最值 void init()//求解最小或者最短时的初

2017-01-22 18:41:39 630

原创 kmp

kmp的原理还好理解但是代码比较难理解#include#includeusing namespace std;int next[105];void getnext(char *s,int lens)//O(m+n){ int j=0;next[0]=0; for(int i=1;i<lens;i++) { while(j&&s[i]!=s[j])j=next[j-1]

2016-12-27 00:03:58 208

原创记忆化搜索区间dp uva629

记忆化搜索区间dp uva629这题一看就知道是区间dp 状态定义很简单但是在写代码的时候有个地方一直错错到我吐血下面代码中有写d(x,y,k,h)表示x行到y行 k列到h列的最少数也就是子矩形的宽度和高度 d(x,y,k,h)=min(d(x,i,k,h)+d(i,y,k,h)+h-k) 列的枚举也是如此#include #include using n

2016-12-04 20:59:35 308

原创记忆化搜索逆向dp uva10118

记忆化搜索逆向dp uva10118 这道题开始做的时候很容易把状态定义成5维 d(i,j,k,h,g) 前面4个变量表示4堆糖果的现在在哪个位置而后一个g则表示篮子里有几颗糖果后面想了一下我用递推的话那么我怎么推出每个状态后面的那个g 就是比较难转移好像不行因为之前很少用记忆话搜索所以没有想到这个原来记忆话搜索有这样的好处！记忆话搜索

2016-12-04 11:18:10 281

Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。这里说下map内部数据的组织，map内部自建一颗红黑树(一种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在map内部所有的数据都是有序的，后边我们会见识到有

2016-11-27 12:35:41 200

原创石子合并帮果实动态规划解法

#include #include #include using namespace std;const int INF = 1 << 30;const int N = 205;int dp[N][N];int sum[N];int a[N];int getMinval(int a[],int n)//dp[i][j]表示的是第i到第j堆合并的最小花费 { for(i

2016-11-23 15:31:30 429

原创 poj1733 离散化带权并查集的思考

poj1733解析离散化带权并查集的思考题意是给你一个区间和区间1的个数是偶数还是奇数然后判断第一个错提问的第一眼看到这题感觉是线段树思考一下线段树的做法线段树维护区间信息维护一个区间是奇数还是偶数线段树一个节点代表一个区间但是一个区间并不代表一个节点要多个节点存储一个信息多个交叉区间维护的话就乱掉了而且一般线段树题是多次询问所以线段树不行，这个题就是维护区

2016-11-22 20:51:07 308

原创第七届蓝桥杯 5题

第七届蓝桥杯 5题对这道题的理解 #include #define N 6#define M 5#define BUF 1024void f(int a[], int k, int m, char b[])//m是还剩下派的人 { int i,j; if(k==N){ b[M] = 0; if(m==0) printf("%s\n",b); r

2016-11-15 21:18:11 322

原创分析问题

分析问题最近在做校内的题一道简单的搜索题我居然卡了很久后面问了下听了下思路我才焕然大悟开始思考了一天一直按题目所给的条件去思考按照题目条件的话就是去暴力搜索现在想下很蠢啊是先搜所有的可能在判断一边判断一边搜特别麻烦对于我来说写不出来其实开始想的时候就没有往先搜后判因为怕这样的思路复杂度太大效率低一般大一点的赛不会出这种题所以就没有往这边想了一边判一边搜复

2016-11-15 20:52:11 268

原创快速幂取模

快速幂取模刚好过来再来理解下原理二分 #include#includeusing namespace std;int pew(int a,int n,int m){ if(n==0) return 1; int x=pew(a,n/2,m);//递归二分 a^b%m=(a^2%m)^b/2 long long ans=(x*x)%m; if(n%2)//如果

2016-11-14 22:23:47 173

原创带权并查集 hdu3038

并查集 hdu3038 集合的应用个人感觉有点难想开始看到的时候还以为是线段树之后会想到并查集想了1个钟头出了一点思路就是维护集合中的元素到根节点的距离但是开始的时候没有考虑到左端点可以减一所以没有算出怎么判断区间集合的冲突（也就是判断错误信息比如exemple 1~3和4~6 这是可以合并一个区间的）后面看了下就出来了还有就是输入要输入文件的EOF才能退出一

2016-11-03 13:23:50 406

原创 poj2236 并查集第一题思路分析

并查集第一题思路分析 poj2236 开始训练并查集这是做并查集第一题所以做一个思路分析有助于自己对并查集的理解题意就不解释了问题一判断各个节点之间是否可达？很明显这里可以用dfs 或者并查集进行判断这里用并查集比较快因为这里并不用用到两点之间的路劲（由于比较慢，所以不用路劲来进行解决）或者其他一些信息一开始做的时候因为是先进行各个点之间用并查集单独进

2016-11-02 16:53:28 311

原创 hdu4614 Vases and Flowers 二分

hdu4614 Vases and Flowers 二分这道题用数据结构为优化时间效率用二分来分别找出左边界答案和右边界答案这是属于线段树数据结构与其他算法的结合使用开始做的时候还死死的在线段树上做文章。。。。问题是在以A为起点的区间第一个可以插花的和最后一个可以插花的地方按照正常思路的话可以想到二分可是与线段树扯上了就只能想到在线段树上处理看来这种结合思想

2016-10-29 21:10:40 252

原创 hdu3974 线段树编号的处理 dfs 加 lazy思想

hdu3974 线段树编号的处理 dfs这道题想了大概一天一直没想出来怎么对节点编号后面百度了看到dfs 瞬间开朗利用dfs的时间戳对节点编号这样保证了每个父节点的子节点都在父节点所代表的区间内这里用了以点保存区间的方式开始的时候没有用lazy思想直接用的setv[x]存储set的点然后一直错后面想通了如果我那样做的话有可能之前set 的点

2016-10-29 13:27:31 227

原创线段树处理 poj2892 hdu1540

线段树处理 poj2892 hdu1540这道题想了很久没有想出来思路后面上网找了题解利用区间左端点连续和右端点连续处理了区间的连续sum数组存储连续村庄个数，lsum存储区间内从左起连续个数，rsum存储区间内从右起连续个数#include #include #include #include using namespace std ;#define INF

2016-10-26 21:16:10 208

原创 poj2528 线段数组离散化

poj2528 线段数组离散化#include #include #include using namespace std;#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1const int maxn = 11111;bool hash[maxn];int li[maxn] , ri[maxn];

2016-10-25 22:30:55 649

原创线段树总结与模板

线段树总结与模板单节点更新的 hdu1166 敌兵布阵 #include#include#include#includeusing namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1const int maxn=100005;int sum[maxn<<2];void PushUp(in

2016-10-24 22:50:54 186

转载 prim算法伪代码

点击打开链接Prim算法1.概览普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美

2016-10-24 21:15:32 8373 2

原创最短路 dijkstra算法 poj2387 bellman_ford spfa

最短路 dijkstra算法 poj2387就是一个模板题，，，，，，，，，，，啊？模板题这个还要套模板？一脸门鼻直接上代码 #include #include #include #include using namespace std;#define inf (0x7f7f7f7f)const int maxn=100005;struct

2016-10-24 18:26:13 444

原创双向广搜代码框架

//双向广搜代码框架struct State { }; //状态queueque[2];bool vis[2];bool flag;void bfs(int d) { int size=que[d].size(); while(size--) { //普通单广转移新状态v if(vis[d][v]) continue; if

2016-10-23 20:26:50 593

原创搜索进阶 hdu2181 回溯

搜索进阶 hdu2181最近在训练搜索题简单的搜索题已经基本大概的掌握了现在做搜索进阶 hdu2181 做这道题一眼思路就是广搜考虑过迭代加深搜索或者dfs 如果他不要求全部输出则这个就可以用但是不是这个题还要求每个城市经过一次回到原点前面是废话只是记录自己的思路而已我他妈在干嘛就是回溯啊卧槽这么简单的题都想错在想什么啊现在考

2016-10-19 16:56:03 265

转载康托展开及其逆运算详解

康托展开及其逆运算详解详细看这里点击打开链接康托展开是什么？定义：X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0!ai为整数，并且0简单点说就是，判断这个数在其各个数字全排列中从小到大排第几位。比如 132，在1、2、3的全排列中排第2位。康托展开有啥用呢？

2016-10-18 17:15:11 385

原创 poj3984 输出路径

poj3984 输出路径第一次做输出路径的搜索题这道题没有想到一个好办法手写队列然后记录前一个在队列中的位置居然没有想到这个办法#include#include#define N 5using namespace std;struct note{ int x,y,pre; //存放坐标，前一个节点在队列中的位置} que[100];in

2016-10-15 17:49:13 252

原创子集生成的三种方法

子集生成的三种方法最近遇到一个子集生成的题没有很快的写出来所以在把之前的过的子集生成方法在复习一边第一种增量构造法在lrj紫书中这是放到第一个讲解的。。。。。。顾名思义增量构造法就是按照递增顺序就行构造子集防止子集的重复如集合{1，2} 就不会输出{1,2} 和{2，1}这样重复的子集了在解答书中生成 2^n方个子集直接看

2016-10-15 11:19:30 5249

原创 poj3278 bfs

poj3278 bfs 这道题是很经典的bfs题比较简单开始想的时候思路并没有很清晰就开始敲代码导致后面速度放慢出错调试也慢没有很快做出来看来bfs还是不是很熟练#include #include #include #includeconst int INF = 0x3f3f3f3f; using namespace std;int maxn=100

2016-10-12 15:06:09 228

转载集合的二进制表示

一些不大的数的集合，可以用二进制的形式来表示，注意这里的集合没有重复元素。集合的存储方法是用一串二进制的数存，第i位表示i这个数是否在集合中。设集合中最大的数不超过（1集合的运算因为是二进制表示，A|B、A&B、A^B、分别对应集合的并，交和对称差。子集元素的输出从1到n枚举，如果在s中就输出，代码： void print_element(int n,int

2016-10-10 21:52:10 1328

原创 HDU 3018 Ant Trip 欧拉路并查集

HDU 3018 Ant Trip 欧拉路并查集开始的时候没有看清题以为是每个联通图判断欧拉路就行了 #include #include #include #include #include #include using namespace std;//hdu3018 对于联通的图判断奇数度数的个数如果==0 就+1 就行了否者加奇数个数 #defi

2016-10-09 18:53:12 248

原创 Fleury算法求欧拉路径

Fleury算法求欧拉路径列出一些有关欧拉的题混合图欧拉回路 poj1637，zju1992，hdu34721HDU 3018 Ant Trip2POJ 1041 John's trip3 POJ 1386 Play on Words4 POJ 2230 Watch Cow5 POJ 2513 Colored Sticks6 POJ 23

2016-10-09 16:44:37 1968

原创 hdu1878欧拉回路并查集学习欧拉路学习

hdu1878欧拉回路并查集学习欧拉路学习本来是学习欧拉路的但在做题的时候发现自己对并查集掌握的不是很好现在用这道题来写下自己对并查集，和欧拉路的一些思路首先以hdu1878 为列子写下这道题是纯的欧拉回路直接写就是了首先介绍下欧拉路的一些定义与性质以下来自于这里欧拉通路欧拉回路的区别及其判定在做一些图类时经常要用到欧拉

2016-10-09 15:07:42 400

原创 01背包第k优解

求次优解、第K 优解#include #include #include using namespace std;struct Node{ int price; int val;} node[1005];int main(){ int t; scanf("%d",&t); while(t--) { int n,

2016-10-07 20:13:00 327

原创 01背包完全背包多重背包实现

01背包完全背包多重背包实现 01背包//O(NV)f[0][0 ~ V] = 0;for(int i = 1; i <= n; ++i) for(int j = 0; j <= V; ++j) if(j < w[i]) f[i][j] = f[i - 1][j]; else f[i][j] = max(f[i - 1][j], f[i -

2016-10-06 21:23:34 262

原创 poj 2059 龟兔赛跑 DP

poj 2059 龟兔赛跑 DP 简单dp 思路很简单一开始想的时候就想出了以f[i]为最后一个站到达时间最短确定了这种思路是正确的然后写出了转移方程 f[i]=f[i-1]+min(要加油的时间，不加油的时间) 这里前面的c不归0 但是但是但是我没写出代码来这种转移方程代码好难写啊后面百度题解发现转移方程不是我这么写的 f[i]=min(f[j]

2016-10-06 17:59:57 292

转载 poj 1050 To the Max

poj 1050 To the Max这道题用到的是最大连续和扩展到二维开始时没想到是最大连续和 #include#includeint a[101][101],n,temp[101];int solve()//最大子序列和函数{ int i,sum=0,max=0; for(i=0;i<n;i++) { sum+=temp[i];

2016-10-06 13:10:27 185

空空如也

空空如也