TbYangZ-CSDN博客

原创十二省联考2019酱油记

在中考前去省选玩一趟。Day -1对于一个还没有学会所有省选内容的初三Oier来说，这一趟真的是去打酱油的啊。但还是要认真复习。最近几天在字符串的路上越走越远…晚上才开始复习图论。还有一大堆没有复习啊，怎么办？明天还要去试机，好像是在南开，但是不知道在重庆具体的哪里。Day 0今天去南开试机~~（原来南开在沙坪坝那边）~~。机子是挺不错的，就是键盘摆的位置有点不是那么舒服。当时竟然没有...

2019-04-07 20:56:56 1591 2

原创「AHOI2013」连通图 - 线段树分治+并查集

题目描述给定一个连通的无向图和若干个小集合，每个小集合包含一些边。对于每个集合，你需要确定将集合中的边从原来的无向图中删除后该图是否保持连通。一个图是连通的当且仅当任意两个不同的点之间存在一条路径连接他们。输入格式输入的第一行包含两个整数n和m(1&lt;=n&lt;=10000, 1&lt;= m &lt;= 100000)，表示无向图的点数和边数，每个点从1到n标号。接下来的m行表示...

2019-03-16 23:51:03 297

原创「Loj120」持久化序列 - Splay+离线

题目描述这是一道模板题。您需要维护一个序列，其中需要提供以下操作：插入一个数到序列的第 ttt 版本使其成为序列的第 kkk 项，这个数为 xxx ；删除序列的第 ttt 版本的第 kkk 项；查询序列的第 ttt 版本的第 kkk 项。第 000 个版本为空序列。修改操作不会影响被修改的版本，而总是产生一个新版本。输入格式第一行有一个正整数 nnn 表示操作的数量。接下来 ...

2019-03-14 13:03:06 443

原创「SDOI2010」古代猪文 - Lucas定理+CRT

题目描述Luogu2480题意简述：给定n,Gn,Gn,G，求G∑d∣nCndmod 999911659G^{\sum\limits_{d|n}C_n^d}\text{mod}\ 999911659Gd∣n∑Cndmod 999911659分析若G mod 999911659=0G\ \text{mod}\ 999911659=0G&nbs...

2019-03-07 00:14:18 197

原创「NOI2018」归程 - 最短路+Kruskal重构树+倍增

题面LuoguP4768题目大意：给定一张nnn个点mmm条边的无向连通图，每条边带两个权值l,al,al,a，每次询问给出v,pv,pv,p，要求从vvv点开始，可以走边a&gt;pa&gt;pa>p的边，路程为0，不能走后，走其他边，路程为lll，求从vvv开始到111的最短路程。部分数据强制在线。分析对于每次询问给定的v,pv,pv,p，若点x,yx,yx,y之...

2019-03-02 21:31:27 348

原创「CQOI2015」任务查询系统 - 差分+主席树

题目描述最近实验室正在为其管理的超级计算机编制一套任务管理系统，而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)(S_i,E_i,P_i)(Si,Ei,Pi)描述，(Si,Ei,Pi)(S_i,E_i,P_i)(Si,Ei,Pi)表示任务从第SiS_iSi秒开始，在第EiE_iEi秒后结束（第SiS_iSi秒和EiE_iEi秒任务也在运行），其优先...

2019-02-22 23:31:47 180

原创「BZOJ2500」幸福的道路 - 树型Dp+ST表+倍增

题目描述小T与小L终于决定走在一起，他们不想浪费在一起的每一分每一秒，所以他们决定每天早上一同晨练来享受在一起的时光。他们画出了晨练路线的草图，眼尖的小T发现可以用树来描绘这个草图。他们不愿枯燥的每天从同一个地方开始他们的锻炼，所以他们准备给起点标号后顺序地从每个起点开始（第一天从起点一开始，第二天从起点二开始……）。而且，他们给每条道路定上一个幸福的值。很显然他们每次出发都想走幸福值和最...

2019-02-22 22:08:04 235

题目描述为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个NNN节点MMM条边的无向图，节点标号为1⋯N1\cdots N1⋯N，边标号为1⋯M1\cdots M1⋯M。初始时小E同学在号节点111，隐士则住在号节点NNN。小E需要通过这一片魔法森林，才能够拜访到隐士。魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻...

2019-02-10 16:27:44 266

原创「SCOI2007」蜥蜴 - 最大流

题目描述在一个rrr行ccc列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任务是让尽量多的蜥蜴逃到边界外。每行每列中相邻石柱的距离为111，蜥蜴的跳跃距离是ddd，即蜥蜴可以跳到平面距离不超过ddd的任何一个石柱上。石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减111（如果仍然落在地图内部，则到达的石柱高度不变），如果该石柱原来高度为111，则蜥蜴离开后消失，以后其他蜥蜴...

2019-02-09 13:44:04 190

原创「WC2013」糖果公园 - 树上带修莫队

题目描述Candyland 有一座糖果公园，公园里不仅有美丽的风景、好玩的游乐项目，还有许多免费糖果的发放点，这引来了许多贪吃的小朋友来糖果公园游玩。糖果公园的结构十分奇特，它由 nnn 个游览点构成，每个游览点都有一个糖果发放处，我们可以依次将游览点编号为 111 至 nnn。有 n−1n-1n−1 条双向道路连接着这些游览点，并且整个糖果公园都是连通的，即从任何一个游览点出发都可以通过这些...

2019-01-15 00:27:40 244

原创「HNOI2009」梦幻布丁 - 线段树合并

题目描述N个布丁摆成一行，进行M次操作，每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。例如颜色分别为1,2,2,1的四个布丁一共有3段颜色。输入格式第一行给出N,M表示布丁的个数和操作次数；第二行N个数A1,A2…An表示第i个布丁的颜色第三行起有M行，对于每个操作，若第一个数字是1表示要对颜色进行改变，其后的两个整数X,Y表示将所有颜色为X的变为Y，X可能等...

2019-01-14 23:37:15 221

原创「BZOJ1901」 Dynamic Rankings - 树套树/整体二分

题目描述给定一个长度为N的已知序列A[i](1&amp;amp;lt;=i&amp;amp;lt;=N)A[i](1&amp;amp;lt;=i&amp;amp;lt;=N)A[i](1&amp;lt;=i&amp;lt;=N)，要求维护这个序列，能够支持以下两种操作：查询A[i],A[i+1],A[i+2],…,A[j](1&amp;amp;lt;=i&amp;amp

2019-01-12 12:02:26 222

原创「BZOJ2631」 tree - 动态树LCT

题目描述一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一：+ u v c：将u到v的路径上的点的权值都加上自然数c；- u1 v1 u2 v2：将树中原有的边(u1,v1)删除，加入一条新边(u2,v2)，保证操作完之后仍然是一棵树；* u v c：将u到v的路径上的点的权值都乘上自然数c；/ u v：询问u到v的路径上的点的权值和，求出答案对于5...

2019-01-03 23:58:59 203

原创「BSOJ3401」建筑 - 主席树+二分

题目描述小敏和小燕是一对好朋友。他们正在玩一种神奇的游戏，叫Minecraft。他们正在盖建筑，他们手上有不同的方块。每种方块有不同的不美观度，他们持有每种方块的数量也不一样。他们现在准备实行他们众多建筑计划中的一个。他们的建筑计划有不同的要求，不美观度有上限和下限。为了方便拿取方块，他们也要求所用的方块在方块堆中的连续一段。每个建筑计划需要固定的方块数。他们现在要知道，在最好情况下...

2019-01-01 15:55:36 262

原创「BZOJ3545」「ONTAK2010」 Peaks - Splay启发式合并

题目描述在Bytemountains有N座山峰，每座山峰有它的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。输入格式第一行三个数N，M，Q。第二行N个数，第i个数为h_i。接下来M行，每行3个数a b c，表示从a到b有一条困...

2019-01-01 15:37:27 200

原创「BZOJ2527」 Meteors - 整体二分

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

2019-01-01 15:37:16 218

原创「HDU5126」 stars - CDQ分治/四维偏序

题目描述约翰喜欢看天空。一天有Q次。每次约翰会在天空中找到一颗新星，或者他想知道(x1，y1，z1)(x_1，y_1，z_1)(x1，y1，z1)和(x2，y2，z2)(x_2，y_2，z_2)(x2，y2，z2)之间有多少颗星。输入格式第一行包含一个整数T(1≤T≤10)T(1≤T≤10)T(1≤T≤10)(Q＞100(Q＞100(Q＞100的数据少于666例)))，表示测...

2018-12-29 00:23:25 403

原创「USACO2012Dec」 Running Away From the Barn - 左偏树

题目描述又到了FJ农场的挤奶时间了，但是奶牛都跑了！FJ需要把它们全部抓回来，并且需要你的帮助。FJ的农场是由N（1≤N≤200000）个牧场组成，编号为1到N，由N-1条无向边连通。谷仓位于牧场1，并且从谷仓出发可以到达任何一个牧场。FJ的奶牛今天早上都在它们的牧场，但没有人知道它们现在跑到哪里了。它们只能往远离谷仓的方向跑，由于它们太懒了，它们最多只能跑不超过L的距离。FJ想知道对于每一...

2018-12-26 23:52:23 227

原创「HNOI2010」弹飞绵羊 - 动态树LCT

题目描述某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmon...

2018-12-15 23:21:13 196

原创「SDOI2011」染色 - 树链剖分

题目描述给定一棵有n个节点的无根树和m个操作，操作有2类：将节点a到节点b路径上所有点都染成颜色c；询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），如“112221”由3段组成：“11”、“222”和“1”。请你写一个程序依次完成这m个操作。输入格式第一行包含2个整数n和m，分别表示节点数和操作数；第二行包含n个正整数表示n个节点的初始颜色下面行每行包含两...

2018-12-15 23:02:30 243

原创「BZOJ2683」简单题 - CDQ分治

题目描述你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：命令参数限制内容1 x y A1&lt;=x,y&lt;=N,A为正整数将格子(x,y)的数加上A2 x1 y1 x2 y21&lt;=x1&lt;=x2&lt;=n,1&lt;=y1&lt;=y2&lt;=n

2018-12-13 00:36:05 461

原创「HNOI2004」宠物收养所 - 平衡树Splay

题目描述最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养所总是会有两种情况发生：被遗弃的...

2018-12-12 23:40:29 300

原创「TJOI2013」攻击装置 - 二分图最大独立集

题目描述给定一个01矩阵，其中你可以在0的位置放置攻击装置。每一个攻击装置(x,y)(x,y)(x,y)都可以按照“日”字攻击其周围的8个位置(x−1,y−2),(x−2,y−1),(x+1,y−2),(x+2,y−1),(x−1,y+2),(x−2,y+1),(x+1,y+2),(x+2,y+1)(x-1,y-2),(x-2,y-1),(x+1,y-2),(x+2,y-1),(x-1,y+2...

2018-12-02 13:22:37 164

原创「HNOI2002」营业额统计 - 平衡树/STL set

题目描述Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管...

2018-12-01 23:21:54 184

原创「NOIP2018」旅行 - 基环树

题目描述小 Y 是一个爱好旅行的 OIer。她来到 X 国，打算将各个城市都玩一遍。小Y了解到， X国的 nnn 个城市之间有 mmm 条双向道路。每条双向道路连接两个城市。不存在两条连接同一对城市的道路，也不存在一条连接一个城市和它本身的道路。并且，从任意一个城市出发，通过这些道路都可以到达任意一个其他城市。小 Y 只能通过这些道路从一个城市前往另一个城市。小 Y 的旅行方案是这样的：任...

2018-12-01 17:37:10 414

原创「Tyvj1432」楼兰图腾 - 树状数组

题目描述在完成了分配任务之后，西部314来到了楼兰古城的西部。相传很久以前这片土地上（比楼兰古城还早）生活着两个部落，一个部落崇拜尖刀(V)(V)(V)，一个部落崇拜铁锹(∧)(∧)(∧)，他们分别用VVV和∧∧∧的形状来代表各自部落的图腾。西部314在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了NNN个点，经测量发现这NNN个点的水平位置和竖直位置是两两不同的。西部314认为这幅壁画...

2018-12-01 16:40:47 303

原创「SHOI2007」园丁的烦恼 - 树状数组

题目描述很久很久以前，在遥远的大陆上有一个美丽的国家。统治着这个美丽国家的国王是一个园艺爱好者，在他的皇家花园里种植着各种奇花异草。有一天国王漫步在花园里，若有所思，他问一个园丁道： “最近我在思索一个问题，如果我们把花坛摆成六个六角形，那么……”“那么本质上它是一个深度优先搜索，陛下”，园丁深深地向国王鞠了一躬。“嗯……我听说有一种怪物叫九头蛇，它非常贪吃苹果树……”“是的，显然这是一...

2018-11-22 22:00:07 208

原创 NOIP2018游记

Day 0考试前一天，我们一群人在分析去年NOIP的题目，想着今年也可能会出相似的题（数据结构），所以在复习时也比较注重这一方面。(然而，今年根本没有数据结构题！也白复习了。）好好迎接考试吧！Day 1PDF密码竟然是飞雪连天！出题人怕不是金庸迷。打开题目，T1不是原题积木大赛吗？敲完过了大样例走人。T2一开始没想到背包，只想到了一定是原序列的一个自序列，就从小到大排序，敲了个Dfs，判...

2018-11-11 21:23:09 1162

原创「NOIP2018模拟赛」 T4 - 并查集+区间Dp

题目描述小 Z 上英语课思考数学问题被英语老师发现啦~英语老师：「你这么爱胡思乱想我问你一道英语题吧」小 Z 想跑，但是已经来不及了。英语老师：「我们定义一个回文串是正方读起来相同的字符串」小 Z:「这个简单，不就是像 &amp;quot;abba&amp;quot;&amp;quot;abba&amp;quot;"abba"&amp;quot;aba&am

2018-11-06 22:20:15 652

原创「ZJOI2007」最大半连通子图 - Tarjan缩点+拓扑排序

题面题目描述一个有向图G=(V,E)G=(V,E)G=(V,E)称为半连通的(Semi-Connected)，如果满足：∀u,v∈V\forall u,v\in V∀u,v∈V，满足u→vu\to vu→v或v→uv\to uv→u，即对于图中任意两点u,vu,vu,v,存在一条uuu到vvv的有向路径或者从vvv到uuu的有向路径。若G′=(V′,E′)G&amp;#x27;=(V&amp...

2018-11-05 13:46:32 631

原创「APIO2009」抢掠计划 - Tarjan缩点+最长路

题目描述Siruseri 城中的道路都是单向的。不同的道路由路口连接。按照法律的规定，在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是，Siruseri 的酒吧也都设在路口，虽然并不是每个路口都设有酒吧。Banditji 计划实施 Siruseri 有史以来最惊天动地的 ATM 抢劫。他将从市中心出发，沿着单向道路行驶，抢劫所有他途径的 ATM 机，最终他将在...

2018-11-03 20:14:42 265

原创「洛谷P2833」等式 - 数论

题目概述题目描述给出a,b,c,x1,x2,y1,y2a,b,c,x1,x2,y1,y2a,b,c,x1,x2,y1,y2，求满足ax+by+c=0ax+by+c=0ax+by+c=0，且x∈[x1,x2],y∈[y1,y2]x\in[x1,x2],y\in[y1,y2]x∈[x1,x2],y∈[y1,y2]的整数解有多少对。输入格式第一行包含7个整数，a,b,c,x1,x2,y1,y2a...

2018-10-19 22:47:43 163

原创「APIO2010」特别行动队 - 斜率优化Dp

题目描述你有一支由nnn名预备役士兵组成的部队，士兵从1到nnn编号，要将他们拆分成若干特别行动队调入战场。出于默契考虑，同一支特别行动队中队员的编号应该连续，即为形如(i,i+1,...,i+k)(i,i+1,...,i+k)(i,i+1,...,i+k)的序列。编号为iii的士兵的初始战斗力为xi，一支特别运动队的初始战斗力xxx为队内士兵初始战斗力之和，即x=xi+xi+1+...+xi...

2018-10-19 21:43:14 235

原创「BSOJ2040」吃西瓜 - Dp/三维最大子长方体

题目描述说明：此题中出现的所有数全为整数SubRaY有一天得到一块西瓜,是长方体形的....SubRaY发现这块西瓜长m厘米,宽n厘米,高h厘米.他发现如果把这块西瓜平均地分成m*n*h块1立方厘米的小正方体,那么每一小块都会有一个营养值(可能为负,因为西瓜是有可能坏掉的,但是绝对值不超过200).现在SubRaY决定从这m*n*h立方厘米的西瓜中切出mm*nn*hh立方厘米的一块小...

2018-10-10 17:17:50 487

原创「BSOJ1030」最大奖励 - 斜率优化Dp

题目描述为庆祝BSOI生日及鼓励广大OIER多切题，管理员xinyue决定推出一项奖励措施：他按照每道题目的难度给其赋了一个分值，第一次AC这道题目的时候作者会得到这道题目的分值。假设大牛叉叉嗯AC了n(n <= 100,000)道题目，它们的分值依次为a1,a2,a3,...,an。叉叉嗯就可以按照顺序把它们分成若干段提交给xinyue，假设某一段从i+1到j，它们的分值和为x，那么叉...

2018-10-08 20:33:24 283

原创「NOIP2018模拟赛」计数 - 容斥原理

题目描述给出 m(<=20) 个数 a[1],a[2],…,a[m](<=1e9) 求 1~n(<=1e9) 中有多少数不是 a[1],a[2],…,a[m]的倍数。分析比较裸的容斥。考虑在1~n中有多少是a[1],...,a[m]的倍数。设是a[i]的倍数的集合为Ai，则=，然后用容斥原理求，最后用总个数n减去就是1~n中不是a[1],...,a[m]的倍数的数的个...

2018-10-07 18:43:22 329

原创「NOIP2018模拟赛」摘果子 - 树形Dp

题目描述分析有依赖的树上背包。可以用Dfs序进行Dp，但更直接的方法是先将其转化为二叉树，在对左右儿子分配，进行Dp。Dfs(x,t)函数表示在以x为根的子树上，还能接受t的毒，所获得的最大美味度。若根节点不选，则直接递归查询右儿子；若根节点选，则对其进行分配，左儿子要i的能接受的毒，右儿子要t-i-p[i]的能接受的毒，再用记忆化优化。最后输出Dfs(1,m)。（注意边界条件与初值，...

2018-10-06 20:42:04 673

原创「NOIP2018模拟赛」迷宫 - 最短路变形

题目描述破了魔法阵后，亮亮进入了一座迷宫。这座迷宫叫做“梦境迷宫”，亮亮只有走出这座迷宫，才能从睡梦中醒来。梦境迷宫可以用无向图来表示。它共有 n 个点和 m 条双向道路，每条道路都有边权，表示通过这条道路所需的时间，且每条道路可以多次经过。亮亮位于一号点，而出口则是 n 号点。原本，亮亮该找到一条最短路，快速冲出迷宫，然而，梦境迷宫的特殊之处在于，如果沿着最短路到达出口，亮亮就会永...

2018-10-05 19:13:02 549

原创「BSOJ3031」 Nosknah的宝藏 - 状压Dp

题目描述Nosknah是BSZX默默无闻的一员，他有一个在2009年NOIP 时一日成名的哥哥Hankson，.....，Nosknah喜欢收集宝藏，他知道学校的后花园里面藏有 P个珍品。经过严密调查，他知道后花园分成了N块区域，由 M条无向路径连接。 Nosknah要从1区域出发，捡完所有的宝藏后从 N区域离开。Nosknah没有Hankson那么聪明，他现在求助你：他最短走多远就能捡完...

2018-10-05 10:36:51 267

原创「USACO2005」 Asteroids - 二分图最小顶点覆盖

题目描述分析对于每一个小行星，可以将它的行与列连边，然后可以发现，这就是要求这个二分图的最小顶点覆盖。又有定理二分图的最小顶点覆盖=该图的最大匹配数，于是就这样做。代码#include <iostream>#include <cstring>#include <cstdio>using namespace std;int g[5...

2018-10-04 13:04:40 218

空空如也

空空如也