鞠永全

题解

/ 注册

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

每日一题

线段树这个题可以先排序，从左到右做，每次更新这个颜色最后一次出现的位置，放入线段树。如果所有颜色都出现过，就去线段树中查询所有颜色最后一次出现时间的最小值。每次更新当前位置与这个最小值之差的最小值作为答案，时间复杂度为O(N(log n+log k))。线段树长度只用开k即可。 #include&l...

2020-08-15

0 767

每日一题

题意：二分图的建图：每件装备只能用一次，如果把攻击序列建成点，就是装备和攻击顺序的匹配。比如属性值是3和5，那么这件装备要么在3位置要么在5位置被使用。当然，按攻击顺序开始匹配，一旦匹配不成功，根据题意就必须中止。还有，每次memset太慢了，用时间戳id。(或者bitset也行)。 #...

2020-08-13

0 765

每日一题

题意：用1 X 2的矩形填充4 X n的矩形，共有多少种不同方法。思路：原来写过一个2*n的，递推推公式就行。如果n-1行填满的话，第n行只有一种情况，如果n-2行填满的话，有4种情况；如果n-3行填满的话，有2种情况；如果n-4行填满的话，有3种情况；如果n-5行填满的话，有2种情况；...

2020-08-12

0 876

每日一题

题意：有30000个岛屿从左到右排列，给你一个n一个d，n代表有n个宝石分别，接下来n行表示每个宝石分别在哪个岛屿上，d代表你第一次从0开始跳跃到的位置，以后你每次可以从你的位置跳跃l-1，l，l+1的距离。解题思路，其实以前做过一个类似的，他跳跃的步数其实很小，解设每次跳一步加以来也是（n+1）...

2020-08-11

0 697

每日一题：二进制枚举，贪心

题意：选总共K行或者列，每个数字选之后就变成0，问最大能取多少？思路：1.枚举选那几行的情况通过二进制表示，标记那几行选了用01串表示，1表示选，0表示不选。2.确定了行后，计算每一列的和，剩下的次数选列的和最大的。 #include <bits/stdc++.h> #define ...

2020-08-10

0 647

每日一题【简单排序】

题意：上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条...

2020-08-08

0 864

每日一题【二分图染色】

每日一题【二分图染色】题意：给两个栈和一个排列每次可以选择序列的第一个数入任何一个栈或者让任一一个栈顶元素出栈要求出栈顺序为1-n 思路：首先如果我们只有一个栈会要怎么做，2，3，1不是怎么入栈都不行吗？那么我们可以考虑a[k]<a[i]<a[j] k<i<j,此时我们...

2020-08-07

0 861

每日一题 dij变形

题目描述：思路：首先最短路不一定边数最短，所以我们肯定要求出所有的情况取最小值，求出每一天的最短路，dis[day][n]，类似于最短路的转移方法就行；看到现场赛有人暴力dfs加剪枝过的，也是很厉害OVO #include <bits/stdc++...

2020-08-06

0 750

【每日一题】8月5日题目—蓝魔法师 (树形dp统计方案数）

https://ac.nowcoder.com/acm/problem/20811参考：https://blog.nowcoder.net/n/a52f02e1f87844e494690964fc6959dc题意：给出一棵树，求有多少种删边方案给出一棵树，求有多少种删边方案使得删后的图每个连通块大小...

2020-08-05

1 1040

购物

购物 https://ac.nowcoder.com/acm/problem/14526 题意：n * m个糖果，每个糖果都有价格，小明需要花最少的钱保证每天都有糖果吃，而且每天不能购买超过m个糖果，每天买第j个糖果的价格是a[i][j]+j*j，问你最少花多少钱过n天？思路：首先想到对每天的...

2020-08-04

0 700