- 博客(38)
- 收藏
- 关注
RSS订阅原创 数论
1.对于大整数NNN来说，不大于NNN的质数大约有NlnN个\frac{N}{\ln N}个lnNN个2. 判断质数的方法试除法 复杂度O(N)\operatorname{O}(\sqrt N)O(N) 绝对正确Miller Robbin 非常高效，但有将合数判为质数的可能通过费马小定理，猜想当满足am−1≡1(modm)a^{m-1}\equiv1\pmod mam−1≡...
2020-02-19 16:01:41
127
1
原创 poj2891 Strange ways to express integers
题目没说互质，所以用不了中国剩余定理。通过数学归纳法：假设前面的几个方程组成的方程组的通解为k∗t+r,k为任意整数.k*t+r,k为任意整数.k∗t+r,k为任意整数.则接下来的这一步对于输入的两个数a,ba,ba,b我们要找k∗t+r≡b(moda)k*t+r\equiv b\pmod ak∗t+r≡b(moda)即k∗t+r+l∗a=b的整数解k*t+r+l*a=b的整数解k∗t+...
2020-02-19 15:54:09
103
1
原创 poj3696 The luckiest number
问题转化:问题转化:问题转化:x888…8⏞=8∗(10x−1)9\begin{matrix}x\\\overbrace{888\dots8}\end{matrix}=\dfrac{8*(10^x-1)}{9}x888…8=98∗(10x−1)令gcd(8,L)=d,令\gcd(8,L)=d,令gcd(8,L)=d,L∣8(10x−1)9 ⟺ 9Ld∣10x−1 ⟺ 10x≡1...
2020-02-18 17:09:40
109
原创 poj1084 Square Destroyer
这题的关键是如何存储信息IDA*估计函数:找到一个未被删除的正方形并去掉所有边，但只记一次操作 一定小于等于实际从当前的最小的正方形（使得搜索树小）开始枚举删去其中的边代码（关键函数变量有注释）#include<iostream>#include<cstdio>#include<vector>#include<cstring>usi...
2020-02-17 10:43:00
274
原创 noip2009/acwing200 Hankson的趣味题
好题。（解法不写了#include<iostream>#include<cstdio>using namespace std;int n;int vis[50005],prim[50005],cnt;int ans;int cal(int x,int y){ int ret=0; while(x&&x%y==0) { x/=y...
2020-02-16 17:25:25
119
原创 acwing199 余数之和
把问题转化为求n∗k−∑i=1nk−⌊k/i⌋∗i把问题转化为求n*k-\sum\limits_{i=1}^nk-\lfloor k/i \rfloor*i把问题转化为求n∗k−i=1∑nk−⌊k/i⌋∗i令g(x)=⌊k/⌊k/x⌋⌋令\operatorname{g}(x)=\lfloor k/\lfloor k/x \rfloor \rfloor令g(x)=⌊k/⌊k/x⌋⌋则⌊k/g...
2020-02-16 15:44:10
114
原创 bzoj1053
很重要的需要看出来的结论：每个数分解后包含的不同质数个数最多10个 因为最小的11个质数相乘大于2e9了每个质数的次数不超过30 因为2302^{30}230超过了2e9质数的指数一定随着底数的增大而减小（否则一定存在g(i)=g(x)且i<x，则x不是anti-prime）以此为准进行搜索 非常快速代码#include<iostream>#include<...
2020-02-16 14:11:41
105
原创 poj1077/acwing179 Eight
A*算法 估价函数为当前每个数到最终结果的曼哈顿距离（因为是和空格交换 所以只能改变一个数的情况 故此处满足f(x)<g(x)）对于一个矩阵的表示（因为要判断vis）可以使用暴力n*n康托展开但是我的代码跑得很慢 应该可以双向bfs什么的会快一点（或者discuss里好像有单向过的？）代码#include<iostream>#include<cstdio>...
2020-02-14 17:25:28
115
原创 poj2449/acwing178 第k短路
A*的算法核心：选择一个合适的估计函数f(x)，且必须估计值小于等于实际值（否则是错的）实际值表示为g(x),则f(x)<=g(x)本题因为是一张图 所以想到每个点的估计函数作为该点到终点的最短路 。这样符合要求，且能顺应g(x)的实际变化趋势代码#include<iostream>#include<cstdio>#include<queue>...
2020-02-14 14:23:33
76
原创 hdoj3085 / acwing177 Nightmare
双向dfs 男孩女孩每到一个地方标记最小时间 第一次来到对方标记的地方的时间就是答案代码#include<iostream>#include<cstdio>#include<queue>#include<cstring>#include<cmath>using namespace std;int n,m;char s[...
2020-02-13 18:11:18
113
原创 acwing175电路维修
看成一张图 如果是原来摆成的状态意为着边权为0，否则为1，在跑最短路这里很特殊的一点是只有0，1所以我们扩展的时候 若边为0 则将扩展的点插入到队首 否则插入到队尾 这需要一个deque 但是可以维护广搜队列任意时刻的两段性和单调性没有vis数组 因为不能保证第一次扩展到就是最短 但是由于满足广搜的上述两条性质 可以保证每次出队的时候距离就是最短距离（仔细想想）所以复杂度还是O(r*c)的代...
2020-02-13 14:38:49
128
原创 poj1475/acwing174 推箱子
这题思路挺新的，，可是相比实现并不那么恶心因为要求箱子的移动次数少 可以bfs，用三元组(x,y,dir)表示箱子在(x,y)，dir是人所在的箱子的方向因为在箱子移动次数少的基础上还要人移动尽可能少 所以每次判断人的移动时要再bfs一次（也就是bfs里套了一个bfs）实际实现时我的队列里存储了6个量q[x][0]:dirq[x][1]:xq[x][2]:yq[x][3]:上一个状态...
2020-02-13 12:18:56
158
原创 acwing173 矩阵距离
很简单 但所含思路我认为非常重要方法：一次性把所有值为1的坐标都入队，再进行bfs很好地利用了bfs的最短特点代码#include<iostream>#include<cstdio>using namespace std;int n,m;bool a[1005][1005];bool vis[1005][1005];int ans[1005][1005...
2020-02-12 14:53:59
143
原创 poj3076 16*16soduku
思路1.若某一个格子只有一种填法了 那就填上2.若某个格子一种填法也没有 无解3.若某行/列/宫格中某个字母的填法唯一 填上4.若某行/列/宫格中某个字母不能填 无解在以上的情况下 再选择可选选项最少的格子去填就行最近做了几个搜索题，可以感觉到在一层dfs里多几个小的遍历没有关系 关键要让搜索树小才能快#include<iostream>#include<cstd...
2020-02-11 17:49:25
164
原创 poj1190 生日蛋糕
原始思路(黑色)正解(highlighter)从几个角度考虑优化搜索顺序：本题本来就有顺序对，的确要从下往上排除等效冗余：无无可行性剪枝：若往上放的蛋糕体积尽可能大也不符合要求直接return除此之外还要注意：1.若放上的体积最小也超出return 2.h和r的取值范围要大于从上往下数的层数（否则后面无法安排）3. h和r要小于上一层且小于sqrt(n-v),v是已经摆出...
2020-02-11 09:09:20
135
原创 poj1011 sticks
做完这题后 再也不敢说自己会搜索会剪枝了剪枝思路见代码注释使用的方法1 优化搜索顺序2 排除等效冗余（主要）代码#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int n;int sum,cnt...
2020-02-10 23:02:31
143
原创 acwing165 小猫爬山
这题很简单的dfs 之所以说是因为一开始贪心错了我原本的贪心思路:先从大到小排序若能在已有的当中找到一个车厢放进这只小猫 就把它放进去，否则开一个新车厢来放hack：4 73 3 2 2 2 2正解：2 错解：3正确思路：dfs(x,y)正在放第x只 已经用了y个车厢然后把x放进1-y个以及新开车厢都试一遍优化: 一开始从大到小排序（减少搜索树大小）；若y>ans 直接...
2020-02-10 17:16:03
141
1
原创 acwing160 匹配统计
做法1：哈希+二分 时间复杂度O(nlogm+q)做法2：kmp匹配 时间复杂度O(n+m+q)值得思考的做法2cnt[j]表示匹配长度为j的个数一位一位的kmp匹配 若我们发现到a的第i位有b的前j个与它匹配 就++cnt[j]kmp后倒着遍历 cnt[nxt[j]]+=cnt[j]，因为kmp每一位匹配到的都是当前最长的，这一遍可以把短的也加进来但这样会有一个问题 若一个a的后缀与...
2020-02-10 09:09:14
98
原创 poj2185 Milking Grid
#挺难的题 数据水 看了几篇题解才确定了正确做法对于一个长度为n的字符串，kmp一遍，它的最短题目要求的长度为n-nxt[n]a个不可分割出循环节的字符串连在一起是不可写成b个连在一起的形式的(a,b互质）但是对于AAAABAAA，符合的长度有5，6，7，8并不全是8-nxt[8]=5的倍数 所以在得出5这个答案后 要把后面三个(AAA)再kmp一次得到1，所以答案为5,5+1,5+1+1,...
2020-02-09 16:13:00
106
原创 poj1635 Subway tree systems
把0看成1 1看成-1对于一个子树来讲如果从开头到某一段的和为0表示又回到了这个子树的根根据子树把字符串截乘小段 再sort string 方便比较两个树是否相同注意截成的小段递归求解时要把开头和结尾的0和1去掉 才算是以这个子树的根为起点（开头本来表示进入这个根，结尾本来表示离开这个根）好用的stl：ss=s.substr(a,b) a为起点下标，b为长度sort(vs,begin(...
2020-02-09 11:37:23
101
原创 poj1193/LGp5763 内存分配
好题。算法不难，实现巧妙堆（按结束时间排序）链表 表示已经占据的空间的开始点和长度 用set表示了队列 等待分配的代码#include<iostream>#include<cstdio>#include<set>#include<queue>#define PII pair<int,int>using namespac...
2020-02-08 22:59:39
145
1
原创 acwing154/LGp1155 双栈排序
性质若存在k>i>j且a[k]<a[i]<a[j] 则i，j不可被放进同一个栈充分性、必要性均易证对这样的i，j连一条无向边，再判断整个图是不是二分图代码#include<iostream>#include<cstdio>#include<memory.h>using namespace std;int n;bool ...
2020-02-08 16:39:46
147
原创 acwing150 括号画家
空序列是合法括号序列若A是合法括号序列，则(A),[A],{A}也是若A,B是合法括号序列，则AB也是这是一个在题目里常见的规则。本题的要求是输入一个字符串，输出其中最长的连续括号序列。O(n)判断一个序列是否括号序列是很简单的。但本题不适用。这里有两种思路：1，栈对于每个字符，如果能与栈顶的字符匹配，则出栈不可的话则进栈这里用栈存储下标，既方便知道对应的字符，也可计算长度每...
2020-02-08 10:44:41
158
原创 bzoj1150
这题调了我3小时…显然只选相邻的两个楼。a_i表示第i个楼与第i+1个楼的距离设i时a_i取最小时的i 根据题意选了a_i就不能选a_(i-1),a_(i+1) 所以在选了a_i后删去a_i,a_i-1,a_i+1并加入a_(i+1)+a_(i-1)-a_i，如果后面选了新加的就表示不应选a_i而应a_(i-1)和a_(i+1),因为a_i最小所以旁边两个要么同时选要么同时不选边界要特殊考虑...
2020-02-07 15:09:14
93
原创 poj2442
先考虑m=2的情况将数组排好序 最小的和肯定是a_1+b_1假设这一个答案为a_i,b_j下一个答案的可能会加入a_i+1,b_j和a_i,b_j+1把所有可能的下一个加入一个堆为了避免一个答案被加入两次 ，可以用vis数组或者直接在加入堆时加入一个变量g表示有无移动过j 如果移动过后面就不能移i只能移j，可以保证不会重复选到代码#include<iostream>#in...
2020-02-07 10:46:47
195
原创 acwing143&144最大异或和
acwing143在给定的N个整数A1，A2……AN中选出两个进行xor（异或）运算，得suoyi到的结果最大是多少？建乘一字典树。插入0,1（从高位向低位）查找相当于贪心？因为从高位查起，所以满足这一位即使后面每一位不满足，也比这一位不满足后面每一位都满足要强（二进制真好）代码#include<iostream>#include<cstdio>using ...
2020-02-06 17:02:59
135
原创 poj1961
先kmp匹配一遍设s的下标为1~n则当i%(1−nxti)=0i\%(1-nxt_i)=0i%(1−nxti)=0时有K=1−nxtiK=1-nxt_iK=1−nxti的的答案证明：令sl,rs_{l,r}sl,r表示由第lll位到第rrr位组成的字符串(inclusive)令len=i−nxtilen=i-nxt_ilen=i−nxti由nxtnxtnxt的定义可知s1,i...
2020-02-05 23:08:46
121
原创 manacher复杂度证明
洛谷p3805 manacher模板题复杂度证明：令fif_ifi表示第i个字母while进行的次数，mximx_imxi表示第i次结束后mx的值。可知，mx是非降的可得fi=mxi−mxi−1 (i<=mxi−1)f_i=mx_i-mx_{i-1}\;(i<=mx_{i-1})fi=mxi−mxi−1(i<=mxi−1)fi=mxi−i (i>m...
2020-02-05 10:53:10
94
原创 bzoj2457
将数先排好序记录每种数字在原序列中最小和最大的出现位置该问题相当于把排序好的数组分成最少的段数 使每段在原序列的出现顺序满足单谷性质（先单调递减再单调递增），因为只有这样才能按照题目的意思放进同一个双端队列记录最大最小值的目的是判断这一段能否与之前的升/降接上 如果不可的话就改变当前的升/降代码//11:18#include<iostream>#include<cs...
2020-02-04 12:05:33
240
原创 poj3714
知识点：分治+平面最近点对全部排好序后：截中点分别先考虑左右两半 假设左右两半最近点距为d 就再在距离mid d的范围内考虑就可 一层层递归下去时间复杂度不太高代码#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>using namespace st...
2020-02-02 19:36:37
510
原创 poj3179
二维离散化 二分#include<iostream>#include<cstdio>#include<algorithm>using namespace std;int c,n;int len;int a[505],b[505];int tmp[1005],s[1005][1005];bool check(int x){ int pos=...
2020-02-01 13:26:42
262
原创 洛谷p2690
f[i][j]表示第i时刻移动了j次的最大答案转移：f[i][j]=max(f[i-1][j],f[i-1][j-1])+(a[i]==(j%2+1))注意：一开始Bessie处在第一棵树代码#include<iostream>#include<cstdio>using namespace std;int t,w;int a[1005],f[1005][...
2020-02-01 09:31:26
112
原创 矩阵乘法
n×m的矩阵a 乘 m×k的矩阵b 等于 n×k的矩阵c其中 for(int k=1;k<=m;++k)c[i][j]+=a[i][k]*b[k][j]
2020-01-31 11:13:49
74
原创 扩展欧几里得
朴素欧几里得：gcd(a,b)=gcd(b,a mod b) 。这个是比较好证明的：假设 a=k∗b+r ，有 r=a mod b 。不妨设 d 为 a 和 b 的一个任意一个公约数，则有 a≡b≡0(mod d) 。由于同余的性质 a−kb ≡ r ≡ 0(mod d) 因此 d 是 b 和 a mod b 的公约数。然后 ∀ d|gcd(a,b) 都满足这个性质，所以这个定理成...
2020-01-31 09:32:42
77
原创 poj1328
[poj1328题解]通过坐标系距离公式计算满足能探测到岛屿i的雷达可能的区间[xi,yi]根据x的大小从小到大排一遍 若xi>y(i-1)则需要一个新的雷达若xi<=y(i-1)则可以与上一个岛屿共用 并yi=min(yo,y(i-1))以便正确判断后面的如此贪心即可代码#include<iostream>#include<cstdio>#in...
2020-01-30 19:29:03
261
原创 欧拉路的困惑
今天写了一道欧拉路的模板题洛谷p2731对于欧拉回路要用栈记录不是很理解现针对此题给出一种hack掉随dfs输出的数据81 22 33 44 24 54 65 16 1画图然后再感受一下 正解的算法真的是妙不可言啊...
2020-01-20 22:28:55
52
原创 c++ windows下对拍
c++ windows下对拍程序笔记#include<bits/stdc++.h>#include<windows.h>using namespace std;int main(){ while(1){ system("Untitled3.exe>data.in");//造数据的exe system("Untitled1.exe<data.in...
2019-08-29 21:40:38
357
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人