beckyUp

分类

--------------作业---------------(4) ACM算法(15) c++(16) codeforces(8) CSP(2) fft(1) java(8) java图像(1) KMP(4) tcp/ip(4) 二分(5) 二分图匹配(1) 分块(1) 分治(2) 前缀和(2) 动态规划(18) 区间dp(3) 博弈(2) 后缀数组(1) 图论(8) 字典树(1) 字符串(8) 小技巧(9) 并查集(2) 感悟(13) 操作系统(2) 数据库(3) 数据结构(22) 数论(10) 未归档(7) 构造(2) 树形dp(1) 水题(22) 状压dp(2) 脑洞(1) 自然语言处理(2) 计算几何(5) 计算方法(4) 读书笔记(2)

/ 注册

全部文章（共224篇）

code forces 894C [分割构造gcd]

题目大意给你一串序列，序列中的每一个数都为一个原始序列中的某一个连续子序列的GCD 让你构造一个原始的子序列题解，这个题对于构造一个原始的子序列，我们很容易发现，如果里面最小的那个数不是某一个数的GCD的话，那么必然构不成这样一个序列，但是我们发现如果要构造一个序列，其中不同的连续子序列的G...

2017-11-20

0 477

codeforces 894B

题目大意：给定一个m*n的方格，在其中放入1或者-1 使得每行每列的乘积都为K 问有多少种放法思路：解法其实只有一句话，但是我想说的是，我真的想了很久没有想到这个角度，之前的时候Trader说想复杂了，其实很简单，但我觉得并不是的，并不是想复杂了的问题，而是角度的切入有问题，我之前一直想不出来是...

codeforces

2017-11-20

0 372

JNU校赛 K 【贪心+数据结构水题】

题目 CTG(Cun Tou Gaming) 是我校的一支 LOL 战队，他们参加比赛总是可以拿到冠军，因为每次都只有他们一支队伍参赛，所以只需要去签个到就可以直接夺冠并领取奖金。现在有 n 场比赛可以让他们选择，每场比赛都有各自的截止日期 d 和奖金 r ，而 CTG 战队必须在截止日期之前（包...

2017-11-20

0 429

codeforces 888E Maximum Subsequence

题目大意：这道题目给了一个序列和给定的m ，要求在这个序列中求若干个数使得他们的和对m取模后最大，然后数据量给定的是35 题目分析：开始的时候，想到对于求和取模最大，感觉并没有什么可以找的规律，唯一的方法就是暴力，但是对于35个数来说，每个数都有取或者不取的可能，2^35远远超过了时间上限，所...

2017-11-15

0 500

codeforces 870c 大数分裂

将一个数尽可能多的分解成若干个合数的和，很显然，要尽可能多，自然是越小的越多越好，首先对于一个奇数来说，拆出一个9就能变成一个偶数，而且只有一个9 的时候一定是最优的情况，对于一个偶数来说，4一定越多越好，如果不能完全被4整除，那么就将4替换成6就行了，这样我们就能将一个数分裂成若干个合数的和 #...

2017-10-22

0 542

区间求差 hihocoder 1305

题目大意：给定 A B两个区间，求在A区间不在B区间的线段长度这个题一开始的时候想用线段树做，但是耗内存太多了，后来发现我们对一个区间标记他的左右端点，遇到左端点+1，遇到右端点-1，这就可以判断某个点是否在区间内，同样这道题也用这样的方法，把所有的端点排序，当某一个端点在A内不在B内的时候，...

2017-10-21

0 346

图论练习-有向图的强连通分量【tarjan】

这周刚刚看了图论的一些东西，感觉自己理解比较费劲，所以这里小小总结一下，如果有误，欢迎指出好了，现在我们来看一下图论的一些基础的概念：有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连...

2017-10-20

0 715

lightoj 1030 - Discovering Gold[期望]

题目大意：起始位置是1，从1走到n，给你一个骰子（6个面），按点数走，收集每一点上的金子，如果你将要走到的位置在n之内，就继续扔，往前走，如果在n之外，就一直扔到合适的位置为止，求到达n点时的期望分析：这个题是一个求期望的题，那么值得注意的是，当扔在n之外的情况是无效的，所以我们在位置 ...

dp

2017-10-16

0 422

二分图匹配Hopcroft-Carp算法介绍

我们在做二分图匹配的时候，最喜欢选择的就是匈牙利算法，但是我们可以知道匈牙利算法的复杂度是O(n*e),那么如果对于一个点和边比较多的图，匈牙利算法很容易超时，所以我们采用Hopcroft-Carp算法来解决这个问题，这个算法能够在 O（sqrt(n)*e）的复杂度内实现二分图匹配。下面我就来讲...

2017-10-13

0 562

hdu 2819 Swap [二分图匹配]

这道题其实是一道比较简单的题，但是我之前WA了一个晚上，简直不敢相信，当然也是我太想当然了，其实之前的写法有很大的问题，小数据就测不出来问题，所以反思一下，还是要谦虚，仔细啊。。这个题就是给你一个N*N的一个由0和1组成的图，然后让你通过交换行和列把他编程斜右下对角线上的元素都是1的情况，问你能...

编程

2017-10-13

0 336