- 博客(132)
- 收藏
- 关注
RSS订阅原创 牛客-删除有序链表中重复出现的元素
题目这里通过递归来解决，对于当前数字a来说，有两种情况1.a的值和a的next值一样：这时候通过while 一直找到最后一个与a值相等的结点，再递归该节点的next2.a的值和a的next值不一样：直接递归a节点的next;/** * struct ListNode { * int val; * struct ListNode *next; * }; */class Solution {public: /** * * @param head
2021-06-11 16:27:03
125
2
原创 牛客-二叉树层序遍历
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */class Solution {public: /** * * @param root TreeNode类 * @return int整型vector<vector<>> */ vector<vector<int.
2021-06-11 15:09:41
102
原创 斜率DP模板
斜率dp 线性裸题 3507#include<stdio.h>#define N 500010int dp[N];int q[N];int head,tail;int sum[N];int a[N];int n,m;int getDP(int i,int j){ return dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m;...
2018-10-03 15:54:57
211
转载 关于lower_bound( )和upper_bound( )的常见用法
lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。在从小到大的排序数组中，lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返...
2018-08-12 15:58:00
2331
转载 CF1005E
题意n个数字，问m是多少个区间的中位数？偶数个数字的区间中位数认为是中间靠左的那个数字，比如(1,3,7,8)中位数为3。E1：这n个数字是1~n的一个排列E2：n个数字，数字大小不超过2e5题解做法①(可过E1，过不了E2)：思路请看：51Nod ~ 1682 ~ 中位数...
2018-08-12 14:51:21
189
原创 组合数学
#define mod 998244353#define ll long longusing namespace std;ll fac[maxn],inv[maxn],dp[maxn];int a[maxn];void Init(){ fac[0]=inv[0]=inv[1]=1; for(int i=1;i<maxn;i++)fac[i]=1ll*fac[i-1...
2018-08-07 15:46:46
648
原创 CF988
先总结一下，这场打的sb了，被hack两题，难受啊！减成呆头鹅A.给定n个数，要选出m个互不相同的数。模拟B.给定n个串，问能否把它们排列成满足前一个是后一个的子串的序列？模拟C.给定n个数列，问是否存在两个数列各取掉一个数字，使得两数列和相等map标记一下就好了#include<bits/stdc++.h>using namespace std;const int maxn=2e...
2018-06-04 22:14:49
332
原创 CF987
A.字面意思，就模拟一下就好#include <bits/stdc++.h>using namespace std;char s[100];int vis[100];int main(){ int n; scanf("%d",&n); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;+...
2018-05-30 16:56:36
423
原创 cf985
题目链接：http://codeforces.com/contest/985A：暴力题吧，只需要在把黑色和白色的值都算一遍，最后取两种情况的min就可以了。B:模拟题，只需要每次枚举那个开关不动即可。C：只需要sort一下，想一下如何选取即可。举个栗子吧：其中划竖线的地方就是临界点（刚好满足题意）#include <bits/stdc++.h>using namespace std;...
2018-05-26 21:17:03
636
原创 树剖模板
void dfs1(int u,int pre,int step){ dep[u]=step; fa[u]=pre; num[u]=1; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(v!=pre) { v
2017-09-28 20:00:48
210
原创 UVA 11990 bit + cdq 分治
题意：动态逆序对做法：对于删除操作可以当做逆向的添加操作 ， 所以对于每个数字都有三个属性 （T,ID,Num） 所以这道题其实就是一个三维偏序问题 。 对于一个数 只需要 左边比它大的数 和右边比它小的数 ，我们可以用一个bit logn 进行操作。三位偏序 可以用CDQ 减去一维 ， 我们先把左边算出来 ，再把右边算出来，最后处理中间部分的。对于中间的部分 用双指针 一个指向 L
2017-08-25 22:32:53
256
原创 HDU 1892 二维树状数组 模板题
假设每个格子代表一个数A[i][j]，i是横坐标，j是纵坐标，左上角的坐标为（1，1)我们要求红色区域元素之和，设sum(i,j)表示以i,j坐标为右下角坐标，以0,0为左上角坐标矩形内的元素之和，sum(c,d):绿色+黄色+红色+蓝色sum(c,b-1):绿色+蓝色sum(a-1,d):绿色+黄色sum(a-1,b-1):绿色则红色区域元素之和=sum(c,d)-sum(c
2017-08-25 22:20:36
335
原创 复习艾教
Day 1 乱搞Day 2 状压DP + 状压 BFSDay 3 线性DP + 区间DPDay 4 素数筛 + 最大公约数 + 分解质因数 + 同余运算 + 快速幂 + 中国剩余定理 + 费马小定理 + 积性函数 miller-rabin 函数 + pollard-rho 分解质因素 +二次剩余 + 原根 + （扩展）离散对数 + 莫比乌斯反演Da
2017-08-13 22:17:00
272
原创 2017 暑假艾教集训 day12 网络流（最大流 最小割）！
模板using namespace std;int n,m;const int maxn=1005;struct node{ int to,next,cap;}edge[maxn<<2];int head[maxn],cnt;void add(int u,int v,int w){ edge[cnt].to=v; edge[cnt].next=head[u];
2017-08-13 00:01:26
215
原创 2017 暑假艾教集训 day11 线段树！
BZOJ 2212做法：线段树的合并，从下往上进行合并，顺便判断兄弟节点是否交换，如果不交换逆序对为左子树的+右子树的+左子树大于mid * 右子树小于mid。如果交换加的就是左子树小于mid*右子树大于mid的。合并操作很神奇，还有 动态开点删点也有多注意！！！ 先递归较大的子树（收点收到早防止MLE）#include using namespace std;typede
2017-08-11 23:27:12
215
原创 2017 暑假艾教集训 day10 AC自动机+马拉车+后缀数组 +kmp
https://vjudge.net/contest/177933#overviewH HDU3068做法：马拉车模板#include using namespace std;const int maxn= 110015;char s[maxn];char str[maxn*2];int dp[maxn*2];int mlc(){ int n=strlen(s+
2017-08-10 23:16:18
409
原创 2017 暑假艾教集训 day10 （补zoj2112带修改的第k大）整体二分
ZOJ 2112带修改的区间第k小只用比静态的多加一个删除操作即可#include using namespace std;const int inf=1e9+7;const int maxn=220000;struct node{ int l,r,k,val,cur; int id,kind;}q[maxn],q1[maxn],q2[maxn];int
2017-08-10 22:49:41
188
原创 2017 暑假艾教集训 day8 （补一道思维题，
HDU 2615做法：好好读题！！！。当时晚上做的，完全不知道在写什么。首先第一刀切任何地方都有可能， 所以先暴力枚举第一刀。而第二刀就不同了，这里第二个人是有智慧的，会切一刀使他得到的最大，只需要在第一重循环下开一个maxtwo变量即可，同时当答案相同时，第三个人取最小答案。wa点 第二刀枚举的时候应该在第一刀的左右都要枚举。 n很小，只要读懂题就可以暴力过#in
2017-08-10 00:49:15
209
原创 2017 暑假艾教集训 day9(整体二分 + cdq分治 cdq真是我女神！！！)
POJ 2104 求第k小做法：整体二分加树状数组。离线把询问和插入做整体二分，每次把s，t扫一般 如果是插入就在线段树上相应的位置插入（val，1）。对于每个询问查询在l，r 中 用多少个数 如果加上累加的数 小于k那么 答案应该在右区域把该询问扔到右区域 并把查询的结果累加（左区间本来有查询结果个前k小，直接进入右边会少算）。如果大于 k 的话那么答案应该在左端扔进左端
2017-08-10 00:42:41
267
原创 2017 暑假艾教集训 day8 （树链剖分+树上点分治）
POJ 2763树链剖分 边权化点权问题（只需要把边的权值给深度大的节点转换为点权值问题即可）#include #include #include #include #include using namespace std;const int maxn=100100;int n,m,s;struct node{ int to,next;}edge[maxn*3]
2017-08-09 02:08:04
196
原创 2017 暑假艾教集训 day7 （树链剖分模板）
HDU 3966树链剖分模板题#include using namespace std;const int maxn= 50010;int n,m,q;int c[maxn];int head[maxn],cnt=0;struct node{ int to,next;}edge[100005*2];void add(int u,int v){ edge[c
2017-08-08 09:05:49
260
原创 2017 暑假艾教集训 day6
CF 240F做法：二维线段树，分别记录一个区间的小写字母个数，每次从小到大给两边分配（字典序最小）（区间更改）！#include #define lson rt<<1,begin,mid#define rson rt<<1|1,mid+1,endusing namespace std;const int maxn= 100100;char str[maxn];
2017-08-07 00:43:47
232
原创 2017 暑假艾教集训 day5
HDU 2157做法：做一个矩阵 MU[S][T]=1 ,那么答案就是 MU[S][T] 在 K次矩阵乘之后的（矩阵快速幂）； HDU 821E做法：和上道题略有区别 分段矩阵快速幂，每次保留最右界的可能数，这里有个wa点需要把 y+1以上的方案都改为0，不可到达。 然后构造如下矩阵#include using namespace std;
2017-08-07 00:27:16
263
原创 合数的质因数分解 + 递归求等比数列前n项和
质因数分解const int maxn=10000;bool book[maxn+10];int prim[maxn+10],pnum=0;void getprim(){ memset(book,0,sizeof(book)); pnum=0; book[1]=book[0]=1; for(int i=2;i<=maxn;++i) {
2017-08-05 00:10:53
430
原创 大数的质数检验以及求最小质因子
#include #include #include #include #include #include using namespace std;typedef long long ll;ll random(ll n){ return ((double)rand()/RAND_MAX*n+0.5);}ll powmuilt(ll a,ll b,ll mod){
2017-08-05 00:07:26
1024
原创 模板 BSGS
大佬的手写Hash。飞快ll p,b,n;class HASH{public: ll a[100005],inv[100005],mod; HASH() { memset(a,-1,sizeof(a)); mod=100003; } ll Find(ll x) { ll idx=x%mod;
2017-08-05 00:05:43
346
原创 欧拉函数+莫比乌斯函数 模板
求单个数的欧拉函数ll getoula(ll n){ if(n==1) return 0; ll ans=n; for(int i=2;i<=(int)sqrt(n+0.5);++i) { if(n%i==0) { ans = ans * (i-1)/i; while(n%i==0
2017-08-05 00:03:51
267
原创 2017 暑假艾教集训 day4
题库： https://cn.vjudge.net/contest/176263#overviewA：HDU 40704做法：相当于将 n 任意组合， 可能的情况为 2^(n-1)，因为n会很大，使用欧拉降幂公式B：Given A,B,C, You should quickly calculate the result of A^B mod C. (1做法：同上题一样算出C
2017-08-05 00:00:10
329
原创 2017 暑假艾教集训 day3
题目：https://cn.vjudge.net/contest/176068#overviewUva 12260做法：Petra的策略满足贪心，所以先把糖果按P在按J排序，然后去取，就看Jan会取哪些糖果了。 每次默认Jan先取，如果petra先取的话，i从2开始循环。那么每个糖果就可以看成是Jan取不取，但是要注意，由于Petra是一定会往后一个取，所以Jan取
2017-08-03 23:57:53
163
原创 2017 暑假艾教集训 day2
练习题 ：https://cn.vjudge.net/contest/175510#overviewCTSC 拯救大兵瑞恩做法：状压BFS，每个节点加一个当前所有的钥匙数，然后进行普通的BFS即可POJ 2411做法：轮廓线 状压经典题，先DFS出 s 状态和它的父亲 pre ，每次转移 dp[i][s]+=dp[i-1][pre]；DFS时 每次有横着放和竖着
2017-08-02 22:10:15
169
原创 2017 暑假艾教集训 day1
1.蓄水池问题http://acm.nyist.net/JudgeOnline/problem.php?pid=547做法：先把池子的四周用优先队列存起来，枚举每个点向四个方向延伸（注意vis数组），如果拓展点的高度小于当前节点的高度 ans+=（H[now]-H[ex]） 并且把拓展点的高度改为当前点的高度 否则直接扔进队列即可，a.UvaLive 7147做法：做过第
2017-08-02 00:24:31
207
原创 2017暑假集训 div1 匹配问题（1）
HDU 4185题意：给一张图，其中有一些#，两个相连的#可以称为一次覆盖，为最多几次覆盖（#只能被用一次）做法：每个#标号，暴力跑一边每个#的四个方向，建图做匈牙利 答案 是pp/2;POJ 3020 题意：用天线覆盖城市，最多可以覆盖相邻的两个城市，问用多少天线可以完全覆盖做法：不仔细想还以为和上道题一样，上道题问的是最多，这道题是完全。
2017-07-21 14:41:19
203
原创 2017暑假集训 div1 DP（2）
poj 3186题意：给一串数字，每次可以从最左端和最右端拿去一个数字，得到的价值是本身数字乘以拿去的次序做法：区间DP 每次枚举长度然后枚举起点，从左右两端开始转移即可DP[I][J]代表I是起点J 是终点的最大值。#include #include #include #include #include using namespace std;int n;
2017-07-20 16:43:23
184
原创 2017暑假集训 div1 DP（1）
HDU 1024题意：为给定一个数组，求其分成m个不相交子段和最大值的问题。做法：很容易想到转移方程 DP[i][j]=max(DP[i][j-1],dp[i-1][k])+a[j]; n2的状态，转移又有n ，所以一共n3。所以我们得想个办法优化一下。优化1：可不可以在进行转移时，已经把 max dp[i][k] 预处理出来呢。答案是可以的，实现的时候加上滚动的思想优化2：
2017-07-18 21:49:48
224
原创 2017暑假集训 div1 匹配问题（1）
A ZOJ 1002题意：放棋子，棋子横竖不能相见。做法：直接暴力DFS就行了。n很小只有4B HDU2444题意：给定n个学生，他们之间可能互相认识，首先判断能不能将这些学生分为两组，使组内学生不认识；现想将学生两两分组，且保证每一组的学生都认识，这样分组可达到的最大组数为多大？做法：首先用BFS染色判断是否是二分图，相连的边异色，如果不是则直接NO就行了
2017-07-18 17:06:44
220
原创 强联通注意点
重边的判断模式void tarjan(int u,int pre){ low[u] = dfn[u] = ++d_cnt; mys.push(u); int flag=0; for(int i=head[u]; i!=-1;i=edge[i].next) { int v=edge[i].to; if(!dfn[v])
2017-07-18 12:33:21
149
原创 强联通
include #include#include#include#include#include#includeusing namespace std;const int maxn=20100;vector g[maxn];stack s;int dfn[maxn],low[maxn],scc[maxn];int vis[maxn];int d_cnt=0,s_cn
2017-07-18 12:29:17
183
原创 2017暑假集训 div1 连通图（2）
HDU 4612 题意，给一张图，问加一条边之后最小剩多少桥做法（参考大神）：直接算出原始桥的个数减去缩点后树的直径（啥玩意啊）树的直径：树上最长的一条路的长度。 就是从最深点经过root到次深点那条路的长度具体的做法就是：先bfs出最后出队列的点，然后以该点为起点再bfs一遍，这次最后出队列的dis值就是直径#include #include #include
2017-07-17 22:09:13
174
原创 2017暑假集训 div1 连通图（1） POJ3694 &&POJ3177
POJ 3694题意：一个网络管理员管理一个网络，网络中的电脑直接或间接的相连接，管理员有Q次操作，每次向网络中建立一条新边，向管理员报告桥的个数思路：先将网络中的桥求出来，在求的过程中进行并查集缩点，在询问的时候，进行最朴素的LCA查找最近公共祖先，在求的过程中判断节点与父节点是不是在同一个集合中，如果不在同一个集合，说明是桥，则这个桥将不存在，将两个集合合并。#includ
2017-07-17 21:32:04
193
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人