1 Deep_Kevin

尚未进行身份认证

暂无相关描述

等级
TA的排名 1w+

Codeforeces Round #585 (Div.2)

正题PortalA.YellowCards最大的肯定就是每一个球员依次黄牌。最小的就是将每个球员都恰好先罚剩一张,再一直罚。#include<bits/stdc++.h>usingnamespacestd;intn,a1,a2,k1,k2;intmain(){ scanf("%d%d%d%d%...

2019-09-21 11:05:15

阶乘,51nod 1982,暴力?

正题Portal很容易就可以处理出来所有阶乘乘积的质因数分解,用,时间复杂度是然后我们开一个vector记录一下,第i个质数在阶乘上什么时候增加了多少的指数。(显然是个pair)然后将后面这个指数做一个前缀和,这部分的时间复杂度也是我们对于每一个vector,找到第一个的位置。每次对于一个质数,可以接受...

2019-09-21 08:23:52

联通期望,51nod 1943,期望Dp

正题Portal考虑对每一个联通块单独计算贡献。因为与该联通块无关的边所构成的联通块的贡献实际上相当于不管这些无关的边。我们设!表示构成S这个联通块的概率。先给边从小到大排个序,一条边会让两个合并成一个新的集合所以我们考虑对的贡献。发现贡献其实很好算:...

2019-09-21 08:12:40

空间统计学,51nod 1920,Dp

正题先考虑爆搜怎么做,从一个坐标开始,然后对于维数进行dfs,若走到了另一个坐标,那么距离也就出来了。那么考虑一个状态:第i维,选取的数为j,走到该处的步数为k后效性显然没有,所以直接设计表示方案数。Dp转移很显然:增加一位,枚举第i+1维选取的数,算差值,加步数,时间复杂度是空间复杂度的3倍。但空间可以用滚...

2019-09-21 07:56:47

Factory,51nod 1862,根号分治

正题首先你要知道一点对多点怎么做,自己想想就知道Dp一下就可以了,处理出每个城市的最近一点工厂。查询直接查询因为总个数也是的。那么考虑根号分治,当的时候直接预处理,空间复杂度和时间复杂度同阶。当的时候,每次询问暴力将两个工厂集合的虚树建出来,然后暴力Dp即可,这里相当于枚举lca,然后查询子树内两者最小值之和。时间复杂...

2019-09-21 07:49:00

染色游戏,51nod 1824,卷积套FWT

正题首先你要发现一个结论,就是的奇偶性:当那么,否则这个结论可以用定理简单证明。当然你也可以数学归纳法。所以我们知道了m必须是n的子集,才会有贡献。那么我们枚举子集,然后转移就是发现这个东西无法用FWT优化,因为他多了一个判断:否则就是一个或卷积。这个判断貌似没办法处理,...

2019-09-21 07:37:07

Clarke and math2,51nod 1769,组合数学

正题印象中好像听人讲过。首先只有的才会贡献到,而且对于,当d为定值的时候,贡献的系数是相同的。考虑这个系数到底是什么:把d标准分解:对于每一个质因子,我们观察一下发现k个点是每一个质数次幂是单调不上升的,相当于将k个点放在这个盒子里面的方案数,其中最后一个点一定要在最后一个盒子里面。那么贡献的系数就是...

2019-09-21 07:25:28

矩形面积交,51nod 1302,贪心+堆

正题长边肯定和长边相对,短边肯定和短边相对,否则只会使答案更小。在一组内的重叠面积一定时最小短边和最小长边相乘。我们按照短边从大到小排个序,假设第一条边在A组里面。枚举B组中最短的短边,在此前面的都是属于A的,因为值都小于B,若有等于那么最大值就不会在这里被算到。后面剩下的B组要么取前n-1长的,要么取前n-...

2019-09-18 08:28:57

取余最大值,51nod 1472,笛卡尔树证明时间复杂度

正题我没想到能保证时间复杂度。处理出来当前作为最大值能拓展到的最左节点l和最右节点r。观察发现一个区间的值等于。题目要求我们看看是左边小还是右边小,小的那边遍历,大的那边用主席树查询就可以了。...

2019-09-18 08:20:10

加权约数和,51nod 1584,困难的莫比乌斯反演

正题首先看到max很不爽,先去掉:后面那个东西可以线性筛预处理出来,我们先不管。考虑对于每一个i,他的取值:。我们先考虑到底等于什么,先给出公式:其实这种方法构造地十分巧妙,我们将每一个质因子分开来讨论;也就是说,观察是否等于因为如果等于的话,相乘一下就是...

2019-09-18 08:15:09

最小公倍数计数,51nod 1222,公式推导+Min_25筛

正题公式还是比较好推的。为什么呢?考虑每一个质因子先将丢到其中的一边,然后另一边有种选择,但这种情况被算了两遍,所以减掉。乘起来,发现每一种二元组都被算了两遍,除了只被算了一遍,所以+1再除以2就可以了。然后发现是一个积性函数,而且当时函数值很好算。,所以直接上Min_25筛就可以了。...

2019-09-18 07:53:11

相交回文串,51nod 1748, Manacher+补集转化

正题当时傻了打了一个及其复杂的线段树维护,维护三个信息,然后调了一下午,瞟了一眼题解发现补集转化一下问题变得很简单?首先我们可以用Manacher来做出以i为中心的所有回文串。然后我们定义分别表示以i为结尾与以i为开头的回文串长度。这两个数组可以差分前缀和求出来。那么答案就是。后面那个东西求一个前缀和再...

2019-09-18 07:42:27

学习笔记第五十一节:图论相关

正题因为图论的东西太多,太杂,就懒得用很多篇blog来写,以免被别人说水blog。这个blog要讲的东西有:割点与割边 点双与边双联通分量 圆方树 欧拉通路,欧拉回路看到身后的wsh大佬学习了上面这些东西,想想发现自己啥都不会,就赶紧来学了。有向图强连通分量首先我们要理解Tarjan求解有向图强连通分量的那套理...

2019-09-02 21:27:16

Meatycake,51nod2117,树状数组

正题Portal这题挺巧妙的。我一开始想的就是考虑一个点对不包含比它大一的点的区间的贡献,在考虑一个点对包含比它大一的点的区间的贡献,这两个东西可以用一个树状数组套主席树来维护,但是死活卡在2700ms过不了,无奈之下翻看题解。题解的做法在这里就不再赘述了:先考虑区间[l,r]的贡献。将区间排序后共有r-l+1段,如果i和i+...

2019-08-30 21:19:23

路径并计数,51nod1828,线段树合并

正题Portal这题咕了好久,因为前面一直认为线段树合并是非常玄学的,就一直没有打(虽然现在也认为它很玄学线段树合并只对一些相似度很低的线段树进行合并,例如大范围的权值线段树就可以,具体操作是这样的:intmerge(intx,inty,intl,intr){if(!x||!y)returnx+y;int...

2019-08-30 21:13:30

最大的最大公约数之和,51nod1826,约数个数性质+单调栈维护前缀max

正题Portal这题前半部分挺简单的,但是后半部分非常巧妙。首先考虑产生贡献的gcd对只有O(n)对。首先若是一个前缀,那么一个后缀的最大gcd对可以扫一遍。若一个后缀,也是一样的。考虑一个非前缀而且非后缀的一个区间,对于每一个数,找到它倍数中最左边的,和倍数中最右边的。那么现在贡献的g...

2019-08-30 21:01:22

取模取模,51nod1968,随机

正题Portal发现随机到一个答案集合内的数是的,那么我们随机化多次,每次暴力枚举m进行检验即可。若随机化T次,不成功的几率是,除非你背,随机100次肯定没有问题。#include<ctime>#include<cstdio>#include<cstdlib>#include<cstring&gt...

2019-08-29 07:23:45

集合求交,51nod1818,根号分治

正题Portal这题发现总的元素数量不超过M,所以我们可以对一个集合内的元素数量来根号分治。当询问的时,暴力维护每一个权值以位置为关键字的线段树(动态开点),这部分的时间复杂度是。当询问的时,我们对于这些特殊的集合维护一个以位置为关键字的树状数组,每个位置的权值就是该集合与特殊集合的交集,更新显然,每次查询直接差分前缀和即可。这部分的...

2019-08-29 07:19:45

斐波那契的最小公倍数,51nod1355,Min-Max反演?Lcm-Gcd反演?

正题Portal首先要知道一个东西那么就可以得到:很明显:那么可以得到:这个是怎么得到的呢?考虑每一个质因子,做Min-Max反演。然后就可以得到这个东西就可以直接做了。莫比乌斯反演可以知道对于每一个d,有多少个大小为奇数的集合的gcd为d,有多少个大小为...

2019-08-28 21:52:54

乘积和,51nod1777,凸包上三分

正题Portal首先可以列出一条式子,无论是把他放在前面还是后面,都满足:若x放在y前面,就有代价=这个可以自己验算一下,在做题的时候我直接把这个东西拆开来,就变成了一个类似整体减去一个值,再求最大后缀的问题,那个问题是不能polylog解决的,很麻烦。结果看了题解,发现这个很简单,因为观察上面的式子,可以发现不能确定的只有,那么这...

2019-08-28 21:39:13

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周上午根据用户上周周三的博文发布情况由系统自动颁发。