Tag_Kausal

分类

未归档(20) 题解(12)

/ 注册

全部文章（共13篇）

排列询问题解

解法1：AC首先需要知道的是满足对于一个排列来说最多只有对，所以我们可以暴力把这对存下来，紧接着是如何处理在里面选，里面选。对于这个容斥就好了。根据容斥定理可以转化为求。其中代表从里面选取不同的并且满足的对数。那么现在问题又转化为了如何快速求里面里面存在多少对满足。这个我们可以把拆分后的询问按照右端...

2020-02-16

2 1060

病毒扩散题解

题解1：AC举个例子，比如有4个线段，我们的是。。那么在叠加后如图：通过例子我们可以知道我们需要看红色线段与多少个线段是“联通”的，这就是我们要找的答案。那么如何找这个联通的个数呢？我们可以贪心的去找。按照左端点从小到大排序，维护右界的最大值，我们就可以知道每一坨连续的区间包含了多少个线段，再看的线...

2020-02-16

0 1425

迷失的括号序列题解

首先我们需要知道如何去判断一个括号序列是否合法，我们需要括号序列的任何一个前缀中左括号的个数大于等于右括号的个数，并且右括号总个数等于左括号总个数。首先我们要判断是否为偶数，因为奇数左括号右括号个数肯定就不相等了。总长度是，所以左括号个数应为，当然如果当前括号序列里面的左括号个数大于，那么也是不行的...

2020-02-15

0 1218

递增数组题解

因为我们要求得一个单调递增的序列，那么我们如果要选择一个区间的话这个区间必为后缀，不然我们选择一个中间的区间相当于把中间提高了，那么对后面就造成了不利的影响。所以我们只需要看每一个位置i与后面的一个元素i+1的差，位置i的贡献为max(0,array[i]+1-array[i+1])。时间复杂度O(...

2020-02-13

6 800

Pokemon题解

方法1：AC需要吃药的时候肯定是撑不住的那一回合，所以我们需要计算他需要吃多少次药，然后才能战胜野生皮卡丘，此题细节较多。特别需要注意杰尼龟可能第一回合打不过皮卡丘，或者杰尼龟可以直接打死皮卡丘的情况，杰尼龟在第二回合就被打死的情况。时间复杂度，空间复杂度。 class Solution { pub...

2020-02-12

0 795

下象棋题解

题解1：AC逆向思维思考，因为所有棋子都只能上下左右移动，所以为了判断牛牛的将能否被吃下，只需要判断牛牛的那一行与列的棋子情况即可。具体来说：对于兵和将，只可能在牛牛的将的上下左右四个相邻的方向上才能取胜；对于车来说，只可能在上下左右四个方向上并且与牛牛的将之间没有其他棋子时才能取胜；对于炮来说，只...

2020-02-07

7 963

生产口罩题解

做法1：AC考虑动态规划，代表选了的工厂后，用个人所能生产的最多的口罩个数。那么转移方程式就很简单了,假设我们现在枚举到了第i个人的第种策略，其中代表人数，代表生产的口罩数。，需要注意的是第i个生产线也可以选择不选任何策略。其实我们也可以用滚动维数组来进行动态规划，只不过这里为了方便大家理解，说明的...

2020-02-07

0 986

扔骰子题解

做法1：AC题意可以转化为我们要找到一个最大的,使得都能被构造出来，那么答案就是。很明显我们为了维护这个集合，需要先把数字排个序，因为集合是从小往大扩充的。考虑我们已经可以用的数表示了的数，此时我们新加入一个数，能加入集合需要满足如下特征：原因是如果，那么将缺失。那么做法就很明显了，我们只需要先把...

2020-02-07

1 723

旅行Ⅱ题解

做法1：AC数据范围较小，考虑状压dp，表示构成集合i的最小花费，用二进制状压表示。所以我们考虑先枚举集合，再枚举集合外的点，去验证这个点能否加入这个集合。总的时间复杂度为，空间复杂度为。 class Solution { public: int Travel(int N, int V, i...

2020-02-07

0 652

旅行Ⅰ题解

做法1：AC按照题意模拟即可，因为要每次选择可达中花费最小的且编号最小的，所以我们用一个优先队列维护拓扑就好，从优先队列中取出花费&编号最小的，然后把这座城市所影响的城市的度数--，我们会发现变为0的只可能是这次度数--的城市，那么只需要将在这次操作中城市度数变为0的城市加入优先队列，然后重...

2020-02-07

1 689