Meul

题解

11eyes的算法笔记(4) ACM(1) Atcoder(14) BFS(1) codeforces(38) DFS(2) dp(3) ICPC(1) sublime text 3(1) 容斥(1) 未归档(10) 模拟(1) 洛谷(2) 牛客(26) 牛客题霸(1)

/ 注册

全部文章 / 题解（共75篇）

NC20568 [SCOI2012]滑雪与时间胶囊

Question 有1到n个景点，每个景点有一个高度h，从1号节点出发，求能到达多少个景点和最小生成树。 Solution 预处理有向边建图 Kruscal这道题和普通的求最小生成问题的区别在于，这里是有向路，高度只能从高到低(可以相等)。那我们需要从1号节点开始dfs预处理能够走得通的有向路，并将...

kruscal dfs

2020-05-01

0 596

NC5505E 装备合成

C 装备合成题意：牛牛有{x}x件材料{a}a和{y}y件材料{b}b，用{2}2件材料{a}a和{3}3件材料{b}b可以合成一件装备，用{4}4件材料{a}a和{1}1件材料{b}b也可以合成一件装备。牛牛想要最大化合成的装备的数量，于是牛牛找来了你帮忙。思路： 1.线性规划 O...

三分数学

2020-04-29

1 776

NC14704 美味佳肴

Question 给定n个食物素材和m个食物种类，每个食物素材具有不新鲜度b，每个食物具有特定且唯一的食物素材编号为j，美味值a和做菜所需要的时间c。食物美味值，求T时刻，最大美味值为多少？ Solution 每个食物的美味度只和他完成的时间点有关。两个食物若默认比先做后做的区别在于: 我们对其排序...

DP 01背包

2020-04-28

0 683

NC17137 Removal

Question 一串由组成的长度为的序列，求拿掉m个数后有多少个不相同的子序列。(mod 1e9+7) Solution 这道题去重和DP的思路和操作集锦是差不多的。唯一不同的点是操作集锦那道题中的表示的是选了多少个，这里是不选多少个，因为的范围比较小，如果表示选了多少个这里会MLE+TLE。再来...

2020-04-28

0 581

NC17065 子序列

Question 一个由n个元素组成的序列，她想知道其中有多少个子序列，满足对于所有的成立。 Solution 盲猜当满足时前后都是单调递增的。严格证明(来源于雨巨的题解！我估计我可能真的做的时候会盲猜试一发，或许这是一种直觉？)然后DP求对应的贡献即可，设表示必选第i个的情况下有多少种满足的取法,...

dp

2020-04-28

0 524

NC14301 K-th Number

Question 将所有连续区间中第K大的数放入一个新的数组B中，求数组B中第M大的数为多少？ Solution 二分+尺取答案具有单调性，故考虑二分。看了邓老师的题解之后发现居然可以二分诶那么问题就是check函数该如何写了，这里要用到尺取法判断。我们求任意连续区间中第K大的数的数量，若数量则L...

二分尺取

2020-04-23

0 620

NC204867 旅旅旅游

Question 牛妹在城市 1，他想把所有城市走一遍，可是她不想走可以属于从1到n的最短路的路径，牛妹不知道他能不能将所有城市全走一遍，你能告诉她吗？ Solution djikstra 并查集 djikstra两遍求从1到n的最短路和从n到1的最短路。判断每一条路是否为最短路，若非最短路则将...

最短路 djikstra 并查集

2020-04-20

2 524

NC14583 糖糖别胡说，我真的不是签到题目

Question 个人排成一排，每个人有能力值，分为两组或。第秒的时候，第个人可以消灭掉所有排在他前面的和他不是同一组的且能力值小于他的人。有次发功，第次发功的时间为，则在第秒结束后，都会增加1.第n秒后，会有多少人存活下来。 Solution 堆模拟差分跟着时间模拟，直接暴力为会TLE，因...

2020-04-20

0 615

NC5158 H-人人都是好朋友

Question 张纸条，上面写着三个整数。若表示和为朋友。否则表示其为敌人。朋友的朋友也是朋友，问是否有矛盾的情况？ Solution 离散化并查集矛盾的情况为既是朋友又是敌人，很容易想到利用并查集去处理这里的关系。"牛可乐的手下有 1e9 个"这句话是告诉我们直接开数组是要MLE的，...

并查集离散化

2020-04-19

1 516

NC5158 D-牛妹吃豆子

Qustion 给你一个的矩阵，有次操作，每次操作给出四个数字 : 表示牛可乐会将所有满足这两个条件的位置上放一个豆子。次询问，每次询问给出四个数字 : 表示询问所有满足这两个条件的位置上中总共有多少个豆子. Solution 二维差分+二位前缀和 ←不会的戳这里← 先根据次操作...

差分前缀和

2020-04-19

3 804