- 博客(121)
- 资源 (3)
- 收藏
- 关注
RSS订阅原创 基于Pytorch使用RNN（LSTM）的音乐生成（基础）
上次跟着Tensorflow的官方教程，用tensorflow写了一遍后，不太习惯tf的风格，于是用pytorch再写了一遍，熟悉了pytorch的基本代码流程本文主要为了熟悉pyTorch机器学习的代码一般格式，在音乐生成的模型上有很多不合理的操作，
2022-02-05 21:51:07
3810
12
原创 使用Tensorflow的RNN(LSTM)生成音乐（基础）
跟着Tensorflow的官方教程，搭建一个简单的LSTM模型，生成midi格式的音乐。只是为了熟悉tensorflow机器学习的代码一般格式，在音乐生成的模型上有很多不合理的操作，所以结果也不太好。
2022-02-05 19:54:51
2817
9
原创 关于tensorflow的dataset执行map的问题
对一个包含dataset的dataset，比如这种window过后的玩意儿如果对这种dataset执行map，在map里对子元素的dataset进行遍历，就会出现内存泄漏并且卡死
2022-02-02 19:47:19
2029
原创 Deep Q-Learning算法解决Cartpole(倒立摆)游戏
倒立摆Cartpole-v1简介倒立摆为一个小车和一个杆通过轴连接，杆在初始时稍有偏离垂直线，在重力作用下会倒下，游戏目的是通过左右控制小车（施加左右的力）来避免杆的倒下。API获取初始状态env = gym.make("CartPole-v1")state = env.reset()state为一个包含4个元素的list，分别表示小车位置，小车速度，杆的角度，杆的角速度，具体范围如下Type: Box(4)Num Observation Min
2021-08-11 12:22:48
1923
1
原创 使用notepad++编译C++程序的命令
找个地方存一下cmd /c chdir /d $(CURRENT_DIRECTORY) & echo 开始编译 & g++ $(NAME_PART).cpp -o $(NAME_PART) -g -std=c++11 & echo 编译结束 & pausecmd /c chdir /d $(CURRENT_DIRECTORY) & echo 开始运行 & $(NAME_PART).exe & echo 运行结束 & pausecmd /c
2021-07-29 10:25:13
120
原创 【BOI2019-Day1T2】Alpine valley（DP+倍增）
题目大意在山谷中有N个村庄，有N-1条道路将村庄连成一棵树，每条道路有一定长度。第E号村庄为山谷的出口。有S个村庄中有商店，商店可提供补给。由于山谷中天气恶劣，一条道路会被封死。当你处于某一个村庄中时，得知一条道路已经封死，你想知道自己能否活下去，即对于每一个询问，你需要计算，你是否能走出山谷，如果不能走出，则计算到最近的商店获得补给品所需最短路程。输入第一行：N,S,Q,E，即 村庄数，...
2019-06-18 21:38:13
359
原创 【洛谷P4719】动态DP（全局平衡二叉树）
题目大意给定一棵n个点的树，点带点权。有m次操作，每次操作给定x,y，表示修改点x的权值为y。你需要在每次操作之后求出这棵树的最大权独立集的权值大小。题解如果不带修改操作，正常的DP式：dp[u][1]dp[u][1]dp[u][1]表示当前结点保证选择，这个结点的子树独立集最大权值。dp[u][0]dp[u][0]dp[u][0]表示当前结点不选择，这个结点的子树独立集最大权值。...
2019-03-23 15:51:19
479
原创 线性规划——单纯形法
问题标准型问题：最大化∑j=1ncjxj\sum\limits_{j=1}^{n}c_jx_jj=1∑ncjxj满足约束∑j=1naij⋅xj≤bi (i=1,2,...,m)\sum\limits_{j=1}^{n}a_{ij}\cdot x_j\le b_i\ (i=1,2,...,m)j=1∑naij⋅xj≤bi (i=1,2,...,m)且 xj≥...
2019-03-18 21:46:23
2157
原创 Min_25筛
简介求积性函数前缀和，线性筛需要把函数的每一位值都算出来，作了许多不必要的操作。线性筛中，通过计算最小质因子幂的函数值，与之前已计算出的函数值相乘，得到新的函数值。如果我们能批量执行上面的操作，即用最小质因子幂的函数值，与另一些函数值的和相乘，就可以得到更多的函数值的和。我们还能发现，当我们要求前n项的和时，大于根号n的质因子都不能用于计算任何其它的积性...
2019-03-07 11:36:19
3779
3
原创 【BZOJ5223】有理有据题（K-D树）
题目大意有n颗炸弹，第i颗炸弹的爆炸范围为[li,ri][l_i,r_i][li,ri].有m个房子，标号为i的房子为一条线段[ai,bi][a_i,b_i][ai,bi]（只要房子线段与炸弹相交视为炸弹能摧毁房子）几种操作：A x y：增加一个房子[x,y][x,y][x,y]，按顺序标号。C i：查询第i个炸弹能炸毁的连续标号的房子，最多连续多少个。Q：查询每个C 1~n...
2019-03-02 21:57:21
474
原创 生成树计数——矩阵树定理(Matrix-Tree)
文章目录结论无向图有向图口胡Matrix-Tree证明前置技能行列式定义初等变换拉普拉斯展开求法柯西-比尼定理（Cauchy-Binet）Matrix-Tree定理证明基尔霍夫矩阵性质基尔霍夫矩阵行列式为0不连通的图的主余子式行列式为0树的主余子式为1关联矩阵证明主体证毕结论无向图对于无向图GGG，设第iii个点的度数为did_idi，第iii个点与第jjj个点相连的边数为aija_{ij...
2019-01-18 20:00:50
3912
1
原创 第一类斯特林数
概念[nk]n \brack k[kn]表示将nnn个数的序列划分为mmm个圆排列的方案数。递推公式[nk]=[n−1k−1]+[n−1k]×(n−1){n \brack k}= {{n-1} \brack {k-1}}+{{n-1}\brack k}\times (n-1)[kn]=[k−1n−1]+[kn−1]×(n−1)[n−1k−1]n-1 \brack k-1[k−1n−...
2019-01-12 12:05:12
6475
1
原创 【2019.1雅礼集训DAY2 T2】bracket（点分治+FFT）
题意给定一棵有 n 个节点的无根树，每个节点上是一个字符，要么是(，要么是)。定义 S(x, y) 为从 x 开始沿着最短路走到 y，将沿途经过的点上的字符依次连起来得到的字符串。合法括号序定义如下:1，()是合法的。2，若 A，合法，则(A)也合法。3，若 A，B 分别合法，则 AB 也合法。函数 f(x, y) 等于对 S(x, y) 进行划分，使得每一个部分都是合法括号序，能...
2019-01-10 11:54:07
678
原创 【BZOJ4543】Hotel加强版（长链剖分 + 启发式合并）
题意给一棵树，从中选三个点，使得三个点两两间距离相等，求方案数。题解对每一个结点，用num[u][d]num[u][d]num[u][d]表示子树中到当前结点u的距离为d的节点数，用way[u][d]way[u][d]way[u][d]表示已经有很多两个结点的配对，再添加一个到当前结点距离为d的结点即可构成一个方案的结点对数。枚举子节点v，先计算答案Ans+=way[u][d+1]×num...
2019-01-09 21:43:30
502
原创 【2019.1雅礼集训 DAY1 T2】permutation（可持久化线段树）
题意给出nnn个数AiA_iAi定义排列一个 1~n 的排列 P 的价值为：∑i=1nAi×Pi\sum_{i=1}^n A_i\times P_ii=1∑nAi×Pi求出排列价值前kkk小的kkk个排列的价值。...
2019-01-09 20:54:39
528
原创 【BZOJ2216】Lightning Conductor （决策单调性DP）
题目大意给一个序列aia_iai，对每一个i，求出最小的非负整数p，使得对任意j满足aj≤ai+p−∣i−j∣a_j\leq a_i+p-\sqrt {|i-j|}aj≤ai+p−∣i−j∣题解移项得p≥aj−ai+∣i−j∣p\geq a_j-a_i+\sqrt {|i-j|}p≥aj−ai+∣i−j∣绝对值可以去掉，正着算一遍，倒着算一遍，取最大值即可此时保证i>...
2018-12-27 19:53:52
209
原创 【BZOJ3864】Hero meet devil（dp）
题目大意对每一个i(1<=i<=n)，求长度为m，与给定字符串S的最长公共子序列的长度为i的字符串有多少个？题解DP新套路刚开始想的时候，怎么定义状态都会造成重复等各种问题，于是搜题解。。。考虑求LCS时的dp：定义lcs[i][j]lcs[i][j]lcs[i][j]表示A串的前i位与B串的前j位的LCS长度lcs[i][j]=max{lcs[i−1][j−1]+1&nb...
2018-12-27 17:12:56
375
原创 【CodeForces553E】Kyoya and Train（DP+FFT+CDQ分治）
题目大意给一个有向图，有一个人要从111走到nnn，第iii号边花费的钱为cic_ici，花费的时间为111~TTT中随机的值，每种时间的概率为pi,jp_{i,j}pi,j，如果这个人在TTT时刻之后走到nnn，就要交XXX的罚款，求这个人花钱的最小期望。题解令dp[u][t]dp[u][t]dp[u][t]表示当前走到了u号结点，已经花费的时间为t，走到终点的最小期望代价。dp[u...
2018-12-25 20:27:55
281
原创 【CodeForces793E】Oleg and chess（扫描线+线段树+网络流）
题目大意给一个n×n (n≤10000)n\times n\ (n\leq 10000)n×n (n≤10000)的棋盘，有q (q≤10000)q\ (q\leq 10000)q (q≤10000)个不相交的矩形区域不能放棋子，在剩余的格子里最多能放多少个车，使得他们无法互相攻击。题解十分综合的题目如果nnn很小，对每一个横坐标和纵坐标建立一个结点...
2018-12-25 20:00:35
310
原创 最小费用流——原始对偶(Primal-Dual)
EK算法的改进版，不知道名字（也许是ZKW？？）EK算法EK算法就是不断的用SPFA寻找一条最小费用的增广路径，直到无法增广为止。改进类似于Dinic，先将结点用到汇点T的最短距离标号，每次只走dis[v]==dis[u]+cost[u-&gt;v]的边进行增广，保证了费用最小。在这种情况下，就可以类似Dinic，同时增广多条路径。细节较多，见代码及注释代码#include&lt;...
2018-12-25 09:17:59
3687
4
原创 【CodeForces908H】New Year and Boolean Bridges （FWT）
题目大意对一个有向图(1≤n≤47)(1\leq n\leq47)(1≤n≤47)，定义f(u,v)f(u,v)f(u,v)的值为true，当且仅当存在一条路径使得uuu能走到vvv给一个“邻接矩阵”A[i][j]A[i][j]A[i][j]：如果A[i][j]=='A'，则f(u,v) and f(v,u)为true如果A[i][j]=='X'，则f(u,v) xor f(v,u)为tr...
2018-12-23 11:44:43
290
原创 【AtCoder2387】+/- Rectangle
题意构造一个H×WH \times WH×W的矩阵，满足一下条件所有元素为整数，且属于[−109,109][-10^9,10^9][−109,109]所有元素和为正数对每个h×wh \times wh×w的子矩阵，它的元素和为负数题解根据样例，最朴素的想法即为，给满足x mod h=0x\ mod\ h=0x mod h=0且y m...
2018-10-02 20:58:49
498
原创 【AtCoder2376】Black and White Tree（博弈）
题意A和B轮流给树上的结点染色，A每次选择没染过的点染成白色，B每次选择没染过的点染成黑色，最后若所有白色都与黑色相邻，则B胜，否则A胜。双方以最优策略，求A胜还是B胜。题解A首先选择叶子结点的父亲u，则B只能选择叶子结点（否则叶子节点染白后，永远不可能与黑色相邻），所以，如果存在u有两个以上叶子结点，则A胜；然后删去u，则u的父亲v，如果v没有了子节点，v就成为新的叶子结点，A可继续先前...
2018-09-30 21:46:22
256
原创 【AtCoder2307】Tree Game（博弈）
题意有一棵树，每个结点上有A[i]个石子，A开始把一个棋子放在任意一个结点上，然后由A开始，A,B轮流操作将当前棋子的结点石子数减1将棋子移动到相邻的结点上不能操作者输求A开始把棋子放在哪儿保证能赢。题解性质：棋子不会往比自己石子多的地方走（如果这样走，对方可以再走回来，自己就少了一颗棋子，对方又比自己多，打消耗战打不赢的。。。）然后就可以直接模拟计算NP状态枚举一个点作为起点，...
2018-09-25 22:01:24
275
原创 【AtCoder2306】Rearranging（拓扑）
题意黑板上有n个数，A首先按照自己的意愿将n个数重新排列(可以是原来的顺序),然后让B进行如下操作:选择一对相邻且互质的数,交换它们的位置.(这个操作B可以进行无数次.)A想要这个序列的字典序尽可能小,而B想要这个序列的字典序尽可能大。两人都采取最优策略的情况下,最后形成的序列是什么样子的.题解发现不互质的数，只要在一开始A放好后，顺序就固定下来，无法改变。为了使得字典序最小，我们对...
2018-09-25 21:55:37
313
原创 【AtCoder2305】Decrementing（博弈）
题意黑板上有n个数，它们的最大公约数为1.于是A和B决定玩一个游戏，两个人轮流进行操作，A先手。从黑板上的数选择一个不小于2的数，把这个数减去1，然后对于这n个数，除以他们的最大公约数.当一个人无法操作时便输了。求先手是否必胜。题解定义状态1：有奇数个偶数，奇数至少一个定义状态2：有偶数个偶数，且奇数个数≥2定义状态3：有偶数个偶数，奇数一个所有数都为1，为必败态，属于状态2状态...
2018-09-25 21:36:19
296
原创 【AtCoder2304】Cleaning
题意一棵树有n个节点,节点i有A[i]个石头。将石头全部移除。对于每次移除石头的操作,选择两个叶子节点(u,v)(u不能等于v),移除u到v路径上的每一个节点的一块石头(包括u,v).注意:如果这条路径上有一个节点没有石头,则不能进行操作.（此处的叶子节点为度数为1的节点）能否通过上述操作将树上的石头移完.题解寻找一个度数大于1的结点为根，dfs下去，每次返回，这棵子树上还需多少次操作...
2018-09-25 19:11:21
221
原创 【AtCoder1984】Wide Swap (拓扑排序转化)
题意给一个(1~n)排列A，你可以做任意次操作，选择两个位置i，j，且∣i−j∣≥K|i-j|\geq K∣i−j∣≥K且∣Ai−Aj∣=1|A_i-A_j|=1∣Ai−Aj∣=1，然后交换AiA_iAi，AjA_jAj。求以此操作得到的最小字典序排列。题解用pos[i]表示值i所在位置，题目操作在pos上即为：选择相邻两个数，且这两个数差大于等于K，交换这两个数。容易发现两个个性...
2018-09-22 22:04:24
419
原创 【AtCoder1983】BBQ Hard （组合数+巧妙模型转化）
半题解输入A[i],B[i]，求∑i=1N∑j=i+1NCAi+Aj+Bi+BjAi+Bi\sum_{i=1}^N\sum_{j=i+1}^N C_{A_i+A_j+B_i+B_j}^{A_i+B_i}i=1∑Nj=i+1∑NCAi+Aj+Bi+BjAi+Bi题解CAi+Aj+Bi+BjAi+BiC_{A_i+A_j+B_i+B_j}^{A_i+B_i}CAi+Aj+B...
2018-09-22 21:26:51
297
原创 【AtCoder1981】Shorten Diameter（图论思维）
题意给一棵树，要求删去最少的点，使得树联通且直径小于等于K(N<=2000)题解简单的问题也容易想复杂。对于K为偶数，枚举一个点，将距离此点>K/2的全部删掉即可满足条件，取删点数最小值。对于K为奇数，枚举一条边，树被此边分为两棵，将其深度>(K-1)/2的全部删掉，取删点数最小值。考试时想复杂了：把直径求出，然后试图从直径两头删点，包含大量特殊情况。。。死路一条...
2018-09-22 21:16:13
409
原创 【AtCoder2000】Leftmost Ball （DP+组合数）
题意Snuke喜欢五颜六色的球。他总共有N×K个球，有N种颜色，每种颜色的球有K个。颜色编号为1到N。他将按照任意顺序排列所有球。然后，对于每种颜色，他将该颜色的最左边的球涂成颜色0，颜色0不同于N种原始颜色中的任何颜色。如将球排列为(1,2,1,2)，染色后就变为 （0,0,1,2）。 所有操作后，球的颜色序列有多少种，求这个方案数mod 10^9+7。题解发现一个性质：对任何前缀...
2018-09-17 10:43:28
296
原创 【AtCoder1998】Stamp Rally（整体二分+并查集）
题意我们有一个N (3<=N<=10^5)个结点和M(N−1≤M≤10^5)个边的无向图。 结点编号为1到N，边编号为1到M。边i连接结点ai和bi。保证图连通。在这张图上，Q(1≤Q≤10^5)对兄弟正在参加一项名为Stamp Rally的活动。 第i对Stamp Rally如下： 一个兄弟从结点xi开始，另一个从结点yi开始。(1≤xi < yi≤N) 两个兄弟沿着边...
2018-09-17 10:35:17
456
原创 【AtCoder1980】Mysterious Light（数学模拟）
题意有一个边长为 N(2<=N<=10^12)的由镜子组成的等边三角形，设结点为a,b,c，从ab上取一点p，使得ap=X(1<=X<=N-1)，从p水平向右发射一条神秘光线，经过若干次反射，回到p点。这条神秘光线有一个特点，他会在他走过的路径留下一条反射镜（光线会被自己走过的路线反射），求最后回到p点时，光线移动的距离。 题解发现光线总是在一个平行四边形里走...
2018-09-17 10:26:59
307
原创 【NOIP2016 D1T3】换教室（期望DP+Floyd）（究极思维陷阱！）
题目大意给出一幅 v 个点的无向图，表示教室及其连边。 有 n 个时刻，每个时刻正常要到教室 c[i] 上课，如果该时刻有申请更换，则到教室 d[i] 上课。 你只能在一切开始之前提交申请，且最多申请换 m 个时刻。第 i 个时刻申请成功的概率为 k[i]。 求移动路程的期望最小值。题解首先用floyd把任意两点 定义dp[i][j][0/1]为从第i个时刻之后开始，...
2018-09-12 19:47:20
204
原创 Rabin-Miller素数测试
本文不证正确概率，因为我不会 判断大整数是否为质数前提定理费马小定理：若 nnn为质数，a<na<naan−1≡1 (mod n)an−1≡1 (mod n)a^{n-1}\equiv 1\ (mod\ n)；若任意整数xxx满足ax−1≡1 (mod x)ax−1≡1 (mod x)a^{x-...
2018-09-04 20:27:40
1229
原创 模线性方程组（中国剩余定理+通用解法）
求解 ⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪x≡a1 (mod m1)x≡a2 (mod m2)x≡a3 (mod m3)...x≡an (mod mn){x≡a1 (mod m1)x≡a2 (mod m2)x≡a3 (mod m3)...x≡an (
2018-09-03 16:16:17
1311
原创 欧拉定理及扩展（附证明）
若(a,m)=1(a,m)=1(a,m)=1，则满足aφ(m)≡1&amp;amp;nbsp;(mod&amp;amp;nbsp;m)aφ(m)≡1&amp;amp;nbsp;(mod&amp;amp;nbsp;m)a^{\varphi (m)} \equiv 1\ (mod \ m)证明设与m互质的数为b1,b2,b3,...,bφ(m)∵(a,m)=1∴ab1,ab2,ab3,...,abφ(m)都与m互质，且每个数均不
2018-09-02 20:27:23
3824
3
原创 【CodeForces1019E】Raining season（边分治+斜率优化）
题目大意有n个结点的一棵树，每条边有两个权值a,b，第t天经过第i条边花费时间ait+bait+ba_it+b，给定m，求t=0,1,2...m−1t=0,1,2...m−1t=0,1,2...m-1时，最长的路径长度。题解简介边分治类似点分治选择重心，边分治选择一条边，把树分成两边，使得两边的点数最接近。 但对普通的树进行边分治容易退化，如下面这种图会退化为O(n)O(n)O(...
2018-08-19 20:42:03
1252
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人