PhantomSamurai
PhantomSamurai
全部文章
分类
图论(1)
基础算法 二分 双指针等(4)
数据结构(3)
数论 数学(5)
比赛(1)
题解(53)
归档
标签
去牛客网
登录
/
注册
Blog
TA的专栏
29篇文章
0人订阅
每日一题
29篇文章
725人学习
全部文章
(共68篇)
减成一
题意 每次任选一个区间减去一 问最少操作次数使得区间内的值都为一 思路 如果位置i的数 比 i-1更小 那么它对答案没有贡献 因为肯定从i-1开始作为区间的左端点 i这个位置相当于白嫖了减去一 直接跳过如果位置i的数 比 i-1更大 那肯定还要再选一个区间 i-1这个数变成1了 i这个数不为1 而对...
2020-06-02
0
568
【每日一题】 contest 树状数组
来自专栏
思路:三维偏序问题 固定某两位选手 计算逆序数对 会有重复计算排名高 和 排名低的情况 最终答案除以2即可 #include <bits/stdc++.h> using namespace std; #define LL long long #define ULL unsigned ...
2020-06-01
0
558
【每日一题】[JSOI2007]建筑抢修
来自专栏
题意: 从n栋楼里修楼 每栋楼有修理时间和截止时间 问最多能修多少栋楼 思路: 贪心是肯定的。我们先按结束时间排序,结束时间越早 你就可以干越多的事 其次按消耗时间排序 但是会存在性价比更高的方式 前面消耗时间太长 导致后面可以有更多的选项没有选到 采用开个堆 反悔贪心一手 如果我当下无法选择这个修...
2020-05-26
0
385
【每日一题】图的遍历 染色法
来自专栏
题意 给出n个点m条边的图 每次只能走两步 问最少加多少条边能完整遍历这个图 思路: 完整遍历首先要保证图联通 这是肯定的 计算联通块的个数 把这几个联通块连在一起就能保证图是联通的 加的边数是联通块个数-1 其次是要保证 每个点都能遍历到 容易想到奇环 如果一开始遍历不到的点 进入奇环后转一圈 ...
2020-05-21
1
723
【每日一题】简单瞎搞题 背包 bitset
来自专栏
实质是一个背包 对于一个数 我们只需要知道能否表示它 即0和1的状态 所以用bitset来优化当前状态由上一个状态转移过来 #include <bits/stdc++.h> using namespace std; #define LL long long #define ULL u...
2020-05-20
0
542
【每日一题】 「土」秘法地震 二维前缀和 + 暴力
来自专栏
题意: n * m的图上求大小为k*k的正方形中和大于0的个数 思路: 首先要知道暴力怎么枚举 枚举正方形的话由当前位置就可以得到 x = i + k - 1 y = j + k - 1 正好为两个对顶点 然后k*k 算正方形内的值 暴力计算复杂度为枚举正方形是肯定的 快速得到各个区块内的值 容易...
2020-05-16
0
426
【每日一题】maze bfs
来自专栏
meaning:n * m的网格图上求S到T的最短距离 走一步耗费时间为1 传送门耗费的时间为3 solution:容易想到bfs 但由于你传送过去所花费的时间不一定是最少的 所以不能用vis来标记 采用维护dist距离数组更新从S到各个点的最短距离 最终求出最短距离 tips:1.判断当前点能...
2020-05-16
4
606
【每日一题】Moovie Mooving 状压dp
来自专栏
题意:n部电影 每部电影有m个放映机会和放映时间 希望在0~l的这段时间内不停的看电影 允许看到一半出来 但不允许跳出来再跳回去 求满足条件下看的电影部数最少 思路:n只有20大 考虑搜索或者状压dp 但每部电影还有不同放映时间 且范围来到1000 就只能是状压dp 用dp[i] 来表示i表示二进制...
2020-05-11
0
560
【每日一题】「火」皇家烈焰 dp
来自专栏
题意:长度为n的字符串 统计不同烈炎的情况思路:首先容易想到用dp[i][0/1] 来表示当前位置是否有火的情况 发现对这题还不太够 这题涉及到当前位置 左右的情况 所以再开一维 来表示当前位置 下一个位置的情况 上一个位置的情况可以由 i - 1 状态得到接下来就是分类讨论了1.当前没有 左右没有...
2020-05-08
0
489
【每日一题】[SCOI2009]粉刷匠 dp
来自专栏
题意:n条木板 每条木板被分成m段 有t次机会粉刷连续的一段木板为蓝色或者红色 问最多能粉刷多少段木板 思路: 当粉刷为第1段时 状态从上一条转移过来上一条明显是i-1 然后你上一条一定已经处理完了所以j的维度为m 当前次为k次 从k-1的状态转移过来 而粉刷的颜色讨论一下 取较大者即可 否则由...
2020-05-08
0
487
首页
上一页
1
2
3
4
5
6
7
下一页
末页