- 博客(183)
- 收藏
- 关注
RSS订阅原创 质因数分解板子(可对long long大小的数进行分解)
板子（有随机性）：#include <cstdio>#include <iostream>#include <cmath>#include <map>#include <algorithm>using namespace std;typedef long long ll;const int MAX = 1e5 + ...
2019-12-12 16:17:32
446
原创 南昌邀请赛网络赛 G. tsy's number（莫比乌斯反演+线性筛）
题目链接：tsy's number题意：求 (mod )思路：原式 =设 设原式 =设T = id ，将 i 的求和变为 T 的求和：原式 =：这个是与的迪利克雷卷积，并且g(x)与f(x)均为积性函数，因此该函数也为积性函数，可通过线性筛O(n)求解。处理上述积性函数前缀和，对原式前半部分的...
2019-04-26 11:54:14
648
原创 南昌邀请赛网络赛 D. Match Stick Game（dp）
题目链接：Match Stick Game题意：给定一个表达式，只包含加减法，其中每个数字都是用棍子拼起来的，包括加减号（具体详见题目链接）。现在可对棍子进行重新分配。但需要保证运算符号数量不变，且参与运算的每个数的位数也不变，且其初始值<=1e9。求重新分配后表达式结果的最大值。思路：先处理出棍子的总数( sum )和参与运算的每个数的位数。设 dp[i...
2019-04-25 16:41:46
224
原创 Codeforces Round #554 (Div. 2) D. Neko and Aki's Prank（记忆化DFS）
题目链接：D. Neko and Aki's Prank题意：有一颗二叉树，每条边表示 "(" 或 ")" ，在 n 对括号匹配的合法序列组成的二叉树中任选几条边，选择的任意两条边不能有公共顶点，求可选边的最大数量。思路：记忆化dfs：设 dp[L][R] 表示还剩余 L 个 "(" ，R 个 ")" 时的答案数。假设要求 n ，我们从 1 开始遍历到 n ，每...
2019-04-25 12:08:45
252
原创 The 2018 ACM-ICPC上海大都会赛 J Beautiful Numbers（数位dp）
题目链接：Beautiful Numbers题意：给定一个 n ，求 1 - n 中 Beautiful Numbers 的个数。一个数为 Beautiful Numbers 当且仅当它是它所有数位上数字和的倍数。思路：数位dp的关键在于定义dp数组以确保该数位上进行如此选择对答案的贡献是唯一的。定义dp数组：dp[pos][sum][res] ：sum表示各数...
2019-04-24 19:41:11
352
原创 Educational Codeforces Round 63 (Rated for Div. 2) D. Beautiful Array（DP：记录状态）
题目链接：D. Beautiful Array题意：给定一个序列和x，可以任选一段连续区间，将其中所有元素*x，（也可以不选），求序列的最大连续子段和。思路：设 dp[i][j][k] ：i：表示当前位置j：0：还未开始计算最大连续子段和 1：正在计算最大连续子段和 2：计算最大连续子段和已经结束k：0：还未开始*x 1：...
2019-04-24 16:39:51
119
原创 南昌邀请赛网络赛 C. Angry FFF Party（python大数 + 矩阵快速幂计算斐波那契数列）
题目链接：Angry FFF Party题意：定义斐波那契数列：F[1]=1，F[2]=1，F[n]=F[n-1]+F[n-2] (n>=3) 。给定一个 w ，，要求在 F[F[x]] 中找任意个数，其和等于 w ，输出其 x 。若有多组解，输出字典序最小的。若不存在，输出 -1 。思路：设 ff[x] = F[F[x]]。斐波那契数列增长速度接近 ，因...
2019-04-21 13:32:32
263
原创 2019中山大学程序设计竞赛 Monitor（HDU 6514 二维前缀和）
题目链接：Monitor题意：有 n*m 的区域，现在有 p 个摄像头，每个摄像头可以监控左上角为（axi,ayi），右下角为（bxi,byi）的矩形区域。有 q 个询问，每次给定一个左上角为（ax,ay），右下角为（bx,by）的矩形区域，问这个区域是不是都在监控范围内。n*m <= 1e7 。思路：总思路为将监控覆盖的区域全标记为1，否则为0。查询时，若所...
2019-04-20 20:50:04
332
原创 Tree（POJ 1741 树的点分治）
题目链接：Tree题意：给定一棵树，每条边有一个权值，求树上长度 <=k 的路径条数。思路：树的点分治例题。参考博客：【算法学习】点分治计算一棵以 A 为根的树上长度 <=k 的路径条数可分为 2 个部分：1. 路径经过 A 点。2. 路径不经过 A 点。可以看出第 2 种情况是以A的子树中的点为根节点时的情况 1 。所以每次计算...
2019-04-17 21:13:13
249
原创 树的重心
定义：对于一个 n 个节点的无根树，找到一个点，使得把树变成以该点为根的有根树时，最大子树的节点数最小。性质：以树的重心为根的有根树，最大子树大小不超过。（ 即树的高度 <= log(n) )思路：先随意以一点为根，dfs处理每个节点的子树大小 siz[i] ，dfs回溯到 i 点时计算以 i 为根的情况下，最大子树大小为：maxsubtree = m...
2019-04-16 11:21:24
195
原创 ZOJ 4098 Defense Plan（暴力+剪枝+思维）
题目链接：Defense Plan题意：王国里有 n 个城堡，初始防御力为 1。每个城堡都可以装备加农炮，装备之后第 i 个城堡的防御力为 w[i]。设现在每个城堡防御力为 t[i]，王国的防御力为。此外，还有 m 个互斥条件，表示 i，j 不能同时装备加农炮。设总共有 k 种不同情况，每种情况王国的防御力为xi，则求方差，其中。思路：先看所求方差：...
2019-04-15 20:36:24
474
5
原创 华中科大邀请赛 Balls（组合数学+Lucas 定理+思维）
题目链接：Balls题意：给定 k，S（1<=k，S<=1e18），p（2<=p<=5e6），求 。思路：需要把这个公式转换成组合数学问题：相当于有 S 个小球，分成 k 堆，可以有剩余小球，然后把每堆小球个数乘起来得到这种情况的价值，最后求的就是所有情况的价值之和。每堆小球个数乘起来可以理解为：从每堆小球中任取一个，有多少种取...
2019-04-15 11:03:15
328
原创 Pangu and Stones（The 2017 ACM-ICPC Asia Beijing Regional J 区间dp变形）
题目链接：J - Pangu and Stones题意：有 n 堆石子，每堆有 a[i] 个，给定L，R，相邻的连续 [L,R] 堆石子可以合并成一堆，代价是这些堆中石子数量之和。求把 n 堆石子合并成一堆的最小代价，情况不存在输出 0 。思路：若L=R=2，则就是传统的区间dp：dp[i][j] = min(dp[i][j]，dp[i][k]+dp[k+1][...
2019-04-11 15:50:27
196
原创 The Elder（hdu 5956 树上斜率dp + 队列还原）
题目链接：The Elder题意：给定一棵树，根节点为1，每条边都有一个权值。节点 i 到节点 j 的花费为这两点间路径权值和的平方。现在从每个点到根节点，可以在路径的任何点停留，每次停留cost+=这两点间路径权值和的平方+P（最后一步跳到根节点不需要+P），使该cost最小化。最后求所有点的cost的最大值。思路：每个点到根节点都是一条唯一路径：设dp[i]...
2019-04-10 10:38:51
217
原创 质因数分解、约数个数、约数和
背景：暴力求 n 的约数个数、约数和的复杂度为 ，往往不能符合题目时限要求。但这个通过质因数分解来优化时间。质因数分解：性质：一个数 n ，最多只存在一个质因子。因此，我们只需要预处理出以内的质数（1e5以内质数大概4000+个）。遍历这些质数，若n%p==0，那么n/p，直到n%p!=0。最后如果 n 还大于 1 ，那么这个剩下的 n 一定也是质数。设，...
2019-04-09 11:27:59
1751
原创 Codeforces Round #546 (Div. 2) E. Nastya Hasn't Written a Legend（线段树+思维(变量替换)）
题目链接：E. Nastya Hasn't Written a Legend题意：给定一个长度为 n 的数组 a[i] 和一个长度为 n-1 的数组 k[i]。有2种操作：1. 给定i，x，使得a[i] += x 。若更新后 a[i]+k[i]>a[i+1]，则 a[i+1]=a[i]+k[i]；若此时 a[i+1] 被更新了，且 a[i+1]+k[i+1]>a[...
2019-04-08 17:07:21
119
原创 Tachibana Kanade Loves Probabilit（除法模拟+思维）
题目链接：Tachibana Kanade Loves Probability题意：给定m，n，k1，k2，求 （n/m） 小数点后 k1 位到 k2 位的数字。其中1<=m<n<=1e9，1<=k1<=k2<=1e9，0<=k2-k1<=1e5 。思路：除法运算相当于每次记录 m/n 的值，并且每次将 m 置为 ...
2019-04-05 23:23:40
126
原创 小A与最大子段和（斜率dp + 二分）
题目链接：小A与最大子段和题意：给定一个序列a[i]，找一个a[i]的连续子序列b[i]，使得满足在所有的情况中最大。（m为b的长度）思路：设 dp[i] 表示以第 i 位为结束位置的最优解。设 f[i] = a[1]*1+a[2]*2+...+a[n]*n 。设 sum[i] = a[1]+a[2]+...+a[n] 。设 j 为b序列的起始位置的...
2019-04-01 10:16:12
325
原创 Print Article（hdu 3507 斜率dp+单调队列 模板）
题目链接：Print Article题意：给定 n 个数 c[i] ，和一个常数 M ，求的最小值。思路：设 sum[i] 表示 c[i] 的前缀和（即c[1]+c[2]+...+c[i]）。 （sum[0]=0，表示为空）设 dp[i] 表示处理到第 i 位时候的最小花费。dp[i]=min(dp[j]+(sum[i]-sum[j])^2+M) 其中...
2019-03-30 20:03:24
114
原创 欧拉降幂
参考博客：欧拉降幂和广义欧拉降幂定理：欧拉定理：若n，a为正整数，且n，a互质，则：。由此得出降幂公式：。更具体：Code：（欧拉函数+快速幂）ll phi(ll n) { ll ans = 1; for (ll i = 2; i*i <= n; i++) { if (n%i == 0) { n /= i; ans *= i - ...
2019-03-26 11:08:28
605
原创 线段树（EOJ Monthly 2019.3 思维 DFS+可行性剪枝）
题目链接：HDU：Solve this interesting problemEOJ：线段树题意：给定一个区间 [l,r] ，求最小的 n ，使得根节点为 [1,n] 的线段树中某个节点为这个区间。若无解，输出-1。思路：从给定的区间 [l,r] 开始，向上dfs，有4种可能：该区间为其父节点的左节点：则其父节点代表的区间为 [l,2*r-l] 或 [l...
2019-03-24 15:41:51
192
原创 Codeforces Round #546 (Div. 2) C. Nastya Is Transposing Matrices（矩阵转置的性质）
题目链接：C. Nastya Is Transposing Matrices题意：给定两个大小均为n，m的矩阵A,B，每次操作可选择A中的一个正方形子矩阵进行矩阵转置，可进行任意次操作，问能否将A矩阵变成B矩阵。思路：矩阵转置的性质：从左下到右上的对角线上的元素位置可以互换。证明：任意一个2*2的子矩阵进行转置，左上和右下的那两个元素位置不变，左下和右上...
2019-03-21 11:58:55
134
原创 zyb的面试（hdu 6468 十叉树）
题目链接：zyb的面试题意：一个 1-n 的排列，按字典序排序，小的在前，求第 k 个数的值。（例(n=15)：1, 10, 11, 12, 13, 14, 15, 2, 3, 4, 5, 6, 7, 8, 9）思路：建立一个十叉树，如下图所示：该树满足如下性质：1. 不算最后一层，均为满十叉树。2. 先序遍历到的第 k 个数就是所求字典序第 k 小...
2019-03-20 20:22:40
631
原创 Count（hdu 6470 矩阵快速幂 含关于n的多项式）
题目链接：hdu 6470 Count题意：f[n] = 2*f[n-2] + f[n-1] + n^3，n<=1e18，求f[n] 。思路：在计算 f[n+1] 的时候， 要变为，所以构造的矩阵中需要有这几项，然后因为引入了，所以要变为，因为项、项、常数项都已经存在，所以不需要引入新的项，其余各项均可通过这几项计算出。因此，构造的矩阵为：...
2019-03-17 21:49:25
639
原创 Infinite Fraction Path（hdu 6223 ST表 + hash ）
题目链接：Infinite Fraction Path题意：给定一个纯数字的字符串，下标从0开始，下标为 i 的那个字符有一条指向下标为（i*i+1）% n 的字符的有向边。现在，从每个点开始走n-1条边，就能得到n个长度为n的字符串，输出其中字典序最大的那个。思路：ST表 + hash：nxt[i][j]：表示下标为 i 的字符后面第（1<<j）个...
2019-03-16 11:20:56
417
2
原创 左偏树
参考博客：浅谈左偏树左偏树的应用：左偏树是可并堆的一种实现。它满足堆的性质，并且能在log的时间复杂度下合并两棵左偏树。左偏树的定义：定义1左偏树中的一个节点，如果它的右子树为空，则称它是一个外结点。定义2对于左偏树中的一个节点x，到它的子节点中，离它最近的一个外结点经过的边数称为它的距离,记为dist(x)。特别地，外结点的距离为0，空节点(null)的距...
2019-03-12 10:26:20
593
原创 The kth great number（hdu 4006 最小堆/优先队列）
题目链接：The kth great number题意：已知k，一开始序列为空，有n个操作，要么向序列里插入一个值，要么询问序列中第k大的数是多少。思路：用最小堆或者优先队列维护最小值。当插入的数大于k个时，弹出最小值。因此，最小堆或优先队列中每次都只有k个数，在询问的时候输出当前最小堆或优先队列中的最小值即可。Code：（最小堆stl实现）#inc...
2019-03-11 12:04:16
274
原创 D. Camp Schedule Codeforces Round #545 (Div. 2)（双模数字符串哈希+贪心）
题目链接：D. Camp Schedule题意：给定一个01串s，再给定一个字符串t，现在可以随意交换s中元素顺序，使得交换后的串中含t的数目最多（t作为子串）。输出交换后的串，special judge。思路：贪心思路，求 t 的后缀与前缀匹配的最大长度。固定重合部分，然后重复剩余部分即可。如何求 t 的后缀与前缀匹配的最大长度？一、求kmp的Next数组...
2019-03-10 16:35:12
462
原创 GCD Expectation（zoj 3868 数学+思维）
题目链接：GCD Expectation题意：已知一个n个元素的序列，任取一个非空子集（{x1,x2,..,xm}），求的期望。假设取任一子集的概率相同。最后答案乘以。思路：定理：任意有n个元素的集合，其非空子集个数为 。因为每种子集概率相同，即都为，最后答案 *，相当于求任意非空子集的和。用 tot[i] 表示 gcd 为 i 的...
2019-03-05 15:56:06
286
原创 Cylinder Candy（zoj 3866 旋转体体积和表面积）
题目链接：Cylinder Candy题意：有一个圆柱体的糖果，底面半径为r，高为h。现在在它外面涂一层均匀的巧克力，厚度为d。求涂完巧克力后该糖果的体积和表面积。思路：所求的糖果并不是一个圆柱，因为厚度均匀为d，那么在顶部会出现圆弧。可以看出，中间部分任为圆柱，只是半径变为（r+d），顶部则为一个旋转体（底部同）。此图为旋转体的截面图。体积：...
2019-03-05 11:12:07
542
原创 1003 Emergency（两点间最短路径的条数）
题目链接：1003 Emergency 题意：给定一张图，且每个节点有一个权值，给定起点和终点，求起点和终点之间最短路径的条数和权值和最大值。 思路：对dijkstra算法进行一定变形即可。用tot[i]表示起点到第i个点最短路径的条数。num[i]表示起点到第i个点的最短路中权值和的最大值，dis[i]表示当前从起点到i的最短路的距离。因此只需在最后的更新操作中进行适...
2019-02-22 14:35:24
787
原创 CCPC-Wannafly Winter Camp Day2 H Cosmic Cleaner（两个球相交部分体积计算）
题目链接：Cosmic Cleaner 题意：在三维坐标系中，有n个球体，每个球的球心为(xi,yi,zi)，半径为ri。再给定一个球（球心为(X,Y,Z)，半径为R），求该球与其余n个球相交部分体积。（保证一开始的n个球两两之间没有重叠） 思路：因为n个球两两之间没有重叠，所以考虑其中每个球(称为小球)与最后给定的那个球(称为大球)即可。分3种情况：设 d 为两球...
2019-01-21 20:31:15
5505
原创 HDU 2196 Computer（树上最远距离）
题目链接：Computer 题意：有一棵树，树上每条边都有一个权值，求每个点与其距离最远的点之间的距离。 思路：dp[root][state]：以root为根节点的子树，root的状态为state的情况下的最远距离。dp[root][0]：root在以root为根节点的子树中的最远距离。dp[root][1]：root在以root为根节点的子树中的次远距离(不是...
2019-01-18 12:02:45
494
原创 POJ 3659 Cell Phone Network（最小支配集：树形dp）
题目链接：Cell Phone Network 题意：有一棵树，问最少取树中的多少个节点，能使其与树的其他节点都联通。（一个点只与其有边相连的点联通） 思路：dp[i][state]：以i为根节点，并且其状态为state的情况下，其子树中被染色的点的个数的最小值dp[i][0]：i不染色，父节点染色覆盖idp[i][1]：i不染色，子节点染色覆盖idp[i]...
2019-01-17 20:34:01
240
原创 ZOJ 3201 Tree of Tree（树上背包）
题目链接：Tree of Tree 题意：有一棵树，每个节点有一个权值，给定一个值k，求大小为k的子树中每个节点权值和最大为多少。 思路：树规方程：f(i,j)=max{ f(i,j-p)+f(v,p) | 1<p<j 且 v是i的子节点 }f(i,j)：表示以i为根节点，大小为 j 的子树的最大权值。siz[i]：表示以 i 为根节点的子树大小。...
2019-01-17 10:44:19
336
原创 洛谷P4551 最长异或路径（树上最长xor路径：01字典树）
题目链接：P4551 最长异或路径 题意：给定一棵n个点的带权树，结点下标从1开始到N。寻找树中找两个结点，求最长的异或路径。异或路径指的是指两个结点之间唯一路径上的所有边权的异或。 思路：xor有一个性质：一个值xor 2次相当于没有xor。因此，任意两个节点i，j之间路径的xor值等于1->i的路径xor值异或上1->j的路径xor值（设根节点为1）...
2019-01-15 16:50:56
1192
原创 牛客练习赛37 C 筱玛的迷阵探险(Trie+折半)
题目链接：筱玛的迷阵探险 题意：一个n×n的矩阵A，每个格子上有一个有一个数Ai,j。入口在左上角的(1,1)处，出口在右下角的(n,n)处。每一步都只能向下或向右移动一格。最后能获得的经验值为初始经验e与路径上经过的所有数的权值异或和。求筱玛最大可能获得的经验值。 思路：如果纯暴力，dfs整张图，复杂度O（2^(2n)），数量级最坏情况下为O（2^40），肯定会TL...
2019-01-12 20:56:46
387
3
原创 zjgsu新生赛题解
大一新生好强啊，oi大佬一个半小时就AC 7题了，orz...几个学长学姐无聊看代码的时候竟然发现了一个神仙老哥！膜，ORZ...0 钞哥拒绝吃土：这是一道水题，遍历这个数组把每个宝贝的价值保存下来相加即可。唯一一个坑点是最后的和会爆int，用long long即可。（PS：本来这题想搞点事情的，比如每个价值可能是小数，最后的答案要用大数等等，后来想想签到题还是不搞你们了~...
2018-12-22 17:00:57
543
原创 Codeforces Round #523 (Div. 2) D. TV Shows（multiset+思维）
题目链接：D. TV Shows 题意：有 n 个电视节目，播放的时间区间为 [li,ri] 。同一时间，不同的节目不能在同一台电视上播放。一个节目必须完整的在一台电视上播放完。现在租一台电视需要先付 x 块钱，之后每分钟要付 y 块钱，即租一台电视从时间区间 [a,b] 需要付 x + （b-a）*y 块钱。问看完所有的节目至少需要多少钱。 思路：把所有节目按开始时间...
2018-12-10 12:18:35
177
原创 tokitsukaze and Similar String（字符串哈希）
题目链接：tokitsukaze and Similar String 题意：tokitsukaze获得了一个长度为n (1≤n≤10^5)，由a-z小写字母组成的字符串。我们定义两个字符串是相似的，当且仅当能通过多次以下操作，使得两个字符串相等。并且把需要操作的最小次数，称为两个字符串的相似度。操作是这样的：选择一个字符串，把字符串的每个字母都替换为字母表上的下一个字母...
2018-12-09 20:50:56
298
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人