- 博客(58)
- 收藏
- 关注
RSS订阅原创 51nod 1237 最大公约数之和 V3(杜教筛)
题目传送门题意：计算由于数据范围达到1e10，显然直接线性筛是完成不了的，所以我们选择杜教筛。对该式分块，令构造,带入，求解。AC代码：//#pragma comment(linker, “/STACK:1024000000,1024000000”#include <bits/stdc++.h>using namespace std;typedef ...
2019-08-05 09:29:16
196
原创 莫比乌斯训练报告(随训练更新)
目录莫比乌斯函数简介：具体运用：莫比乌斯反演公式训练记录：zoj3435 传送门bzoj2154 Crash的数字表格莫比乌斯函数简介：莫比乌斯函数，数论函数，由德国数学家和天文学家莫比乌斯(August Ferdinand Möbius ,1790–1868)提出。梅滕斯(Mertens)首先使用μ(n)作为莫比乌斯函数的记号。而据说，高斯(Gauss)...
2019-08-04 21:16:18
280
原创 FFT学习报告(随训练更新)
简介FFT,快速傅里叶变换，用于快速求多项式。首先，我们知道任何一个任何一个周期函数都可以表示成为傅里叶级数的形式。通过对应关系我们可以求出周期函数系数或者傅里叶级数的系数。建议具体过程看复变函数或者高数。FFT过程：两个次数界为n的多项式a(x)和b(x)相乘，输入输出均采用系数表示法。（假定n为2的幂）1）使次数界增加一倍：a(x)和b(x)扩充为次数界为2n的多项式，并构造起...
2019-08-03 09:37:23
259
原创 杜教筛学习报告(随训练更新)
目录关于杜教筛的简述训练记录：51nod1244 莫比乌斯函数之和51nod1239 欧拉函数之和bzoj3944 sumhdu5608 Function关于杜教筛的简述看了skywalkert的博客大概明白了。author: skywalkertoriginal article:http://blog.csdn.net/skywalkert...
2019-08-01 10:55:09
154
原创 2019 hdu多校round1 1011 Function（数论+线性预处理）
题目传送门简单题意算法先分块，有令函数对,通过差分有,显然f(i,i)通过线性欧拉筛可以预处理.所以显然只需要考虑上界为n时的情况,的跑一边f(i,n)即可。这题卡常很严，所以离线查询(__int128长见识了)，整体复杂度为#include <bits/stdc++.h>using namespace std;typedef long l...
2019-07-24 21:33:11
185
原创 2017 北京区域赛J Pangu and Stones（石子合并升级版 区间dp）
Pangu and StonesIn Chinese mythology, Pangu is the first living being and the creator of the sky and the earth. He woke up from an egg and split the egg into two parts: the sky and the earth.At th...
2018-11-11 16:27:24
431
原创 UVA - 10288 Coupons (数学 + 模拟)
传送门：UVA - 10288Coupons in cereal boxes are numbered 1 to n, and a set of one of each is required for a prize (a cereal box, of course). With one coupon per box, how many boxes on average are require...
2018-10-15 20:48:33
276
原创 poj 1061青蛙的约会（扩展欧几里得+同余方程）
传送门：青蛙的约会两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了...
2018-10-08 16:49:22
154
转载 感谢IronStark对ORB算法的讲解
本文为原创文章，转载请注明出处：http://blog.csdn.net/yang843061497/article/details/38553765 绪论假如我有2张美女图片，我想确认这2张图片中美女是否是同一个人。这太简单了，以我专研岛国动作片锤炼出来的火眼金睛只需轻轻扫过2张图片就可以得出结论。但是，如果我想让计算机来完成这个功能就困难重重了：再性感的美女在计算机眼中也只是0-1组成...
2018-10-07 14:56:07
179
原创 HDU 4449 Building Design(计算几何 三维凸包 + 坐标转化 模板)
传送门：HDU 4449题目：You are a notable architect. Recently, a company invites you to design their new building for them. It is not an easy task, because they make some strange claims to the new buildin...
2018-09-29 20:59:53
387
原创 HDU 4451 Dressing（组合数学 + 容斥）
传送门：HDU 4451题面：Wangpeng has N clothes, M pants and K shoes so theoretically he can have N×M×K different combinations of dressing. One day he wears his pants Nike, shoes Adiwang to go to school ha...
2018-09-29 20:47:26
176
原创 UESTC 1983 不骗你这题真的是送分的(hash + 神奇的自动取模)
传送门：UESTC 1983字符串的哈希就是通过某些映射关系，将字符串映射到数字上去方便进行比较。比如二进制数110110110110，我们知道这个数的十进制是 5454基于同样思路，我们可以定义这样的一个哈希函数：哈希函数是基于163163进制的，即hashihashi=(s1−′a′)=(s1−′a′)163i−1163i−1+(s2−′a′)(s2−′a′)*163i−2...
2018-09-19 16:30:12
281
原创 poj2407 Relatives（欧拉函数 水题）
日常水题传送门：RelativesGiven n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0,...
2018-09-19 13:47:15
144
原创 poj2262 Goldbach's Conjecture（素数筛 水题）
日常水题传送门：Goldbach's ConjectureIn 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture: Every even number greater than ...
2018-09-19 13:31:18
144
原创 poj1142 Smith Numbers（素数+唯一分解定理）
传送门：Smith NumbersWhile skimming his phone directory in 1982, Albert Wilansky, a mathematician of Lehigh University,noticed that the telephone number of his brother-in-law H. Smith had the following ...
2018-09-19 00:33:32
186
原创 poj 1050 To the Max（dp 最大子矩阵和）
传送门：poj 1050 To the Max 题意：给出一个的矩阵，求该矩阵的最大子矩阵和。思路：我们可以先固定行，来对列进行求最大前缀和的操作，固定行，先求出隔行的前缀和，来对列进行规划。我们发现针对每一次行规划的时候求最大值即可，所以我们可以直接维护最大值。AC代码：//#include <bits/stdc++.h>#include<ios...
2018-09-18 17:19:34
216
原创 2018ACM_ICPC焦作网络赛L题 Poor God Water（矩阵快速幂）
目录 传送门：Poor God Water题意：思路：AC代码：传送门：Poor God WaterGod Water likes to eat meat, fish and chocolate very much, but unfortunately, the doctor tells him that some sequence of eating will mak...
2018-09-18 13:07:23
279
原创 wustoj2200 一道出错题意的emmm01背包
wustoj2200: 我能反杀题目：Time Limit: 5 Sec Memory Limit: 128 MB 64bit IO Format: %lldSubmitted: 23 Accepted: 7[Submit][Status][Web Board]Description众所周知， cyh喜欢打游戏， 而且喜欢打boss， 但boss的血量太高， cyh必须...
2018-09-12 16:38:48
180
2
原创 poj 1141 Brackets Sequence（区间dp+回溯）
题目：Brackets Sequence的题目链接Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 34409 Accepted: 9949 Special Judge DescriptionLet us define a regular brackets seq...
2018-08-30 10:11:00
148
原创 区间dp详解（入门到进阶）
目录 前言：初级版：51Nod - 1021 石子合并（区间dp，时间复杂度）思路：状态转移方程：AC代码：中级版：HDU - 3506 Monkey Party（四边形不等式优化，时间复杂度）思路：四边形不等式：状态转移方程：AC代码：高级版：HYSBZ - 3229 石子合并（GarsiaWachs算法优化，时间复杂度常数小）思路：AC代...
2018-08-30 08:45:47
1388
原创 wustoj 1506 药丸（卡特兰数+高精度）
目录题目：思路：AC代码：题目：1506: 药丸 Time Limit: 1 Sec Memory Limit: 65535 MB 64bit IO Format: %lldDescription一个药瓶里装有...
2018-08-29 11:10:25
389
原创 卡特兰数详解
目录关于卡特兰数：计算公式一般性质代码实现：关于卡特兰数：卡特兰数是一种经典的组合数，经常出现在各种计算中，其前几项为 : 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786……计算公式卡特兰数一般的计算公式： 另类递推公式：C(n)=C(n-1)*((4*n-2)/(n+1));一般性质Cn的另...
2018-08-29 11:07:08
2137
原创 wustoj2230 Cheap deliveries（dijkstra（heap优化） + 状态压缩 + dp）
题目：2230: Cheap deliveriesTime Limit: 2 Sec Memory Limit: 64 MB 64bit IO Format: %lldSubmitted: 40 Accepted: 16[Submit][Status][Web Board]Description Abu runs a delivery service...
2018-08-29 09:15:02
371
原创 关于解除键盘锁定
今天，开机，不知道为什么键盘锁定了，真的尴尬，搜了好久解锁键盘的方法才找到，emmm。特写此文给同样莫名其妙被锁定键盘而不解锁的小伙伴。关于解除锁定键盘：首先，win+r召唤出运行指令框。选择cmd，回车。召唤命令行。记住，这里要使用管理员权限打开，输入指令：sc config i8042prt start= auto如果不使用管理员权限打开就会：成功就会...
2018-08-27 11:14:40
8439
3
转载 高精度模板（转载）
转载博文感谢cb大大的模板#include <algorithm>#include <cassert>#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <vector>#includ
2018-08-25 20:52:08
122
原创 hdu 6441Find Integer(CCPC网络赛D 数论+勾股数+费马定理)
目录题目：题意：思路：AC代码：题目：Find IntegerTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 117 Accepted Submission(s): 49Special JudgePr...
2018-08-25 19:20:54
173
原创 poj 1042 Gone Fishing(dp + 回溯)
目录题目：题意：一解：DP+回溯状态转移方程：AC代码： 题目：Gone FishingTime Limit: 2000MS Memory Limit: 32768K Total Submissions: 38276 Accepted: 11894 DescriptionJohn is going on a fishi...
2018-08-24 11:18:18
205
原创 poj 1015 Jury Compromise（一道很老很经典的二维dp）
目录 题目：题目大意：思路：状态转移方程：AC代码：题目：poj 1015 题目链接Jury CompromiseTime Limit: 1000MS Memory Limit: 65536K Total Submissions: 31847 Accepted: 8592 Special Judge D...
2018-08-23 19:51:19
319
2
原创 poj 2479 Maximum sum(前缀和 + dp)
目录 题目：题目大意：思路：AC代码：题目：Maximum sumTime Limit: 1000MS Memory Limit: 65536K Total Submissions: 43867 Accepted: 13643 DescriptionGiven a set of n integers: A={a1, a2,...
2018-08-23 11:09:18
155
原创 poj 1811 Prime text（很经典的随机算法，Miller_Rabin和Pollard_rho算法）
目录题目：题目大意：关于Miller_Rabin探测：关于Pollard_rho：AC代码：题目链接题目：Prime TestTime Limit: 6000MS Memory Limit: 65536K Total Submissions: 37982 Accepted: 10195 Case Time Limit: 4...
2018-08-23 10:07:57
208
原创 Miller_Rabin算法详解
目录基本引理：1，费马定理：2，二次探测定理：作用：证明：代码实现：目录基本引理：1，费马定理：2，二次探测定理：基本引理：1，费马定理：费马定理的证明链接2，二次探测定理：二次探测定理的证明链接作用：有效的检测大整数是否为素数。证明：由费马定理，可以排除大部分非素数的情况（满足费马定理是素数的必要条件），给出一个奇素数n...
2018-08-22 16:53:05
10113
原创 二次探测定理（数论，理解Miller_Rabin算法所需要引理）
最近学习的过程中接触了随机算法，Miller_Rabin算法，关于大数判断是否为素数的随机算法，然后就学习的数论知识。定理很简单，如果p为一个素数，则的解为，.证明过程如下：由p为一个素数可以推出。...
2018-08-22 15:24:19
4791
原创 CodeForces - 961D——（计算几何——叉积的运用）
我们个人赛的一个题目，简单的计算几何，在聊题目之前，我想先聊聊我的心路历程。。。写了150行斜率和截距判断的函数后，突然发现其实根本不需要。。。然后改叉积就50行就过了，emmmm。目录题目链接：题目：题意：思路：AC代码：题目链接：http://codeforces.com/problemset/problem/961/D题目：D. Pair Of Lin...
2018-08-15 09:41:08
324
原创 牛客练习赛24（完全背包+常数优化）
这场比赛是看到孟巨佬一个半小时就AK了，所以我才做的。。。这个题是牛客网这场比赛的卡人题，说实话，有点水。。。看到这个题算了一下复杂度，其实远远达不到背包的o(nm)，所以我毫不犹豫的选择了背包，尴尬的是，我的状态写错了。。。贼丢脸。。。链接：https://www.nowcoder.com/acm/contest/157/F来源：牛客网 题目描述小k有一个三轮，它最多可以装105...
2018-08-11 09:09:40
305
原创 逆元详解（加扩展欧几里得和费马小定理的证明）
最近，wyb小朋友老是不好好搞他的数据结构，跑过来问我数学，没办法，所以我决定每天发一篇数论的博客，骗骗流量（以后wyb有不会的就看我博客，哈哈哈）先从基础的更起吧。逆元：我第一次接触逆元是在离散数学的代数系统中，对于一种运算满足（为该运算的单位）则称是的逆元。逆元在算法中的运用：逆元在算法中主要是为了整数的除法取模，显然除法是不能直接取模的。但是我们可以转化一下，因为乘法是可以直...
2018-08-08 21:03:37
3142
2
原创 HDU1728逃离迷宫（一道巨坑的bfs）
今天，集训，我旁边的wyb死怼了这道题，然后我看了一下，嘲讽了一波，“这么简单的bfs，要是我绝对一发过”，然后直播打脸。。。最后是看了一下wyb的博客A掉的，好了，先发一下题面。。。逃离迷宫Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission...
2018-07-30 15:07:08
275
原创 欧拉降幂（欧拉-费马定理）
map<ll,ll> map_phi;ll get_phi(ll n){ ll res = n,a = n; for(ll i = 2;i * i <= n;++i){ if(a % i == 0){ res = res / i * (i - 1); while(a % i == 0) a...
2018-07-30 09:06:56
1486
原创 牛客多校第四场 A Ternary String（dfs + 递推 + 欧拉降幂）
链接：https://www.nowcoder.com/acm/contest/142/A来源：牛客网 题目描述A ternary string is a sequence of digits, where each digit is either 0, 1, or 2.Chiaki has a ternary string s which can self-reproduce. E...
2018-07-29 22:08:02
202
原创 关于计算几何凸包的五种求法（陆续更新）
目录1.穷举法（暴力求解）：2,Graham扫描法（常用方法）：凸包，在二维平面中可以定义为，一个将所有给出点包含的凸多边形。如下图所示：绿色线条就是凸包而在计算几何中凸包有五种求法：1.穷举法（暴力求解）：将所有点两两对应，然后将剩下的（n - 2）个点 一一枚举判断是否在同一侧，如果都在同一侧即这两个点是凸包上的点。具体的算法实现利用到了叉乘。如果该式子...
2018-07-26 10:08:15
2213
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人