- 博客(441)
- 收藏
- 关注
RSS订阅原创 新博客地址
换博客了博客二：https://www.cnblogs.com/liweihang/博客三：https://blog.nowcoder.net/liweihang入职腾讯了，有很多工作上的东西就不能写博客了。
2021-09-10 11:26:12
192
原创 每日一题 4月8日 黑白树 树形DP
题目链接：https://ac.nowcoder.com/acm/problem/13249#include<bits/stdc++.h>#define LL long longusing namespace std; int k[100005], f[100005];int ans=0;vector<vector<int> > v(10000...
2020-04-07 15:08:39
301
原创 每日一题 4月7日 树 dfs序+DP
题目链接：https://ac.nowcoder.com/acm/problem/13611#include <bits/stdc++.h>#define LL long longusing namespace std;const int mod=1e9+7; LL f[305][305];int main(){ int n, m; scanf("%d%d...
2020-04-07 15:07:06
248
原创 牛客OI周赛15-提高组 A 环球旅行-树的直径
题目链接：https://ac.nowcoder.com/acm/contest/4912/A#include <bits/stdc++.h>#define LL long longusing namespace std; struct E{ int to, w; E(int a, int b){ to=a; w=b; }};...
2020-04-07 15:05:30
209
原创 学军信友队趣味网络邀请赛 A-B-D 思维+树形DP/直径+数论
题目链接：http://115.236.49.52:83/contest/1351题解：假设n是奇数。n如果是偶数，翻转90度就可以了。B:#include <bits/stdc++.h>using namespace std;#define LL long long vector<vector<int> > v(50005);int...
2020-04-07 15:02:48
308
原创 牛客OI周赛15-普及组 B 三角形+D 多元组 DP
B:#include <bits/stdc++.h>#define LL long longusing namespace std; int a[105][105];LL f[105][10005];int main(){ int n, k, m; scanf("%d%d", &n, &k); for(int i=1; i<=...
2020-04-07 14:58:24
181
原创 牛客OI周赛15-提高组 - 恢复数列
题目链接：https://ac.nowcoder.com/acm/contest/4912/B#include <bits/stdc++.h>#define LL long longusing namespace std; vector<int> v;int main(){ int n, x; scanf("%d%d", &n, &x...
2020-04-07 14:55:10
137
原创 每日一题 4月3日 Shortest Path 树上贪心
题目链接:https://ac.nowcoder.com/acm/problem/13886题意：有一棵树，有n个节点。让你分成n/2对。所有对之间的距离和最小。思路：我们尽量让每条边不重复经过。那么对于一棵子树v。和他的父亲节点u。还有之间的边权w。如果siz[u]%2== 1那么v就和u连。ans+=w。如果siz[u]%2== 0那么v和自己的子树连过了。不加w的贡献。#includ...
2020-04-02 20:08:04
160
原创 牛客练习赛60 旗鼓相当的对手 树上启发式合并
题目链接：https://ac.nowcoder.com/acm/contest/4853/E#include <bits/stdc++.h>using namespace std;#define LL long longtypedef pair<LL, LL> pll;LL n, k, a[100005];vector<vector<int&g...
2020-04-02 20:05:58
198
原创 每日一题 4月1日 Rinne Loves Edges 树形DP
题目链接：https://ac.nowcoder.com/acm/problem/22598?&headNav=acm#include<bits/stdc++.h>#define LL long longusing namespace std; struct node{ LL to, w;};vector<vector<node> ...
2020-04-01 16:06:23
138
原创 区间的连续段 - 倍增DP
题目链接：https://ac.nowcoder.com/acm/contest/82/B#include<bits/stdc++.h>#define LL long longusing namespace std; LL a[1000005], s[1000005]={0}, f[1000005][25];int main(){ int n, m, k; ...
2020-03-31 21:45:56
185
原创 每日一题 3月31日 城市网络 树上倍增 or DFS+线段树 or DFS+单调栈
题目链接：https://ac.nowcoder.com/acm/problem/13331//我们讲一讲这个是怎么逼近//可以证明f[u][0]一定是f[father[u]][i]购买路径上的节点//把一个查询作为一个节点。那么最后就是看从查询的u节点开始能最多跳多少次，并且不超过v节点。//往上倍增寻找第一个比a[u]大的节点下面那个节点(他的父亲就是第一个比a[u]大的节点);...
2020-03-31 21:43:40
202
原创 每日一题 3月30日 滑动窗口 单调队列
题目链接：https://ac.nowcoder.com/acm/problem/50528//单调队列的模板题。#include <bits/stdc++.h>using namespace std; int a[1000010];int q[1000010];int main(){ int n, k; scanf("%d%d", &n, &...
2020-03-31 21:40:11
135
原创 牛客练习赛60 D-斩杀线计算大师(exgcd)
思路：#include <bits/stdc++.h>using namespace std;#define ll long long ll extend_gcd(ll a,ll b,ll&x,ll&y) { if(!b) { x = 1; y = 0; return a; } ll ...
2020-03-28 21:47:42
181
原创 牛客练习赛60 C-操作集锦 长度为k的子序列个数(DP)
题目链接：https://ac.nowcoder.com/acm/contest/4853/C#include <bits/stdc++.h>using namespace std;#define LL long longconst int mod=1e9+7; char s[100005];LL f[1005][1005], g[30]={0};int main...
2020-03-28 00:14:52
793
原创 P3332 [ZJOI2013]K大数查询 - 整体二分-区间修改
题目链接：https://www.luogu.com.cn/problem/P3332思路：我们区间修改用一个线段树维护就可以了。#include <bits/stdc++.h>using namespace std;#define LL long long#define mid (l+r>>1)LL a[200000+10], sum[50000*4+10...
2020-03-26 20:52:34
220
原创 ZOJ-2112 整体二分 单点修改-区间第k小
题目链接：https://vjudge.net/problem/ZOJ-2112多样例：输入一个样例数t。输入一个n和m。数组长度和操作数Q l r k：查询区间[l, r]的第k小的数C x y：修改a[x]=ySample Input25 33 2 1 4 7Q 1 4 3C 2 6Q 2 5 35 33 2 1 4 7Q 1 4 3C 2 6Q 2 5 3...
2020-03-26 20:50:48
207
原创 每日一题 3月27日 数学考试 线性DP
题目链接：https://ac.nowcoder.com/acm/problem/15553#include <bits/stdc++.h>using namespace std;#define LL long long LL a[200005], f[200005];int main(){ int t; scanf("%d", &t); w...
2020-03-26 13:52:06
198
原创 每日一题 3月26日 合并回文子串 区间DP
题目链接：https://ac.nowcoder.com/acm/problem/13230思路：我们用f[l1][r1][l2][r2]:表示A[l1]A[r1]和B[l2]B[r2]是否能合并成一个回文串。考虑转移：因为顺序是不能改变的。所以只有这4个可能的转移。#include <bits/stdc++.h>using namespace std;#define ...
2020-03-25 16:18:03
212
原创 POJ 1390 Blocks - 颜色段消除的最大分数 三维DP
题目链接：http://poj.org/problem?id=1390&tdsourcetag=s_pctim_aiomsg题目大意：一个积木游戏，有连续的n个方块。相同颜色的方块连续方块可以消除。如果该段由k个积木组成。得分为k*k。我们首先把相同颜色的积木合并成一个块a[i],用b[i]表示a[i]有多少个积木。我们用dp[i][j][k]:表示段[i,j]并且j的右边有k个和a...
2020-03-11 22:27:21
272
原创 洛谷P3147 DP-倍增
题目链接：https://www.luogu.com.cn/problem/P3147题目大意：思路：我们用f[i][j]表示从位置j开始合并成一个数i的最远位置。怎么转移呢？我们只考虑i由两个i−1合并而来。那么合并完第一个i−1的位置f[i−1][j]。那么第二个i−1的起始位置在f[i−1][j]，终点在f[i−1][f[i−1][j]]所以f[i][j]=max(f[i][j],f...
2020-03-10 20:51:30
166
原创 Codeforces Round 83 E. Array Shrinking DP-相同的元素可合并求剩余的最少元素
题目链接：https://codeforces.ml/contest/1312/problem/E题目大意：给你一个数组，两个相邻的相同元素X可以合并成一个元素X+1。可以无限次合并。问最后数组剩余的最少元素。我们用dp[i]表示前i个元素可以合并成的最小元素数量。考虑转移:如果a[1]−a[i]的某个后缀a[x]−a[i]可以合并成一个元素。那么就可以dp[i]=min(dp[i],dp...
2020-03-10 14:30:30
336
原创 Codeforces Round 83 D.Count the Arrays 单峰数组数量-组合计数
题目链接：https://codeforces.ml/contest/1312/problem/D题目大意：问你一个满足下列条件的数组数量。1.有n个元素2.每个元素在[1,m]3.正好有两个元素相同4.存在一个i:a[j]<a[j]+1(j<i)a[j]>a[j]+1(j≥i)\begin{array}{l}1.有n个元素\\2.每个元素在[1, m]\\3.正好有...
2020-03-10 13:55:27
174
原创 洛谷P3224 永无乡 - 连通块合并查询第k小权值 并查集+线段树合并
题目链接：https://www.luogu.com.cn/problem/P3224题目大意：思路：直接给每个岛建立一棵线段树。然后用并查集合并岛，线段树合并一下两个岛的权值。#include <bits/stdc++.h>#define LL long longusing namespace std;const int N = 1e5+5;int w[N], p[...
2020-03-09 21:36:15
204
原创 洛谷P3605 线段树合并
题目链接：https://www.luogu.com.cn/problem/P3605题目大意：给出一颗树，每个点都有一个权值，最后对于每个点，输出在它的子树中，有多少个点的权值比它大。把权值取负，就是p[j]<p[i]的节点个数。直接线段树合并。#include <bits/stdc++.h>#define LL long longusing namespace s...
2020-03-09 20:33:29
144
原创 调度问题-完成事件需要时间:a[i]，截止时间：t[i]
问题一：https://nanti.jisuanke.com/t/43373水灾了。有n个城市。抢救每个城市需要时间a[i]。每个城市会在t[i]时被销毁。必须在<=t[i]（小于等于）才能抢救这个城市。问你最多能够抢救多少城市，时间从0开始。in:55 106 152 73 34 11out:4#include <bits/stdc++.h>#d...
2020-03-02 23:34:51
521
原创 ICPC North Central NA Contest 2017 - D. Smooth Array 分组背包+前缀最大值转移
题目链接：https://nanti.jisuanke.com/t/43371题目大意：有n个数。给你一个k和s。每个数字可以改变成0-s。让你以相邻的k个为一组[a[1]…a[k]], [a[2]…a[k+1]]…。问使每一组的和为s。至少需要改变多少个数。根据题目的条件这个数组最后的样子一定是以k为循环节。a[1]=a[k+1],a[2]=a[k+2]…那么就是有k组数。我们把每组数出...
2020-03-02 20:48:20
301
原创 Codeforces Round #625 E - World of Darkraft: Battle for Azathoth - 线段树
题目链接：https://codeforces.com/contest/1321/problem/E题目大意：有n个武器。每个有属性攻击力：a[i]，价格：ca[i]。有m个盾牌。每个有属性防御力：b[i]，价格：bc[i]。有k个怪物。每个有防御力xk, 攻击力yk，价值zk。现在你必须并且只能买一个武器和一个盾牌。如果你的攻击力>怪物的防御力并且你的防御力>怪物的攻击力。...
2020-03-02 19:23:04
306
原创 牛客练习赛58 E-最大GCD 离线-区间与X的最大gcd
题目链接：https://ac.nowcoder.com/acm/contest/4090/E题目大意：思路：我们可以证明一定是一个区间里面的a[i]与X。你们问题就转化成给你一个区间[L, R]找到一个L<=i<=R。最大化gcd(a[i], X)。因为最大GCD一定是X的因数。可以直接莫队维护一个区间%P的个数。题解思路：//莫队#include<bits/st...
2020-03-01 18:30:40
353
原创 poj1947 Rebuilding Roads - 树上背包-删除最少边得到一个大小为p的连通块
题目链接：http://poj.org/problem?id=1947题目大意：一棵节点数为n的树。让你删除最少的边。得到一个大小为p的子树。 p<=n<150。我们考虑用f[u][s]为选择u节点及其子树大小为s的删除最小边树我们考虑用f[u][s]为选择u节点及其子树大小为s的删除最小边树 我们考虑用f[u][s]为选择u节点及其子树大小为s的删除最小边树dfs过程中增加一棵...
2020-02-28 14:25:50
208
原创 [FJOI2015]最小覆盖双圆问题 - 最小圆覆盖+坐标系旋转
题目链接：https://ac.nowcoder.com/acm/problem/19959题目大意：思路：我们考虑有一条直线把这些点，分割成两个部分。分别做一个最小圆覆盖。半径取max(R1, R2)。我们可以考虑旋转坐标系来枚举直线的斜率。那么对一条特定的坐标系。按坐标轴就可以二分一下。得到最优的半径。只要旋转180度就够了。#include<bits/stdc++.h&g...
2020-02-27 19:36:31
286
1
原创 2018 ACM 上海大都会赛重现赛 A Fruit Ninja-随机算法
题目链接：https://ac.nowcoder.com/acm/problem/17376题目大意：给你n个点。问算法存在至少有M个点在一条直线上。M/N>=x。X为只有一位小数的实数。思路：我们假设存在。那么M>=0.1n。每次选择两个点至少有0.01的可能性选择到。当然这是最坏复杂度。我们随机找200次如果还不能找到就No。#include <bits/stdc...
2020-02-24 21:37:20
153
原创 POJ3318-随机算法-O(N*N)判断矩阵A*B=C
题目链接：http://poj.org/problem?id=3318题目大意：多样例。给你3个nn的矩阵A， B，C。问AB=C是否成立。成立输出YES。不成立输出NO。并且题目提示O(N^3)复杂度会T。暴力肯定是O(N^3)。我们可以随机化一个N1的矩阵D。如果AB=C。那么ABD=CD并且BD的复杂度为O(N ^ 2)得到一个N1的矩阵再和A相乘也是O(N ^ 2)。CD的复杂度...
2020-02-24 21:30:02
1144
1
原创 Codeforces Round #622 (Div. 2) C2. Skyscrapers (hard version)-单调栈+dp
题目链接：https://codeforces.ml/contest/1313/problem/C2题目大意：有n栋房子。每个房子的最高的高度b[i]应该在[1, a[i]]区间里。现在要满足不存在i<j<k有a[i]>a[j]<a[k]。并且要b[i]的和最大。输出b[i]-b[n]。方案可能不唯一。随便输出一个就可以。思路：我们可以知道b[i]数组是一个单峰函数。...
2020-02-24 13:05:43
410
原创 牛客小白月赛22 H 货物种类- 扫描线+差分
题目链接：https://ac.nowcoder.com/acm/contest/4462/H题目大意：思路：我们可以把每个仓库当作一个时间点。把操作颜色离线保存。那么对于一个操作就是拆分：在时间点l添加颜色d。在r去掉颜色d那么对于一个操作就是拆分：在时间点 l 添加颜色d。在r去掉颜色d那么对于一个操作就是拆分：在时间点l添加颜色d。在r去掉颜色d按时间线扫描一下就可以 了。对于...
2020-02-23 09:25:19
226
原创 洛谷 P1020 导弹拦截 Dilworth定理
题目链接：https://www.luogu.com.cn/problem/P1020题目大意：Dilworth定理:偏序集能划分成的最少的全序集个数等于最大反链的元素个数。例如对于(a[i],b[])和(a[j],b[j])这两个元素,如果我们定义偏序关系为：a[i]<a[j]并且b[i]>b[j]那么它的反链为：a[i]<a[j]并且b[i]<=b[i]对于这道题...
2020-02-18 19:11:30
182
原创 Codeforces Roun d #621 (Div. 1 + Div. 2) D. Cow and Fields 最短路+贪心 图上特殊点加边使最短路最大
题目链接：https://codeforces.ml/contest/1307/problem/D题目大意：有一个无向图n个点m条边，其中有k个特殊点。现在让你在两个特殊点之间连一条边。让1到n的最短路最大， 。...
2020-02-18 16:48:29
271
原创 2020牛客寒假算法基础集训营6 E-立方数 - 质因子分解
题目链接：https://ac.nowcoder.com/acm/contest/3007/E题目大意：我们要求最大的A。我们根据唯一分解定理：N=e1p1∗e2p2∗e2p2∗e2p2∗...ekpkN=e_1^{p_1}*e_2^{p_2}*e_2^{p_2}*e_2^{p_2}*...e_k^{p_k}N=e1p1∗e2p2∗e2p2∗e2p2∗...ekpk...
2020-02-17 14:38:19
463
3
原创 2020牛客寒假算法基础集训营3 J-牛牛的宝可梦Go - floyd最短路+类LIS DP
题目链接：https://ac.nowcoder.com/acm/contest/3004/J题目大意：我们可以很容易得到一个K^2的算法。因为每个时间都不同。那么按时间排序。就是一个LIS。如果满足(j->i)时间差>=dis(i, j)那么就可以转移。f[i]:在捉完第i只宝可梦获得的最大战斗力f[i]:在捉完第i只宝可梦获得的最大战斗力f[i]:在捉完第i只宝可梦获得的...
2020-02-17 13:11:22
168
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人