Deep_Dark_FAntasy♂

分类

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

/ 注册

TA的专栏 39篇文章 0人订阅

2020/7/8 VJ contest 8 比赛

7篇文章 722人学习

2020/7/10 VJ contest 9 比赛

4篇文章 590人学习

2020牛客暑期多校训练营（第二场）

3篇文章 899人学习

2020牛客暑期多校训练营（第一场）

1篇文章 1194人学习

2020牛客暑期多校训练营（第三场）

4篇文章 596人学习

2020牛客暑期多校训练营（第四场）

3篇文章 603人学习

2020牛客暑期多校训练营（第六场）

5篇文章 723人学习

2020牛客暑期多校训练营（第五场）

4篇文章 639人学习

2020牛客暑期多校训练营（第七场）

3篇文章 622人学习

2020牛客暑期多校训练营（第九场）

1篇文章 708人学习

2020牛客暑期多校训练营（第十场）

2篇文章 577人学习

2020 CCPC网络赛

2篇文章 657人学习

SDNU Contest 10.15

0篇文章 0人学习

愿早日绿名

0篇文章 0人学习

全部文章（共235篇）

(大数判断素性)Miller-Rabin素数测试算法

作用：有时候我们想快速的知道一个数是不是素数，而这个数又特别的大导致 O( √n) 的算法不能通过，这时候我们可以对其进行 Miller-Rabin 素数测试，可以大概率测出其是否为素数。两个定理：费马小定理：如果p是素数，a是小于p的正整数，那么a^(p-1) mod p = 1。证明：首先我们...

Miller_Rabin素性测试大数素性判断

2020-06-29

0 4697

最大公约数(lcm)

先看题目：https://ac.nowcoder.com/acm/problem/16710解题思路：公式lcm(a,b) = ab / gcd(a,b)记得要先a/gcd(a,b)然后再乘b以防止越界*代码：** #include<bits/stdc++.h> using namesp...

lcm

2020-06-26

0 438

同余方程

先看题目：https://ac.nowcoder.com/acm/problem/16563解题思路：exgcd模板题，求ax≡1(mod b)，可以写为方程的形式 ax = yb + 1, 即 ax - by = 1，这个符号可以塞到y里，令k=-y，就还是二元线性方程的形式了 —— ax + b...

exgcd 同余方程二元线性方程

2020-06-26

1 625

大水题

先看题目：https://ac.nowcoder.com/acm/problem/15079解题思路：题目要求的是不是2，5，11，13的倍数，我们可以考虑是2，5，11，13的倍数有多少个，即求|2的倍数 U 5的倍数 U 11的倍数 U 13的倍数|，如果把它们直接加起来，发现会有一些元素重复统...

容斥原理

2020-06-25

0 520

【高斯消元】To xor or not to xor(最长异或子序列)

题目描述：就是给你n个数然后从中选择一些出来异或，求异或可得到的最大值解题思路：跟据题目可以假设答案ans=d1d2d3d4...(di代表ans的二进制位0/1)(这里不是乘法哦)，从高位一直枚举到低位，检验是否可行。但如果直接检验的话，复杂度是O(2^n)，显然超时。所以可以从高位枚举到低位，同...

贪心高斯消元最大异或子序列

2020-06-25

0 821

石子合并2

先看题目：https://ac.nowcoder.com/acm/problem/50493题目描述：与石子合并1的规则相同，只不过所有石子现在围成了一个环形。解题思路：处理环有两种方法，一种是取模，另一种是序列加倍。序列加倍就是把‘1234’变成'12341234'使循环的完全可以用链的方法解决了...

取模石子合并环形区间dp 序列加倍

2020-06-23

0 686

石子合并(简单版)

先看题目：https://ac.nowcoder.com/acm/problem/51170题目描述：N堆石子排成一排，每次可以合并相邻的两堆，每次合并得分为合并的两堆石子之和，问把所有石子合成一堆的最小得分是多少？解题思路：区间dp入门题，dp[i][j]表示从i到j合并的最小得分，则可写出状态转...

区间dp

2020-06-23

0 762

牛客假日团队赛43：B perimeter

先看题目：https://ac.nowcoder.com/acm/contest/5723/B题目描述：有一些草堆块放在一些格子里，每个格子只能放一个草堆块，这些草堆块会形成一个连通块，算连通块的外围周长。解题思路：我一开始的思路是，每个初始ans是4*N，也就是每个草堆块四个面的周长都算的情况，然...

dfs 剪枝思维

2020-06-23

0 579

简单瞎搞题

先看题目：https://ac.nowcoder.com/acm/problem/17193题目描述：略解题思路：暴力枚举总共有100^100次方种情况，考虑使用dp。那么状态定义为什么呢？如果定义为dp[i][j]表示前i项有没有构成j这个数字，那么状态转移方程就变得很麻烦了，首先，开个1e8的数...

bitset dp的优化

2020-06-22

0 522

牛客假日团队赛43：J Square Overlap

先看题目：https://ac.nowcoder.com/acm/contest/5723/J题目描述：给出一些边长都为k的正方形的中心坐标，如果只有一对正方形重叠，则输出重叠面积，如果有多对正方形重叠，输出-1，如果没有正方形重叠，则输出0解题思路：画图模拟一下可知，如果两正方形中点坐标为(x1,...

思维优化图形重叠水题搜索

2020-06-22

0 567