- 博客(414)
- 收藏
- 关注
RSS订阅
原创 NOIP 2017总结
NOIP一周以后CDQZ_GXOI队再一次重聚在机房，也许这是最后一次在机房看见大部分昔日的战友。与往日不同的是，大多数身旁的人都是省一，而本人并不是。 官方成绩是30+190=220分，也许历史上很少有人考出类似的分数（估计去年来考第一天都有100多分），就连hfu老师都又气又笑地问我：“你介(这)个第一天整(怎)么连山(三)~~~十分都考出来啦？！”。第二天破釜沉舟拼来一个正常的分数，...
2017-11-21 21:48:55
531
原创 期望dp小结
虽然我知道写了这篇总结之后说不定我还是不会期望dp，但是还是要收个尾，至少形式上要来一下，况且万一写着写着就想通了呢？先说一说如何求概率和期望：概率：到达当前状态的概率等于到达前驱状态的概率乘以到达当前状态的概率，即dp[now]=Σ(dp[pre]*p[pre][now])。期望：当前状态的期望等于所有{后继状态的输出值（期望）乘以其到达它的概率}之和，即E[now]=Σ(p1*E[
2017-10-30 19:16:37
1131
1
原创 bzoj 1977 （浅谈如何hack掉hzwer学长）（严格次小生成树）（LCA+kruskal）
传送门题解：（**以下内容出自代码有错但是过了bzoj评测的hwzer学长**）先求出最小生成树，要严格次小。枚举每一条非树边找俩顶点树链上的最大边（如果最大边相同与非树边边权相同则找次大边）然后更新最小增量。最大边和次大边可以通过树上倍增求出。下证hzwer学长和其他一些同学的错误，以hzwer的代码为例：void cal(int x,int f,int v){ int
2017-10-15 21:50:29
736
2
原创 再探深度学习序列模型 - 基于“melody/chord embedding“ + LSTM的旋律续写器
（最近想申一段实习所以特意来补一下blog233）春季Machine Learning和两位小伙伴Billy和Harry的期末项目–旋律续写。具体来说，任务是给定和弦走向和一段不完整旋律之后让模型续写旋律。用自己采集的极小的数据集(QAQ…)训出来效果一般般，大概最后生成十轮能出来一两段能make sense的旋律~paper原文如下：...
2021-08-31 16:06:32
337
原创 图神经网络（Graph Neural Networks）入门之Node Classification
又回来补DL的坑了，这次是关于一个相对较新的方向——图神经网络。之前想做melody/chord generation时听Computer Music方向的大佬Gus Xia教授随口提了一句可以用图神经网络。最近暑期跟Finance相关的研究又跟Knowledge Graph扯到一起，于是开始了解一点GNN~为什么要在graph的基础上跑neural networks？目的其实就是为了考虑entities之间的关系。李宏毅教授（的助教）的课中举的一个很贴切的例子：给定一部悬疑片的人物信息，需要预测凶手是
2021-03-24 21:38:55
1481
原创 NLP入门 - 基于Word Embedding + LSTM的古诗生成器
一共实现三个功能：1. 续写五言诗2. 续写七言诗3. 写五言藏头诗之前用这个做Intro to Computer Science的期末项目折腾太久，不想赘述，内容介绍及实现方法可参考期末presentation的slides：https://docs.google.com/presentation/d/1DFy3VwAETeqK0QFsokeBpDwyVkMavOjpckQKpc6XPTI/edit#slide=id.gb037c6e317_2_312训练数据来源：https:
2020-12-21 15:06:54
1213
4
原创 Deep Reinforcement Learning入门 - DQN/Policy Gradient实现LunarLander-v2
超参数设置参考：https://github.com/ranjitation/DQN-for-LunarLander/blob/master/dqn_agent.py之前CartPole照着Deeplizard的教程做给做废了，于是换了OpenAI - Gym另外一个小游戏LunarLander，尝试自己从零实现DQN。官方文档的描述如下：Landing pad is always at coordinates (0,0). Coordinates are the first two numbe
2020-12-20 11:53:28
2359
8
原创 Meta Learning入门之MAML实现Few-Shot Learning（Ominglot部分论文复现）
最近看了李宏毅老师的MAML课，尝试了一下自己implement from strach：关于Ominglot数据集的5-way 1-shot分类先挂一下参考的资源：李宏毅的Lectures：https://www.youtube.com/watch?v=EkAqYbpCYAc论文原文：https://arxiv.org/abs/1703.03400一篇知乎笔记：https://zhuanlan.zhihu.com/p/66926599用一句话概括MAML的灵魂，大概就是...
2020-11-11 22:13:59
1600
4
原创 基于PyTorch的GRU网络实现股票价格预测
参考：https://www.7forz.com/3319/根据Tushare的数据，用LSTM的变体GRU试着做一个股票价格预测，参考了上述博客的代码，大多数参数经过了调整。1. 用新晨科技（300542）的640天的收盘数据训练2. 在沪深A股代码中随机抽取50条用于测试3. 查看50条里面loss最大的一支股票，画出其数据与预测曲线（有明显误差但趋势大致相同）预测的结果比预期好很多，留个坑--Midterm考完回来研究解释......代码：# -*- coding: ut
2020-10-25 23:33:02
6032
9
原创 2020暑期旷视科技经历总结
三个月时间飞逝，暑假余额也所剩无几。很有幸到刘帅成博士带领的旷视科技成都研究院进行学习/实习，几个月来学到了太多，更重要的是见识到深度学习巨大的魅力和潜力，也结识了几位成研院优秀的算法研究员。最后几周花一些时间总结、吸收、实践一下之前收获的机器学习、深度学习相关知识。5月28号，以一个稍有一定算法基础，几乎毫无工程能力的小白来到天府软件园C区。在李海鹏师兄的推荐下花了两三周自学Andrew Ng的机器学习课程前七周的内容。这部分主要覆盖了机器学习的线代基础、逻辑回归、正则化、朴素神经网络（手推了一次后向
2020-08-18 17:21:47
819
原创 基于PyTorch的卷积神经网络（CNN）实现MNIST分类模型
最近第一次玩了一下Kaggle，用PyTorch手写了一个四不像的卷积神经网络（有一点Inception v1的结构），测试准确率约为99.2%# -*- coding: utf-8 -*-"""Digit Recognizer.ipynbAutomatically generated by Colaboratory.Original file is located at https://colab.research.google.com/drive/1sbq5hjhjO3I5jQQ
2020-08-18 15:41:14
459
原创 poj 3279 Fliptile（DFS）
传送门题意：给一个的网格，每个格子的颜色为0或1，每次操作会使自身以及上下左右四个相邻的格子的颜色翻转。问最少翻转几次可以使网格全为0。如果无法实现则输出impossible。题解第一段转自：https://www.cnblogs.com/caitian/p/5396946.html“如果从上到下搜索，当前行是否需要反转取决于上一行的状态，通过翻转当前行使上一行为0，而不是通过上一行翻转为0后，看当前行的状态判断自己是否需要翻转，否则还会继续影响上一行。所以枚举一下第一行所有的状态，搜索到最后一
2020-08-06 17:45:15
156
原创 AtCoder Beginner Contest 174 总结
翘了实时比赛，今天用virtual补一下......发现题变水了......怕是错失了一次上分机会。A,B,C略。D题每次交换尽可能远的一对"W......R"。E题二分答案，注意下边界初始化不能直接设成0，否则二分判断时除数太小精度爆炸。F虽然n还不小，但还是可以用莫队水过去（理论上大于3e9，2000ms有点危险），正解应该是主席树或者离线+树状数组。主席树空间开大点没毛病......A#include<cstdio>#include<cstring>#incl
2020-08-03 15:18:00
233
原创 Codeforces 622C Not Equal on a Segment（思维）
传送门题意：给一个长度为n的数组a，每次询问区间内是否存在和不同的数，如果存在则输出一个下标，否则输出-1。题解：想了想似乎在线/离线都不是很好搞，看了一眼题解也是绝了。记一个表示从第i位往右第一个与i不同的数。每次询问如果则直接输出，否则根据和的大小关系输出或者-1。复杂度为。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using names
2020-07-24 18:28:27
177
原创 hdu 6769 In Search of Gold（二分答案+树形dp）
传送门题意：给一棵n个点的树，每条边的有两个边权和，现将某m条边的长度设为对应的，剩下n-m-1条边的长度设为。问得到的树的直径最小为多少。。题解：二分一个mid，check能否使这棵树的直径不大于mid。每次check时，由于k不大，可以用二维的树形dp来搞，定义表示p为根的子树内让i条边选a且保证子树内最长简单路径不超过mid时，子树内离p最远的点与p的距离最小值（有点绕，通过合理选择a来使这个距离尽量短）。最后如果，就说明当前mid可行。从儿子v往当前点p转移的时候，一开始设为0，每转移一
2020-07-24 16:13:21
528
2
原创 基于Keras的人工神经网络（ANN）实现Fashion-MNIST分类模型
仿照TensorFlow官方教程中的Basic classification: Classify images of clothing，自己写一遍最朴素的人工神经网络来实现Fashion_MNIST分类模型。Coursera上学了快两个月理论终于有了个稍微像样的实操......import tensorflow as tffrom tensorflow import kerasimport numpy as npimport matplotlib.pyplot as pltfashi
2020-07-21 18:30:20
2114
6
原创 Codeforces 1373D Maximum Sum on Even Positions（线性dp）
传送门题意：给一个数组，问最多选一个子数组reverse一次之后最大的偶数位元素之和为多少。题解：选一个长度为奇数的子数组reverse不改变答案。所以考虑reverse一个长度为偶数的子数组。大致乱搞思想：默认取偶数位时，选某一段区间连续取奇数位，最大和位多少，以及默认取奇数位时，选某一段连续取偶数位的最大和。#include<cstdio>#include<cstring>#include<iostream>#include<algorith
2020-07-20 15:47:33
220
原创 Codeforces 580D Kefa and Dishes（状压dp）
传送门题意：有n道菜，要求按一定顺序吃m道，第i道菜吃了能获得的满意度，又有k条加成，第i条表示如果吃完第道后马上吃道可以获得的满意度。问合理安排可以获得的最大满意度为多少。题解：看数据范围盲猜搜索或者状压，一开始想着这最大可以达到，这状态数量肯定承受不了......后来发现对于某个二进制状态，对之后有影响的只有最后一道菜，所以记表示在st这个二进制状态下下，吃过的最后一道菜为i，能获得的最大满意度。从子状态转移时也要枚举一下子状态最后一道菜，复杂度为。#include<cstdio&g
2020-07-20 14:46:26
208
原创 Codeforces 979C Kuro and Walking Route（LCA）
传送门题意：给一棵n个点的树，给定。问有多少点对满足从沿最短路径从u走到v，不会先经过x再经过y。题解：根据x和y是否在一条链上判断一下，两种情况用子树大小算一下就行。x和y在一条链上等价于，所以求一下LCA来判断。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;typedef long long ll;
2020-07-17 17:48:52
329
原创 Codeforces 1156D 0-1-Tree（并查集）
传送门题意：给一棵n个点，边被黑白染色的树，问有多少对点对满足从x沿最短路径走到y，经过白边(1-edges)后不经过黑边(0-edges)。题解：开两个并查集，第一个只连黑边，第二个只连白边，讨论三种路径：①黑②白③黑转白。前两种在并查集merge的时候可以计算，第三种路径怎么搞？对于某个点x，经过它的第三种路径有条。为什么这么不会算重，因为树是没有环的（脑补一下似乎没毛病）。做完发现可以不用讨论，直接。减去那个1就是去掉(pos, pos)这条路径。WA了好久发现应该find的地方写成了
2020-07-16 18:28:19
190
原创 Codeforces 1139C Edgy Trees（并查集）
传送门题意：给一棵n个点，边被红黑染色的树，给定m，有多少种选法，选出可重集满足从走到，再从走到，......，再从走到（都走最短路径），至少经过一条黑边。题解：由于是最少经过一条黑边，直接算不好算，所以正难则反尝试算有多少种选法使得走下来只经过红边。显然这样选必须在某个只含红边的极大连通子图里选。于是只用并查集连红边，每次合并计算一下贡献即可，类似Codeforces 1213G。记计算出的选法有种，那么。#include<cstdio>#include<cstring&
2020-07-15 17:57:08
224
原创 Codeforces 519E A and B and Lecture Rooms（LCA）
传送门题意：给一棵n个点的树，m次询问，第i次询问有多少点到和距离相等（所有边长均为1）。题解：每次询问考虑路径上的中点，分中点是/不是LCA两种情况讨论一下即可。本以为这种要讨论的咋也得调一小会儿，结果居然1A......再加上懒得画图，所以贴个Codeforces的链接捡懒。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using names
2020-07-15 17:08:41
228
原创 Codeforces 1213G Path Queries（并查集+离线）
传送门题意：给一棵n个点有边权的树，m次询问，第i次询问有多少点对的简单路径上最大边权不超过。题解：直接在一棵建好的树上搞貌似不太可行...好像点分治可以莽一下？于是尝试离线做法，把询问从小到大排序，每次把边权小于当前询问的边都连起来，算一下合并联通块造成的贡献即可。我居然不是那个写点分的莽子（偷笑）....#include<cstdio>#include<cstring>#include<iostream>#include<algorith
2020-07-14 18:31:11
195
原创 Codeforces 495B Modular Equations（简单数论）
传送门题意：求有多少个解(x)。题解：无法直接枚举。可以看出如果一个x使得等式成立，那么b-a一定是x的倍数，于是枚举一下b-a的因子check一下（是否比b大）即可。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int a,b;inline int read() { int x=0,f=1;char
2020-07-14 17:33:14
200
原创 hdu 3555 Bomb（数位dp）
传送门题意：问1~n的范围内有多少个数包含连续数位“49”。题解：数位dp，重点考虑哪些状态是可以直接记下来的。如果定义f[pos][pre]来表示搜到第pos位，上一位是pre时之后的填法，那么可以此时不能确定49是否出现过，所以会WA。如果定义f[pos][pre][found]表示搜到第pos位，上一位是pre，当前出现过49（found == true）或者没出现过的填法，那么记忆化效率不高，会T。因为如果出现过49，那之后填什么效果都一样，可以压成一个状态直接return。所以可以定义f[
2020-07-13 15:32:12
176
原创 Luogu 2657 [SCOI2009] windy 数（数位dp）（模板）
传送门题意：略题解：略，挂一个洛谷日报关于数位dp的介绍注意：此题记忆化搜索时数组不光要记录pos还要记录pre（上一位填的数），因为上一位填比如说1和2，对当前位的答案有影响（这一位可以填的数的个数不同）。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>using namespace std;in
2020-07-13 14:50:16
190
原创 Codeforces 734E Anton and Tree（并查集+树的直径）
传送门题意：给一棵黑白染色过的树，每次操作可以将一块连通的同色子图（连通块内不含另一颜色）染成另一颜色，问最小需要操作几次才能将树上所有节点统一为同一颜色。题解：先用并查集缩点，把同一颜色的连通的缩成一个点，得到新树，然后直径上的点数/2即可。（从直径中间那个点开始染色，把同色的区间不断往直径两端扩展，这个过程中非直径上的点的颜色也会被统一）脑洞还是不够大....树的直径又没看出来诶#include<cstdio>#include<cstring>#includ
2020-07-10 14:46:49
138
原创 Codeforces 763A Timofey and a tree（思维）
传送门题意：给一棵n个点的无根树，每个点有一个颜色，问是否存在一个点使得以它为根时，每棵子树内颜色相同。题解：第一反应树形dp，想了想好像没法搞......树上分块这些好像也不行。看了一眼题解...这个想法真的是...一针见血...如果所有点颜色相同那输出YES再随便输个点就好。如果有颜色不同的点对，那么找一条两个端点颜色不同的边，如果他们两个都不能作为合法的根，那么答案是NO（别的任何一点为根，这条边所在的子树不满足条件）。否则答案为YES。复杂度为级别，真是......不知道该说啥...刁钻
2020-07-09 18:12:03
183
原创 Codeforces 1201B Zero Array（思维）
传送门题意：给一个长度为n的非负数列，每次可以选两个数同时减1，问能否将整个数列的数全部归零。题解：第一波猜结论猜错了（只猜中第一个必要条件“所有数之和为偶数”，也考虑过如果只有两个数那么必须相等）。其实再多想一步就可以发现如果有多个数，那么最大的那个数在不能超过剩下的之和。超过了的话这个最大数无法归零。现在想想如何证明不超过就一定可以归零。假设最大数为a，次大数为b，剩余的数之和为sum，剩余的数中最大的为c（原数列第三大），我们先用a“消耗”b（同时使a，b减1）直到b==c（这一步一定可以
2020-07-08 17:37:09
180
原创 Codeforces 220B Little Elephant and Array（莫队）
传送门题意：给一个长度为n的数列，m次询问，第i次询问到区间内有多少个数的出现次数等于它自己。n, m<=1e5题解：由于询问可以离线，所以用莫队。注意要先离散化，否则再开个map复杂度会多一个log，会TLE。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>#include<set>
2020-07-08 14:34:57
134
原创 Codeforces 827B High Load（构造）
传送门题意：构造一棵n个点，k个叶节点的树使得最远的两个叶节点的距离尽可能近。题解：由于叶节点个数的限制，可以先以1为根，用2到k+1这k个点与1连边，其他的点都塞到这k条边上。如何分配其他的点使最远的两个叶节点尽量近？尽量平均分就行，先往每条边上都加一个，有多的就再加一轮，直到所有点都在树上。正确性比较显然，也可以反证。#include<cstdio>#include<cstring>#include<iostream>#include<a
2020-07-07 18:01:31
193
原创 Codeforces 1092F Tree with Maximum Cost（树形dp）
传送门题意：给一棵n个点的无根树，每个点的权值为，每条边长度为1，选一个点使得最大，其中dist(i, v)表示i到v的简单路径的长度（n<=2e5）。题解：把n个点都算一次的复杂度为，所以先默认1为根（选为“v点”），然后考虑换根对答案的影响，从而两次dfs可以算出以每个点为v点的答案，在其中选一个最大的即可。适合中午昏昏欲睡的时候写的题......#include<cstdio>#include<cstring>#include<iostream
2020-07-06 14:29:45
282
原创 Codeforces 888E Maximum Subsequence（折半搜索）
传送门题意：在n个数里选m若干个使得它们之和mod m最大，n<=35题解：直接搜复杂度为会炸，所以尝试折半搜索，左右两边复杂度不超过，可以接受，搜出来的和记录在两个数组里，然后尝试凑出一个最大的。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;typedef long long ll;const
2020-07-06 13:37:43
176
原创 AtCoder Beginner Contest 173 总结
感觉这次出题怪怪的......做了5道但是感觉很不爽C直接暴力枚举状态然后check，D是一道蜜汁贪心，现在也不知道咋证明，E差不多就模板题，一个点被卡了精度还调了好久......F考了一点逆向思维？直接算不好算所以先算一开始一条边都没有的时候答案是多少，然后考虑每加一条边答案会减去多少，看起来像树形dp的一道题不到10行就弄完了......虽然确实挺巧的，但感觉AtCoder出题日渐趋向脑筋急转弯？A#include<cstdio>#include<cstrin.
2020-07-06 10:37:28
372
原创 Codeforces 721C Journey（DAG上dp）
传送门题意：n个点m条边的有向无环图，每走一条边消耗一定时间，问从1走到n，消耗时间不超过T的情况下最多经过多少个点题解：由于n，m范围不大所以对于这个DAG可以做的dp，定义f[i][j]表示走到i点，经过了j个点消耗时间的最小值，顺便开个pre数组记录一下转移路径。说一下坑点，首先这个题卡空间，边权和f数组都不能是longlong。而且1不一定是DAG入度为0的点，也就是说1不一定能走到所有点。所以要先将1不能走到的点的出边贡献给别的点的入度减掉，否则拓扑排序时有可能有些点入度始终无法为0导
2020-07-03 18:36:18
176
原创 Codeforces 1132F Clear the String（区间dp）
传送门题意：给一个长度不超过500的字符串，每次可以消掉字符串中连续相同的一个子串，消去之后剩下的两个串自动连在一起，问最少消多少次使字符串清空。题解：区间dp，一看应该使的但是第一把居然写出来个的。过了样例交上去果然WA了，原因是没有考虑最优解是讲原串分成若干子串的情况。所以转移时需要引入断点k，从而复杂度多一个n。比如6adabcb就可以卡掉这个会WA的算法（正解在后面）#include<cstdio>#include<cstring>#incl
2020-07-03 17:02:13
193
原创 Codeforces 1101D GCD Counting（点分治）
传送门题意：给一棵n个点的数以及n个点的点权，一条路径(x,y)合法当且仅当从x到y的路径上所有点权的gcd大于1（一条路径也可以是一个点），问所有合法路径经过的点的数量最大的经过了多少点。题解：就是求最长的合法路径再+1。这种在树上询问路径的可以优先考虑点分治。每次分治到一个重心，把每条链的链上gcd分解质因数，去和之前这些质因数对应的最大链长加起来再+1，然后这些质因数对应的最大链长都更新一下。注意每次先把一棵子树中的链记下来，先询问再更新（避免同一棵子树内的两条链更新答案）。还是要注意先加
2020-07-03 15:09:08
219
原创 Codeforces 1093D Beautiful Graph（二分图染色+组合数学）
传送门发这篇只是为了记录一个容易TLE的坑点：对于这种多组数据，所有数据n之和不超过3e5的题，初始化的时候要for 1 to n，而不能memset，否则比如30000组数据每组n为10，那么如果memset进行30000次的复杂度就会炸......#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;typede
2020-07-02 12:24:34
212
原创 Codeforces 1209D Cow and Snacks（并查集）
传送门题意：有n个点心，m个客人，每个客人有两个喜欢的点心，现需要给客人安排一定顺序，每轮到一个人，他吃掉所有剩下的他喜欢的点心（有一个吃一个，有俩吃俩）。一个都吃不到的人就会伤心。请问合理安排后最小的伤心人数是多少。题解：我们需要尽可能平均分配，就让每个人尽可能只吃一个（可以理解为重复利用一些点心？A吃了1，2，B吃了2，3相当于2利用了两次）。于是灵光乍现想到把每个客人看成一条边然后跑个最长路之类的东西？后来细想一下发现不对，如果这么建图，一个人会伤心当且仅当这条边两端已经被连通过，所以应该用并
2020-07-02 11:16:30
177
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人