hwzzyr-CSDN博客

原创 NOIp系列题目及CF小结

长期更新中23332018/7/2先看一下昨晚的cfCodeforces Round #493 (Div. 2) A. Balloons这个题。。。直接模拟233B. Cutting来一下奇加偶减。统计合适位置然后排个序，贪心减C. Convert to Ones连续的0或者1显然可以表示为一个那么可能的情况就只有0101010……或者101010……交...

2018-07-02 15:59:19 907

原创 Achen模拟赛

良心的noip模拟赛首先感谢队爷Achen学长为我们出的一套"良心的noip模拟题"(原话如此)。虽说他总是自称蒟(Amorphophalms\tiny morphophalmsmorphophalms)蒻（konjac\tiny onjaconjac），但是这改变不了他总是AK的事实。确实是一套良(du)心(liu)的题目。T1T1T1题面如此。数位Dp可能是第一想法，但是位...

2018-09-28 20:11:25 433

原创简单的圆方树（一）

圆方树是什么呢？我们先不管仙人掌，来看看一般图的圆方树。众所周知，TarjanTarjanTarjan算法可以在强连通分量，点双和边双三个地方使用。有向图是强联通，无向图是双联通。我们使用TarjanTarjanTarjan算法很多时候都是为了将图简化以达到目的。SccSccScc缩点之后会形成一张DAGDAGDAG图，用Top SortTop\ SortTop S...

2018-09-26 20:29:59 1157

原创【SNOI2017】炸弹——并查集解法

【SNOI2017】炸弹Description在一条直线上有 N 个炸弹，每个炸弹的坐标是 Xi，爆炸半径是 Ri，当一个炸弹爆炸时，如果另一个炸弹所在位置 Xj 满足：Xi−Ri≤Xj≤Xi+Ri,那么，该炸弹也会被引爆。现在，请你帮忙计算一下，先把第 i 个炸弹引爆，将引爆多少个炸弹呢？Input第一行，一个数字 N，表示炸弹个数。第 2∼N+12∼N+12∼N+1行，每行...

2018-09-21 20:05:25 812

【BZOJ3784】树上路径Description　　给定一个N个结点的树，结点用正整数1…N编号。每条边有一个正整数权值。用d(a,b）表示从结点a到结点b路边上经过边的权值。其中要求a &amp;amp;lt; b.将这n*(n-1)/2个距离从大到小排序，输出前M个距离值。Input　　第一行两个正整数N,M　　下面N-1行，每行三个正整数a,b,c(a,b&amp;amp;lt;=N，C&amp;amp;lt;=10000.

2018-09-21 15:56:16 458

原创一次没有苟住的模拟赛

GG!!! 今天的这一套题本来以为有380(四道题来着)，但是后面两道题GG了。前两题暂且不谈。我们来看看第三题【BZOJ2438】杀人游戏 Description 一位冷血的杀手潜入 Na-wiat，并假装成平民。警察希望能在 N 个人里面，查出谁是杀手。警察能够对每一个人进行查证，假如查证的对象是平民，他会告诉警察，他认识的人，谁...

2018-08-22 15:16:18 295

原创【noip模拟题】华尔街的秘密

【noip模拟题】华尔街的秘密Description　　最近美国人致力于掀翻华尔街的资本家们，因为他们的生活并不太好，可是那些资本家却依然过着奢华的享乐生活。一些人在游行，而另一些人则试图揭开华尔街的金融家们获取财富的秘密，终于，白宫发现了这个秘密，那就是——一个括号矩阵！！！　　所谓括号矩阵，就是一个n*m的矩阵，其中的每一个元素要么是’(‘，要么是’)’。矩阵中有公共边的格子...

2018-08-16 16:30:28 446 1

原创【Noip2016十连赛day3】平均数

平均数Description　　有一天，小A得到了一个长度为n的序列。　　他把这个序列的所有连续子序列都列了出来，并对每一个子序列都求了其平均值，然后他把这些平均值写在纸上，并对它们进行排序，最后他报出了第k小的平均值。　　你要做的就是模仿他的过程。Input　　第一行两个整数n,k，意义如题中所述。　　第二行n个正整数，即为小A得到的序列。Output...

2018-08-09 20:58:18 766

原创 Kruskal重构树学习笔记

Kruskal重构树前几天做noi2018的同步赛时，Day1T1我就拿了离线+树剖的80分暴力。后来就知道有Kruskal重构树这样一种新科技(14年以前就有了)什么是Kruskal重构树简单来讲，就是在Kruskal算法进行的过程中，我们把最小生成树的边权改为点权。这样，原树的节点个数变成2n-1个，并且有着许多有趣的性质。Kruskal重构树的性质1.根据我们构造...

2018-07-24 19:29:45 9890 11

原创莫比乌斯反演小结——套路的胜利

关于莫比乌斯反演和杜教筛简介&amp;amp;amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp;amp;amp;吐槽　　莫比乌斯反演，通常又可以称为“懵逼钨丝繁衍” 　　这样一种听上去就很高端的知识是做什么的？莫比乌斯反演是数论数学中很重要的内容，可以用于解决很多组合数学的问题。　　这和没说有什么区别…… 　　我们开心的来看一下它的定义吧。　　不过在这之前，我们先补一些有趣的小知识。

2018-07-19 22:24:27 655

原创 Lct系列小结

这个东西欠了很久了(博客也停了很久了)这篇博文不负责讲解Lct的基础知识（太麻烦）所以有需要的同学可以看这里PART 1 我们首先给一个模板struct Splay{ int F,s[2],rev; int val,sum; inline void NewNode(int fa,int x){ F=fa; s[0]=s[1]=rev=...

2018-07-02 16:24:26 1025 1

原创【SDOI2008】郁闷的小J

【SDOI2008】郁闷的小JDescription　　小J是国家图书馆的一位图书管理员，他的工作是管理一个巨大的书架。虽然他很能吃苦耐劳，但是由于这个书架十分巨大，所以他的工作效率总是很低，以致他面临着被解雇的危险，这也正是他所郁闷的。　　具体说来，书架由N个书位组成，编号从1到N。每个书位放着一本书，每本书有一个特定的编码。　　小J的工作有两类：　　图书馆经常购置新书，而书架任意时刻都是满的，...

2018-03-17 09:22:59 407

原创平衡树三连击

普通、文艺以及二逼平衡树平衡树的题。这种数据结构的裸题，就是拿来虐我这种巨菜的（尤其是代码能力不强的同学）。首先说明，这三道题我都是用Splay写的，想要看Treap的同学可以出门右转了。那么先说第一道，普通平衡树。普通平衡树Description　　您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：　　1. 插入x...

2017-11-17 23:30:27 298

原创 NOIP2017 滚粗记

Day 0 下午去看了看考场。。。我分配到了最菜的一个机房（ccf评测机都有2.8GHz，我们那个居然只有1.8GHz），键盘的空格键许多都有问题（跷跷板）。不过总的来说还是不错，给椅子点个赞。晚上突然发慌（Flag），于是上洛谷疯狂水模板题，一晚上做了20多道。。。结果最后打算做一道模拟题找信心，结果从9:20调到10:30。我当时说NOIP模拟不可能这样（Flag*

2017-11-12 22:26:18 479

原创【模拟试题】花园

【模拟试题】花园Description　　小豪有一个花园，里面有n个花棚，编号1..n，每个花棚里有一定数量的花a i 。小豪花园的路十分神奇，可以使得任意两个花棚之间仅有一条最短路，即形成树结构，其中根节点是1号花棚。现在小豪打算修缮一下他的花园，重新分配每个花棚里花的数量。为了能方便快捷地知道花园的情况，小豪现在需要你的帮助。具体地说，小豪共有m个操作。操作有三种：　　1. 1 u k 表示如...

2017-10-15 16:05:56 529

原创【BJOI2010】次小生成树

【BJOI2010】次小生成树【BJOI2010】次小生成树Description小C最近学了很多最小生成树的算法，Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时，小P又来泼小C冷水了。小P说，让小C求出一个无向图的次小生成树，而且这个次小生成树还得是严格次小的，也就是说：如果最小生成树选择的边集是EM，严格次小生成树选择的边集是ES，那么需要满足：(value(e)表示边e...

2017-09-16 17:31:58 341

原创【BZOJ3091】城市旅行

【BZOJ3091】城市旅行DescriptionInputOutputSample Input4 51 3 2 51 21 32 44 2 41 2 42 3 43 1 4 14 1 4 ...

2017-08-22 21:29:49 384

原创【模拟试题】上学路线

【模拟试题】上学路线Description　　小C所在的城市的道路构成了一个方形网格，它的西南角为(0,0)，东北角为(N,M)。小C家住在西南角，学校在东北角。现在有T个路口进行施工，小C不能通过这些路口。小C喜欢走最短的路径到达目的地，因此他每天上学时都只会向东或北行走；而小C又喜欢走不同的路径，因此他问你按照他走最短路径的规则，他可以选择的不同的上学路线有多少条。由于答案可能很大，所以小C只...

2017-08-19 12:09:33 389

原创【SDOI2010】古代猪文

【SDOI2010】古代猪文Description“在那山的那边海的那边有一群小肥猪。他们活泼又聪明，他们调皮又灵敏。他们自由自在生活在那绿色的大草坪，他们善良勇敢相互都关心……” ——选自猪王国民歌很久很久以前，在山的那边海的那边的某片风水宝地曾经存在过一个猪王国。猪王国地理位置偏僻，实施的是适应当时社会的自给自足的庄园经济，很少与外界联系，商贸活动就更少了。因此也很少有其他动物知道这样一个王...

2017-08-19 11:55:58 361

原创【NOIP2016-D1T3】换教室

【NOIP2016-D1T3】换教室Description Solutionemm，最近学习了一下期望。所以就回头把去年noip的题做一下。这个题目描述很长，虽然说...

2017-08-15 20:58:53 530

原创【模拟试题】德雷克的追捕

【模拟试题】德雷克的追捕Description　　这一次，德雷克要追捕一个从古代遗迹中逃脱的超自然人造物。　　在古代遗迹中，德雷克拿到了人造物的OS说明，凭借出题人给他开的挂，他看懂了。　　人造物会严格地从输入的地图中的起点出发，总是走最短路；也就是说，它访问任何一个结点时，走的路线都是从古代遗迹到这里的最短路。同时，如果没有最短路可走，人造物会选择停下。为了简化题目，我们保证从古代遗迹（结点1）...

2017-08-14 21:42:20 330

原创【模拟试题】分糖果

【模拟试题】分糖果Description幼儿园的小孩们收到了一个有M颗糖果的大包裹，现在要把这些糖果分给N个小孩。每一个小孩都给出了一个期望的糖果数，如果没有达到他的期望值a[i]，小孩就会生气。每差一个糖果，小孩的生气指数就会增加。可以认为他生气的程度等于他少得到的糖果数的平方。比如，Mirko想要得到32个糖果，但是只得到了29个。他少了3个，所以他的生气指数是9。不幸的是，糖果数不足以满足所...

2017-08-12 17:13:56 1410 2

原创【BZOJ2631】tree

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

2017-08-11 15:29:21 318

原创 P1072新年趣事之债务

新年趣事之债务Description【题目背景】　　在HNSDFZ的信息组里，Vivian Snow、Charles和Sunnypig之间有着一种奇怪的债务关系：Vivian Snow欠了Charles一百块钱，Charles欠了Sunnypig一百块钱，Sunnypig欠了Vivian Snow一百块钱。【问题描述】　　一天，三个人遇到了一起。由于他们都不够理智，一心想要回自己借出去的钱，于...

2017-07-14 15:04:41 374

原创【模拟试题】连接格点

【模拟试题】连接格点Description　　有一个M行N列的点阵，相邻两点可以相连。一条纵向的连线花费一个单位，一条横向的连线花费两个单位。某些点之间已经有连线了，试问至少还需要花费多少个单位才能使所有的点全部连通。Input　　第一行输入两个正整数m和n，以下若干行每行四个正整数x1,y1,x2,y2，表示第x1行第y1列的点和第x2行第y2列的点已经有连线。输入保证|x1-x2|+|y1-y...

2017-05-02 17:21:44 1086

原创【Tyoj1098】任务安排

【模拟试题】任务安排Description　　N个任务排成一个序列在一台机器上等待完成（顺序不得改变），这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个...

2017-04-30 15:42:38 719

原创【模拟试题】甲虫

【模拟试题】甲虫Description一只甲虫发现它呆在一根狭窄的水平树枝上。“我呆在一根狭窄的水平树枝上，”甲虫心想，“我感觉象呆在X轴上一样”（这是一只数学思维相当深刻的甲虫！）在那根树枝上还有N滴露珠，每一滴含有M单位的水分，它们的位置分别在整点坐标x1, x2, . . . , xn。甲虫的初始位置在坐标原点。天气很热，在一个单位时间里每滴露珠都会蒸发掉1单位

2017-04-30 15:28:36 638

原创【练习试题】分组(poj1112 Team Them Up!)

【练习试题】分组(Poj1112 Team Them Up!)Description你的任务是把一些人分成两组，使得：•每个人都被分到其中一组；•每个组都至少有一个人；•一组中的每个人都认识其他同组成员；•两组的成员人数尽量接近。这个问题可能有多个解决方案，你只要输出两组人数之差的绝对值即可，或者输出这样的分组法不存在。

2017-04-30 15:04:32 1368

原创【POJ3683】Priest John's Busiest Day(Special Judge)

【POJ3683】Priest John's Busiest Day(Special Judge)DescriptionJohn is the only priest in his town. September 1st is the John's busiest day in a year because there is an old legend in the tow

2017-04-26 15:28:47 327

原创【POJ3207】熊猫的戏法Ikki's Story IV - Panda's Trick

【POJ3207】熊猫的戏法Ikki's Story IV - Panda's TrickDescriptionliympanda, one of Ikki’s friend, likes playing games with Ikki. Today after minesweeping with Ikki and winning so many times, he is

2017-04-24 10:21:55 430

原创【POJ2411】Mondriaan's Dream

【POJ2411】Mondriaan's DreamDescriptionSquares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his 'toilet series' (where he

2017-04-22 15:52:35 333

原创【NOI2001】炮兵阵地

【NOI2001】炮兵阵地Description　　司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：　　　　如果在地

2017-04-20 11:21:04 418

原创【模拟试题】完成工作

【模拟试题】完成工作Description当前有n（nInput有多组数据。第一行一个数tot表示数据的组数，后面紧接tot组数据。对于每一组数据的第一行有一个整数n，表示工作的数目。后面n行每行描述一个工作。对于一个工作，a，b，k，h1，h2……hk来描述，表示这个工作需要占用一个工人[a，b]的时间，并且能够完成这个工作的工人只有k

2017-04-19 10:04:40 414

原创 2255 -- 【JZOJ 4.1】俄罗斯方块

2255 -- 【模拟试题】俄罗斯方块Description相信大家都玩过“俄罗斯方块”游戏吧，“俄罗斯方块”是一个有趣的电脑小游戏，现有一个有C列、行不受限定游戏平台，每一次下落的方块是下列的7个图形的一种：在下落的过程中，游戏者可以作90、 180或270 度旋转，还可以左右移动，对于每一次方块落地，我们要求方块的每一部分都必须与地面

2017-04-18 11:56:16 563

原创 JOJ 2453 Candy

【JOJ 2453】CandyDescription有N 颗糖果和M 个小孩，老师现在要把这N 颗糖分给这M 个小孩。每个小孩i对每颗糖j 都有一个偏爱度Aij，如果他喜欢这颗糖，Aij = 2，否则 Aij = 1。小孩 i觉得高兴当且仅当∑Cij×Aij >= Bi，j=1,2, …,N ，若他分得了糖 j ，Cij = 1，否则 Cij = 0。问能否合理分配这 N

2017-04-11 10:07:05 693

原创小白逛公园加强版（vijos1620）

小白逛森林公园Description　　小新经常陪小白去公园玩，也就是所谓的遛狗啦……在小新家附近有n个公园，这些公园通过一些路径相连，并保证每两个公园之间有且仅有一条通路相连（也就是说这是一棵树），小白早就看花了眼，自己也不清楚该去哪些公园玩了。　　小白对每个公园都有一个评价（可正可负），并且它只会让小新做两件事：　　1. 询问公园a到公园b路径上最大连续公园的

2017-04-06 16:11:51 749

原创小白逛公园（vijos1083）

小白逛线性公园Description　　小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。　　一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择连续的

2017-04-06 16:01:03 412

原创【bzoj3262】陌上花开

【bzoj3262】陌上花开Description有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。Input

2017-03-31 09:18:22 559

原创【Balkan2007】Mokia

【Balkan2007】MokiaDescription维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数MInput第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小接下来每行为一下三种输入之一(不包含引号):"1 x y a""2 x1 y1 x2 y2

2017-03-31 09:02:05 292

原创【模拟试题】逛公园

【模拟试题】逛公园Description窝窝头经常陪碳原子去公园玩，也就是所谓的遛狗啦…在窝窝头家附近有一条“公园路”，路的一边从南到北依次排着n个公园，碳原子早就看花了眼，自己也不清楚该去哪些公园玩了。一开始，碳原子就根据公园的风景给每个公园打了分-.-。窝窝头为了省事，每次遛狗的时候都会事先规定一个范围，碳原子只可以在第a个和第b个公园之间（包括a、b两个公园）选择

2017-03-31 08:34:25 394

空空如也

空空如也