平凡的小白

分类

未归档(48) 题解(64)

/ 注册

TA的专栏 69篇文章 0人订阅

38篇文章 1224人学习

牛客算法竞赛入门课第一节例题、习题

17篇文章 1119人学习

牛客算法竞赛入门课第三节例题、习题

4篇文章 845人学习

牛客算法竞赛入门课第二节例题、习题

2篇文章 981人学习

牛客算法竞赛入门课第八节例题、习题

3篇文章 969人学习

牛客算法竞赛入门课第六节列题、习题

2篇文章 676人学习

2篇文章 1153人学习

1篇文章 617人学习

全部文章（共111篇）

【每日一题】华华给月月准备礼物来自专栏

戳我传送题意：n根木棍中截取k根长度一样的木棍，多余的木棍舍去。思路：先用最简单的方法从长度1开始一个一个枚举，直到达不到题目要求，这样的复杂度 (n^2)，显然会超时。我们就可以选区间的中点，如果不行答案一定比这个小，如果可以我们继续试试大一点可不可以，一步步缩小区间，这是二分的思路。以前...

二分

2020-04-18

1 635

斐波那契

小白月赛20戳我传送题目大意：输出前斐波那契数列前n项平方和，1<=n<=1e18。前备知识：快速幂和矩阵，可以进我的博客了解一下，小白非常容易理解：戳我了解思路：斐波那契数列前n项平方和有递推式：前n项平方和等于 f[n] * f[n+1]。因为n非常大，用递归的思路去求肯定超时...

矩阵快速幂

2020-04-17

1 686

矩阵快速幂求斐波那契数列

快速幂： 1.求5^19，19个5相乘当然可以算出来，但是当指数特别大的时候O(n)就不行了，必须要O(logn)的算法，也就是根据位运算来求解。19的二进制是（10011）5^19=5^1 * 5^2 * 5^16;指数对应的二进制如下：1---00001,2---00010,16---1000...

矩阵快速幂

2020-04-17

1 774

JOI 2019-Final比赛真题（重现赛）

前面的碎碎念：菜鸡不敢打这个比赛，赛后看题解有“水题”就补了题。戳我传送 A、勇者比武大意：H * W的格子上放了J,O,I三种字符，求满足条件(i,j,k,l)的四元组的数量，(i,j)上是J，(i,l)上是O，(k,j)上是I。其中l大于j，k大于i，也就是说问有多少JOI的组合满足O在J的右...

思维组合前缀和贪心

2020-04-17

1 544

【每日一题】Treepath 来自专栏

戳我传送思路：方法一：因为每条边的权值都是一样，所以可以用LCA求得每个结点想对于根结点1的深度，在这里深度就是距离。从偶数层到偶数层和从奇数层到奇数层的路径都是偶数。这里可以用链式向前星存图，然后dfs统计有多少个奇数层a和偶数层b，不必要区分偶数层和奇数层，答案就是 + 。如果1e5...

树状数组 DFS LCA dp 树状dp

2020-04-16

0 599

【每日一题】逆序对来自专栏

戳我传送 solution：大佬们一看到1e18就知道要找规律，本菜鸡还想着递推。方法一：刘大佬说可以在n个位置里找出2个组成1 0，有种方案，其它位置有种可能，答案就是* 。这太神仙了，递推菜鸡的我看了好久。刘大佬原话----0就是没有贡献，1的话会在选这个位置是1后面是0算到。看了邓老师的...

规律逆序对

2020-04-16

2 619

牛客算法周周练2

前面的碎碎念菜鸡被碾压的一场比赛，就会一题。比赛传送门 A、相反数思路：签到题，直接枚举每一位， (n)能过，我写这一题的时候居然慌了。 Code： #include<bits/stdc++.h> #define js ios::sync_with_stdio(false);ci...

dp 打表贪心 DFS 模拟树状dp 二分

2020-04-15

1 650

【每日一题 4.13】Accumulation Degree 和树学来自专栏

Accumulation Degree 题意：不知道题目讲什么真的要命，水从根结点往下流，流量不能超过边的权值,sum[i]表示i结点最多可以流出多少水（流量），这个需要从叶子节点一直回溯来求，父结点的流量sum[u]+=min(w,sum[v]),w表示u和v边的权值，特别的当v是叶子结点的时候，...

换根树状dp

2020-04-14

1 663

【每日一题】Xorto 来自专栏

戳我传送思路：前缀和sum[i]保存前i个数的异或值，sum[i]=sum[i-1]^a[i]，[L,r]的异或值显然是sum[r]^sum[L-1]。试着枚举右端点i从1到n，得到以i为右端点的全部全部区间的异或值。为避免重复可以二分一下，同时枚举全部以i+1为左端点的全部区间的异或值，如果和...

前缀和二分

2020-04-13

1 703

【每日一题 4.9】二分图染色（弱化版）来自专栏

传送门戳我 Solution：将完全二分图匹配问题转化为n*n棋盘的涂色问题，初始颜色都为绿色，在棋盘上选一些格子替换成红色或者绿色，同时任意一行任意一列不能同时出现红色或者蓝色。1、首先我们先考虑只涂一种颜色的情况。假设当前染了k条边，因为棋盘的对称性，可以选择k行，这部分的方案数为 ;对于k列...

容斥组合

2020-04-13

1 777