levil

题解

/ 注册

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

《小白月赛25》部分题解

D：思路：概率论.计算出每个卡池拿不到的概率,最后1-即可.注意1-之后可能会<0,所以要加上模数再取模.这里的概率计算直接上逆元就可以了.小细节:ma *= a%mod,是不对的这样本质上是先对a取模再乘ma.这样存在爆精度的问题.Code: LL quick(LL a,LL b) { ...

2020-05-18

0 667

《算法周练5》C：序列最小化

贪心：首先注意题目说这个数列肯定是1-n的一个全排列。那么说明这个数列一开始的数都是1~n中的,并且最小的是1.那么,很显然最后的结果肯定全部为1.因为想要替换为全部都一样,且每次替换都是在变小,那么最后肯定是全部为1才能实现.所以我们直接用1去替换更优.为什么呢？因为如果用其他的数去替换,最终还是...

2020-05-06

0 695

《算法周练4》A题解

题意：问的是给定比例的齿轮能否旋转.思路：首先,如果这个齿轮不成环,那么肯定可以通过相邻的齿轮转动.所以我们需要的是判断成环的时候是否也能够转动.首先,我们dfs时进行赋值,通过这个比例来赋值,让起始点为1.0即可.然后当我们第二次来到这个点时,它已经判断下成环后重新赋的值和之前赋的值是否一样,一样...

2020-04-29

2 795

《算法周练3》E

二分图的多重匹配问题解法:1.带限制的匈牙利算法.对匈牙利做一点调整就行了.Code: #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; ...

2020-04-22

0 658

《算法周练3题解》 C

C：分层图的最短路.思路：对于每一层里面的点建边.然后给每个车站开一个虚点,和每个地铁里对应的车站建边。这里的对应应该每次都要和对应地铁里建边。建边:对于每一层,最多的点数就是总车站数n。所以给每一层开n个点存这一层的信息,可能会有空缺,但是没什么影响。然后和前面的点建立双向边,因为地铁也可以往回坐...

2020-04-22

0 609

【每日一题】4月16日组合数学

include<bits/stdc++.h> using namespace std;typedef long long LL;typedef pair<int,int> pii;const int N = 2e5+5;const int M = 1e6;const int ...

2020-04-16

0 571

《每日一题：4月2日》预处理加速

对于这个字符串，很明显直接暴力查询,复杂度会TLE。所以我们考虑预处理出下一次跳转的位置。因为一共就26个字母，所以我们可以定义.dp[i][j].表示i位置后面第一个'a'+j字符的位置.很显然，如果我们要跳转要跳去第一个后面的这个字符的位置。 Code： #include<iostream...

2020-04-02

0 576

《【每日一题】3月31日城市网络》倍增法

题目相信大家都看的懂思路：我们从几个点入手，剖析出这题的解题思路。首先这是个树状网络，那么我们肯定可以从树的思路入手。然后很重要的一点，，保证 v 在 u 前往首都的最短路径上。那么很明显，v就是在u和根节点的路径上的一点。那么就可以归到求LCA的问题了。普通的往上跑，那么这题的数据范围会超时，所以...

2020-03-31

1 871

【每日一题】3月30日，滑动窗口（单调队列）

单调队列，就是一种单调的队列，队列里的元素都是单调的。单调队列如何维护队列的单调性，通过两个指针,head和tail.注意的是单调队列中存的是元素的下标,所以我们才能来判断队首是不是在该区间内.通过head <= tail来判断是否队空.如果队首元素已经不在区间内,就移动head指针.每次从队...

2020-03-29

0 539

【每日一题】3月27日每日一题题解(dp+前缀和）

题意：求两段连续不相交的长度为k的序列的和的最大值。思路：dp+前缀和。定义状态：dp[i]为[1,i]区间内所有长度为k的区间的最大值。那么当我们枚举到区间[i+1,i+k+1]时，我们把这个区间作为右区间,然后他的左区间里的最大值也就是[1,i]里的最大值。就是dp[i],可以通过O(1)的时间...

2020-03-27

0 673