Cruiying
Cruiying
全部文章
分类
2-sat(1)
BSGS(2)
dfs(2)
dp(63)
dp + 线段树(1)
floyd(3)
Hash(1)
KM算法(1)
Kruskal重构树(2)
LCA(6)
manachar(2)
Mendix(4)
tarjan(1)
中位数(1)
主席树(2)
二分(3)
分数规划(3)
前缀和优化dp(2)
单调栈(6)
单调队列(1)
单调队列优化dp(1)
博弈(2)
后缀数组(15)
字典树(1)
差分约束系统(1)
并查集(4)
异或(2)
思维(2)
思维题(4)
扩展欧几里得算法(1)
拉格朗日插值(2)
数论(8)
未归档(15)
构造(1)
枚举(1)
模拟(3)
模板(1)
水题(4)
矩阵加速(2)
线段树(3)
网络流(2)
莫比乌斯反演(2)
莫队(4)
蓝桥杯(1)
规律(2)
贪心(2)
输入输出(1)
题解(1)
归档
标签
去牛客网
登录
/
注册
Cruiying的博客
全部文章
(共193篇)
CF946D (思维 + 分组背包 + dp)
题目大意:给出n行m列01串,对于每一行所要花费的代价是行中第一个1和最后一个1之间的距离加一,现在你有魔法可以去除掉k个1,问去掉不多于k个1的情况下,你所能获得的最小代价是多少。 题解:每一天翘多少课所得到的价值都是互相独立的,那么就很容易想到将每一天都看成一个物品组,翘不同数量的课可以达到不同...
dp
2019-08-20
0
381
CF1016C (前后缀 + 思维题)
题意:给一个2n的矩阵,每一个点有一个权值,从左上角出发,时间t=0开始,连续的走,将矩阵走完,每走一步,t++,并且得到t当前格子的权值的值,问如何走,使得最走完得到的最大权值和是多少。不难发现方案一定是先走一个S形,再直着走到头,再走回来。 #include <bits/stdc++.h...
dp
2019-08-17
0
374
CF1153D (树形dp + 思维 + 贪心)
n个节点以1为根的一棵树,每个非叶子节点都有一个操作max或min(0表示min,1表示max),表示这个节点中的值应该分别等于其子节点中所有值的最大值或最小值。假设树上有k个叶节点,你可以将每个叶节点填上[1,k]的数字,且每个数字只使用一次,求根节点的最大值 题解:树形dp 可以看出来是个树形d...
dp
2019-08-15
0
370
924C (思维好题)
大概意思就是说,每天画一条水平线(若与之前的重合则相当于线的数量不变,每天告诉你画的这条线上的线有多少条)。要每天这条线下的线的数量之和最小,求这个最小值。 题解:首先分析得出要是线下数量最少,因为线上是定值,所以转而求每天线的总数最少。设第i天,线上数为a[i],线下数为d[i],线总数为sum...
2019-08-14
0
336
CF1083A(树形dp)树上最长路径
题意:点有正权,边有负权。在这样的无根树中找到一条权重最大的链并输出权重(树上最长路径) 题解:将无根树转为有根树,我们把1当做根dp[u]表示节点u开始,子树先得最长路径 转移方程为:dp[u] = max(dp[u], dp[to] + a[u] - edge[i].w)对于每一个子树,找到最长...
dp
2019-08-14
0
368
CF375B (dp)
题目描述: 给你一个0、1组成的矩阵,大小为 n × m ,你可以把任意的两行的位置相互交换,请你给出变换后能得到的最大子矩阵,满足只由“1”组成。 输入: 第一行给出两个整数 n 和 m (1 ≤ n, m ≤ 5000)。 接下来 n 行每行给出两个给出一个矩阵a,仅有0、1组成,中间没有间隔。...
dp
2019-08-02
0
338
CF721C Journey(SPFA + dp)
给出一个n个点m条边的有向无环图。问从1到n,在距离不超过k的情况下最多经过多少点,并输出一个方案。 SPFA + dpdp[i][j]表示第i个点经过j条边的最小值 然后二维标记,直接跑SPFA #include <bits/stdc++.h> using namespace std...
dp
2019-08-02
0
474
多校(第五场)T2(十进制求广义斐波那契)好题
You are given four positive integers x0, x1, a, b. And you know xi=a⋅x(i−1)+b⋅x(i−2) for all i≥2. Given two positive integers n, and MOD, please calcu...
dp
2019-08-01
0
408
CF126B(后缀数组求LCP + 扩展KMP求LCP)
Asterix,Obelix和他们的临时伙伴Suffix、Prefix已经最终找到了和谐寺。然而和谐寺大门紧闭,就连Obelix的运气也没好到能打开它。 不久他们发现了一个字符串S(|S|<=1000000),刻在和谐寺大门下面的岩石上。Asterix猜想那一定是打开寺庙大门的密码,于是就大声...
2019-07-31
0
605
CF 407B. Long Path(dp好题+思维)
题目大意:有n+1个房间。从1-n个房间。每个房间有两扇门。一扇去i+1的房间另一扇去编号为pi的房间。问到达n+1的房间至少要走多少次。如果走过的次数是奇数次:就走pi这个门如果走过的次数是偶数次:就走i+1这个门(初始值1的位置是奇数)dp[i] 表示1到i这个位置需要走多少次门思路:因为 1 ...
dp
2019-07-31
0
437
首页
上一页
1
2
3
4
5
6
7
8
9
10
下一页
末页