8 haha593572013

尚未进行身份认证

暂无相关简介

等级
TA的排名 3k+

gcd and exgcd

数论入门基础最大公约数问题1给定平面上的两个格点P1=(x1,y1)P1=(x1,y1)P2=(x2,y2)P2=(x2,y2)求线段P1P2上有几个格点−109<=x1,x2,y1,y2<=109-10^9<=x1,x2,y1,y2<=10^9解法1枚举所有的合法的min(x1,x2)<=x<=max(x1,x2)min(x1,x2)<=x<=ma

2017-07-01 21:19:00

ACM核武器

工欲善其事必先利其器,给大家介绍一下ACM里面常用的一些工具,平台,作为第一发福利。 各种强大的编辑器+codeforces平台+topcoder平台有什么问题欢迎留言。问题一:如果发现arena打不开那么打开控制面板->java->常规->设置,点击删除文件或者下载这个,解压后点击run.bat运行即可。1:codebloc

2015-06-05 22:25:58

srm 583

500:最多50个点的一棵树,每条边代表一盏灯,有两种状态,开或关,还有两种属性,重要或者不重要定义一种操作是选择一条路径,将路径上的边的开关状态取反。问最少需要多少次操作才能使得每条重要的边都处于开的状态。显然,所有的不重要的边都可以合并起来,然后搞成一棵新的树,每条边都是重要的,然后再YY一下,每条已经开的边不需要被覆盖到了,因为取反后还是要取反回来的,这样跟不去取反是一样的,所以现在

2014-02-07 23:11:56

SRM 582

250:最大的最小,最小的最大之类的题。。二分+验证600:是个好题,整了好几天才整明白。题意:给你n个数123。。n,代表n个楼,每个数有一种颜色,数值就代表building的高度,

2014-02-07 02:57:05

srm 581

250:一个模拟题,我一眼不会做,哈哈500:给你最多300个点的两棵树,然后tree1的每一个点分别与tree2的每一个点相连,形成一副图,求这副图中长度为K的环的个数的期望。K所以直接暴力求出Count[i]表示长度为i的点对数量就好了。答案就是Sum(Count1[i]*Count2[K-2-i]*2*(n-2)!)/(n!) #in

2014-02-02 00:28:19

srm 605

250:有最多50个物品,每个物品有一个type标号,并且有一个taste值,现在要求选择若干个物品使得x*y最大,x为选择的物品种类的总数,y为总的taste值之和贪心,然后对于每种物品,如果有大于0的物品存在,就不要小于0的那些了,因为他们不能增大x,只会减少y。如果某一种物品只有小于0的,那就只可能选择一个绝对值最小的。按照每种物品能选择的值从大到小排序,枚举种类数贪心算即可。。

2014-01-24 23:52:56

SRM 555

呜呜呜。。。。最近感觉头脑迟钝啊255:给你一个01序列,问你最少能将其分成几段,使得每一段都不含前导0且都是5的幂次一开始我是建了个最短路跑,后来发现两个循环其实就可以搞定了。类似于dp,从前往后更新,没发现一段区间合法就更新当前的dp值importjava.math.*;importjava.util.*;publicclassCuttingBitString{

2014-01-18 23:45:19

SRM 551

250:sb题450:一只狼,一开始为颜色0,每次会挑当前所能变到的颜色中最小的一种颜色变过去,给你一个颜色变换的矩阵,s[i][j]为Y表示i颜色可以变成j颜色,否则不能,现在问你最少把几个Y变成N,能够使得颜色0能变成颜色n-1.转移方向不确定,可以直接用spfa的dp跑,dp[i]表示变到颜色i最少需要的代价。建个最短路也是可以的,某个点向他的邻接点建边,第一条边权为0,

2014-01-08 14:51:54

SRM 603

250:给一棵树,两个人玩游戏,轮流切断一条边,然后选择留下一个连通块,最后会剩下一个点,第一个人想最后剩下来的点的点权最大,第二个人想让他最小,问最后剩下的点的点权智商题啊,,,答案就是最大的叶子。。知道结果后,想想就清楚了。500给定nk,求有多少的长度为n的“字符串”对AB,满足A+C=C+B各种讨论之后可以得到AB是循环同构的(还是不影响大家的思考的

2014-01-07 14:59:18

强连通分量的Kosaraju算法

http://edward-mj.com/archives/455dfs真是神奇,大师们利用简简单单的深搜搞出了不知道多少神奇的图论算法。。图论问题就得往树的方向想,改天得好好做一些跟树相关的题目了。我在扯什么啊。。。/////////////////////////////////////////////////////////////////////算法的步骤是:1:先

2013-12-29 22:44:25

SRM 601

ORZ芒果爷!!!!!http://blog.csdn.net/merlininice/article/details/17496799250pt:刚睡醒就打开题目,题目都看不懂,最后才180分。。500pt不会,逗逼了整场。。update:  //////////////////////补题///////////////////////////////500pt

2013-12-23 18:43:17

SRM 600

250:题意:给你50个数,问你最少去掉多少数能使得剩下的数不可能具备子集S,OR起来为goal如果一个数不是goal的子状态,那么我们没必要删除他,所以我们只关心goal的子状态的数1:如果所有的数OR起来都没有到达goal,那么就是02:每个数都会贡献一些位,去掉1的个数最少的那一位就好了600:题意:给你一个14*14的01矩阵,现在要反转最少的网格使得矩阵至

2013-12-22 09:37:37

Codeforces Round #219 (Div. 1)(完全)

戳我看题目A:给你n个数,要求尽可能多的找出匹配,如果两个数匹配,则ai*2排序,从中间切断,分成相等的两半后,对于较大的那一半,从大到小遍历,对于每个数在左边那组找到最大的满足条件的数配对用一个变量移动一下就好了。这样的配对数量肯定就是最多的。因为1:如果左边那一半数量取少一点,比如取a1a2a3...ak(k那实际上ak+1ak+2..an/2这些数

2013-12-18 20:05:01

SRM 597div2 1K

题意:n1,2,3,4,5,6.。。n问你有多少个数字集合,不包含重复的数位好题数位dp预处理cnt【state】,然后背包注意11这种,本身重复的也不行#include#include#include#include#include#include#include#include#include#include#include

2013-11-24 02:38:40

Codeforces Round #209 (Div. 2)

A:一次搞定不可能,如果有边界上的点可以两次搞定,没有的话每一次就只能搞定一个角落了,所以答案不是2就是3B:for(inti=1;in;i++){if(k)printf("%d%d",i*2,i*2-1),--k;elseprintf("%d%d",i*2-1,i*2);}n+k-(n-

2013-11-03 03:00:51

为什么二分图的最大二分匹配数等于最小点覆盖数

md,昨晚上的tc500pt竟然能没做出来,说到底还是没有对算法有深入的理解。。。。2333333,不扯了。。我想说的是这里有一篇很详细的文章,不过感觉有点过于详细了。http://www.matrix67.com/blog/archives/116按照博文中所说,做完一次匈牙利算法后我们从右边的未选点出发,开始找增广路(显然已经找不到了),这个过程中会搜出一颗颗的交错树,起点都是未匹配点

2013-10-16 15:22:26

嗯,我是一个偏执狂。

http://davidzai.blog.163.com/blog/static/18712621200971293444516/很久没删日志了,把SPOJ那篇删了。其实对大多数事情都非常随意的,但对少数特别喜欢的事情就特别敏感。在ACM的云雾里我沦为一名空想社会主义者,总是情不自禁地希望这个环境无比美好。小时候觉得恩格斯脑子被门挤了,自己那么多钱还变卖家产闹革命,其实

2013-09-24 17:22:52

2013 ACM/ICPC Asia Regional Hangzhou Online(解题报告) 正在更新

hdu4745  TwoRabbits  求一个环形序列的最长双回文子序列,可以先在后面补一段来破环,但仔细观察可以发现这个题并不需要破环,比如 cdedcba fff  ab,可以将bafffab组合,然后前面剩下的还是回文的。hdu4747 Mex 此题太神,找了份代码研究了一下,边看又边思考,发现了单调性,然后果断涨姿势。 首先可以发现mex

2013-09-16 03:44:24

Codeforces Round #199 (Div. 2)

C: 可以避免用浮点D:推荐逐格递推法,想学的话去http://blog.csdn.net/crazy_ac/article/details/9819191E:Qtree5的弱化版,顺便问一句。。。CF真是没题出了么??这个题由于是弱化版,没有向qtree5那样对某个点的颜色取反,所以有一种简易的lct写法,我是跟小水大神学的。。学会了lct,我的splay写法也可以改观很多了

2013-09-10 18:28:00

Codeforces Round #198 (Div. 1)

E:给你n个数,每次可以拿出两个数,ab假设a然后问你这n个数能否变成只有两个数>0的序列。组合数学里面一开始就讲了一段话,先从小的case着手,然后归纳出问题的一般特性.这个题的话我们先考虑三个数的情况,如果三个数能够成功的将一个数变成0,那么n个数自然就可以了。事实上我们肯定可以将三个>0的数abc转换成ABC,满足a既然一次转换能够将最小值变小,那么经过若干

2013-09-05 22:20:43

查看更多

勋章 我的勋章
    暂无奖章