3 200815147

尚未进行身份认证

暂无相关描述

等级
TA的排名 7k+

[BZOJ]5093: [Lydsy1711月赛]图的价值 NTT+第二类斯特林数

Description“简单无向图”是指无重边、无自环的无向图(不一定连通)。一个带标号的图的价值定义为每个点度数的k次方的和。给定n和k,请计算所有n个点的带标号的简单无向图的价值之和。因为答案很大,请对998244353取模输出。Solution考虑每个点的贡献,容易得到如下式子:ans=n×2n(n−1)2−n+1∑i=1n−1Cn−1iikans=n\times2^{{n(n-...

2019-04-25 07:30:42

[BZOJ]4160: [Neerc2009]Exclusive Access 2 状压DP+Dilworth定理

Description给出N个点M条边的无向图,定向得到有向无环图,使得最长路最短。N≤15,M≤100Solution大家都知道Dilworth定理的其中一个内容:最小路径覆盖=最长反链。实际上与之相似的是:最长路=最小反链划分数。这个东西虽然比较显然,但是之前没有接触过的话可能还是比较难想到。有了这个,直接状压DP就行了。Code#include<bit...

2019-04-17 12:06:24

[AGC028] E - High Elements 思维

Solution考虑知道前面的一段后,怎么判断后面是否合法,这样就可以逐位确定。先上一个结论:令mximx_imxi​为原序列111~iii的最大值所在位置,我们称原序列中每个mxi=imx_i=imxi​=i的位置为上升位,分割后的序列的新的上升位为新晋上升位,那么若存在一种合法方案,一定可以将其调整为其中一个序列中的所有上升位置都是原序列的上升位。证明可以考虑若两个序列都存在新晋上升位,...

2019-04-16 20:40:50

[LOJ]#2720. 「NOI2018」你的名字 后缀自动机+主席树

Solution首先讲一下一个68分的水法:建广义SAM,然后每次询问完之后暴力撤销,复杂度未知。这种做法本身复杂度好像就不对,而且也没法扩展,考虑另外的做法。考虑每个询问串前缀的贡献。首先要保证本质不同,所以先求出每个前缀的最短的没有在之前出现过的后缀,这个可以对每个询问串建SAM求。然后要求出每个前缀的最短的没有在SSS出现过的后缀,如果是68分,相当于在SSS的SAM上匹配,求最长匹配...

2019-04-13 17:00:09

[Codeforces] 1037 H. Security 后缀自动机+主席树

Solution这题思路还是比较简单的。由于∑∣S∣\sum|S|∑∣S∣较小,所以可以枚举答案前多少位是和给出的串是一样的,再枚举下一位填什么,这样问题就转化为快速判断一个区间中某个字符串是否出现过。把parent树建出来后,就是询问某个点子树中有没有值域在某个范围内的点,可以用主席树解决。需要注意的是,当询问长度为lenlenlen的串是否在[l,r][l,r][l,r]中出现时,询问...

2019-04-11 17:26:48

[LOJ]#572. 「LibreOJ Round #11」Misaka Network 与求和 min_25筛+杜教筛

Solution推一下式子,容易得到一个线性做法:∑d=1nfk(d)((2∑i=1⌊ni⌋φ(i))−1)\sum_{d=1}^nf^k(d)((2\sum_{i=1}^{\lfloor{n\overi}\rfloor}\varphi(i))-1)d=1∑n​fk(d)((2i=1∑⌊in​⌋​φ(i))−1)这个东西数论分块加速一下,只需要快速求欧拉函数的前缀和和fff的kkk次方的前缀...

2019-04-09 13:23:09

[Codeforces] 1109F. Sasha and Algorithm of Silence's Sounds LCT+线段树

Solution假如要求的不是一棵树而是一个森林那就很好做,直接用一个双指针+LCT就可以对每个右端点维护出没有环的左端点。那么树这个限制怎么解决呢?树也就是连通块只有一个,而连通块数=点数-边数,用一个线段树维护这个东西就行了。Code#include<bits/stdc++.h>usingnamespacestd;#defineLLlonglong#defin...

2019-04-05 13:33:44

[Codeforces] 888G. Xor-MST Boruvka算法/分治+01trie

Solution经典的异或最小生成树,我所知道的有两个做法,分别介绍一下。1、最小生成树的Boruvka算法。这个最小生成树算法大概流程是把开始的nnn个点视为nnn个连通块,然后每次每个连通块找到一条连向其他连通块的权值最小的边并连起来,这样每次至少减少一半的联通块数,复杂度为O(nlog⁡n)O(n\logn)O(nlogn)。那么在这题套用这个算法的话,可以建一个所有数的010101...

2019-04-05 12:05:58

[LOJ]#2731. 「JOISC 2016 Day 1」棋盘游戏 DP

Solution首先判断无解:四个角没有棋子或者第一、三行连续两个没有棋子。然后通过观察可以发现,按照空格的四连通块来划分的话,每个连通块之间是互不影响的。所以可以对每个连通块分别DP,最后再用组合数把各个连通块给拼起来。设fi,j,0/1f_{i,j,0/1}fi,j,0/1​表示第二行的第iii个空格,是当前这个连通块第jjj个填的,填的时候是上下填好还是左右填好,如果上下左右都已经填好...

2019-04-03 07:26:59

[AGC031]E - Snuke the Phantom Thief 费用流

Solution假设我们一共选了kkk个,那么假如x≤ax\leax≤a最多选bbb个,那么xxx第b+1b+1b+1大的宝石的xxx必须大于aaa,假如x≥ax\geax≥a最多选bbb个,那么xxx第k−bk-bk−b大的宝石的xxx必须小于aaa。也就是说只要枚举选了多少个,那么对于每个宝石的x、yx、yx、y都可以得到一个上下界,可以直接跑上下界费用流,但是其实没有必要。因为上下解...

2019-04-02 19:12:21

[HDU]6326 Problem H. Monster Hunter 贪心

Solution回顾一下经典的打怪兽问题。设打死一只怪兽先掉aia_iai​血,再回bib_ibi​血,那么我们排序策略是:对于ai≤bia_i\leb_iai​≤bi​,aia_iai​小的排在前;对于ai>bia_i>b_iai​>bi​,bib_ibi​大的排在前,前一种情况排在前面,正确性显然。到了树上,并且有了打完父亲才能打儿子的限制,考虑怎么做...

2019-03-25 21:21:50

[BZOJ]5259: [Cerc2017]区间 线段树

Description给定一个1到n的排列a1,...,an。对于一个区间[l,r],我们称该区间是连续的,如果将al,...,ar排列之后得到的是一列连续的数。(换句话说,如果x,y都在该区间中,那么所有介于x,y之间的数也在该区间中)现在有m(1≤n,m≤100000)个询问,每个询问给出一个区间[xi,yi],你需要找到一个长度最短的连续区间[li...

2019-03-25 19:06:12

AtCoder Grand Contest 031 C - Differ by 1 Bit 构造 归纳法

Solution下面基本都是题解的中文翻译。为了方便,称一个数的奇偶性为二进制表示中111个数的奇偶性。首先判掉无解,即AAA与BBB奇偶性相同,因为每次有一位不同,所以每次奇偶性会变。下面用归纳法证明其他情况都是有解的。n=1n=1n=1时显然有解,假设n=kn=kn=k时有解,现在证明n=k+1n=k+1n=k+1时也有解。AAA和BBB至少有一位不同,假设是第xxx位,两个数同时去...

2019-03-17 21:47:41

[BZOJ]3711: [PA2014]Druzyny 分治+线段树

Description体育课上,n个小朋友排成一行(从1到n编号),老师想把他们分成若干组,每一组都包含编号连续的一段小朋友,每个小朋友属于且仅属于一个组。第i个小朋友希望它所在的组的人数不多于d[i],不少于c[i],否则他就会不满意。在所有小朋友都满意的前提下,求可以分成的组的数目的最大值,以及有多少种分组方案能达到最大值。Solution先列出最简单的DP:fi=max⁡{fj+1...

2019-03-15 13:44:35

[BZOJ]4730: Alice和Bob又在玩游戏 sg函数+trie

DescriptionAlice和Bob在玩游戏。有n个节点,m条边(0<=m<=n-1),构成若干棵有根树,每棵树的根节点是该连通块内编号最小的点。Alice和Bob轮流操作,每回合选择一个没有被删除的节点x,将x及其所有祖先全部删除,不能操作的人输。注:树的形态是在一开始就确定好的,删除节点不会影响剩余节点父亲和儿子的关系。比如:1-3-2这样一条链,1号点是根节点,删除1号点...

2019-03-15 13:02:29

[BZOJ]4180: 字符串计数 SAM+矩阵乘法+二分

DescriptionSD有一名神犇叫做Oxer,他觉得字符串的题目都太水了,于是便出了一道题来虐蒟蒻yts1999。他给出了一个字符串T,字符串T中有且仅有4种字符‘A’,‘B’,‘C’,‘D’。现在他要求蒟蒻yts1999构造一个新的字符串S,构造的方法是:进行多次操作,每一次操作选择T的一个子串,将其加入S的末尾。对于一个可构造出的字符串S,可能有多种构造方案,Oxer定义构造...

2019-03-14 17:37:06

[BZOJ]4844: [Neerc2016]Foreign Postcards 概率DP

Descriptionls是一名集邮爱好者,他专门有一个栈来存放他的所有的邮票,但ls同时也是一名很粗心的人,有一些邮票可能放反了(上下颠倒),有一天他想把他的邮票拿出来向他的妹子炫耀,但因为有一些邮票可能反了,于是ls就想把那些邮票矫正方向,但ls特别懒,他觉得一张一张矫正太费时间了,即使是要给妹子看的,他也不想费太多时间,于是ls就想出了一种奇迹淫巧:1.假设栈中还剩n张邮票,他每次从1到...

2019-03-14 15:20:11

[BZOJ]4987: Tree 树形DP

Description从前有棵树。找出K个点A1,A2,…,Ak。使得∑dis(AiAi+1),(1<=i<=K-1)最小。Solution这道题首先要用到一个结论,即ans=最小的包含A1到Ak的连通块中所有边的和×2−这个连通块直径ans=最小的包含A_1到A_k的连通块中所有边的和\times2-这个连通块直径ans=最小的包含A1​到Ak​的连通块中所有边的和×2−...

2019-03-13 17:48:55

[BZOJ]5068: 友好的生物 放缩

Solution猜到复杂度……却依然不会做……这个方法感觉和不等式证明中的放缩法有点类似,所以我个人这样称呼……先把CiC_iCi​乘进去,把式子写出来:∑i=1k−1∣ai−bi∣−∣ak−bk∣\sum_{i=1}^{k-1}|a_i-b_i|-|a_k-b_k|i=1∑k−1​∣ai​−bi​∣−∣ak​−bk​∣绝对值很烦,考虑怎么去掉它,我们可以直接2k−12^{k-1}2k−1枚...

2019-03-13 17:42:12

[BZOJ]4849: [Neerc2016]Mole Tunnels 模拟费用流

Description鼹鼠们在底下开凿了n个洞,由n-1条隧道连接,对于任意的i>1,第i个洞都会和第i/2(取下整)个洞间有一条隧道,第i个洞内还有ci个食物能供最多ci只鼹鼠吃。一共有m只鼹鼠,第i只鼹鼠住在第pi个洞内,一天早晨,前k只鼹鼠醒来了,而后n-k只鼹鼠均在睡觉,前k只鼹鼠就开始觅食,最终他们都会到达某一个洞,使得所有洞的ci均大于等于该洞内醒着的鼹鼠个数,而且要求鼹鼠行动...

2019-03-13 12:30:39

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。