Deep_Dark_FAntasy♂

未归档

Codeforces(3) 博弈论(3) 基本数论、组合数学（排列组合，容斥等）(14) 并查集(2) 数据结构(2) 深度优先搜索、广度优先搜索、搜索剪枝(8) 线性dp、背包问题、区间dp(15) 题解(12)

/ 注册

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

Exclusive OR(线性基、FWT) 来自专栏

题目链接：https://ac.nowcoder.com/acm/contest/5667/E题目描述：给n个整数A1~An，从n个数中可重复的选i个数出来，算它们的异或和，能得到最大值就是答案。解题思路：这个题首先考虑i>19的时候有ansi=ansi-2，证明也很简单，首先只需要在ans...

线性基多项式乘法fwt

2020-07-16

1 554

快速傅里叶变换(FFT)）(复习模板用)

默认n是2的整数幂次。f(x)=a0+a1+...+an-1，比如8，对应的bit就是3，因为只有a0a7，rev[i]是把一个数在二进制下倒过来，思想是把一个数在2进制下分为前bit-1位和最后一位的话，需要让前bit-1位倒过来，并把最后一位放到前面去，由于让rev[i>>1]倒过来...

FFT 数论

2020-07-15

1 671

Easy Integration(积分) 来自专栏

题目链接：https://ac.nowcoder.com/acm/contest/5666/J解题思路：要是你知道沃里斯公式，就知道这是个结论，但要是你不知道就老老实实积分吧。再做一遍换元，然后作二项式展开。最后写出W1,W2,W3...找找规律解决。这道题还可以用分部积分法来做。(是不是求着...

积分推公式逆元

2020-07-14

1 1194

Duration(签到题) 来自专栏

题目链接：https://ac.nowcoder.com/acm/contest/5667/D解题思路:签到题，比手速。一开始写成了：s[1][0]-s[0][0]-’0‘，但不需要-'0'。在那看了3，4分钟才看出错误。以此铭记自己的错误。代码： #include<bits/stdc++.h...

2020-07-14

1 507

Fake Maxpooling(滑动窗口最大值) 来自专栏

题目链接：https://ac.nowcoder.com/acm/contest/5667/F这道题我们队之前没用过单调队列，这道题用二维线段树其实有点杀鸡用宰牛刀的感觉。并且由于数据量的原因导致二位线段树不用树套树会tle，用树套树会mle。预备知识：单调队列：单调队列要从一个比较经典的问题说起来...

滑动窗口单调队列

2020-07-14

1 899

整数二分查找算法模板

详见：https://www.acwing.com/blog/content/31/

二分

2020-07-10

0 418

D - A Simple Math Problem 解题报告来自专栏

题目链接：https://vjudge.net/contest/381753#problem/D解题思路：跟据题意可以列出两个式子：X+Y=a （1）LCM(X,Y)=b （2）题目让求X,Y，我们思考如何把（2）做一个转化变为一个一般方程使用结论：gcd(X,Y)=...

解方程 gcd

2020-07-10

3 722

G - windy数解题报告来自专栏

题目链接：https://vjudge.net/contest/381753#problem/G 知识预备：数位DP数位DP的题目往往是这样的：给定一个闭区间[L,R],求这个区间中满足"某种条件"的数的总数量。数位DP技巧：技巧1：[X,Y] -> f(Y)-f(X-1)...

dfs 数位DP

2020-07-10

4 675

I - Pyramid 解题报告来自专栏

题目链接：https://vjudge.net/problem/%E8%AE%A1%E8%92%9C%E5%AE%A2-A2144题目大意：求n行三角形中等边三角形的个数，图二的三角形也算，n<=1e9解题思路：n范围这么大，一看就是个找规律题，那么先来打个表看看。打表(暴力)代码： #inc...

打表函数思维逆元导数

2020-07-09

2 607

A - Roundgod and Milk Tea 解题报告来自专栏

题目链接：https://vjudge.net/contest/381753#problem/A预备知识：回顾二分图：二分图：无向图G=(V,E),如果可以把结点集分成不相交的部分，即X和Y=V-X，使得每条边的其中一个端点在X中，另一个端点在Y中，则称图G是二分图。二分图最大匹配1.把二分图的两个...

最大匹配二分图贪心思维霍尔定理

2020-07-09

1 547