- 博客(352)
- 收藏
- 关注
RSS订阅原创 leetcode 95. 不同的二叉搜索树 II(给一个数n 求1-n所有不同的二叉搜索树 首先结果是卡特兰 然后枚举所有情况)
题目class Solution {public: TreeNode* clone(TreeNode *root,int diff){ if(root==NULL) return root; TreeNode* newroot=new TreeNode(root->val+diff); newroot->left=clone(root->left,diff); newroot->right=clone(r
2020-11-11 16:44:13
184
原创 leetcode 543. 二叉树的直径(无脑 多叉树直径则要换根dp)
题目class Solution {public: int ans=0; int getdep(TreeNode *root){ if(root==NULL) return 0; int dep1=getdep(root->left),dep2=getdep(root->right); ans=max(ans,dep1+dep2+1); return max(dep1,dep2)+1; } in
2020-11-07 21:52:03
332
原创 康复计划
POJ1664(m个相同苹果放在同样的n个盘子里有多少种方法)dp[i][j]:i个苹果放在j个相同的盘子i<j: dp[i][j]=dp[i][j-1];i>=j: dp[i][j]=dp[i-j][j]+dp[i][j-1]dp[0][1-n]=1
2020-10-31 22:02:06
215
原创 leetcode 23. 合并K个升序链表(归并合并 时间:klogk*n 空间logk)
题目注意lists为空时，归并时会l<r，导致一直递归。。栈溢出class Solution { public ListNode[] lists; public ListNode mergeTwo(ListNode l1,ListNode l2){ ListNode head=new ListNode(); ListNode now=head; while(l1!=null&&l2!=null){
2020-10-27 19:58:40
130
原创 leetcode 19. 删除链表的倒数第N个节点 (哦我不想无意义的双指针)
题目/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
2020-10-27 18:29:25
105
原创 Executor
文章目录线程池状态构造方法工作方式几种线程池newFixedThreadPoolnewCachedThreadPoolnewSingleThreadExecutor提交任务关闭线程池线程池状态构造方法工作方式几种线程池newFixedThreadPoolnewCachedThreadPool如果每个任务时间较长，那新来一个任务,别的线程都在执行任务的可能性很大，又要创建一个新的线程。浪费资源。newSingleThreadExecutor提交任务关闭线程池shut
2020-10-25 10:31:32
100
原创 手写线程池
文章目录阻塞队列coreSize用完了，队列也满了采用了 才用这个接口的实现类的方法线程池测试本文代码可能会因为某些地方没有加锁，会抛出异常！请谨慎食用。写这个只是为了更好地了解线程池的实现。阻塞队列public class BlockQueue<T> { private Deque<T> queue=new ArrayDeque<>(); private int capcity; private ReentrantLock lock=new
2020-10-25 00:07:26
154
2
原创 ThreadLocal应用及原理
文章目录使用Demo运用场景源码使用Demopublic class Test1 { private String name; public String getName() { return name; } public void setName(String name) { this.name = name; } public static void main(String[] args) { Tes.
2020-10-24 00:04:25
208
3
原创 synchronized原理
文章目录对象头Monitor(synchronized的重量锁通过它来实现)机制wait()、notify()偏向锁应用场景(就是通过什么场景发现synchronized需要优化，进而诞生偏向锁)存在意义轻量锁存在意义重量锁对象头假如对象是非数组类型，则没有 Array Length这一项。从上往下分别是 无锁，偏向锁，轻量锁，重量锁，GC标记。Monitor(synchronized的重量锁通过它来实现)机制(挖坑)wait()、notify()偏向锁应用场景(就是
2020-10-21 20:51:39
993
7
原创 类加载过程
文章目录类加载的时机类加载的过程类加载器类加载的时机上图中，加载、验证、准备、初始化和卸载这五个阶段的顺序是确定的，类型的加载过程必须按照这种顺序按部就班地开始，而解析阶段则不一定：它在某些情况下可以在初始化阶段之后再开始，这是为了支持Java语言的运行时绑定特性(也称为动态绑定或晚期绑定)。请注意，这里写的是按部就班地“开始”，而不是按部就班地“进行”或“完成”，强调这点是因为这些阶段通常都是互相交叉地混合进行的，会在一个阶段的过程中调用、激活另一阶段。关于在什么情况下需要开始类加载过程的第一个
2020-10-14 22:09:49
337
原创 HDU3091 (2n个分成n对使得结果最小 n小于等于10 状压dp 根据题目特性减少状态)
题目转自#include<bits/stdc++.h>typedef long long ll;using namespace std;const int N=21;struct node{int x,y;double d;}p[N],st;double dis[N][N],dp[1<<N];inline double get_dis(node A,no...
2020-02-24 09:22:02
177
原创 HDU4628 Pieces(n小于等于16的串 最少分成几个回文子序列)
题目思路： 先求出所有的回文串。if(!(i&该回文串)) dp[i|回文串]=min(dp[i|回文串],dp[i]+1).#include<bits/stdc++.h>using namespace std;const int N=17;char s[N];int n;int st[1<<N],tmp[N],dp[1<<N];in...
2020-02-23 15:02:20
148
原创 HDU1074 Doing Homework(写作业的顺序改变使失分最少 基础状压dp+记录路径)
题目#include<bits/stdc++.h>#define low(x) ((x)&(-x))using namespace std;const int N=16,INF=0x3f3f3f3f;char s[N][105];int d[N],c[N],sum[1<<N];int bin[1<<N],dp[1<<N],now...
2020-02-23 12:11:25
122
原创 HDU4049 Tourism Planning(状压dp 一个状态的所有子集)
题目题意： 有n人，m个景点，每个景点有一个花费，每个人对每个景点有一个喜爱值，若去某个景点则每个人的bonus为对该景点的喜爱值减去该景点的花费，若两个人同时到某个景点则总bonus加上一个额外值，两两到同一点的额外值通过一个n*n的矩阵表示，每个人可以在中途离开，一旦离开不得再回来，现在旅行路线已经确定，求怎样计划每个人的去留使得总的bonus最大，输出最大bonus，若最大bonus小于等...
2020-02-23 11:08:00
145
原创 HDU1358 Period(字符串s的每个前缀是否为周期串 若是输出最大周期)
题目设前缀长度为len，若len%(len-该前缀子串的最长公共前后缀)==0.则证明该前缀是周期串，最大的周期为 len/(len-该前缀子串的最长公共前后缀)。 kmp中 nex数组可用来解决这个问题。证明的话 首先证明 若可以整除，则一定为周期串。再证明 若不可以整除要想为周期串的话，那么最长公共前后缀一定比nex[len]大，反之证明不整除一定不为周期串。最大周期是 len/(...
2020-02-11 20:57:55
234
原创 HDU1711 Number Sequence(kmp板子 输出t串在s串出现的第一个位置)
题目#include<bits/stdc++.h>using namespace std;const int N=1e6+5,M=1e4+5;int s1[N],s2[N],nex[N],n,m;void get_nex(){ int i=0,k=-1;nex[0]=-1; while(i<m){ if(k==-1||s2[i]==s2...
2020-02-11 20:11:50
118
原创 cf1263E(可修改判断括号是否为合法序列以及最大嵌套深度 线段树维护最大/小前缀和)
题目题意给你一段序列，其中L代表左移，R代表右移，小写字母代表在当前位置放置对应字母，),(代表在当前位置放置左右括号，当括号可以匹配时输出括号的最大层数，否则输出-1题解题解： sum==0&&mi[1]=0 为合法括号序列，mx[1]为括号嵌套最大深度。线段树维护最大前缀和 最小前缀和 详情见代码中update函数。#include<bits/stdc++.h&...
2020-01-28 12:09:35
319
原创 cf1168A. Increasing by Modulo(每次选择若干数进行(ai+1)%m，问使数组非递增的最小操作次数 二分+贪心 哭)
题目啊啊啊啊啊啊啊啊啊啊啊啊啊学习链接：https://www.cnblogs.com/Carered/p/10937082.html题意： 给一个数组，数组中元素范围为0~n，每次你可以选择若干元素进行(ai+1)%m的操作，问使数组呈非递增的最小操作次数。思路：因为每次都可以选若干个元素，用贪心思想，假设要操作x次，第一个元素加上x若能超过m，则对m取模最小值为0，令其等于0就好了，...
2020-01-20 22:44:38
262
原创 cf1168B. Good Triple(挺好的一道题！！思维灵活的不像尺取sl=smid=sr)
题目按正常的尺取就不会做。哭了。对于右端点取r找到一个l。 符合要求以r为右端点的点对有l个。对于右端点r+1。l 应该从之前的l+1开始遍历。假如以r为右端点的时候没有s[l]==s[r]==s[(l+r)/2]的点对，那么符合要求以r为右端点的点对个数为之前的p。这是最靠右的p.代码很好懂。#include<bits/stdc++.h>using namespace ...
2020-01-20 20:52:56
230
原创 cf1172B. Nauuo and Circle(全排列在圆上画边不相交的生成树 的种数)
题目#include<bits/stdc++.h>using namespace std;const int N=2e5+5,mod=998244353;typedef long long ll;int deg[N];int main(){ int n;scanf("%d",&n); ll ans=1; for(int i=1,x,y;i...
2020-01-20 18:19:40
236
原创 cf1175D. Array Splitting(将数组分成k部分 所有数的值*他所在的第几个部分 和最大 拆式子)
题目我就是个弱智。哭了。唉。怎么就是想不到拆开式子呢? 拆开之后很简单。sum=s[r1]*1+(s[r2]-s[r1])*2+(s[r3]-s[r2])*3+....+(s[rk-1]-s[rk-2])*(k-1)+(s[n]-s[rk-1])*k;把括号打开sum=k*s[n]-s[r1]-s[r2]-...s[rk-1];为了使sum尽可能大就选前k-1个前缀和即可 那么就对前...
2020-01-20 17:36:15
359
原创 cf1176D. Recover it!(给个2n序列打乱顺序找到长为n的原序列)
题目答案难道不是唯一的吗? 我觉着是唯一的代码第20行： 先从大到小，合数不能由合数变成，假如可以变成的话这个合数就不会剩余，遍历到比他大的那个可变成他的合数的时候–vis[它]了。代码第21行： 经过上一行的处理，剩下的数都是质数了。#include<bits/stdc++.h>#define m(a,b) memset(a,b,sizeof a)using nam...
2020-01-20 15:27:39
176
原创 cf1176E. Cover it!(将连通图选出不超过一半的点 使剩点与已选某或多个相邻 生成树奇偶层)
题目题意： 给你一张n个点m条边的连通图，无自环和重边。输出k和k个点的编号。 k<=[n/2]。使得没被选的点一定会和这k个点里至少一个有边相连。思路： 直接将图生成一棵树，第一种涂色方法是将奇数层全涂色，若这种方法涂色节点数大于⌊n/2⌋，那么将偶数层全涂色肯定可行。#include<bits/stdc++.h>#define m(a,b) memset(a,b,s...
2020-01-20 13:08:23
251
原创 cf1189A. Keanu Reeves(一个01串最少分割成多少串 使得每个串01数量不同)
题目题意： 一个01串最少分割成多少串 使得每个串01数量不同。思路: 要么不分割，要么分割成两个串。。#include<bits/stdc++.h>using namespace std;const int N=100+5;char s[N];int main(){ int n;scanf("%d%s",&n,s+1); int num0=...
2020-01-19 21:39:01
171
原创 cf1202B. You Are Given a Decimal String...(求出所有的x-y型 对于s串需要添加多少字符可被该计算器打印 巧妙地最短路暴力)
题目#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=10+5,M=2e6+5,INF=2e7;int dis[N][N];char s[M];int len;inline ll cal(int x,int y){ for(int i=0;i<10;++...
2020-01-19 16:55:52
149
原创 cf1204C. Anna, Svyatoslav and Maps(给一段邻间皆连边的路径，可删多少点使得最短路径不变)
题目题意： 给一段abcdefab…路径，保证相邻的两个点一定有直接边相连。问你可以最多删掉多少点，使得 给定路径也可以作为 要想经过删后的所有点的最短路径。思路： abcde 假如dis(a,b)+dis(b,c)=dis(a,c)。d这个点一定要删掉。因为此时ac之间经过d也是最短的。假如dis(a,c)+dis(c,d)>dis(a,d). c这个点一定要删掉。。显而易见。哦对刚...
2020-01-19 16:01:08
248
原创 cf1196D2. RGB Substring (至少修改多少字符才有一个长为k的RGB循环串 简单地推但我不会)
题目题意： 给你一个长度为n的只有R G B的字符串和k。问最少修改多少次，可以得到一个长度为k的RGB循环串。RGB循环串是RGBRGBRGB任意摘取的子串。思路：dp[i][0]分别表示从1-i为RGBRGBRGBR。。。这样的循环。dp[i][1]分别表示从1-i为GBRGBRGBRG。。。这样的循环。dp[i][0]分别表示从1-i为BRGBRGBRGB。。。这样的循环。那么...
2020-01-18 22:20:59
192
原创 codeforces1184C2. Heidi and the Turing Test (Medium) (坐标系旋转+固定长宽的矩阵最多覆盖多少点)
题目题意： 给n个点和半径r，请问半径为r的图形最多覆盖多少点。这里是指欧几里得距离。#include<bits/stdc++.h>using namespace std;const int N=6e5+5;struct node{int x,y1,y2,o;}a[N];inline int cmp(node A,node B){return (A.x==B.x)?(A...
2020-01-18 17:01:47
300
原创 HDU5091 Beam Cannon(给定长宽的矩阵最多覆盖几个点 模板)
题目题意：有N个点，有一个W*H的矩形，这个矩形和x，y轴平行，问你怎么放置这个矩形，能让矩形里的点最多。思路： 把每个原点（x，y）对应再来个映点（x+w，y），这样就有2N个点。这N个原点每次在区间【y，y+h】加1，而N个映点在区间【y，y+h】减1。就保证当前线段树里的所有的点都是横坐标位于最早的那个x往右w之内，代表这个矩阵的左下角的纵坐标是[y,y+h]此时可另当前点合法。解释不清...
2020-01-18 15:57:54
298
原创 poj3678 Katu Puzzle(2-sat 裸题 tarjan判断是否可行)
题目题意： 给你n个数和m组关系。 u v d XOR 意思是u^v=d。问是否可行。主要就是 u uu必须选u的时候应该 add(uu,u).#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=1e4+5,M=3e6+5;str...
2019-11-12 14:08:30
148
原创 poj3683 Priest John's Busiest Day(2-sat裸题 tarjan+topo输出方案板子)
题目题意: n个活动 属性为x y d.每个活动可以选择在[x,x+d]处举行，也可以选择在[y-d,d]处举行。判断n个活动是否可以不冲突的举行并输出任意一种方案。思路： 判2*n个决策是否相交。具体见make_graph()函数。#include<cstdio>#include<queue>#include<cstring>#include&l...
2019-11-12 09:40:55
152
原创 poj3207 Ikki's Story IV - Panda's Trick(2-sat 裸题 tarjan判断是否可行)
题目题意： 圆环上n个点编号为0,1,2,3…n-1，连接m组点，连线要么在圆内要么在圆外，判断这m条线是否有互不相交的情况。思路： 第 i 条线 和第 j 条线在圆内相交，在圆外也一定相交。设第 i 条线 在园内相连 是 i 否则是 ii ，第 j 条线 在园内相连 是 j 否则是 jj.如果 i 和 j 相交 则 i->jj jj->i ii->j j->...
2019-11-11 22:58:50
87
原创 gym102411E. Equidistant(是否找到树上一点到给定的树上k个点的距离相等并输出 多源bfs)
题目#include<bits/stdc++.h>using namespace std;const int N=2e5+5;struct Edge{int to,nex;}edge[N<<1];int head[N],tot;inline void add(int from,int to){ edge[++tot]=(Edge){to,head[fro...
2019-11-08 19:53:20
412
原创 cf701E. Connecting Universities(树上2*k个点分成k对 路径长度和的最大值)
题目题目给你一个n个顶点的树和2*k个点，可以组成k对，问k对的道路和最大是多少。思路考虑每条边的贡献的最大值，每条边都贡献最大也一定可以构造出这样的对，猜的。#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=2e5+5;struct Edge{int to,nex;...
2019-11-07 14:33:09
120
原创 cf701D. As Fast As Possible(小学数学推导)
题目题意已知n个人，一段路程为 l，走路v1，坐车v2，每车最多坐k人（每人最多做一次车），求所有人到终点的最小时间。上下车不需要时间，车转弯不需要时间，但是只有一辆车，车回去需要时间。思路所有人到达终点的时间是一样的。所以每个人坐车行走的距离都是一样的.第一组上车的人在0处上车，设在坐车行走距离 l1 然后下车。第二组此时走到了l1/v2*v1, 人和车此时相距(l1-l1/v2*v...
2019-11-07 11:19:42
257
原创 Codeforces Round #362 (Div. 2)
比赛链接文章目录cf697B. Barnicle(科学计数法转正常小数 模拟)题意代码cf697C. Lorenzo Von Matterhorn(超大线段树两点间的LCA)题意代码cf697D. Puzzles(树上dfs序遍历每个点编号的期望)题意：思路代码cf697E. PLEASE(简单概率+基础数论知识)题意思路代码cf697B. Barnicle(科学计数法转正常小数 模拟)cf...
2019-11-06 11:01:53
243
原创 cf697E. PLEASE(简单概率+基础数论知识)
题目题意有三个杯子都倒放在桌面上，中间的杯子里有筛子，每一次都把中间的杯子与左右两边的杯子等概论交换，问交换n后，筛子还在中间的杯子里的概率，对该式子约分之后 分母分子分别%1e9+7 输出分子分母。n非常大，给你k个数，n就是这k个数的乘积。#include<bits/stdc++.h>using namespace std;const int mod=1e9+7,p...
2019-11-06 10:45:22
240
原创 cf697D. Puzzles(树上dfs序遍历每个点编号的期望)
题目题意： 每个点访问他的儿子没有顺序。有好多dfs序。问树上每个点的dfs序标号的期望值。思路： 这个节点要么排在兄弟节点之前要么之后就是：dp[y]=dp[x]+0.5*1+0.5 * (sz[x]-sz[y]-1 +1).#include<bits/stdc++.h>using namespace std;const int N=1e5+5;struct Edge...
2019-11-05 23:46:11
215
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人