wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共395篇）

快速傅里叶变换简记

多项式一个次数界为的多项式次数界为说明这个多项式最高次项的指数小于系数表示法我们可以只保留多项式每项的系数来描述这个多项式。即表示指数为的项的系数运算多项式之间的加运算，只要将对应项的系数相加即可。即若那么有多项式之间的乘法。若那么其中叫做卷积可以看出暴力计算卷积的复杂度为点值表示法我...

2020-05-29

1 751

莫比乌斯反演

重新学习了一遍莫比乌斯反演，整理一下。莫比乌斯函数莫比乌斯函数是一个积性函数。$x1.x=1\mu(x)=12.x\mu(x)=(-1)^kkx3.\mu(x)=0$莫比乌斯函数是个积性函数，所以可以线性筛。性质 $2.$ 线性筛莫比乌斯函数代码 for(int i = 2;i &l...

2020-05-29

1 712

【每日一题】Contest

solution 先从三个排名中选择两个，假设是，就是要找对于每个队伍，满足a比他大并且b比他小的队伍有多少个。这就是一个二维偏序的问题，先按照a从大到小排序，这时每个位置左边都满足a比他大，所以从左向右扫的过程中维护一个权值树状数组，每次将一个元素的b***去，并且在树状数组上查询小于当前这个b的...

2020-05-29

1 993

【每日一题】管道取珠

solution 我们可以将问题转化为进行两次游戏，最终输出的序列相同的方案数。为什么可以这么转化呢？我们尝试用式子表示这个新问题，对于一种序列，如果在一次游戏中取到他的方案数为，那么根据乘法原理，在两次游戏中都取到他的方案数就是，那么所有可能序列的方案数之和自然就是了。那这个问题怎么做呢？我们...

动态规划

2020-05-28

1 612

【每日一题】Protecting the Flowers

problem 有n头牛在吃花，第i头牛每分钟吃的花，John每次可以运走一头牛，运走第i头牛需要的时间是。设计一种运牛的顺序，使得被吃掉的花最少。 solution 非常经典贪心题。先考虑只有两头牛的情况。如果先运走，那么被吃掉的花就是，同理如果先运走被吃掉的花就是。所以我们按照排序，然后统计答...

贪心

2020-05-27

1 652

【每日一题】货币系统

solution 想起当年noip赛场上没做出来这道降智题就来气。。。这个题目其实讲的也就是去掉最多的元素，使得剩下的元素可以组成原来可以组成全部数字。仔细想一下，其实就是将原数组排序之后，如果比较大的那个可以被比较小的表示出来，那么这个元素我们就可以删去了。所以我们用表示前i个元素是不是可以组...

背包动态规划

2020-05-26

1 559

【每日一题】[JSOI2007]建筑抢修

solution 显然的，越小的就应该越优先考虑。所以我们先按照从小到大排序。然后我们用记录下现在已经选择的建筑所需要花费的时间。如果加上当前建筑的不大于当前建筑的。那么就直接将这个建筑修复即可。那么如果应该怎么办呢？有两种选择，一种是从前面选的里面踢掉一个(只会踢掉一个，因为每个建筑的贡献都是...

贪心

2020-05-25

1 631

【题解】牛客练习赛64

A 怪盗-1412 problem 用个，个，个进行排列，求最多有多少个子序列。 solution 显然让所有的4和2分别相邻答案会更大。然后就是将1分成两份，分别放在4两边。如果前面的有个，那么答案就是，这是一个二次函数，当时取得最大值。 code /* * @Author: wxyww * @D...

字符串贪心动态规划

2020-05-24

2 724

线性代数基础

[toc] 线性方程组概述线性方程组就是形如下方的方程组。初等行变换与高斯消元线性方程组有3种初等行变换（将某行乘以某个数，将两行相减，交换两行）通过三种初等行变换，我们可以进行高斯消元。高斯消元其实就是平时解方程组的过程。大体过程就是通过第i行消去每行(除第i行)的第i个未知数的系数...

2020-05-22

2 683

数hash

树的同构两棵树如果形态相同，就称这两棵树同构。也就是：存在一个排列，将其中一棵树的编号改为，使得这棵树和另外一棵树完全相同。树hash 判断两棵树是否同构可以使用树hash的方法。用表示i这棵子树的hash值。那么有，表示第个素数。表示以为根的子树的大小。dfs一遍即可求出。任意点为根的has...

2020-05-22

1 538