- 博客(91)
- 收藏
- 关注
RSS订阅原创 2018-2019 ACM-ICPC, Asia Jiaozuo Regional Contest H题(后缀数组+单调栈+线段树)
题目链接：https://nanti.jisuanke.com/t/A2206题意：给你n个数，1<=l<=r<=n，求所有本质不同的a[l...r]的最大值的和分析：本质不同的子串可想到用后缀数组，所有子串等价于该串的所有后缀的所有前缀，利用后缀数组求本质不同的子串的原理，即本质不同的子串=总子串个数-本质相同的子串个数=n-sa[i]+1为该后缀的前缀个数，即...
2019-10-20 21:39:38
252
原创 BZOJ1150(WQS二分优化dp）
题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1150分析：我们用dp[i][j][0/1]表示第i座楼与第i-1座楼是否相连(0/1)，前i座楼构成了前j组的最小距离花费。然后可以写出转移方程但显然是n^2，由于j与dp具有单调性，j增加，dp也会增加，而且dp是一个下凸函数，因为选的组的距离会越来越大。考虑二...
2019-08-20 21:20:22
207
原创 2019牛客暑期多校训练营（第十场)（斜率优化dp)
先推荐一个大佬的博客：https://blog.csdn.net/lxc779760807/article/details/51366552J题链接：https://ac.nowcoder.com/acm/contest/890/J题意：给 n 个木材，求制造 k 个木板浪费的木材的最小值，木材可以随意组合，制造木板浪费的木材：将 m 块木材连在一起，将所有的木材砍成一样的高度，砍掉的就是...
2019-08-20 17:40:09
190
原创 wustoj2613电话号码(字典树)
题目链接：http://10.162.32.3/problem.php?id=2613&soj=0分析：要求独一无二的字符串，可把每个号码的所有后缀都插入字典树，这样就会得到每个号码的所有子串，然后枚举每个号码的每个后缀，假设删除该后缀后，不存在该后缀了那么该后缀肯定是独一无二的，最后恢复一下就好了。Ac code：#include<bits/stdc++.h>...
2019-08-17 09:22:20
183
原创 Codeforces Round #136 (Div. 1)E(尺取法+树状数组)
题目链接：https://codeforces.com/contest/220/problem/E题意：只保留a数列中1..l和r..n的数构成b数列，然后b数列的逆序对数小于等于k.问这样的l,r的对数。分析：树状数组+尺取枚举l,每次找到最小的满足题意的r，对答案的贡献是n-r+1,然后用两个树状数组，分别维护增加或者减少一个数的时候，前半段和后半段对逆序数的影响。Ac cod...
2019-08-16 20:31:22
132
原创 hdu6665(离散化+bfs)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6665题意：两个矩形能把平面分割为多少个部分比赛时都是疯狂if else 做的，写了200+行，然鹅我不想写这种繁琐的，就没写....考虑简洁明了的方法，先把坐标离散化，然后把矩形边界标记为1，每次从标记为0的开始bfs，把访问过的点标记为1，由于矩形边界被标记为1了，矩形外面的点bfs时进...
2019-08-14 20:37:23
165
原创 期望DP
推荐一篇大佬的博客：https://www.cnblogs.com/hua-dong/p/8166093.html直接上例题1、hdu4405题意：有n+1个点编号从0->n，有m组通道可以直接从xi->yi不需要花费一次走的次数，每次可投一个骰子，如果点数为x，当前处于i点，即可走到i+x位置，求走到n点的花费的次数的期望。分析：期望dp一般都是从后往前推，设dp[i...
2019-08-13 14:23:09
350
原创 2019 Multi-University Training Contest 7 补题
题目：hdu6656题意：你处于i级，必须花费a[i]元的前提下，有r[i]/s[i]的概率跳到i+1级，也有1-r[i]/s[i]的概率掉回x[i]级（x[i]<=i)，有q组询问，每次有l,r问从l升到r的花费期望。分析：需要列出方程找公式，设f(i->i+1)表示从i->i+1花费的期望，则用sum[i]表示从1->i的花费期望则化简得：最后递推一...
2019-08-12 21:14:41
255
原创 2019牛客暑期多校训练营（第八场）补题
A题：题目链接：https://ac.nowcoder.com/acm/contest/888/A题意：求所有全为1的矩阵且每个子矩阵都不会被其他矩阵完全包含的子矩阵的个数。分析：最近遇到的全1子矩阵的题有点多额....，可是还是不怎么会做。但基本都用了单调栈....设h[i][j]表示第i行以j点为底点的最高连续的1的个数，可以用单调栈求使j点以h[i][j]为高度的矩形的左右边...
2019-08-12 10:34:54
159
原创 2019牛客暑期多校训练营（第七场）补题
C题：链接：https://ac.nowcoder.com/acm/contest/887/C题意：n中树，第i种树有P[i]颗，砍掉每颗树的代价是C[i], 高度是H[i].需要用最小的代价砍掉一些树，让最高的树超过一半。分析：从从低到高枚举最高的树，在剩下的树当中砍掉代价最小的。可以用一颗线段树维护。线段树按照代价从小到大的顺序构建，支持单点插入，查询前x个的总和。Ac c...
2019-08-12 10:00:08
96
原创 Comet OJ - Contest #8 C题
题目链接：https://www.cometoj.com/contest/58/problem/C分析：一个dp题，关键是怎么设计，详细见代码注释Ac code:#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=1e5+5;ll a[maxn],b[maxn...
2019-08-09 23:06:35
120
原创 2019 Multi-University Training Contest 6补题
题目：hdu6638题意：给你n个点，每个点都有一个坐标和权值，要你寻找一个矩阵使其内部的点的权值和最大。分析：把n个点按横坐标排序一下，首写枚举左右边界，当左边固定右边界移动时，会将x值相等的坐标加进来，x值相等的左边加完后查询此时的最大子段和，更新答案。Ac code:#include<bits/stdc++.h>using namespace std;typ...
2019-08-07 21:17:21
195
原创 2019 Multi-University Training Contest 5补题
题目：hdu6625题意：给你两个数组a,b，要求你重排a,b使c[i]=a[i]^b[i]得到的c数组字典序最小分析：根据贪心思想，每次都要求得a[i]^b[i]都最小才能保证字典序最小。有两种方法：方法一：对a,b两个数组建两颗字典树，每次同时遍历两棵字典树，如果都为0或都为1就走，否则没有办法只有一个走0一个走1，此时对答案产生贡献，每次找出来的最后排个序就okAc co...
2019-08-06 22:57:33
91
原创 ACM-ICPC 2018 焦作赛区网络预赛 E(树链剖分+线段树)
题目链接：https://nanti.jisuanke.com/t/A2015题意：给你一棵树，根结点为1，初始每个结点值都为0，支持以下操作1、u v x 将u->v路径上的每个结点的值都乘上x2、u v x 将u->v路径上的每个结点值都加上x3、u v 将u->v路径上的每个结点值都按位取反4、u v 求u->v路径上的每个节点的值的和分析：如...
2019-08-06 18:53:49
160
原创 2019 Multi-University Training Contest 2 补题
1011：http://acm.hdu.edu.cn/showproblem.php?pid=6601题意：给你n个数，q次询问，每次询问一个区间[l,r]表示只能从[l,r]区间里选最大的能构成三角形的三条边，输出其最大周长。分析：一看肯定说用线段树维护，但。。。。。比赛时想了好久不知道维护什么，甚至还不顾莫队的T飞的复杂度交了几发。维护一个区间的45个最大值，这样一定能找到周长最大...
2019-07-24 23:35:07
117
原创 2019 Multi-University Training Contest 1补题
1002：http://acm.hdu.edu.cn/showproblem.php?pid=6579题意：给你n个数，有m次操作，每次操作有两种1、0 l r 表示查询[l,r]里选任意个数时异或值最大。2、1 x表示在n个数后面继续添加1个数x，并令n=n+1分析：选任意个数使异或值最大肯定是线性基的题，比赛时直接上线段树维护区间线性基，时间复杂度都没算，结果T到飞起.......
2019-07-23 15:04:41
149
原创 2019牛客暑期多校训练营（第二场）补题
题目链接：https://ac.nowcoder.com/acm/contest/882#questionH题：题意：给你一个01矩阵，要你求全为1的第二大子矩阵分析：用单调栈或悬线法皆可以。法一：单调栈设dp[i][j]表示以(i,j)为底点，底边长为1，dp[i][j]为高的矩阵。用单调栈处理最大子矩阵问题，但要注意每个点都要更新最值，不然找不出所有的值也就不一定找的到第二...
2019-07-21 23:29:50
97
原创 hdu3804(树链剖分+线段树)
题目：http://acm.hdu.edu.cn/showproblem.php?pid=3804题意：给你一个树，每条边都有一个权值，现在有m组询问，每次询问输入一个二元组(x,y)，其结果要满足以下两个条件的最大值1、必须是从x->1路径上的一条边2该边的权值必须<=y，且是最大的边分析：把询问离线处理，先把原本树的边按权值从小到大排序，询问按y值从小到大排，对于边...
2019-07-17 15:29:11
134
原创 Codeforces Round #199 (Div. 2) E
题目链接：https://codeforces.com/problemset/problem/342/E题意：给你一个树，起初根结点(1号结点）为红色，其余结点为蓝色，每次有两种操作。1、把蓝色结点涂成红色2、求给定结点v与树上最近的结点之间的距离，每条边权值都为1分析：题解很巧妙，把m次操作中1操作分成块，每次对于1操作次数如果到了sqrt(m)，就用bfs更新已有的红色点i到其...
2019-07-17 10:52:03
88
原创 树链剖分
第一次学树剖，推荐一篇大佬博客：https://www.cnblogs.com/KatouKatou/p/9557540.html树剖关键代码：void dfs1(int u,int f){ sze[u]=1; for (int i=head[u];~i;i=edge[i].nxt){ int v=edge[i].v; if(v==f)co...
2019-07-16 17:40:07
91
原创 LCA的应用
1、多次询问求树上两个点的距离例题：hdu2586http://acm.hdu.edu.cn/showproblem.php?pid=2586分析：LCA的板子题，关键利用dist[u,v]=dist[1,u]+dist[1,v]-2*dist[1,lca(u,v)];Ac code:#include<bits/stdc++.h>using namespace s...
2019-07-15 21:30:50
465
原创 二维树状数组
1、单点修改，区间查询例题：https://loj.ac/problem/133分析：类比一维的单点修改，区间查询Ac code:#include<bits/stdc++.h>using namespace std;const int maxn=5100;typedef long long ll;ll c[maxn][maxn];int n,m;int l...
2019-07-15 15:11:18
137
原创 扫描线
首先推荐一篇大佬的博客：https://blog.csdn.net/xianpingping/article/details/83032798题目：http://poj.org/problem?id=1151扫描线裸题，主要是为了贴个板子Ac code:#include<stack>#include<cstdio>#include<iostrea...
2019-07-15 11:01:43
69
原创 Comet oj Contest #3 D(线段树维护线性基+差分树状数组）
题目：https://www.cometoj.com/contest/38/problem/D?problem_id=1543分析：如果是单点修改，这题就是⼀个线段树维护区间线性基的题，但这⾥是区间xor，我们考虑维护原序列的xor差分，这样每次修改的时候只需要修改两个位置的值就可以了，不⽤修改⼀个区间。 查询的时候，只需要特判边界，因为简单的线性代数知识告诉我们维护xor差分的线性基和原序...
2019-07-13 15:35:00
93
原创 牛客小白月赛16D(前缀和+二分)
题目：https://ac.nowcoder.com/acm/contest/949/D题意：中文题自己看分析：利用前缀和的后缀max的单调性，它是单调递减的，sum[i]表示前缀和，pmax[i]表示从i~n中最大的sum[j]，i<=j<=n。然后枚举起点i,在[i,n]上二分终点，只要pmax[mid]>sum[i-1]就表示满足条件，继续增加l=mid+1，否则不...
2019-07-13 10:51:47
100
原创 线性基
感谢大佬博客：https://blog.csdn.net/qaq__qaq/article/details/53812883定义设数集TT的值域范围为[1,2n−1][1,2n−1]。TT的线性基是TT的一个子集A={a1,a2,a3,...,an}A={a1,a2,a3,...,an}。AA中元素互相xor所形成的异或集合，等价于原数集TT的元素互相xor形成的异或集合。可以理...
2019-07-12 17:05:26
123
原创 Codeforces Round #566 (Div. 2) E(矩阵快速幂)
题目：https://codeforces.com/contest/1182/problem/E分析：一道矩阵快速幂的题，关键是要两边取对数，再构造矩阵。两边取对数：令g[i]=,则g[i]=g[i-1]+g[i-2]+g[i-3]+2*i-6,从而可以构造出矩阵。最后再取幂还原就行了Ac code:#include<cstdio>#include ...
2019-06-13 12:59:52
226
1
原创 HDU6534(离散化+树状数组+莫队)
题目：http://acm.hdu.edu.cn/showproblem.php?pid=6534题意：给一段序列，27000次询问l到r区间有多少对（i,j）（i<j）使得|ai−aj|<=k分析：首先分析可知，每增加一个数x，答案就会增加num(x−k<=i<=x+k)，减少同理减少这么多。所以离散化+莫队+树状数组就完事了，总复杂度O()。Ac code:...
2019-06-04 21:58:24
233
原创 Minieye杯第十五届华中科技大学程序设计邀请赛网络赛
题目：https://ac.nowcoder.com/acm/contest/560/J题意：给你n个数，要你求最少删除多少个数使剩下的数可以划分成两个和相等的集合分析：一个简单的dp，比赛时想不出来唉。。dp[i][j]表示前i个数划分成两个集合，使和相差为j，要删除的数的个数，最终dp[n][0]即为所求初态dp[0][0]=0;状态转移：dp[i][j]=min({dp[i-...
2019-05-12 18:25:35
132
原创 树形dp+二分
题目：https://ac.nowcoder.com/acm/contest/560/I题意：给你结点数为n的树，有n-1条边，每个结点都有一个权值，要你划分成k个连接的部分使每个部分的最小值最大分析：对于这种最小值最大问题一般都是二分，二分答案，然后dfs如果一部分>=答案就把它截取下来，一直截完看它有没有k个部分。Ac code:#include<bits/std...
2019-05-12 17:38:59
150
原创 第十五届华中科技大学程序设计邀请赛补题
C题：https://ac.nowcoder.com/acm/contest/700/C题意：给你n个数，要你求长度在[L,R]之间的区间中有多少个区间的区间和>=S分析：考虑以点pos作为左端点，其满足条件的区间和为[pos,pos+l-1]到[pos,pos+r-1]，转化为前缀和，即为求x∈[pos+l-1,pos+r-1]的区间内，满足pre[x]−pre[pos−1]≥...
2019-05-03 22:57:51
184
原创 马拉车算法求回文子串个数
题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=6012分析：给定两个字符串s,t 结论：s，t不相同的第一个字符下标为l，最后一个字符下标为r 如果l==r，那么不存在解 如果l<r,那么翻转s的一个子串时，一定是将s[l]和s[r]互相翻转反证：假设存在s[l]和s...
2019-05-03 19:58:07
879
原创 欧拉降幂
题目：分析：一道欧拉降幂的题，关键是要知道多次(最多25次)欧拉降幂后最后取模会变为1，也就是指数会变为0，剩下的直接求。ac code:#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=1e7+1;int phi[maxn],prime[maxn...
2019-04-19 21:52:57
126
原创 hdu5787数位dp
题目：http://acm.hdu.edu.cn/showproblem.php?pid=5787分析：数位dp板子题，关键要去除前导0的影响。ac code:#include<bits/stdc++.h>using namespace std;typedef long long ll;ll dp[20][11][11][11][11];int num[20];...
2019-04-19 20:07:44
92
原创 树状数组求逆序对
题目：http://acm.hdu.edu.cn/showproblem.php?pid=5792分析：计算像a，b这样上升的有la对，像c，d这样下降的有lb对，ans=la*lb。这样是有重复的，重复的就是a与c重合，a与d重合，b与c重合，b与d重合这四种情况。那么减去这四种情况就ok了。可以用树状数组预处理出每一位i的左边比a[i]大的有多少La[]，少的有多少Li[]，右边比...
2019-04-10 23:09:21
104
原创 第k短路
题目：http://poj.org/problem?id=2449分析：第k短路板子题贴个板子：#include<cstdio>#include<cmath>#include<algorithm>#include<vector>#include<cstring>#include<queue>using...
2019-04-10 20:57:28
226
原创 二分+线段树
题目：C. Storetime limit per test 1.0 smemory limit per test 256 MBIchuan is a store owner and his store has n products, numbered from11tonn.Recently, his business is not very good, and he c...
2019-04-07 21:55:46
497
原创 2017 Multi-University Training Contest - Team 8
题目：http://acm.hdu.edu.cn/showproblem.php?pid=6143题意：给你长为n的姓和长为n的名，有m种字母，要求姓和名不能出现相同字母且姓和名必须填满长为n，求种类数分析：枚举姓用了i种颜色，则为C(m,i)*a[n][i],其中a[n][i]表示用i种颜色涂n个格子的方案数且i种颜色必须都用，剩下(m-i)种颜色填名字可随便填有(m-i)^n种，故总方...
2019-04-06 19:44:23
102
原创 离散化+线段树
题目：http://acm.hdu.edu.cn/showproblem.php?pid=6464分析：每次1操作会往序列底加first个second，first 和 second 都是最大1e9的数据，每次2操作询问序列中第first到第second个数的和一开始就感觉有点像线段树，输入数据太大我们可以离线处理把数据离散化下，然后扔到线段树上，维护两个数组：sum: 区间数的值的...
2019-03-18 17:05:27
969
原创 牛客练习赛41
B题：https://ac.nowcoder.com/acm/contest/373/B分析：一个简单的计数dp，比赛时居然在dfs...状态转移dp[i][j]=dp[i-1][j-a[i]]+dp[i-1][-j],dp[i][j]表示第i回合分数为j，由于有-j，可把分数整体加上一个大数k,并且由于空间不够要用滚动数组,特判去掉666的情况。Ac code:#include...
2019-03-02 20:28:50
315
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人