01 bfs UVA11573 Ocean Currents 分析：题中给了两种移动方式，一种是沿着洋流的方向移动，不需要消耗能量，不沿着洋流走需要消耗1能量，此类按照普通的bfs不能保证队列前面的一定是当前消耗能量最少的情况。正确做法是利用双端队列，不消耗能量就从队首入队，消耗能量就从队尾入队，这样就能保证队列前面的一定是当前消耗能量最小的AC代码： #include <bits/stdc++.h> using namespace std; int n, m; char ch[1005][1005]; int ans; int k; int rs, cs, rd, cd; str...

并查集有关 食物链 分析：存在A吃B，B吃C，C吃A这三种关系，即存在三种生物，三个集合，而这三种生物又是等价的，对于每一个生物x，他都可以是A，也可以是B，也可以是C，假定fa[x],fa[n + x], fa[2 * n + x]分别是生物x是A,B,C的情况下的父节点。对于每次的两个生物都要把他们当作A,B,C分别看一遍。eg.2 2 31 1 3第一句话表示2吃3，即2是A的时候，3不能是A,和C，2是B的时候，3不能是B和A，2是C的时候，3不能是C和B,判断后合并第二句话同样判断AC代码： #include <cstdio> using namespace std; i...

POJ3275 Ranking the Cows 题意：有N个数字，已经比较了M对(x,y),其中x>y, 问至少再需要比较多少对数字，就能把N个数按大小有序的排列起来 分析：如果x>y,就在x和y之间连一条单向边，然后用floyd算法（floyd传递闭包）， AC代码： #include <bitset> #include <cstdio> using namespace std; int n, m, a, b, ans; bitset<1005> bi[1005];//要用bitset来存01矩阵，可以省掉最外面的一层for循环，不然会超时 ...

dijkstral算法 (复杂度O(nlongn + m))——不能有负权边spfa算法 (复杂度O(km))——不能有负权环 如何存图 用的是伪邻接表（链式前向星）插入用的是头插法 int tot; struct node { int to, l, next;//to代表这条边指向谁，l代表边权，next代表下一条边的位置 }edge[1050]; //添加一条x指向y的边权为z的边 void addedge(int x, int y, int z) { edge[++tot].to = y; edge[tot].l = z; edge[tot].next = head[x]; head[x...

NC20185 [JSOI2010]缓存交换 这是一道堆的题，堆的题常与贪心有关，此题也是。借鉴别人的博客 + 别人的代码给整明白了，于是乎自己写篇博客再理理思路首先这个题肯定是要在下标上做文章，因为要判断当前数是否在缓存区内，我们可以用一个bool数组，而这个数组肯定存第i个数在不在缓存区内，所以bool[i]的这个i就是指第i个数，不能指i这个数在不在缓存区内，因为最大值1e9，开不了那么大的数组，而找到第i个数下一次出现的数组nexti同样。 思路：1.大体思路：我们把前m个数放到缓存区后，再碰到不在缓存区里的数时，我们需要删除一个原来在缓存区的数，然后把这个数加到缓存区内，首先问题在于...

单调队列 单调队列这个东东之前学过一遍了~但似乎忘得一干二净惹，或者当时就妹学会 NC50528 滑动窗口 模板（找最小的数）  l = 0;//左闭右开的区间 r = 1; p[0] = 1;//数组p存的原数组的下标 if(k == 1) printf("%d ", ar[1]);//k是区间长度 for(int i = 2; i <= n; ++i) { if(i - p[l] >= k && (l < r)) l++;//判断队头有没有出窗口 while(r > l && ar[p[r - 1]] >= ...

一.STL的二分函数 1.binary_search(ar, ar + n, x); 三个参数，第一个是数组首地址，第二个是数组名+数组大小，第三个数要找的数。存在这个数则返回true，否则返回false； 2.lower_bound(ar, ar + n, x); 参数和上面那个一样，返回的是第一个大于或等于x的数的迭代器，减去数组首地址得到的是这个数的下标 3.upper_bound(ar, ar + n, x); 参数一样，这个返回的是第一个大于x的位置。 POJ2785 4 Values whose Sum is 0 题意：有4组数，让你从每组中找一个数，然后这4个数和为0，有几种找法...