Haaland

分类

杂谈(3)

/ 注册

全部文章（共4篇）

2021 CCPC 威海 M 810975 容斥

题意:问有多少种长度为n的01串，其中1的总个数为m，最长的连续1的长度为k 解法:看到要精准计算k，考虑转化一下，计算最长的连续1的长度小于等于k的方案数-计算最长的连续1的长度小于k的方案数，那么就是我们想要的答案。我们记最长的连续1的长度小于等于k的方案数为anskans_kansk...

计数容斥

2022-10-18

0 633

The 13th Chinese Northeast Collegiate Programming Contest【B】

题意：现在有m种糖，n颗糖，每一颗糖有俩个属性，一个是所属种类，一个是自身价格。对于每一种糖，最少要取least[i]颗，现在我们定义S代表我们取的糖果的价格总和，C代表我们在所取得糖的类型中，取的最多的糖果的种类取了多少个现在我们要求Value的最大值首先价格总和要最大，简单贪心就是在同一种类型的...

2021-04-17

1 669

单调队列及例题【Sliding window】

有一种题目类型，需要不断查询区间长度为k的子区间内的最小值和最大值，这时候单调队列就出来了，使用单调队列可以很好的解决这一类问题。什么是单调队列呢？听名字就知道这是一种队列这种队列支持对头和队尾都能出队，但只能从队尾入队。更为严苛的条件是所有入队的元素必须满足队头到队尾是递减或者递增的，我们可以...

2021-03-18

4 592

字符串hash模板题【Olipo】

题目大意：给出一个匹配串S和一个字符串T，问匹配串在字符串中出现了几次经典的字符串匹配问题，可以用KMP,BM,Sunday等各种方法解决，但是我觉得字符串哈希才是最好写最好理解的。。先将匹配串hash一遍然后从字符串的第一位开始，判断第i位和匹配串的第一位是否相同，相同的话对字符串的第i到第...

2021-03-16

1 358