Pikachu_杨京

分类

动态规划(1) 并查集(2) 搜索(3) 最小生成树(2) 最短路径(3) 未归档(24) 欧拉路径(1) 线段树(2) 背包问题(1) 贪心(2) 题解(3)

/ 注册

全部文章（共44篇）

2019牛客暑期多校（第二场） H题悬线法or单调栈

Second Large Rectangle 悬线法用来求解最大子矩形问题通过悬线法，可以找到以点（i，j）为底的极大矩形。 u[i][j]、l[i][j]、r[i][j]分别表示以为底的极大矩形的上边界，左边界，右边界；首先预处理：找到点（i，j）可以沿伸的的上端...

2019-07-20

1 1020

2019牛客暑期多校训练营（第一场） E ABBA dp

ABBA d[i][j] 表示放 i 个A j 个 B的方案数 d[i][j] 可以由d[i-1][j] 和d[i][j-1] 得到当 i <= n ,那么A可以随意放；当 j <= m，那么B可以随意放；当 i > n，如果放A，AB的数量要...

2019-07-19

6 2258

2019牛客暑期多校训练营 A 笛卡尔树 OR 单调栈

Equivalent Prefixes 题意：给你两个数组a，b，大小为n，让你寻找一个数p (1<= p <= n) ，使之在 1~p 任意一个区间中a,b数组的最小值下标相同。笛卡尔树：概念笛卡尔树的树根是这一子树中键值最小（或最大）的元素；且对于某个序...

2019-07-19

2 1095

洛谷P1020 导弹拦截最长不上升子序列及其优化

P1020 导弹拦截第一问，相当于求一个最长不上升子序列。第二问，相当于求一个最长上升子序列证明如下：假设打导弹的方法是这样的：取任意一个导弹，从这个导弹开始将能打的导弹全部打完。而这些导弹全部记为为同一组，再在没打下来的导弹中任选一个重复上述步骤，直到打完所有导弹。 ...

2019-07-17

0 937

Codeforces Round #270 D题：Design Tutorial: Inverse the Problem ，最短路+LCA+树上前缀和

Design Tutorial: Inverse the Problem 题意：给你一个距离矩阵，让你证明该矩阵是不是一颗加权树的距离矩阵。对于一个点u，与它距离最近的点一定是与它直接相连的，所以对矩阵求一次最短路，可以得到这颗树。然后只需要求出树上任意两点之间的距离是否与矩阵的距离相同就可以...

2019-07-15

0 732

牛客小白月赛16 小雨坐地铁分层图，最短路

小雨坐地铁官方题解：考虑分层图最短路。很容易想到建 m 层图，如果多条地铁线都经过同一个点，则在这些点之间暴力两两连边，这样连边是 O(n) 的，可能会超时。我们可以多建一层虚点，所有点到它对应的虚点不需要代价，从虚点到它对应的点需要对应的代价，这样就可以优化到 O(nm) 建图。最...

2019-07-15

0 723

牛客小白月赛16 小石的妹子线段树

小石的妹子官方题解：因为有两维的限制，所以我们先按 ai 从大到小排一下序，对于排序后的第 i 个妹子，她的排名就是 max{rk[j]}+1 (bj>bi)，那么我们把排名 bi 当成下标，把 rki 当成值，用线段树维护一下区间 max 即可。将bi排序...

2019-07-15

0 521

牛客小白月赛16 小阳买水果线段树

小阳买水果从大佬处学习的求出ai的前缀和，用线段树维护前缀和最大值，从 0 遍历到 n ，在线段树中找到大于sum[i]的最远的一个编号，每次先往右找，保证找到的值是最远。然后取最远距离 - i 的最大值。 #include<bits/stdc++.h> using na...

2019-07-15

0 573

ArabellaCPC 2019 J. Thanos Power 动态规划

J. Thanos Power 题意：给你一个数N，让你求它最少通过多少次操作得到的。初值为0，每次操作只能增加，x >= 0; 0最少通过多少次操作得到的N，等价于N通过多少次操作得到的0 从高位往低位看，，，对于每一位上的数x，我有两种方法让它变成0，一直加 1，加到1...

2019-07-14

0 807

ArabellaCPC 2019 I:Bashar and Hamada 贪心

Bashar and Hamada 给你一个长度为 n 的数组选k个数，使F=，ai 、aj k个数，i！= j 。求k=2，3，……n时，F的最大值首先n=2时，肯定选择数组中的最大值和最小值，这样F2=max-min，F2最大 n=3时，在F2的，然后无论选择哪个，假设选取的...

2019-07-14

0 666