- 博客(1332)
- 收藏
- 关注
RSS订阅原创 协同过滤实现
推荐系统的描述对于电影推荐系统，记nn为用户的数量，mm为电影的数量，r(i,j) = 1表示用户 j 对电影 i 进行过了评价，y(i,j)就是它的分数。r(i,j) = 0 表示用户还没观看过这个电影，也没评分过。我们假设用户看过电影后，一定会给电影一个评分，如果没有给，默认评分为零。电影推荐系统的任务，就是根据用户的评分，预测出那些用户还未观看的电影的评分，从而把那些用户可能会给出较高评...
2018-07-21 16:33:28
802
原创 小Y的字符串（拓展KMP）
题目链接：https://www.nowcoder.com/acm/contest/127/D解题思路：拓展KMP，只要求出字符串b对字符串a每一个后缀的最长公共前缀即可#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <alg...
2018-07-10 17:56:09
475
原创 简单环
题目链接：https://www.nowcoder.com/acm/contest/114/C解题思路：状态压缩DP，把环拆成一条路径，设dp[i][s]表示当前路径中点的状态为ｓ，且当前路径的末尾为ｉ的方案数。为了使路径不重不漏，每次枚举一个编号最小的点ｖ作为起点，这样计算时因为一个环有两种拆成路径的方法，所以答案要除以2#include <iostream> #include...
2018-07-04 22:05:32
2802
原创 黑妹的游戏IV
题目链接：https://www.nowcoder.com/acm/contest/130/D解题思路：网络流，预处理出所有的（i，j）对和（p，q）对，源点S和（i，j）连容量为1的边，（p，q）和汇点T连容量为1的边，如果(i,j)和(p,q)可以同时选择则连容量为1的边。跑一遍最大流即可得出答案。边数可能很大，注意到（i，j）和（p，q）可以连边的条件是不互质，可以将质因子作为中间点，（i，...
2018-07-03 20:11:53
599
原创 ZOJ4027-Sequence Swapping
Sequence SwappingTime Limit: 1 Second Memory Limit: 65536 KBBaoBao has just found a strange sequence {<, >, <, >, , <, >} of length in his pocket. As you can see, each element ...
2018-05-03 22:19:20
1267
原创 UVA12294-RPG battles
题意：给你n和p，有n个敌人要打败，每个敌人有p1, p2, t1, t2, w1, w2, 代表如果你的p大于p2的话，那么将只花费t2秒，在p1和p2之间的话，就需要在t2到t1的线性比时间，w1代表力量加一药水的数量，w2代表力量翻倍药水的数量，要按顺序消灭敌人，求最短的时间。解题思路：dp，设dp[i][j][k]表示第i个敌人，此时j的力量的，w2药水的数量。有加一的药水肯定立马用掉，但...
2018-04-28 19:19:52
205
原创 小Y写文章
时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 131072K，其他语言262144K64bit IO Format: %lld题目描述 小Y写了一篇文章，他对自己的文笔很有自信，尤其是自己总结出了一套计算文章通顺性的公式。文章共N段，对于文章的每一段小Y对它都能计算出一个估值，而一篇文章的不连贯值定义为，现在小Y想要发布他的文章，但是编辑小Z让他加入一些广告，具体来说就是M段估值分...
2018-04-20 23:17:40
319
原创 序列变换
时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 131072K，其他语言262144K64bit IO Format: %lld题目描述 给定两个长度为n的序列，ai, bi(1<=i<=n), 通过3种魔法使得序列a变换为序列b，也就是ai=bi(1<=i<=n). 魔法1： 交换ai和aj，i!=j首先通过若干次的魔法1将序列a变换成序列c 魔法2： 对1...
2018-04-20 23:10:03
1111
原创 合约数
时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 131072K，其他语言262144K64bit IO Format: %lld题目描述 在埃森哲，员工培训是最看重的内容，最近一年，我们投入了 9.41 亿美元用于员工培训和职业发展。截至 2018 财年末，我们会在全球范围内设立 100 所互联课堂，将互动科技与创新内容有机结合起来。按岗培训，按需定制，随时随地，本土化，区域化，虚拟...
2018-04-20 23:05:24
396
原创 连续区间的最大公约数
时间限制：C/C++ 4秒，其他语言8秒空间限制：C/C++ 131072K，其他语言262144K64bit IO Format: %lld题目描述 给一个数列共n(n<=100,000)个数，a1,a2,...,an.(0<=ai<=1000,000,000).有q(q<=100,000)个询问。每个询问为l,r(1<=l<=r<=n).求gcd(al...
2018-04-20 00:30:50
1477
1
原创 The Maximum Unreachable Node Set
In this problem, we would like to talk about unreachable sets of a directed acyclic graph G = (V,E)G=(V,E). In mathematics a directed acyclic graph (DAG)(DAG) is a directed graph with no directed cycl...
2018-04-19 19:21:08
386
原创 Codeforces 39E-What Has Dirichlet Got to Do with That?
What Has Dirichlet Got to Do with That?time limit per test2 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard outputYou all know the Dirichlet principle, the point of which is ...
2018-04-15 22:18:53
407
原创 Codeforces 37E-Trial for Chief
Trial for Chieftime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputHaving unraveled the Berland Dictionary, the scientists managed to read the notes o...
2018-04-08 00:02:17
367
原创 Codeforces 37D-Lesson Timetable
Lesson Timetabletime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputWhen Petya has free from computer games time, he attends university classes. Every ...
2018-04-07 23:41:23
380
原创 Codeforces 38D-Vasya the Architect
Vasya the Architecttime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputOnce Vasya played bricks. All the bricks in the set had regular cubical shape. ...
2018-04-07 20:54:40
280
原创 Codeforces 38F-Smart Boy
Smart Boytime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputOnce Petya and Vasya invented a new game and called it "Smart Boy". They located a certai...
2018-04-07 20:47:37
352
原创 Codeforces 940E-Cashback
Cashbacktime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputSince you are the best Wraith King, Nizhniy Magazin «Mir» at the centre of Vinnytsia is of...
2018-03-16 21:51:30
377
1
原创 Codeforces 936B-Sleepy Game
Sleepy Gametime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputPetya and Vasya arranged a game. The game runs by the following rules. Players have a d...
2018-03-16 21:36:54
508
原创 Vijos1493-穿纸条
描述小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只...
2018-03-12 23:53:25
246
原创 Codeforces 935E-Fafa and Ancient Mathematics
Fafa and Ancient Mathematicstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputAncient Egyptians are known to have understood difficult concepts in m...
2018-03-11 22:05:59
364
原创 Codeforces 939E-Maximize!
Maximize!time limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a multiset S consisting of positive integers (initially empty). There are t...
2018-03-10 00:25:33
255
原创 回文树小结
回文树是一个用来解决回文串相关问题的数据结构。回文树由若干个节点组成，每个节点代表一个回文串。相比于manacher，回文树要显得强大的多，同样是接近o(n)的复杂度，回文树只需要多一点的空间，就可以实现许多用manacher实现起来非常复杂的功能，并且能解决很多关于回文串的问题。节点之间通过有向边连接起来，回文树中有两种类型的边：第一种类型的边上同时有字符做标记，比如：u和v通过带字符x通过带字...
2018-02-13 13:39:40
372
原创 树链剖分小结
树链剖分，简单的说，其实就是把一棵树拆成很多条链，然后变成一个序列，这样就可以把树上的问题转换成简单的区间问题，而区间问题我们可以用线段树和树状数组等等数据结构来维护。首先是一些必须知道的概念：重结点：子树结点数目最多的结点；轻节点：父亲节点中除了重结点以外的结点；重边：父亲结点和重结点连成的边；轻边：父亲节点和轻节点连成的边；重链：由多条重边连接而成的路径；轻链：由多条轻边连接而成的路径；其实，...
2018-02-13 12:58:53
226
原创 OpenCV-最大极值稳定区域MSER分析
最大稳定极值区域MSER是一种类似分水岭图像的分割与匹配算法，它具有仿射不变性。极值区域反映的就是集合中的像素灰度值总大于或小于其邻域区域像素的灰度值。对于最大稳定区域，通过局部阈值集操作，区域内的像素数量变化是最小的。MSER的基本原理是对一幅灰度图像（灰度值为0～255）取阈值进行二值化处理，阈值从0到255依次递增。阈值的递增类似于分水岭算法中的水面的上升，随着水面的上升，有一些较矮的丘陵会...
2018-02-12 23:08:35
9418
原创 OpenCV-利用颜色、形态学和最大稳定极值区域MSER实现车牌区域检测
要想提取车牌号，首先要定位车牌区域，本文分别三种方法用，即颜色、形态学和最大稳定极值区域MSER的方法，对车牌区域进行判定。说得是三种方法，其实并无多大的区别。方法一：利用颜色提取车牌区域的思路：1.求得原图像的sobel边缘sobelMat2.在HSV空间上通过对色调H、饱和度S、明度V进行约束条件的限制获得图像中满足车牌背景底色的区域，得到图像bw_blue3.通过对图像中每一个像素进行决策来...
2018-02-12 22:04:17
3317
原创 OpenCV-边缘检测算子Marr-Hildreth实现
二阶微分算子典型的是Laplace算子，LoG可以看成是一个高斯模板的拉普拉斯变换。LoG最底层的原理是二阶微分算子，也就是对原始图像求二次微分的边缘定位算法，当使用二阶微分算子的时候，其对边缘的响应是一个零交叉，而且能够判断出高灰度方向，但二阶微分对噪声的敏感度过高，需要平滑预处理。由于噪声点对边缘有一定的影响，所以更好的边缘检测器是LoG算子，它把高斯平滑滤波器和拉普拉斯锐化滤波器结合起来，先...
2018-02-12 19:54:40
2618
原创 OpenCV-边缘检测算子Canny实现
最优边缘检测方法所需的特性，给出了评价边缘检测性能优劣的3个指标：1.低错误率，即将非边缘点判定为边缘点的概率要低，将边缘点判为非边缘点的概率要低；2.高定位性，即检测出的边缘点要尽可能在实际边缘的中心；3.对单一边缘仅有唯一响应，即单个边缘产生多个响应的概率要低，并且虚假响应边缘应该得到最大抑制；Canny算法就是基于满足这3个指标的最优解实现的，在对图像中物体边缘敏感性的同时，也可以抑制或消除...
2018-02-12 19:11:08
548
原创 OpenCV-基本边缘检测算子Sobel实现
简要描述sobel算子主要用于获得数字图像的一阶梯度，常见的应用是边缘检测。原理算子使用两个3*3的矩阵（图1）算子使用两个3*3的矩阵（图1）去和原始图片作卷积，分别得到横向Ｇ（ｘ）和纵向Ｇ（ｙ）的梯度值，如果梯度值大于某一个阈值，则认为该点为边缘点 图1：卷积矩阵 ...
2018-02-12 17:27:44
1372
1
原创 OpenCV-基于傅里叶变换的旋转文本图像矫正实现
代码实现：int main(){ cv::Mat image = cv::imread("1.jpg", 0); if (image.empty()) return -1; //图像尺寸转换 const int nrows = image.rows, ncols = image.cols; //获取DFT尺寸 int crows = cv::getOptimalDFTSize(nro...
2018-02-12 16:40:17
1709
原创 数一数
时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld题目描述设s,t为两个字符串，定义f(s,t) = t的子串中，与s相等的串的个数。如f("ac","acacac")=3, f("bab","babab")=2。现在给出n个字符串，第i个字符串为si。你需要对，求出，由于答案很大，你只需要输出对 998...
2018-02-11 20:16:32
218
原创 Codeforces 920E-Connected Components?
Connected Components?time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an undirected graph con
2018-02-07 21:52:10
526
原创 Codeforces 920F-SUM and REPLACE
SUM and REPLACEtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet D(x) be the number of positive divisors
2018-02-07 21:44:46
263
原创 Codeforces 920G-List Of Integers
List Of Integerstime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLet's denote as L(x, p) an infinite sequen
2018-02-07 21:40:03
431
原创 Codeforces 919D-Substring
Substringtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a graph with n nodes and m directed
2018-02-02 15:04:07
292
原创 Codeforces 909E-Coprocessor
Coprocessortime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a program you want to execute a
2018-01-27 12:25:12
469
原创 Codeforces 912B-New Year's Eve
New Year's Evetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputSince Grisha behaved well last year, at New Y
2018-01-27 12:09:15
367
原创 Codeforces 912D-Fishes
Fishestime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputWhile Grisha was celebrating New Year with Ded Moroz,
2018-01-25 19:50:08
418
原创 Codeforces 912E-Prime Gift
Prime Gifttime limit per test3.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputOpposite to Grisha's nice behavior, Oleg, thou
2018-01-21 23:18:30
510
原创 Codeforces 915E-Physical Education Lessons
Physical Education Lessonstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis year Alex has finished schoo
2018-01-21 23:08:09
481
原创 Codeforces 916C-Jamie and Interesting Graph
Jamie and Interesting Graphtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputJamie has recently found undire
2018-01-20 16:23:31
631
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人