Deep_Dark_FAntasy♂

未归档

Codeforces(3) 博弈论(3) 基本数论、组合数学（排列组合，容斥等）(14) 并查集(2) 数据结构(2) 深度优先搜索、广度优先搜索、搜索剪枝(8) 线性dp、背包问题、区间dp(15) 题解(12)

/ 注册

全部文章 / 未归档（共176篇）

（博弈—尼姆博弈）1509.G.Triple Nim

尼姆博弈：https://blog.csdn.net/BBHHTT/article/details/80199541 里面有个定理比较重要题意，就是有一堆石子，一共有n个，把n个石子分成三堆，求有多少种分配的方式能够使得bob win？很容易就能够明白题目是让干什么的，这道题目就是一道尼姆博弈...

2020-09-23

1 712

(邻项交换法)奎奎发红包

题目：情人节又到了，又到了一年一度发红包的时间。经大家研究决定，今年让奎奎自愿发红包。俱乐部有n个人(0<n<100000)，每个人都有一个单身值v[i]与亲密度ti，单身值越大的人，在情人节的时候就越羡慕奎奎，奎奎就需要给他更大的红包来安慰他。由于一个寒假没有见到奎奎，领红包的时...

2020-09-23

1 679

[素数筛水题---为什么会TLE]- Goldbach`s Conjecture

题意很简单，就是一个n<=1e7，n若可以被两个素数a,b(a<=b)所表示，问可以被多少组素数对表示。 1.bool类型占内存小，之前开的都是int数组，可以优化一下素数筛。（标记数组最好换成布尔类型的，节约时间和空间） 2.数组开的太大就会超时，尽量不要开这么大。 #include...

2020-09-23

1 535

[打表的策略,调和级数]I-Harmonic Number

题意：求f(n)=1/1+1/2+1/3+1/4…1/n (1 ≤ n ≤ 108).，精确到10-8 两种做法：先介绍数论解法：解法1.调和级数+欧拉常数参考：https://www.cnblogs.com/shentr/p/5296462.html 知识点：调和级数(即f(n))至今...

2020-09-23

1 610

(数论推理)Harmonic Number (II)

挺有趣的一道题。求出前sqrt(n)项和：即n/1+n/2+…+n/sqrt(n) 而（n/1-n/2)就是后面项中1.x的个数 (n/2-n/3)就是后面项中2.x的个数依次类推。。。举两个例子： n/1-n/2 = 5; 1.x n/2-n/3 = 2 2.x n/3-n/4 = 1 ...

2020-09-23

1 626

1到n有多少奇数，多少偶数公式

n为奇数时，有（n+1）/2项奇数，（n-1）/2项偶数 n为偶数时，有n/2项奇数，n/2项偶数

2020-09-23

1 525

[eps]四舍五入真是要命!!

https://blog.csdn.net/qq_40907279/article/details/81265253 eps是浮点误差. 可以做什么？对于数字5，如果计算机存储的数据为5.000000000000001，显然对这种情况不需要用到eps进行补偿，而对于有缺省的类似于4.9999999...

2020-09-23

1 418

(唯一分解定理，数论分析)Sigma Function

题意：对一个给定的n，从1到n，他们的σ[n]中有几个是偶数。pi 是n的素数因子，ei 是对应素因子的个数。分析：对所有的素数，如果p为2，则那一项一定为奇数，对于不是2的素数，可以发现当ei+1为奇数的时候(因式分解你就懂了)，即pi这个素因子出现偶数次时，那一项项也为奇数。若使得那一整个...

2020-09-23

1 444

(大数取余)Large Division

题意：给你两个数a，b，让你求出来a是否能够被b整除。题解：大数取余当一个数很大时，大到long long int类型都存放不了的时候，我们该怎么办呢？首先我们举个简单的例子来了解该算法的思想：假设有一个数443，我们要求443%3，不妨拿起笔和纸和我一起演算一下。 #include &...

2020-09-23

1 572

(exgcd)青蛙的约会

拓展gcd详解传送门思路：设时间为t，则两个青蛙的位置分别为(x+mt)mod L、(y+nt) mod L，相遇即是(x+mt)%L=(y+nt)%L，即(m-n)t+kL=y-x。 OK，现在已经符合ax+by=c的方程了，设a=m-n，b=L，c=y-x，然后套用模板求出特解t的值，注意t&...

2020-09-23

1 495