- 博客(106)
- 收藏
- 关注
RSS订阅原创 节点之和最大的路径 递归/树形dp
dfs(root) 函数表示，root节点为路径起点(该节点必选)开始往下，求最大的路径和，路径拓展其实只有2中选择,走左边或者右边。那么取max( dfs(left) , dfs(right) )就行了。那么定义一个全局变量ans,每次同时考虑左右子树的最大路径和时，就和ans取max,就不会影响dfs(）返回值的定义。但是，root节点也可能是路径的中间节点呀，也可能左右子树的路径可以拼接得到更大值。在一颗二叉树中找一条路径，使其路径和最大。
2023-02-25 21:53:57
86
原创 矩阵中最大的矩形 单调栈
对于每一行，预处理出每一个节点(i,j)作为全1矩阵右下角的话，高度为hight[i][j]，这个矩阵左右的边界，求它最宽能左右延申多远。那么，如果（i，j)点是全1矩阵的右下角，那么它能构成的最大全1矩阵面积是hight[i][j]*(r[j]-l[j]-1)用单调栈处理出，（i，j)左边第一个hight小于hight[i][j]的下标，作为l[j],同理求出r[j]先预处理出每一个位置，往上的最长连续1 的长度，hight[i][j]重点是：你需要把>a[i] 还是
2023-02-25 20:16:11
99
原创 线性筛法 笔记
但是当前9%3==0，发现当前的基数i=9是某个质因数的倍数，那么i=9的任何倍数都应该只被3所标记，所以，后面所有的9*N合数都不用再去标记。那么就会对9*2，9*3等9的倍数，进行合数标记。核心理解：每个数只被它的最小质因数所标记。
2023-02-20 15:33:22
45
原创 线段树
链接题意：给你n个数，接下来有q次询问每次询问给你一个区间[ l , r ] ,问：在[ l , r ] 的所有子区间中有多少个子区间中的数，出现次数最多的个数恰好为k解法：用滑动窗口预处理 L[i],R[i] 表示当右端点为 i 时，\左端点的合法区间为[ L[i] , R[i] ]然后对q次询问离线处理，按查询区间的 r递增排序当查询某个区间[ L , R]时把右端点在[ 1, R]范围中的L[] , R[] 数组值作为线段树上的区间，进行区间+1操作 ，表示对答案的贡献...
2020-12-20 14:08:45
98
原创 Hatsune Miku DP
链接题意：给你n 和 m ，n表示n大小的数组a[]，m表示有个m*m 的矩阵数组a[]，当a[i] 为-1 时，表示该数数未被固定可以改变，a[i]不为-1时，表示固定不能改变每相邻两个数 i 和 j 可以产生一个数 f(i,j) ,此值可以从矩阵中得到对应第 i 行第 j 列的数求如何修改未固定的数，使得该数组两两相邻的数之和最大解法：设状态dp[i][k]表示，前i个数，第 i 个数为 k 的最大相邻数和转移方程为：即可#include<bits/s..
2020-11-27 14:21:46
181
原创 Happy Matt Friends DP记忆化
链接题意：给你n 和 m ,一个大小为n 的数组k[]每次可取多个数并得到多个数的异或和，求有多少种取法解法：设状态dp[id][now]表示前id个数中取多个数后异或和为now的方案数，然后针对每个数进行 取与不取 暴力递归记忆化即可#include<bits/stdc++.h>#define ll long longusing namespace std;int t;int m,n;int a[50];ll dp[50][1000006];ll .
2020-11-27 13:53:55
123
1
原创 Little Zu Chongzhi‘s Triangles 状压DP
链接题意：给你 n 个棍子长度，求用这些棍子所能组成的多个三角形的总面积最大值解法：用状压表示每根棍子的使用情况，最多12根棍子，那么最大的状态数为2^12-1，可用longlong保存若状态数二进制为 i =1001001(2），则表示第1，4，7根棍子已经使用，故后面不能再使用dp[i] 表示 状态数 i 中剩下的棍子中所能取得的最大总三角形面积值然后暴力递归记忆化即可#include<bits/stdc++.h>#define ll long lon..
2020-11-27 13:45:29
75
原创 Little Tiger vs. Deep Monkey DP
链接题意：给你两个数n和p，然后一个大小为n的数组a[]，你和一个机器人答题竞赛，n个题目，第i个题目答对可得ai的分数，假设机器人答对每一题的概率都是0.5求：你最少需要得到多少分，使得你赢的概率大于等于P解法：设方程表示为，机器人在前 i 个题目中共得 j 分数的方案数，那么n个题目，机器人获取 j 分数的概率为：那么你获得 x 分数，赢的概率为：枚举x使得概率大于等于p,即可#include<bits/stdc++.h>#define ll lon.
2020-11-26 20:23:43
128
原创 GTY‘s gay friends 线段树+前缀和
链接题意：n个数，m次询问，每次询问判断一个区间是否为一个序列解法：判断长度为x的序列只要满足两个条件： 1.区间和为(1+x)*x/2 2.1~x每个数只出现一次；对于第一个限制前缀和求区间和即可第二个限制可以用一个nt[]数组，存每个数y右边最近的一个相同数y的位置，用线段树维护nt[]数组，只要每次查询区间内的最小值大于r即表示每个数只出现了一次#include<bits/stdc++.h>#define ls o*2#define rs o*2+1#d..
2020-11-25 20:40:23
193
原创 C. Xor Tree 字典树
题目链接题意：给你n个数对应n个节点，对与每一个数ai,在剩余数中找一个aj,使得ai^aj异或值为最小值，并将这两个节点连无向边，由此可以得到一个连通图，可以选择删除一些数，求最少删除多少数可以使得最终连通图为一颗树解法：把每一个数放到01字典树上面，假设每个字数根节点的值表示为该子树中覆盖的数ai可以组成的最大连通块，那么对于一个父节点u和它的两个儿子节点x和y,1.如果x和y子树上都有题目给的数，u子树的最大联通块大小ans_u=max(ans_x+1,ans_y+1) 此处.
2020-11-17 16:57:05
494
原创 XHXJ‘s LIS (数位DP+状压)
链接记忆化数组dp[len][s][K] 表示后len位，s表示当前LIS的状态，题目要求长度为K,的数目其中s状态：由于LIS最长为10，则用二进制表示当前LIS的中取的数，且不断修改其中某位的值例如：二进制数 s=00010010（2）表示当前LIS长度为2，且表示为1 4函数cnt( s, k , id ) 表示 当前LIS状态为s, 且长度为k,现在后面接上一个数 为 id ,则修改状态 需要把id左边的一个1变成零（如果存在1），再在id的位改成1 ；题目要求[L,R]范...
2020-11-01 19:48:46
315
原创 E. Two Round Dances 环排列
链接循环排列（circular permutation）亦称圆排列、环排列等。是排列的一种，指从n个不同元素中取出m（1≤m≤n）个不同的元素排列成一个环形，既无头也无尾。两个循环排列相同当且仅当所取元素的个数相同并且元素取法一致，在环上的排列顺序一致。#include<bits/stdc++.h>using namespace std;int main(){ int n; scanf("%d",&n); unsigned long long ans=0;
2020-10-22 16:21:46
249
原创 Extended Traffic SPFA判负环
Extended Traffic解法：因为存在负环，则需要使用SPFA求最短路，跑一遍模板，记录负环所能达到的点集学习博客#include<bits/stdc++.h> using namespace std;int n,m,q;int a[202];struct node{ int v,w;};vector<node > G[202];int inq[202];//当前是否在队列 int num[202];//进入队列次数 当进入队列次数大.
2020-09-28 20:23:03
84
原创 1026 - Critical Links tarjan求桥
Critical Links题意：给出一个 无向图，求桥的个数思路：求桥模版题，注意输入格式学习博客 博客2模板：#include<iostream>#include<cstdio>#include<vector>#include<stack> #include<cstring>#include<algorithm>using namespace std;const int maxn=10000+..
2020-09-27 19:55:07
82
原创 牛牛和字符串的日常 kmp
牛牛和字符串的日常解法：对主串求next数组，在分别和n个串匹配，每次求最大前缀长度相加即可，（kmp算法）#include<bits/stdc++.h>using namespace std;int nt[100005];void getnt(string s){ int len=s.size(); int i=0,j=-1; nt[0]=-1; while(i<len) { while(j!=-1&&s[i]!=s[j]) j=nt.
2020-09-20 11:31:50
113
原创 2020牛客暑期多校训练营（第六场） H
Harmony Pairs解法：数位DP方程：dp[x][d][p][q] 表示状态 ：A，B的第x位数之前的数位和差值为d (sumA-sumB),p=1表示B当前位最大只能取N[x],p=0,表示B当前位可任意取，q=1表示A当前A==B所以当前位最大只能取和B位相同的数，q=0表示A<B，A当前位可取任意数。#include<bits/stdc++.h>#define mod 1000000007using namespace std;char s[10...
2020-07-29 20:16:49
166
原创 2020牛客暑期多校训练营（第三场）D、E、F
Points Construction Problem解法：首先判断无解的情况：1.易得m为奇数时无解2.大于最大组数4*n时无解3.小于最小组数时无解 ：接下来构造合法情况：采用不断从最小组合情况里从上到下的顺序不断拆出，放到遥远处，使得组合数为m每次拆一个正方形组合数加num当该正方形的四个方向有2个正方形相邻时，num=4;当该正方形的四个方向只有1个正方形相邻时，num=2;当出现还差2个组合数时，需要特殊处理：假设现在轮到( i ,j ...
2020-07-26 16:20:50
173
原创 2020牛客暑期多校训练营（第五场） B、D、E
Drop Voicing解法：观察可发现：规律1：连续多次使用操作1，相当于将前n-1个数不断内循环调换规律2：连续多次使用操作2，相当于将n个数不断内循环调换规律3：多次使用操作1后，再使用操作2,将a[0]放去末尾,相当于，取前n-1中的任一个数放到a[n-1]规律3可得：通过这两种操作的组合，可以将任意一个数放到任意一个位置那么题目可转化为求：通过最少的组合操作调换，使得目标序列sorted枚举n个最长上升子序列的长度取max答案就是总长度减去max a...
2020-07-25 23:10:23
423
2
原创 Race to 1 Again 概率DP
题目链接题意：给你一个数N，你可以等概率的对N除以它自身的约数，即N%X==0 ，N=N/X ,次此为一次操作一直对N进行此操作，直到N==1，求操作的期望次数解法：此题为经典概率dp,dp[i] 定义为：对 i 进行操作数次，使之变为1的操作次数期望值而dp[i] 的值，可通过 i的约数状态进行逆向操作转移得到，即设 i 的n个约数分别为X0 , X1 , X2 …… Xn那么末尾的+1解释：该方程的意思是从 约数X转移到 i ，此时就进行了一次操作通过左右乘以n，化解方.
2020-07-17 17:20:34
130
原创 H-Happy Triangle 动态开点线段树
存个代码#include<bits/stdc++.h> using namespace std;int inf=1e9;const int maxn=2e5+10;int tr[maxn*36],ls[maxn*36],rs[maxn*36];//存左右儿子节点下标 int rt;int cnt=0;map<int,int> mp;void up(int & o,int l,int r,int pos,int v) { if(!o)//动态开点...
2020-07-16 16:29:36
163
原创 2020牛客暑期多校训练营（第二场） All with Pairs (kmp、hash_map)
链接：https://ac.nowcoder.com/acm/contest/5667/A来源：牛客网All with Pairs时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld示例1输入3abbaaba输出29说明So the answer is 4×12+4×22+1×32=294\times 1^2 + 4\times 2^2 + 1\time..
2020-07-15 13:29:36
622
原创 The Super Powers 数论+枚举
题目链接题意：判断一个数能否写成至少两种指数形式，例如：64=2^9=8^2 题目要求把【1，2^64-1】之间所有符合条件的数输出。解法：由分析得，若一个数的指数为合数，那么这个数一定符合题目条件，设，则因为在【1，2^64-1】范围内，合法指数最大为63，最小为4那么我们可以枚举指数合数，然后再枚举底数a考虑到unsigned long long 溢出问题，可通过换底公式取log ，求出底数a最大的指数ti将所有合法数放入set，在输出即可#include<bits.
2020-07-11 16:54:12
129
原创 C Looooops 拓展gcd
题目链接解法：exgcd模板题注意：计算mod时，需要 ，不能模线性方程Ax=C(mod B) ：void exgcd(ll a,ll b,ll &d,ll &x,ll &y) { if(!b) { d=a; x=1; y=0; } else { exgcd(b,a%b,d,y,x); y-=x*(a/b); }}ll mod_count(ll a,ll c,ll b)//求解模线性方程ax=c(mod b)...
2020-07-09 17:06:35
106
原创 青蛙的约会 拓展gcd
题目链接参考自：博客#include <map>#include <set>#include <cmath>#include <queue>#include <cstdio>#include <vector>#include <climits>#include <cstring>#include <cstdlib>#include <iost.
2020-07-08 13:20:19
150
原创 Code Feat 中国剩余定理+dfs
题目链接题意：有一个正整数N满足C个条件，每个条件都形如“它除以X的余数在集合{Y1,Y,2,Y3……Yk}中”，所有条件中的X两两互素，你的任务是找出最小的S个正整数解。#include<bits/stdc++.h> #define ll long long using namespace std;int C,S;int X[20],k[20];int Y[20][150];int bestC;//存 k/X最小的那个条件C下标 vector<int&g.
2020-07-06 16:28:04
1493
1
原创 GCD - Extreme (II) 欧拉函数打表
题目链接题意：求在1-n之间所有任意两个数的的最大公因数的和。解法：先解释每一对互质数对对答案的贡献：1.数对[a,b] 互质， 那对答案的贡献：ans[b]+=1;2.那么不互质的时候，gcd(k*a,k*b)=k : 数对[k*a,k*b] ，对答案的贡献：ans[k*b] +=k*phi[b] ( phi[b]为欧拉函数值，即小于b的范围内gcd(a,b)==1，a值可取的个数，也可说是[?,b] 的互质对数)综上：只需预处理出【1，4e6】的欧拉函数值phi[i]，然后...
2020-07-05 15:01:34
190
原创 J - Janitor Troubles 三分 海伦公式
交题链接解法：（1） 利用三分查找两边角度，求出围成最大面积的那个角度此处用角度求面积方法：余弦公式 得到对角线C边长度再用海伦公式可分别求出两个三角形面积，然后相加为四边形面积#include<bits/stdc++.h>double pi=acos(-1);using namespace std;double a,b,c,d;double A,B,C,D;double S(double x,double y,double z) { doubl...
2020-07-03 14:03:24
256
原创 LightOJ - 1220 Mysterious Bacteria 质因数分解gcd
题目链接求满足条件的最大的指数p，使得a^p = x（a是整数）解法：当x为正数时，求所有质因数的指数，然后取gcd就是答案当x为负数时，因为任意数的偶数次方都为正数，则需要将gcd化为奇数#include<bits/stdc++.h>#define ll long longusing namespace std;ll x;const int N=1e6+5;bool mark[N];int prim[N];int cnt;void initial(){.
2020-07-02 16:40:40
152
原创 Harmonic Number 调和级数求和
链接题意：多次询问求Hn解法：当n>1e6时 使用求和公式： C≈0.57721566490153286060651209当n<=1e6 时，预处理求。#include<bits/stdc++.h> using namespace std;int t;int n;double mp[1000004];int main(){ double hh=0; for(int i=1;i<=1000000;i++) { hh+=(doubl...
2020-07-01 10:24:40
4253
1
原创 Pairs Forming LCM 唯一分解定理+组合数
链接解法：素数筛完后，n素数因子分解然后GCD LCM 的公式：也就是说 LCM(i,j)=n， 则 i 或 j 的素数指数ai,bi中的最大值，必须为满足n 的素数因子指数大小ei而其组合数每个素数的组合数为 2*(ei+1)-1 , 其中减一是出现了两次同时为ei每个组合连乘则得到ans,所有LCM(i,j) =n 的组合数但是题目要求是 i<=j ,则需要去重满足i==j&&LCM(i,j) =n 的情况只能是 i=n,j=n ,因为 ..
2020-06-28 22:24:59
207
原创 Leading and Trailing
链接题意：给定两个数n,k 求n^k的前三位和最后三位解法：后三位：快速幂求即可前三位：设方程， P由 整数部分和小数部分组成 P= X+ Y ，则对前三位的数没影响，重点是的值，再*100即是前三位的数PS:注意后三位输出是使用%03d补全前缀0！#include<bits/stdc++.h> #define ll long long using namespace std;int T;int n,k;int main() { sca...
2020-06-25 11:17:26
133
原创 LightOJ-1336 Sigma Function 因子和为奇数个数
链接题意：求【1，n】 区间内，有多少个数x，满足x的因子和为偶数解法：由上图（2）可得：只要任意一个括号值为偶数则N的因子之和必为偶数可得：N因子和为偶数的情况远远多于和为奇数的情况，则可通过求【1，n】中和为奇数个数ans，再n-ans即为和为偶数个数现在问题转化为 ：求【1，n】中因子和为奇数的个数1.当某个数存在因子2时，则必定为奇数 （因为：1+偶数+偶数……=奇数）2.因为其他所有素数都是奇数，则只有当ai为偶数时，括号值才为奇数 (因为：奇数的任意次方为奇数 .
2020-06-24 21:29:18
205
原创 Aladdin and the Flying Carpet (正约数个数)
链接求出a的所有约数个数num，因为不可能是sqrt(a)*sqrt(a) ==a ，则成积为a的数对为num/2 ，然后再减去短边长小于b的对数，num就是答案了#include<bits/stdc++.h> #define ll long longusing namespace std;ll a,b;int T;const int N=1e6+5;bool mark[N];int prim[N];int cnt;void initial(){ cn.
2020-06-24 18:29:17
85
原创 牛客小白月赛26 牛牛种花 线段树+离散化
链接：https://ac.nowcoder.com/acm/contest/6013/C来源：牛客网牛牛种花时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld题目描述牛牛看到家里的花圃空荡荡的，花圃是无限大的矩阵(有钱就是任性)。于是他就去买了n朵花。牛牛会把第i朵花种在(xi,yi)位置。然后牛牛有m次询问，他想知道在(ai,bi)坐标的左下角(x<=ai &&...
2020-06-23 11:11:28
218
原创 Prime Independence 素数 奇偶分图+二分图HK最大匹配
题目链接x方点集为 因数个数为奇数y方点集为 因数个数为偶数满足 a=b*k(prim) 条件，只能是 a,b 在不同点集时枚举每个a[i]的因子，然后枚举除去每个因子 判断该数是否存在 ，若存在则建边(意味着 这两个数不能同时选中)此处需用“链式向前星存图” 做法 就是不断修改链表的head头指针建完图后跑HK，即可二分图最大匹配（HK）博客二分图最大匹配-HK算法的简单理解和实现博客#include<bits/stdc++.h>usi...
2020-06-23 11:03:14
148
原创 牛客小白月赛24题解 A-J
A最短路 几何大佬几何模板求出sum角，求A，B 角, C角得直线A-D1 直线B-D2 弧线D1-D2 相加即可#include<bits/stdc++.h> using namespace std;// `计算几何模板`const double eps = 1e-8;const double inf = 1e20;const doubl...
2020-04-19 15:37:52
439
原创 Kadj Squares 几何思维
Kadj Squares题意：不断加45°角站立的正方形,在互不相交的情况下，使得每个正方形底端点尽量靠左，求在上方视角可以看到的正方形编号解法：先求每个正方形左右端点L[i] R[i] X[i] 分别表示 i正方形的左端点、右端点、边长因为每个新正方形 i 总会和另外一个正方形 j 的一条边重合，由此可计算新正方形左端点坐标L= R[j]-fabs(X[i]-X[j])/s...
2020-04-18 16:11:26
197
原创 水题(water) 数论+N皇后
链接易得：f[i] 为斐波拉契数列该题分两部分：其一 、求阶乘数m进制末尾0个数：以2进制为例，若8= 1000(2) 6 = 110(2) 24=11000(2)易得：若num的m劲字末尾有ans个0，则必当num%()==0，末位数转化为求ans，即m的最大指数。更根据唯一分解定理，可将m 表示为这种形式求出a1,a2, ...an; 再求出在k!...
2020-04-15 15:48:28
204
原创 相似的子串 哈希+二分+STL unordered_map
相似的子串解法：字符串哈希预处理字串长度存在单调性 二分长度xcheck(x) 利用unordered_map<int,pair<int,int> > 快速匹配 x长字串的出现次数二分注意：存在答案为0 的情况 ：4 2qwer#include<bits/stdc++.h>#define hash Hash#define ul...
2020-04-12 17:56:41
93
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人