Codeplay0314-CSDN博客

原创【转播公告】

由于界面等等一些原因，今天转到Hexo了，感觉灵活性大多了- -传送门>>http://codeplay0314.gitcafe.io/还有2048玩噢快来踩踩~然后就可以愉快地玩耍了~

2015-07-08 16:44:25 838

原创 [BZOJ 3884] 上帝与集合的正确用法【欧拉定理/初等数论】

[Description]求值 [Solution] 不要被无限个2吓到了，这一题有一些有趣的性质可以发掘的。这里介绍两个解法。· Solution 1我们温习一下欧拉定理：和它的推广：我们发现，这题的n,p并不一定互素啊，怎么办呢？我们可以让他们强行互素。利用公式：我们把原题中的p分为2^k+y 所以原式化为此时y是奇数，和指数互质了！然后就可以愉快地使用欧拉定理

2015-07-04 11:13:45 2510

原创 [BZOJ 1951] 古代猪文【Lucas定理/费马小定理/中国剩余定理/扩展欧几里得】

[Description] 求 [Solution] 容易得到，所以，重点在怎么求如果是p-1是个质数，我们可以用sqrt(n)的时间枚举所有d,用Lucas定理分别计算求和即可。但是我们发现p-1=2*3*4679*35617，并不是一个质数，所以Lucas定理不能用了吗？并不，我们可以算出这个合式分别对2、3、4679、35617的模值，写出四个同余方程，再用孙子定理求解即可。注意特

2015-07-02 21:30:06 1109

原创 [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]的因数的数量（

2015-06-29 17:19:41 628

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

没想到时隔两天竟然又打了cf,做了3题就弃疗了。题目链接：Codeforces Round #309 (Div. 2)A. Case of Zeros and Ones [Description] 给定一个01串，相邻的0和1可以消掉，问最终这个串最短可以消到多长。 [Solution] 可以证明，当这个序列0和1都还存在，是可以继续进行消除的，直到某个数字没有。 [Ans] n-2*(m

2015-06-28 00:48:14 484

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

[Description] 求第k个无平方因子数。无平方因子数指分解之后所有质因数的次数都为1的数。[Solution] 我们可以进行二分操作，查找区间[1,x]里有几个无平方因子数，逐渐缩小范围依次求解。然而怎么计算区间[1,x]内无平方因子数的个数Q呢？根据容斥原理， Q=x-x内有一个平方因子的数+x内有两个平方因子的数-x内有三个平方因子的数… =x-x内(4的倍数个数+

2015-06-27 18:09:47 566

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

鉴于本人水平有限，两小时只A了三道，剩下的又不想看了，无聊写写前三题题解。题目链接：Codeforces Round #309 (Div. 2)A. Kyoya and Photobooks[Description] 给定一个只有小写字母的字符串，可以在任意位置插入任意一个小写字母，求得到的字符串种数。 [Solution] 枚举+哈希水题 [Code]#include<map>#incl

2015-06-25 20:34:57 480

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

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

2015-06-25 19:20:19 542 1

原创 [数学小考] 2015.6.24

考了三道比较简单的数学题（题目来源网络）傻牛的约数研究(divisor)[Description] 傻牛最近在研究约数，它觉得这玩意很牛逼。首先，对于一个数字 X 来说，设 F(X) 表示 X 的约数个数，可以先将 X 表达成为若干个质数的幂次之积，即 X=p1k1*p2k2 ……*psks，然后 F(X)=(k1+1)(k2+1)……(ks+1) 。傻牛觉得这个碉堡了。有一天它想，我

2015-06-24 15:45:43 445

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

————————————————————————————————— HNOI 2008 明明的烦恼Description 自从明明学了树的结构,就对奇怪的树产生了兴趣…… 给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树?Input 第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入

2015-06-22 22:25:32 928

原创组合数学八题

(题目来自朱全民老师PPT) 题目如下（样例： n=3 m=2） A 给定N个不同的球，放进M个不同的盒子，盒子允许为空，有多少种方案？样例输出：8 B 给定N个不同的球，放进M个不同的盒子，盒子不允许为空，有多少种方案？样例输出：6 C 给定N个不同的球，放进M个相同的盒子，盒子允许为空，有多少种方案？样例输出：4 D 给定N个不同的球，放进M个相同的盒子，盒子不允许为空，有多

2015-06-21 19:49:44 2109

原创图论专题总结

P.S. 这篇主要是自己记记玩玩的，可能只有我一个人看的懂…图论就这么浩浩荡荡搞了一个多星期…感觉很一般。随着专题并没有什么思路，这几天跟着大白皮过了一遍，那就随着这个思路再过一遍知识点，复习一遍经典题。图的一些基础概念无需多说。而图的应用中，最直接的就是搜索。这里重点提及一下隐式图搜索，说白了，就是把题中给定的情况，分离出多种状态，在各个状态中连上边权适合的边，以将其转化成一个图论问题。这种方

2015-06-18 08:41:35 600

原创 [Dairy 2：2015.6.18] 停课之前

今天是个非常特殊的日子。6.18，一年前，这个时候已然进入中考最后一门考试的考场，考完就标志着初中生活的结束了。而一年后的今天，信息竞赛组正式停课了，竞赛生活就浩浩荡荡地开始了。为了以表我们的决心（其实并没有这回事），我们决定每天早上集体晨练，男生跑10圈，女生跑8圈，lfw跑6圈。早上很早到了操场，等了20分钟人才陆陆续续到，跑了20多分钟，最后爬到机房已经8:30.但是依然感觉很爽！虽然脑袋

2015-06-18 08:34:02 639 1

原创哈希专题总结

哈希专题总结哈希专题算是我学的最比较好的专题之一了…感觉。我把哈希的操作笼统地总结为，你有很多东西，然后你要get一件新的东西，你需要判断有没有这件东西，然后你再拿下它。而哈希的核心问题就集中在如何判断上面。先抛开这个问题，我们想另外一件事，哈希可以用来做什么。最简单地，可以用来判重。而依我的理解，哈希既可以用来帮助状态记录，也可以用来减少枚举量。回到开始的问题，怎样判重。我看来，所有的哈希都无异于

2015-05-17 18:49:42 605

原创 KMP 算法

KMP 算法（KMP算法并不很好理解，请读者在阅读过程中集中精力并有自己的思考）这是一种神奇的算法—- 首先解释一下KMP算法是干什么的。你有两个长度不同字符串S、T，它们的长度分别为len1/len2，你要判断T是否为S的子串（即S中是否包含T）。以人类的思维是是这样进行判断的：一位一位比较。然而这样速度太慢了，因为在最坏的情况下你最多可能需要比较进行(len1-len2)*len2

2015-04-19 16:46:32 380

Codeplay0314