haha593572013-CSDN博客

原创 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 1514

原创 ACM核武器

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

2015-06-05 22:25:58 3455 4

原创 srm 583

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

2014-02-07 23:11:56 1559

原创 SRM 582

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

2014-02-07 02:57:05 1650

原创 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 1650

原创 srm 605

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

2014-01-24 23:52:56 1475

原创 SRM 555

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

2014-01-18 23:45:19 1283

原创 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 1138

原创 SRM 603

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

2014-01-07 14:59:18 1572

原创强连通分量的Kosaraju算法

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

2013-12-29 22:44:25 1499

原创 SRM 601

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

2013-12-23 18:43:17 1481

原创 SRM 600

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

2013-12-22 09:37:37 1571

原创 Codeforces Round #219 (Div. 1)（完全）

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

2013-12-18 20:05:01 1390

原创 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 1625

原创 Codeforces Round #209 (Div. 2)

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

2013-11-03 03:00:51 1720

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

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

2013-10-16 15:22:26 2414

转载嗯，我是一个偏执狂。

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

2013-09-24 17:22:52 2055 2

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

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

2013-09-16 03:44:24 2442

原创 Codeforces Round #199 (Div. 2)

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

2013-09-10 18:28:00 1623

原创 Codeforces Round #198 (Div. 1)

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

2013-09-05 22:20:43 1209

原创为什么我们同时搞acm，结果是你就可以去final

“为什么我们同时搞acm，结果是你就可以去final，我就。。。。”“我在有一定基础之后，就不看解题报告了”

2013-08-28 15:53:53 3603 1

原创 hdu 1007 最近点对问题（Splay解法）

为什么要写这个题、、经典啊，当然，别以为我用分治做的，不过主要思想还是那神奇的六个点共存（一个h*2h的矩形中最多能放下多少个点使得两两距离不超过h）其实我是在这里看到的http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep排个序，然后扫描过去，每次确定Y的范围，暴力找每个点（其实这是O(1)

2013-08-24 18:46:00 1224

原创 ABBYY Cup 3.0 - Finals(总结)

题目链接D题真的有点难写，，，不过写完后发现，也还行（我冒着可能万劫不复的心态研究了下tourist的代码），尽管如此，写的时候还是感觉各种不顺，还好1A了，不过肯定得重写，。这种题非常锻炼代码能力。这场比赛如果参加的话能暴涨啊。虚拟比赛的时候很快就做完了A B C ，然后D题不会做，暴力懒得写，写了的话估计还能涨点。A题：题意：给你一个序列，让你挑出一个子序列，子序列的两端必

2013-08-22 21:58:07 1851 2

转载 vim 常用快捷键！！！！

http://www.cnblogs.com/sld666666/archive/2010/04/05/1704462.html光标移动指令 1. h 左2. l 右3. k 上4. j 下5. Ctrl+f 向前翻页6.Ctrl+b 向后翻页7. 0 行首8. 移至行首第一个非空白字9. $ 行尾10.G

2013-08-19 21:27:19 876

原创 zoj 3164 分组背包 + 各种背包

把所有的背包结合起来的一道终极背包题，做了的话背包一般就没问题了题意：给你n个种类的物品的描述，背包容量D每个种类有三个属性 K E PK表示这类物品最多可以选多少个，如果为0表示可以选无限多个E表示选择这类物品每个物品的价值P表示每个物品的花费如果单纯是这样，那这道题目就太水了，直接多重背包就ok了所以题目又加了点，而这一点想了我n久啊题目还将一些种类的物品分了

2013-08-19 18:58:45 849

原创 codeforces 127 div2

第一题我还写了一个dfs暴力--!实在是太水了，第三题一直错，赛后发现忘了特判x=3时的情况，第二题最后时刻一气呵成，无奈时间过了。。。。。啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！！！！！！！！！！！！！！！！！！！结果自然名落孙山。但是有句话说的好失败是成功他妈

2013-08-19 18:58:27 744

原创有更新浙大月赛 ZOJ Monthly, June 2012 on June 24

zoj 3611 同类型的题目poj 2688化简模型即可得这样的问题，一幅图给定起点终点，求起点到终点最多经过几个点，如果两种方案经过的点数相同，选路径总长短的注意，这幅图最多只有12个点，所以立刻可以想到用状态压缩来做dp[i][j]表示以i为终点的路径为j状态（经过了那些点）时的最短路径ps:在预处理最短路的时候不要将'$'算进去，就看成一个普通的可以走的格

2013-08-19 18:58:25 862

原创 Codeforces Round #124 (Div. 2) （Div.1）

ps:D题挂了，最后只有三个。。。。E题是赛后看着一群大神的代码YY的（网上找不到题解，好奇怪，肿么都没人写的）之所以这么迟是因为一直在纠结E题A:如果第一个人能放，那就放在中间的位置，然后第二个人不管放哪第一个人总有对称的放法B：水题C：简单贪心，错了一次D:给你一幅图，假如在地板上铺上无限的同样的图，判断从S出发能否走到无限远的地方只需要判断能否从一幅图的一个

2013-08-19 18:58:11 746

原创 Never underestimate the heart of a champion

The 1995 Rudy Tomjanovich-coached Houston Rockets basketball team were defending NBA champions, but they entered the NBA playoffs with a low seed after a poor regular season. The Rockets went on to de

2013-08-19 18:58:09 3064

原创 codeforces 123 div2

前两题做的还算快，可是最后却没有出题了，原因是题目都看不懂，特别是D题，真想骂几句，这神马意思啊最后由于做的比较快居然还涨rating了， ——！E题，并查集的带权合并 w[x]表示x到根的权值和在find的时候合并掉View Code #includeconst int maxn = 100010;const int mod = 1000000007;int

2013-08-19 18:58:04 888

原创 codeforces 122

A : 暴力枚举B：找规律，也可以用数学方法找最小的x使得 a*x%b == 0 a,b已知(a=4*n b=n+1)x是所走的圈数，易得只要把x只要等于 b/gcd(a,b) 就满足了然后答案就是a*x/b 即a/gcd(a,b)还要加上1，因为出发前就在1的位置走了一步了所以答案： a/gcd(a,b)+1;B题开始太草率了，被人黑了，于是又回来看

2013-08-19 18:57:55 733

原创 codeforces 121 （比赛） codeforces 191C

哎，CF终于变色了A题：我写了个二分，囧。。。B题：模拟题，水C题：想了半天，水王（一学长）告诉我是DP，果断敲了dp[i][j]表示i字符走到j字符最大的权值View Code int dp[30][30];int max(int a,int b){ return a>b?a:b;}int main(){ int n,i,j,k;

2013-08-19 18:57:48 996

原创 CF 4 练习

ABC水题 D：n个二元组，求最长的一个序列组seq,序列的每一个元素的两个值都分别大于前一个元素记忆化搜索或者筛选后DP都可以两种方法View Code #include#include#includeset>#includestring>#include#include#include#includeusing names

2013-08-19 18:57:39 698

原创 Codeforces Beta Round #3 练习

A:裸的广搜题，需要输出路径 B:贪心抓住题目的特殊性，每个物品只有1 2 两种体积先按性价比排序，贪心的优先选择性价比高的，某次选了之后体积超了，就剪掉这样子遍历一遍之后还不是答案因为可能会有1体积的空位，而可能通过去掉已选集合中某个1体积的物品，再用一个2体积的物品替代达到更优解所以这里要判断一下View Code #include#include#includ

2013-08-19 18:57:37 707

原创 Codeforces Beta Round #2 练习

A题：模拟题，仔细点就好B题：DP给你一个数字矩阵，要求从左上角走到右下角的一条路径，这条路径上的数乘起来后末尾的0的个数最少末尾的0是由2、5产生的，于是联想一下是不是走2最少的一条路或者5最少的一条路就ok了呢？嗯，就是ok的.*_*假设从左上角走到右下角走过的数含因子2的最小的个数是x，5的最小的个数是y，则答案是min(x,y)，即最优解x、y的个数中有一项是最少的

2013-08-19 18:57:30 624

原创 Codeforces Beta Round #1 练习

A 大水题B 模拟题，要很小心，注意细节处理 C 给你在一个正多边形上的三个点，判断这个多边形的最小面积。由于这个多边形最多只有100条边，可以直接枚举多边形的边数计算是否满足判断是否满足：三个点组成的三角形的每个角是圆周角的整数倍判断整数的时候精度不宜太大View Code #include#include#include#includ

2013-08-19 18:57:27 691

原创 codeforces 练习 ---- CF 24

A 给你一个环，环上的每条边都有一个方向，按某个方向（顺时针或逆时针）走一遍，把与行走的方向相反的边反向，并加上相应的费用，判断走哪个方向的费用比较少直接dfs搞即可View Code #include#include#include#includeusing namespace std;int out[110];vectorint> edge[110

2013-08-19 18:57:21 804

原创后缀数组论文推荐题

先是论文中的一个模板View Code /*后缀数组模板rank[0~n-1] : 值域： 1~nsa[1~n] ; 值域： 0~n-1height[2~n]: suffix[i-1]与suffix[i]的最长公共前缀suffix(i-1) 与 suffix(i)是排名相邻的两个后缀height[1]无意义*/#include#include#i

2013-08-19 18:57:00 794

原创树的直径（最长路）的详细证明

主要是利用了反证法：假设 s-t这条路径为树的直径，或者称为树上的最长路现有结论，从任意一点u出发搜到的最远的点一定是s、t中的一点，然后在从这个最远点开始搜，就可以搜到另一个最长路的端点，即用两遍广搜就可以找出树的最长路证明：1 设u为s-t路径上的一点，结论显然成立，否则设搜到的最远点为T则dis(u,T) >dis(u,s) 且 dis(u,T)>dis(

2013-08-19 18:56:17 692

原创与树相关的题目树形DP 总结，不断汇总中

hdu 1561 The more, The Better 树形DP入门利用分组背包的思想#include#include#includeusing namespace std;int dp[250][250];vector edge[250];int n,m;int val[250];int max(int a,int b){ ret

2013-08-19 18:56:14 950

空空如也

空空如也