塔子哥学算法

分类

未归档(82) 题解(1)

/ 注册

全部文章（共83篇）

普通莫队基本思想

莫队基本可解决一切区间查询的问题. 普通莫队常用于维护区间答案，比如：对于一个长度为 n 的序列，给出 m 次询问，每次询问区间 [l,r] 内有多少个不同的颜色，其中 n,m<=100000. 先考虑暴力的方法，对于每个询问，我们都去遍历统计一遍，复杂度换一种暴力的方式,我们用左右端点两个...

2020-03-14

0 505

常见博弈模型

目录: 一、巴什博弈（Bash Game）二、尼姆博弈(Nimm Game) 三、威佐夫博奕（Wythoff Game）四.斐波那契博弈五.环形博弈一、巴什博弈（Bash Game）情形：有n个石子，每个人最少拿a个石子，最多拿b个石子，问先手赢还是后手赢. 分析：当n = a + b时,...

2020-03-13

0 604

知识点:组合数的求法+Lucas定理

① 1 <= m <= n <= 5000 1.1 如果 m,n非常小以至于C(n,m)都不会爆long long ,那么我们直接上杨辉三角去解 1.2 如果 n , m 比较大，但是要求取模,还是用杨辉三角去解。 1.3 如果保证了最终的结果不爆long long ,那么我们可...

2020-03-12

0 466

牛客-最大gcd-数论,预处理,STL

思路：由于区间GCD的单调性，我们显然是在[L,R]之间选择一个数a[i]使得 d = gcd(x,a[i])最大，而d一定是x的一个因子。考虑到1e5之内的因子不算多(可以用约数个数去算一下，最多应该是100左右).我们将x的所有因子求出来。然后从最大的因子开始枚举。接下来任务就变成了在区间[...

2020-02-29

0 542

状压dp-安排教室座位

题目: 思路：一旦看出来这是个状压dp就很好做了..某一行状态就只跟上一行有关.这样直接就转成线性dp了. 可是我没看出来.傻子吧啦. 发现一个新的想法：O(n) 算出 1 ~ n 内所有数二进制数中1的个数. AC代码:

2020-02-09

0 444

1200D-二维前缀和

题意: 大意：给你一个n*n的矩阵，只含W,B两种字符,代表白，黑块。现在你有一块k*k的橡皮檫,能够把矩阵中所有的B给擦去。现在问你用一次橡皮擦之后能够得到的最多的完整的白行/列的个数是多少例如: 3 1 BWB WWB WWB 那么能够...

2020-02-07

0 390

609D:思维，贪心

Domino for Young 题意：

2020-01-28

0 407

聪明可可

题意：给你一棵树，问你树上有多少条路径其长度为3的倍数，输出一个整数.注意路径有方向性且自身到自身也算一条路径. 解法一:树形dp 首先对于这种统计树上路径的题，我们要认清两个事实, 一.我们对树上的路径做一个划分 :分为两种，一种是不拐弯的直链，一种是弯链（只折一下）。我们将其深度最小的点作为他...

2020-01-20

0 383

聪明可可

题意：给你一棵树，问你树上有多少条路径其长度为3的倍数，输出一个整数.注意路径有方向性且自身到自身也算一条路径. 解法一:树形dp 首先对于这种统计树上路径的题，我们要认清两个事实, 一.我们对树上的路径做一个划分 :分为两种，一种是不拐弯的直链，一种是弯链（只折一下）。我们将其深度最小的点作为他...

2020-01-20

0 412

CF613E-动态更新

题意: 一开始有一个初始顺序的排列[1,n]，一共有m次操作，每次将数ai从序列中取出，放到最开头的位置生成一个新的排列。求问在所有过程中每一个数最小的下标位置和最大的下标位置。题解: 首先，最小坐标很容易求，若序列m中出现过，那么最小值就是1,否则最小值就是他开始的值，因为每个数他要么是被移动...

2020-01-19

0 397