博文

目前显示的是 六月, 2015的博文

[BZOJ 2301] Problem b【莫比乌斯反演/容斥原理/分块】

图片
[Description] 有n个询问(n≤50000),每个询问有五个整数a,b,c,d,k,求有多少个数对(x,y)满足a≤x≤b,c≤y≤d,且gcd(x,y)=k.(a≤b≤50000,c≤d≤50000,k≤50000)

[Solution]
我们发现,计算一个数x在某个闭区间[a,b]内的因数数量并不是很方便,可以转化为x在区间[1,b]的因数的数量-x在区间[1,a-1]的因数的数量(因为求[1,Z]比较好求)。

原问题是,对于所有x∈[a,b],y∈[c,d],求所有gcd(x,y)=k的点对的数量。
根据容斥原理,问题转化为,计算:
所有x∈[1,b],y∈[1,d],所有gcd(x,y)=k的点对的数量
-所有x∈[1,a-1],y∈[1,d],所有gcd(x,y)=k的点对的数量
-所有x∈[1,b],y∈[1,c-1],所有gcd(x,y)=k的点对的数量
+所有x∈[1,a-1],y∈[1,c-1],所有gcd(x,y)=k的点对的数量

所以怎么求解任意x∈[1,n],y∈[1,m],所有gcd(x,y)=k的点对的数量呢?

[Codeforces Round #310 (Div. 2)] #ABC题解

没想到时隔两天竟然又打了cf,做了3题就弃疗了。

题目链接:Codeforces Round #310 (Div. 2)

[BZOJ 2440] 完全平方数【莫比乌斯函数/容斥原理/二分法】

图片
[Description] 求第k个无平方因子数。无平方因子数指分解之后所有质因数的次数都为1的数。
[Solution] 
我们可以进行二分操作,查找区间[1,x]里有几个无平方因子数,逐渐缩小范围依次求解。 
然而怎么计算区间[1,x]内无平方因子数的个数Q呢? 

[Codeforces Round #309 (Div. 2)] #ABC题解

图片
鉴于本人水平有限,两小时只A了三道,剩下的又不想看了,无聊写写前三题题解。

题目链接:Codeforces Round #309 (Div. 2)

[Codeforces Round #309 (Div. 2)] 酱油记

这是人生第一次打codeforces啊...前前后后发生了很多事,手一抖又写了篇Blog.

...其实前几天就有所准备,昨天晚上大约7点才发现当晚有比赛qwq,租的房子又没网==,只能凌晨待在学校打啊!!!瞬间大家就就纷纷打电话回家说今晚不回去了==然后有家长打电话给cy问了问情况,然后那个爆炸啊==,cy勒令我们回家,还扬言要到学校来抓人--,然后我们就决定在机房关灯锁门,装作不在==还花了半个小时堵了门。

[数学小考] 2015.6.24

考了三道比较简单的数学题(题目来源网络)

傻牛的约数研究(divisor)

[Description]
傻牛最近在研究约数,它觉得这玩意很牛逼。
首先,对于一个数字 X 来说,设 F(X) 表示 X 的约数个数,可以先将 X 表达成为若干个质数的幂次
之积,即 X=p1k1*p2k2 *……*psks,然后 F(X)=(k1+1)*(k2+1)*……*(ks+1) 。傻牛觉得
这个碉堡了。有一天它想,我们是不是可以求出 F(1)+F(2)+F(3)+……+F(N) 的值呢?结果,它
晕掉了。

[BZOJ 1005] 明明的烦恼 && [BZOJ 1211] 树的计数【组合数学】

图片
—————————————————————————————————
HNOI 2008 明明的烦恼

Description
自从明明学了树的结构,就对奇怪的树产生了兴趣...... 给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?

组合数学经典八题

图片
题目如下(样例: n=3 m=2) A 给定N个不同的球,放进M个不同的盒子,盒子允许为空,有多少种方案?  样例输出:8
B 给定N个不同的球,放进M个不同的盒子,盒子不允许为空,有多少种方案? 样例输出:6
C 给定N个不同的球,放进M个相同的盒子,盒子允许为空,有多少种方案?  样例输出:4
D 给定N个不同的球,放进M个相同的盒子,盒子不允许为空,有多少种方案? 样例输出:3
E 给定N个相同的球,放进M个不同的盒子,盒子允许为空,有多少种方案?  样例输出:4 F 给定N个相同的球,放进M个不同的盒子,盒子不允许为空,有多少种方案? 样例输出:2
G 给定N个相同的球,放进M个相同的盒子,盒子允许为空,有多少种方案?  样例输出:2
H 给定N个相同的球,放进M个相同的盒子,盒子不允许为空,有多少种方案? 样例输出:1

[囤水帖] 此页真·水题一波流

[Dairy 2:2015.6.18] 停课之前

今天是个非常特殊的日子。

6.18,一年前,这个时候已然进入中考最后一门考试的考场,考完就标志着初中生活的结束了。
而一年后的今天,信息竞赛组正式停课了,竞赛生活就浩浩荡荡地开始了。

为了以表我们的决心(其实并没有这回事),我们决定每天早上集体晨练,男生跑10圈,女生跑8圈,lfw跑6圈。

早上很早到了操场,等了20分钟人才陆陆续续到,跑了20多分钟,最后爬到机房已经8:30.

但是依然感觉很爽!虽然脑袋是要炸了–用TB的话来说,这是件多么炫酷的事!等人的时候路过的同学都以惊奇的眼光看着操场–今天还下着小雨。

回到机房感觉状态很好,就要开始了!开始什么…我也不知道。

总之要开始刷BZOJ了!先试几天再定一个计划什么的。然后慢慢把以前的坑填上。

没什么其他的了,开始切题。

–By Foggy
2015.6.18

图论专题总结

P.S. 这篇主要是自己记记玩玩的,可能只有我一个人看的懂…

图论就这么浩浩荡荡搞了一个多星期…感觉很一般。
随着专题并没有什么思路,这几天跟着大白皮过了一遍,那就随着这个思路再过一遍知识点,复习一遍经典题。

[Dairy 1:2015.6.6] 随记一篇

貌似很久没有写过流水账了,趁高考假的时候比较赋闲扯一下淡;
   …打完一个句子习惯性打上一个分号;
   这周开始了图论,然而我并是感觉没跟上节奏。其实从LCA开始就是。
   …反正是扯淡,我想到哪里就写到哪里好了。

哈希专题总结

哈希专题算是我学的最比较好的专题之一了…感觉。

我把哈希的操作笼统地总结为,你有很多东西,然后你要get一件新的东西,你需要判断有没有这件东西,然后你再拿下它。

而哈希的核心问题就集中在如何判断上面。

先抛开这个问题,我们想另外一件事,哈希可以用来做什么。最简单地,可以用来判重。而依我的最近刷的题加以理解,哈希既可以用来帮助状态记录,也可以用来减少枚举量。

回到开始的问题,怎样判重。我觉得,所有的哈希都无异于设一个集合,往里面及元素罢了。而最简单的方式就是开一个数组(即桶),记录正整数元素出现的有无。而对于其他类型的元素,我们可以用到一些数据结构比如哈希树,甚至STL中的map,set等。

我们来讨论各个方式的优劣。

KMP 算法

图片
(KMP算法并不很好理解,请读者在阅读过程中集中精力并有自己的思考)

这是一种神奇的算法----

首先解释一下KMP算法是干什么的。

你有两个长度不同字符串S、T,它们的长度分别为len1/len2,你要判断T是否为S的子串(即S中是否包含T)。

以人类的思维是是这样进行判断的:一位一位比较。然而这样速度太慢了,因为在最坏的情况下你最多可能需要比较进行(len1-len2)*len2次比较(想一想,为什么)。

那你有没有思考,为什么会很慢呢?是因为在此过程中,你做了很多重复的工作,而KMP算法就是用来尽量缩减这些重复工作的。

先举个例子

[Codeplay0314] 写在之前

为OI专门开一篇博客。

作为一个名副其实的蒟蒻,还有很多东西要学。

我会写一写对算法的理解,专题总结,随记Dairy等。

希望得到各路神犇的指导。

和我兴趣相投的可以私call/mail我。

--Foggy
2015.6.18