平凡的小白

未归档

题解(64)

/ 注册

全部文章 / 未归档（共47篇）

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

快速幂： 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

牛客练习赛61

前面的碎碎念：菜鸡差点爆0，题目有点不对胃口传送门 A、打怪签到题，差点没签到成功思路：计算勇士砍死一个怪需要的次数，从而得到砍死一个怪需要消耗的血量，于是能砍死的怪物数量就等于自身血量除于需要消耗的血量，如果能整除则答案数减一，特判自身血量为0；复杂度： (1)。 Code： #inclu...

DFS 模拟贪心 dp Dijkstra 字符串哈希二分答案

2020-04-12

1 677

月月查华华的手机

题目大意：给一个文本串和一个n，接着n个模板串，问文本串中是否有子序列和模板串相等传送门难度暴力枚举一定超时的，要想到和AC自动机一样预处理的方法来优化暴力枚举思路预处理得到一个数组，从A数组的首字符开始获取B的首字符第一次出现的位置（如果第一个都不可以那么后面的也都不可以），再从这个位置...

子序列

2020-04-10

1 603