- 博客(28)
- 收藏
- 关注
RSS订阅原创 CS231 笔记
SGD with momentum有两种写法 效果等价 Adam中的bias correction项的存在是出于以下考虑：first_momentum以及second_momentum都初始化为0，为了仅在开始的几次迭代中增大他们的影响，增加了一个参数为t的correction，值得注意的是，t的值随时间增大，也就是说放大效果越来越弱。...
2019-05-18 11:52:45
478
原创 SICP练习
练习1.8(define (good-enough? old new) (and (< (/ old new) 1.001) (> (/ old new) 0.999)))(define (improve guess x) (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))(define (cube-root guess...
2018-12-15 11:32:05
395
原创 网络流初步总结
今天终于把kuangbin大佬的网络流专题给做完了，感觉这些题都是很棒的。在网络流题目中，比熟练掌握各种算法更重要的，是根据不同的题目建立一张图，有些题目看似与图论无关的题目，硬是可以抽象出一张图来，下面随意总结几种建图方法1.拆点法如果题目对通过某个点的流量有要求，可以把这个点拆成两个点，其中一个入点和一个出点，从入点到出点有一条容量为流量限制的边，然后以该点为终点的边都连到入点上，以该...
2018-10-21 22:24:03
409
原创 POJ-3436 ACM Computer Factory (Dinic或Edmonds_Karp)
1.编码用一个int表示电脑的一种状态，其中最低的二进制位表示第一个部件的状态，最高的二进制位表示最后一个部件的状态，1代表存在，0代表不存在2.建图图中的点包括电脑所有的状态，共有2^p个点；和机器，共n个点。由题意可知，一台机器可以加工多种不同状态的电脑，但是产生的电脑的状态可以唯一确定。加边过程为：对于每个机器。将它与它产生的电脑状态点之间建立一条容量为机器的performanc...
2018-10-08 22:42:23
257
原创 HDU-1325 Is it a tree? (勉强算并查集？）
判断是不是一棵树，只要三个条件1. 每个点至多只能有一个父节点2.n个点，对于n-1条边3.不存在自环用一个集合p储存出现过的点的序号，f储存有已经父节点的点;flag表示是是否满足条件1和3，edgenum记录边的数量#include<cstdio>#include<set>using namespace std;set<int> ...
2018-09-19 22:40:14
181
原创 ZOJ-3261 Connections in Galaxy War(并查集）
1.读入点的权值和边（保证first顶点编号小于second顶点）,集合清空，并查集每个元素置为-12.读入所有请求，将摧毁请求中的边转换为一个int储存在集合中（设两顶点编号为a,b,且a<b,那么哈希值为10000*a+b,因为最多有10000个点，采用了10000进制的思想，ab有序保证一条边的哈希值不因为定点出现顺序不同而不同）3.遍历所有的边，若该边不在集合中，合并两个顶点...
2018-09-18 20:24:50
181
原创 POJ-2892/HDU-1540 Tunnel Warfare (树状数组+二分查找）
这两道题的题目时一样的，但是数据不一样。bool d[maxn]; 用于记录村庄i是否被炸毁建立一个树状数组bit[maxn]，sum(i)用于计算[1,i]区间内被摧毁的村庄的个数stack<int> 记录被炸毁的村庄的顺序下面对三种指令进行处理首先对数据做一点说明：POJ的数据中应该没有继续炸毁已经被炸毁村庄的操作，但是HDU的数据中有1. D x 摧毁...
2018-09-17 12:28:53
265
原创 LightOJ-1074 Extended Traffic (stack优化Bellman-Ford)
每个junction就是图的一个顶点，边权就是（终点的busyness-起点的busyness) ，所以可能会出现负边和负环。要用Bellman-Ford算法求单源最短路。在这里要注意，本题的图中是包含负环的，对于能求得最短路的点就求，不能到达的点和无最短路的点都要标记出来。d[i]==inf 表示i处无法到达，d[i]仍是初始值；cnt[i]>=n,代表i点已经n次入栈，如果有最短...
2018-09-11 20:22:37
259
原创 POJ-3159 Candies( 栈优化Bellman-Ford+邻接表）
与POJ1151类似，较大输入，需要用邻接表。由于我们要求的是与顶点1最大的差值，需要先将d[]数组初始化为无穷大，然后一步步根据边的约束缩小到合理的最大值。然而这道题与众不同的一点是队列优化的Bellma-Ford会超时，栈优化就不会，网上有博客说在很多情况下栈的效率的确高于队列，我也不知道为什么....记录一下这种做法最后注意用于指向数组模拟链表的下一节点的nxt[]数组的大小应与...
2018-09-08 00:21:03
315
原创 POJ-1511 Invitation Cards (SPFA+邻接表)
这个题主要的点在于数据量过大（以及题目废话过多），然后就带来了储存上的不便，用刘汝佳紫书上喜欢用的vector那样会因为直接超时，然后简单的邻接矩阵在VS中直接提示数组过大....所以一个好的方案是数组模拟链表实现邻接表。这样做比直接使用链表的好处在于节省了反复申请释放内存所消耗的可观的时间。然后对于这种百万级别的数据，简单的bellman-ford或者dijkstra应该会超时，所以这里选择...
2018-09-07 19:25:07
212
原创 UVa247 Calling Circles (Floyd +DFS/并查集）
本题中两点A，B在一个一个calling circle中的条件是存在一条A->B的路径,也存在一条B->A的路径。可以用Floyd算法传递闭包，g[i][j] 为1表示i->j存在路径，反之表示不存在，那么AB在一个circle中等价于 g[A][B]&&g[B][A]。可以用DFS或者并查集来输出连通分量。本题的顶点以string表示，可以用STL ...
2018-09-04 13:27:54
213
原创 UVa 1151 Buy or Build （子集枚举+Prim）
从刘汝佳的紫书上看到的这道题，没看懂他的神奇的解法什么意思，干脆直接暴力枚举子集，因为这相当于是一道稠密图的题，用kruskal不太划算，直接上Prim，250ms解决虽然比别的提交者慢了很多，但是解决这道题也足够了。因为最多只有8个subnetwork，可以直接枚举他们的每种组合（这里用了bitset枚举），至多2^8=256种，在可接受的范围内。本题以坐标的形式给出了城市间的关系，因此边的...
2018-08-30 18:26:15
211
1
原创 HDU-4009 Transfer Water(无固定根朱刘算法）
首先明确一点，这道题目是肯定有解的，也就是说题目中说的“If the plan does not exist, print “poor XiaoA” in one line. ”，是不存在的，因为无论如何，每家都可以自己挖一口井喝水用。从题目中的信息中抽象出最小树形图的思想：A可以给B供水，那么A->B就存在一条有向边；如果S点挖了一口井，他就可以作为一棵树形图的树根。由于谁是树根，共有...
2018-08-30 07:51:15
278
原创 Leetcode 893 特殊等价字符串组 from weekly contest 99
等价类问题使用并查集解决即可题目要求所谓的移动只能在一个字符串的奇数号字符之间或者偶数号字符之间进行，所以我们要分别统计两个字符串的奇数号字符和偶数号字符的分布，然后比较是否等价，最基本的并查集操作class Solution {public: int find(int ufs[],int y) { return ufs[y]<0?y:find(u...
2018-08-26 16:35:50
892
原创 POJ-3164 Command Network (朱刘算法）
这是一道最小树形图的模板题朱刘算法开始时的确不是太好理解，在网上看了好多文章才差不多理解。在这里说一点，缩点时，如果弧(u,v)的v点在一个环中，这个环形成的缩点在新图中的编号是k，那么新图中(u,k)的权值是W(u,v)-in[v],因为ret(即最终的返回值）只在朱刘算法的开始置了一次0，这个权值的变化可以保证，在对一个点加入新的入边时，可以顺便把上一次的旧边的权值在ret中去掉，对于...
2018-08-25 07:16:34
315
原创 UVA-10462 Is there a second way? (DFS/并查集+次小生成树）
暑假快结束了，唉，不想回学校。题目的意思很简单，给出一些点和连接这些点的边，如果1. 无法形成连通图 输出No way：这个用并查集或者DFS检查连通性即可，对本题的数据规模来说时间效率没有什么显著差别，看个人喜好了；e<v-1时，无论如何都无法联通，直接输出No way2. 能形成连通图，也就有了最小生成树。如果 1.刚好联通，即e==v-1,那么就没有...
2018-08-23 13:52:18
254
原创 UVa 10600 ACM contests and blackout(次小生成树）
这是一道次小生成树标准的模板题，使用prim算法计算最小生成树的同时，在用tmax[u][v]记录u点到v点的路径中最长的一条边的长度，used[i][j] 记录以i和j为两个端点的边是否在最小生成树中；此外，在用prim算法时除了用closedge[i]记录未访问顶点到已访问顶点集合最短边的长度, 还要用pre[i]表示这个最短边的另一个顶点。在prim的最后更新closedge时同时更新pre...
2018-08-22 23:20:25
138
原创 HDU -2181 哈密顿绕行世界问题
由于数据量其实很小，直接DFS即可，细节见注释#include<cstdio>#include<cstring>#include<algorithm>using namespace std;bool vis[21];int adj[21][3],cnt,tpath[20],start;void dfs(int k,int level){ i...
2018-08-18 17:21:23
379
原创 POJ 3414 Pot (BFS)
这也是一个类似倒水问题的题把两个杯子中的水量形成的有序数组(x,y)，看作有向图中的一个顶点，起点是(0,0)，终点是一个杯子的水量为C。若一种状态A可以通过对某个杯子的某种操作转移到另一个状态B，那么图中有一条从A指向B的边。求起点到终点的最短路，BFS即可。注意几点1. 因为这道题需要打印路径，所以需要多设置一个保存操作的结构体数组，递归打印操作即可：我的做法是从目标终点出发，...
2018-08-13 18:51:59
215
原创 HDU 2612 Find a Way (BFS)
这道题的英语水平非常的惨不忍睹（虽然作为同样精通Chinglish的中国人我完全可以看懂，但还是莫名地觉得搞xiao啊233对两个人分别bfs一下，记录每个kfc所需的总时间，最后输出最小的即可，几点注意1. 要求输出的答案是总步数*11，因为走一步要十一分钟2.因为有可能某些kfc两个人都到达不了，所以可能会出现某些kfc用时为0，最后比较出最小值时选择非零值即可3.两人的起始位...
2018-08-12 20:21:35
145
原创 LeetCode 890 可能的二分法 from weekly contest 97(DFS)
把每个人看作无向图中的顶点，如果两个不能分到一组，则看作两点间有一条边。如果一个连通图满足1. 无环2.有环，并且每个环上的顶点数都为偶数这两个条件中的一个，我们就可以通过 将相邻的顶点分配到不同的组 这个策略来实现二分。不能二分的情况是连通图中肯定出现了奇数个顶点的环，显然对于这样的环，是无法把所有相邻的顶点分到不同组的eg 1-2 2-3 3-1 就无法二分对于非连...
2018-08-12 11:44:43
493
原创 POJ-3126 Prime Path (BFS&&筛法)
用相同的花费从一个状态转移到另一个状态这真是一个检验宽搜的完美标准num[i]为1表示i是素数，为0表示i不是素数，用筛法可以很快地标注是不是素数。有一个小技巧就是筛法最外层的循环只要循环到最大范围的一半就可以了，因为后一半数的性质由前一半决定（如果x是小于MAX的合数，它的因子必成对出现，因子的最大值一定<=x/2<MAX/2,因而后一半数的性质以及可以确定），而他们又不会对...
2018-08-10 19:53:25
212
原创 UVA-11624 Fire! (BFS)
这题的一个做法是先对 'F' BFS一遍，这样就可以记录下来火势到达每一个格子最早的时间，对于每个 '.' 来说，在这个火到达的最早时间之前，joe是可以走的。然后对joe BFS 一遍就可以了，重点是joe在”边上“，也就是最左边最右边最上边最下边。特别的是，我在bfs中采用的是每产生一个新的节点就判断一下是不是终点，所以对于joe一开始就在边上的情况需要额外判断。#include&l...
2018-08-10 17:48:53
186
原创 HDU-1495 (BFS)
总体思路与经典的倒水问题相同（可参考刘汝佳《算法竞赛入门经典》P202-P205对Uva10603的讲解）对于总可乐量为奇数的情况，直接输出不可能，因为对于没有刻度的整数容量的杯子，我们可以操作的最小可乐量不会小于1，因而无法平分。下面讨论偶数的情况：把每种状态以三个杯子中的水量排成的有序三元组表示，该三元组可看成有向图中的一个节点。如果经过一次倾倒，状态A转移成了状态B，那么在图中就...
2018-08-09 18:23:19
1714
3
原创 CodeForces-717G Potions Homework
将a[]数组排序，求它的逆序和即可，这个很直观但是需要数学证明，证明见排序不等式需要注意的是ai的最大值为10，0000，ai*ai的最大值为10^10,超过了INT_MAX=2147483647,需要使用long long 类型还有就是最后要求结果取余10007AC代码如下#include<iostream>#include<algorithm>us...
2018-07-31 16:50:18
301
原创 LeetCode 189 旋转数组
补数据结构的作业的时候，被老师要求写出时间复杂度为O(n)，空间复杂度为O(1),的算法。断断续续想了一天，终于有了一个大概思路，写出来自己跑了几组数据，没发现什么问题。在LeetCode上找到了这道题提交了一下，用时战胜了89%的提交者（最优的那种算法真的是简单又高效，但是我实在是没有想出来，就不在这里剽窃了）。下面叙述一下我的想法。首先明确，k>=n时，应有k%=n，因为移动一圈跟不...
2018-05-31 19:06:10
653
原创 LeetCode 136 只出现一次的数字
一个寻常的思路是建立一个二位数组rec，val分量用于储存出现的数字的值，cnt分量用于储存他出现的次数，然后遍历一遍数组，对于数组中的每个元素，如果rec中有这个数，就把cnt++，没有就创建一个，把cnt置为1；最后遍历一遍数组rec，返回cnt值为1的val。该算法代码量较大，空间复杂度为O(n),时间复杂度为O(n^2),emmmm，垃圾算法冥思苦想了好半天我终于想到了神奇的位操作----...
2018-05-16 12:54:58
203
原创 LeetCode 278 第一个错误的版本
题目的意思很简单，一个数组中前面都是0，后面都是1，你可以通过 isBadVersion(int version) 函数来判断n位置处的元素是1还是0。并强调了要尽可能地少调用该函数。那么很显然就是要二分查找了。但是我开始写的二分查找竟然在第11组测试用例就超时了（原因见文末），后来一直也没有找出来错来，自暴自弃地写了一个线性查找竟然撑到了第16组测试用例才TLE。于是我改良了线性查找，先缩小查...
2018-05-14 21:31:41
2296
5
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人