Bernard5

题解

作业(2) 学习笔记(17) 技术教程(45) 期末应试(57) 未归档(17) 赛后分析(7) 题集(15)

/ 注册

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

Sequence 分治结构纳入线段树来自专栏

题意给n个数，有两种操作把改成求有多少个连续区间的最小值是思路首先很容易想到：求有多少个连续区间的最小值是，其实就是找到左边第一个比小的数，下标，找到右边第一个比小的数，下标，那么就有个满足题意的区间。然而硬找肯定是T的，虽然题目数据太水，稍微优化一下就能过。考虑正解做法，明确目标...

树状数组线段树二分

2021-01-23

3 681

照看小猫排列组合 IOI周赛22普及组C 来自专栏

题意有n只猫，它们可以接受不同的名字长度。问共有多少种不同的方案可以满足所有猫。思路首先我们知道名字长度有限，所以可以桶一下。表示接受名字长度为的猫的数量。表示长度小于等于的小写字母组成的字符串总数。它可以这样计算所以当存在某个时，无法分配。如果可分配，答案为如果觉得公式太抽象了，...

数学排列组合

2021-01-22

4 582

Magical Number 暴力出奇迹来自专栏

magical number是越走越窄的，在就已经结束了。所以直接dfs即可，只是不敢写。最大的可行魔法数消耗木棍139，故可打表。然而根本不需要打表，就硬搜就能过。打表代码 #include <bits/stdc++.h> #define sc(x) scanf("%lld",...

DFS 暴力

2021-01-21

3 936

WZB's Harem 状压DP 来自专栏

状压DP 每一列对于每一行是唯一确定的，这一点契合了状态压缩的特性。出题人的话：一道状压 dp。首先不考虑皇后的差异性，把所有皇后当作是一样的，在第 i 行第 k 列安排一位皇后的方案数为 f[i][j|(1<<k)] += f[i][j]((j>>k)&1...

dp 状压DP

2021-01-20

3 694

A Simple Math Problem 容斥原理来自专栏

题意给定一个数，求，其中表示的是的数位和。思路题目要我们求对于每个数，所有与互质的的和。可以将其转化成反向的：对于每个数，所有与互质的数的个数，这就是的权重。这一对称情况忽视了对角线上的，所以要将其补上。本题亦可使用莫比乌斯反演推导。 solution #include <bit...

容斥原理数学思维

2021-01-19

2 584

Color Sequence 异或前缀和江西省赛2020 来自专栏

题意给定一个颜色序列，求它有多少个颜色出现次数都是偶数的连续子序列。思路出现次数为偶数容易联想到异或的性质：异或前缀和。由于c很小，所以可以用int作为一个01串来存储颜色是否出现过，同时也可以利用异或通过前缀和来存储len从1到n的01串的状态然后对于每个前缀和，找有多少个同值前缀（...

2021-01-19

9 1010

小M和天平 bitset dp 来自专栏

bitset对dp的优化，非常典型 #include <bits/stdc++.h> using namespace std; const int N = 1e4; bitset<N + N + 100> b; int main() { int a, c; w...

STL 思维 dp bitset 位运算

2021-01-18

0 684

python中的堆/优先队列

python中的优先队列的写法，记录一下。 n,k=map(int,input().split()) l=list(map(int,input().split())) import heapq heapq.heapify(l) while len(l) > 1 : a=heapq.he...

STL 语法

2021-01-07

1 586

字符串子序列双指针二分来自专栏

这手双指针堪称妙手。 class Solution { public: int Maximumlength(string x) { int n = x.length(), mx = 0; int na = 0, nb = 0, nc = 0; ...

2020-12-08

0 500

线段树区间加区间查板子来自专栏

#include <bits/stdc++.h> #define sc(x) scanf("%lld", &(x)) #define pr(x) printf("%lld\n", (x)) using namespace std; type...

线段树数据结构板子

2020-12-07

0 613