- 博客(43)
- 收藏
- 关注
RSS订阅原创 牛客网 C张老师的旅行 三维区间DP
链接：链接来源：牛客网时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 262144K，其他语言524288K64bit IO Format: %lld题目描述张老师到了一个王国去旅游，王国有n个景点，张老师到达这个城市所在的车站恰好位于第x个景点，这个王国非常特别，恰好所有著名的景点都在分布在直线上，每个景点在坐标pi上(单位：公里)，张老师身体非常好，每走一公里花费一分钟。每个景点都有一个打卡点，并且必须在不迟于相应的时间（时间从张老师到达王国开始计算）前到达才能打卡成功并且给
2020-05-11 15:07:41
291
原创 牛客网 E.弦 初见卡特兰数
题目地址组合数学答案是 2^n / (n + 1)!。概率可以通过合法方案数/总方案数来计算。合法方案数 f(n)=Σf(i) * f(n-i-1), 即为卡特兰数，故 f(n)=C(2n, n) / (n + 1)。总方案数为 C(2n, 2) * C(2n – 2, 2) … C(2, 2) / n! = (2n)! / n! / 2^n。两者相除即为答案。除法取模的话用逆元来计算（即费马小定理）。 总复杂度O(n)。卡特兰数讲解//MADE BY Y_is_sunshine;//#inc
2020-05-10 18:39:39
208
原创 E.+Kaavi+and+Magic+Spell
codeforce div2 E我看了网上的一些博客和题解 在这里谈谈我对这道题的看法题意很好理解 经过合法操作以后找出前缀为t的序列的个数我们这里可以形象的理解 把字符串t补齐 和N一样大（斗地主中的癞子玩过吧） 我们定义’*'为万能字符那么题意就变为经过合法操作以后 可以变成t字符串的个数比如样例1s = “abab”t = “ba**”开始题解首先定义dp[l][r...
2020-04-16 15:41:41
594
2
原创 E. Tree Queries 子树编号()
dfs中引用l r这两个数组可以来说明该节点所在的子树的最小和最大编号很明显 本身就是最小的编号 最大的编号就是访问完所有的子节点之后的编号//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <...
2020-04-13 12:55:21
238
原创 尺取 POJ 2566
POJ 2566尺取法的应用条件和贪心比较像 必须递增或者递减才可以尺取//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib&...
2020-01-10 15:11:51
106
原创 尺取法 POJ 3320
题目地址求出包含所有数字的最短的子序列长度POJ好像不支持cin优化 想过改成scanf//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <...
2020-01-10 14:05:48
124
原创 codeforces round 75 D Salary Changing 二分
二分#include <bits/stdc++.h>using namespace std; const int MaxN = 200005; typedef pair <int, int> pii; int n, aim;pii seg[MaxN];long long s; int main() { int T; scanf("%d", &a...
2019-11-07 13:32:41
145
原创 牛客国庆大礼包 day1
题目地址牛客B题学到了 __int128的神仙用法牛客I题 记忆化搜索//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdli...
2019-10-02 16:23:17
159
原创 Educational Codeforces Round 73 (Rated for Div. 2) D
D链接//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include <cstring>#includ...
2019-09-20 00:38:59
162
原创 2019南京现场赛 Robots 概率DP
Robot//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include <cstring>#incl...
2019-09-03 23:00:18
145
原创 HDU 1166 敌兵布阵 树状数组
题目链接基本上卡着时间过得//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include <cstrin...
2019-09-03 11:01:12
107
原创 欧拉函数
欧拉函数快速求质因子的个数long long f1(long long N) { long long res; long long a; res = a = N; for (long long i = 2; i * i <= a; i++) { if (a % i == 0) { res = res / i * (i - 1); while (a % i == ...
2019-08-15 16:58:40
141
原创 概率DP POJ3071 正求概率
如果用按位操作符就一定要加括号。。除非你能都搞懂…还有啊这题get到新知识 二分式比赛的方法题目ID//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#in...
2019-08-10 10:58:54
124
原创 Educational Codeforces Round 70 (Rated for Div. 2) B D
ORZ#include <iostream>#include <string>#include <algorithm>#define llint long long#define inf 1000000000000000000using namespace std;string s;llint cnt[15];llint cost[15];...
2019-08-09 18:25:20
312
原创 概率DP POJ2096 逆序期望 （算是所有的模板了）
POJ 2096标程可能有问题… 最后输出要用%f这道题可以算是所有题目的模板了//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cst...
2019-08-09 17:12:13
196
原创 概率DP HDU4405 逆求期望
题目链接既然逆序 所以是N - 1的状态//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include <...
2019-08-09 16:06:25
163
原创 概率DP HDU 3853 逆求期望
这里第一道 感觉 ，，，，，，不要太用算法那来看待概率DP这就是数学题…//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdli...
2019-08-09 10:59:43
167
原创 区间DP HDU4283
HDU 4283这题柯南 柯南 柯南我也不是很懂大佬题解//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#i...
2019-08-08 17:51:57
144
原创 区间DP HDU2476 区间染色升级版
区间染色的升级版相当于两次区间DPHDU 2476//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#inclu...
2019-08-08 16:02:07
191
原创 区间DP HDU4632 容斥原理
比较新奇的区间DP题目涉及容斥原理题目地址//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include &...
2019-08-08 11:22:17
160
原创 区间DP 环形石子问题 四边形优化
题目就是环形石子问题，要优化//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include <cstring&...
2019-08-08 10:24:09
104
转载 区间DP 洛谷1430 序列取数
超链接大佬讲解//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include <cstring>...
2019-08-07 18:30:26
122
原创 区间DP 洛谷4170 区间染色
传送门独立做出来的第一道区间DP题目个人感觉不难//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#includ...
2019-08-07 17:05:20
278
原创 区间DP POJ1654
链接//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include <cstring>#include...
2019-08-07 16:36:56
82
原创 区间DP POJ2955 括号匹配
这里~//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include <cstring>#includ...
2019-08-07 15:26:28
149
原创 区间DP POJ1160
传送门大佬题解确定状态转移方程是很重要的dp[i][j] 表示前i个村庄有几个邮局时的最优解cost(i,j)表示 第i个到第j个村庄有一个邮局的时候的最优解核心是要想到 如果有奇数个村庄 邮局应该建立在正中间偶数个村庄的时候建立在中间的那两个村庄都一样//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#inc...
2019-08-07 10:47:40
109
原创 树形DP 洛谷P1490 奶思
- -、 在这里第一个代码 很巧妙数据是 dfs 过后的数据 因为本来dfs就是一种递归那么就可以去递归的重新读数据重新 递归 dfs 但是时间效率不是很高记忆化搜索//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorith...
2019-08-02 15:50:30
136
原创 树形DP 洛谷P2014
题目~跟那道苹果树 一样做得多了就有了更深的理解//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#inclu...
2019-08-02 10:12:50
130
原创 树形DP 洛谷P1131
猛戳这里我咋认为这题是贪心呢…//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include <cstri...
2019-08-02 09:29:29
119
原创 树形DP POJ2342 基础题
传送门//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include <cstring>#includ...
2019-08-01 12:44:39
92
原创 树形DP 洛谷P2015 含模板
传送门题目描述有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树2 5\ /3 4\ /1现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少...
2019-08-01 10:25:01
145
原创 HDU 1456 错排
递推DP大佬讲解//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include <cstring>#...
2019-07-31 21:53:07
138
原创 hdu 1516 LCS (编辑距离+记录路径)
注意输出的格式与内容DP很简单了LCS//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include <cs...
2019-07-31 18:43:13
171
原创 区间DP 含模板 取石子问题
//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include <cstring>#include &l...
2019-07-31 18:13:22
147
原创 CF# 576 div2 C D
C题题目 挺难理解的新知识long long maxx = 1LL << min((K * 8 / N), 31);AC 代码//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include &l...
2019-07-31 15:25:22
208
原创 牛客假日团队赛8
emmmmm<—在这里A题 最小支配集//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include <...
2019-07-31 15:20:16
110
原创 A Simple Problem with Integers 线段树
//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include <cstring>#include &l...
2019-07-15 21:41:47
122
原创 P1196 [NOI2002]银河英雄传说
洛谷题目//MADE BY Y_is_sunshine;//#include <bits/stdc++.h>//#include <memory.h>#include <algorithm>#include <iostream>#include <cstdlib>#include <cstring>#inclu...
2019-07-13 22:40:50
139
原创 食物链
Description动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述： 第一种说法是"1 X Y"，表示X和Y是同类。 第二种说法是"2 XY"，表示X吃Y。此人对N个动物，用上述两种说法，一...
2019-07-13 21:37:26
4596
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人