• 等级
  • 87835 访问
  • 614 原创
  • 1 转发
  • 5004 排名
  • 142 评论
  • 25 获赞

bzoj 3813: 奇数国 树状数组

题目大意: 给你1e5个数,开始全为3,要求支持两个操作。修改一个数的值,保证该值不含除前60个质数外的质因数。 查询区间[l,r][l,r][l,r]的积的ϕ\phiϕ值。 分析: 对于每一个质因数开一个树状数组,维护该质因数的个数。对于一个询问,可以查询各个质因数的个数,因为各个质数间互质,答案就是每一个质数的ϕ\phiϕ值的积。 而ϕ(pk)=(p−1)∗pk−1\phi(p^k)=(p-1...

2018-11-13 21:28:23

洛谷 P3343 [ZJOI2015]地震后的幻想乡 dp

题目描述 傲娇少女幽香是一个很萌很萌的妹子,而且她非常非常地有爱心,很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。 这不,幻想乡突然发生了地震,所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。 幻想乡一共有n个地方,那么最快的方法当然是修复n-1条道路将这n个地方都连接起来。 幻想乡这n个地方本来是连通的,一共有m条边。现在这m条边由于地震的关系,全部都毁坏掉了。...

2018-10-17 10:09:56

jzoj 5908.【NOIP2018模拟10.16】开荒 虚树+树状数组

Description 题目背景: 尊者神高达作为一个萌新,在升级路上死亡无数次后被一只大黄叽带回了师门。他加入师门后发现有无穷无尽的师兄弟姐妹,这几天新副本开了,尊者神高达的师门作为一个 pve师门,于是他们决定组织一起去开荒。 题目描述: 师门可以看做以 1 为根的一棵树,师门中的每一个人都有一定的装备分数。一共会有 q 个事件。每个事件可能是一次开荒,也可能是因为开荒出了好装备而导致一个人的...

2018-10-16 22:01:12

jzoj 5907.【NOIP2018模拟10.16】轻功

Description 题目背景: 尊者神高达进入了基三的世界,作为一个 mmorpg 做任务是必不可少的,然而跑地图却令人十分不爽。好在基三可以使用轻功,但是尊者神高达有些手残,他决定用梅花桩练习轻功。 题目描述: 一共有 n 个木桩,要求从起点(0)开始,经过所有梅花桩,恰好到达终点 n,尊者神高达一共会 k 种门派的轻功,不同门派的轻功经过的梅花桩数不同,花费时间也不同。但是尊者神高达一次只...

2018-10-16 21:57:02

jzoj 5906.【NOIP2018模拟10.15】传送门

Description 8102年,Normalgod在GLaDOS的帮助下,研制出了传送枪。但GLaDOS想把传送枪据为己有,于是把Normalgod扔进了一间实验室。这间实验室是一棵有n个节点的树。现在Normalgod在一号节点,出口也在一号节点,但为了打开它,必须经过每一个节点按下每个节点的开关,出口才能打开。GLaDOS为了杀死Normalgod,开始在实验室里释放毒气,...

2018-10-16 21:48:04

jzoj 5904. 【NOIP2018模拟10.15】刺客信条 并查集

Description 故事发生在1486 年的意大利,Ezio 原本只是一个文艺复兴时期的贵族,后来因为家族成员受到圣殿骑士的杀害,决心成为一名刺客。最终,凭借着他的努力和出众的天赋,成为了杰出的刺客大师。刺客组织在他的带领下,为被剥削的平民声张正义,赶跑了原本统治意大利的圣殿骑士首领-教皇亚历山大六世。在他的一生中,经历了无数次惊心动魄、扣人心弦的探险和刺杀。 这次的故事就是他暗杀一位作恶多端...

2018-10-16 20:45:42

jzoj 5905.【NOIP2018模拟10.15】黑暗之魂(darksoul) 基环树+

Description oi_juruo热爱一款名叫黑暗之魂的游戏。在这个游戏中玩家要操纵一名有 点生命值的无火的余灰在一张地图中探险。地图中有n个篝火(也就是存档点)。在篝火处休息可以将生命值恢复满。每个篝火都会向其他篝火的其中之一连有一条通道(显然,通道是双向的),这些篝火之间都相互可达。也就是说,这是一张n个点,n条边的无向连通图。每条通道里都有一些怪物,经过oi_juruo的分析,他得到了...

2018-10-16 07:29:50

洛谷 P4022 [CTSC2012]熟悉的文章 广义后缀自动机+d

题目大意: 有多个主串,每次询问将询问串分成多个连续子串,如果一个子串长度≥L≥L≥L且在主串中出现过就是合法的 如果合法的子串总长度≥≥≥询问串长的90%90\%90%,这个串就是合法的字符串,求使得询问串成为合法的字符串的最大的LLL。 分析: 我们可以二分答案,显然答案越大可以使用的合法串就越多,而且是包含关系,满足二分性。 我们把这些串建一个广义后缀自动机。 设f[i]f[i]f[i]前i...

2018-10-12 14:52:29

洛谷 P3973 [TJOI2015]线性代数 最小割

题目描述 为了提高智商,ZJY开始学习线性代数。她的小伙伴菠萝给她出了这样一个问题:给定一个n×nn×nn×n的矩阵BBB和一个1×n1×n1×n的矩阵CCC。求出一个1×n1×n1×n的01矩阵AAA。使得D=(A×B−C)×ATD=(A×B-C)×A^{\sf T}D=(A×B−C)×AT最大,其中ATA^{\sf T}AT为AAA的转置。输出DDD。 输入输出格式 输入格式: 第一行输入一个...

2018-10-11 10:15:56

bzoj 4154: [Ipsc2015]Generating Synergy k-d tree

Description 给定一棵以1为根的有根树,初始所有节点颜色为1,每次将距离节点a不超过l的a的子节点染成c,或询问点a的颜色 Input 第一行一个数T,表示数据组数 接下来每组数据的第一行三个数n,c,q表示结点个数,颜色数和操作数 接下来一行n-1个数描述2…n的父节点 接下来q行每行三个数a,l,c 若c为0,表示询问a的颜色 否则将距离a不超过l的a的子节点染成c Output 设...

2018-10-10 15:49:15

洛谷 P3307 [SDOI2013]项链 burnside引理+polya定理+莫比乌斯反演

题目描述 项链是人体的装饰品之一,是最早出现的首饰。项链除了具有装饰功能之外,有些项 链还具有特殊显示作用,如天主教徒的十字架链和佛教徒的念珠。 从古至今人们为了美化人体本身,也美 化环境,制造了各种不同风格,不同特点、不同式样的项链,满足了不同肤色、不同民族、不同审美观的人的审美需要。就材料而论,首饰市场上的项链有黄金、白银、珠宝等几种。 珍珠项链为珍珠制成的饰品,即将珍珠 钻孔后用线串在一起,...

2018-10-09 20:40:06

洛谷 P3527 [POI2011]MET-Meteors 整体二分+树状数组

Byteotian Interstellar Union有N个成员国。现在它发现了一颗新的星球,这颗星球的轨道被分为M份(第M份和第1份相邻),第i份上有第Ai个国家的太空站。 这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。 BIU的第i个成员国希望能够收集Pi单位的陨石样本。你的任务是判断对于每个国家,它需要在第几次陨石雨之后,才能收集足够的陨石。 输入: 第一行是两个数N,M...

2018-10-09 14:51:49

洛谷 P4841 城市规划 ntt

题目描述 刚刚解决完电力网络的问题, 阿狸又被领导的任务给难住了. 刚才说过, 阿狸的国家有n个城市, 现在国家需要在某些城市对之间建立一些贸易路线, 使得整个国家的任意两个城市都直接或间接的连通. 为了省钱, 每两个城市之间最多只能有一条直接的贸易路径. 对于两个建立路线的方案, 如果存在一个城市对, 在两个方案中是否建立路线不一样, 那么这两个方案就是不同的, 否则就是相同的. 现在你需要求出...

2018-10-09 09:32:54

洛谷 P4253 [SCOI2015]小凸玩密室

题目描述 小凸和小方相约玩密室逃脱,这个密室是一棵有 nnn 个节点的完全二叉树,每个节点有一个灯泡。点亮所有灯泡即可逃出密室。每个灯泡有个权值 aia_iai​,每条边也有个权值 bib_ibi​。点亮第一个灯泡不需要花费,之后每点亮一个新的灯泡 vvv 的花费,等于上一个被点亮的灯泡 uuu 到这个点 vvv 的距离 Du,vD_{u,v}Du,v​,乘以这个点的权值 ava_vav​。在点灯...

2018-10-08 21:04:33

洛谷 P3345 [ZJOI2015]幻想乡战略游戏 动态树分治

题目描述 傲娇少女幽香正在玩一个非常有趣的战略类游戏,本来这个游戏的地图其实还不算太大,幽香还能管得过来,但是不知道为什么现在的网游厂商把游戏的地图越做越大,以至于幽香一眼根本看不过来,更别说和别人打仗了。 在打仗之前,幽香现在面临一个非常基本的管理问题需要解决。 整个地图是一个树结构,一共有n块空地,这些空地被n-1条带权边连接起来,使得每两个点之间有一条唯一的路径将它们连接起来。 在游戏中,幽...

2018-10-07 11:39:43

jzoj 5898. 【NOIP2018模拟10.6】距离统计 动态树分治

Description Input Output Sample Input 5 3 1 2 3 1 3 1 2 4 4 2 5 2 1 2 3 3 5 1 Sample Output 3 6 2 Data Constraint 分析: 我们可以先二分一个答案,那么问题就变成了从一个点xxx开始的路径长度≤mid≤mid≤mid的有多少条。 考虑用动态树分治。 每个点维护一个vector表示以...

2018-10-06 19:30:50

jzoj 5899. 【NOIP2018模拟10.6】资源运输 矩阵树定理

Description Input Output Sample Input 3 2 1 3 5 2 1 6 Sample Output 30 样例说明: 显然m=n-1时,只有一种选择方法,优秀程度为5*6=30,所以输出为30。 Data Constraint 分析: 答案就是每棵生成树的价值和除以生成树的数量。 因为价值的边的权值,所以都可以直接用矩阵树解决。 代码: #include...

2018-10-06 19:23:00

jzoj 5895.【NOIP2018模拟10.5】旅游 最小生成树

Description Input Output Sample Input 6 10 4 6 4 5 3 6 5 2 3 2 1 2 3 4 6 1 2 4 1 3 Sample Output 2132 Data Constraint 分析: 显然至少每条边走一次,在这基础上,所有的奇点都要走一条路径到另外一个奇点。相当于把奇点两两配对,配对代价是他们的最短路,然后我就不会了。 最后发现两...

2018-10-05 19:32:55

洛谷 P3976 [TJOI2015]旅游 树链剖分

题目描述 为了提高智商,ZJY准备去往一个新世界去旅游。这个世界的城市布局像一棵树。每两座城市之间只有一条路径可以互达。每座城市都有一种宝石,有一定的价格。ZJY为了赚取最高利益,她会选择从A城市买入再转手卖到B城市。由于ZJY买宝石时经常卖萌,因而凡是ZJY路过的城市,这座城市的宝石价格会上涨。让我们来算算ZJY旅游完之后能够赚取的最大利润。(如a城市宝石价格为v,则ZJY出售价格也为v) 输入...

2018-10-05 16:29:32

洛谷 P2056 [ZJOI2007]捉迷藏 动态树分治

题目描述 Jiajia和Wind是一对恩爱的夫妻,并且他们有很多孩子。某天,Jiajia、Wind和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特,由N个屋子和N-1条双向走廊组成,这N-1条走廊的分布使得任意两个屋子都互相可达。 游戏是这样进行的,孩子们负责躲藏,Jiajia负责找,而Wind负责操纵这N个屋子的灯。在起初的时候,所有的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房...

2018-09-29 18:12:00

Amber_lylovely

关注
  • 学生
  • 中国 广东省 东莞市
奖章
  • 持之以恒