lqybzx-CSDN博客

原创 Petrozavodsk Winter Training Camp 2018: Carnegie Mellon U Contest I. Statistics

题目大意：有n个物品放入体积为v的背包内，问正好放满n时的最小物品数量在这个数量的基础上求a.体积平均最小b.体积中位数最小c.相同体积出现的次数最大值最小d.最大体积减去最小体积值最小题解：背包四合一，四个问题分开求解。a.直接放背包维护最小值即可。b.正反各放一遍背包，记录放进每一个时候背包的形态。放到x则将1放到x与n放到x+1的背包合并，查询

2018-04-28 20:01:52 869 2

原创 Petrozavodsk Winter Training Camp 2018: Carnegie Mellon U Contest A. Mines

题目大意：给你n个点，分别位于pi。每个点有个爆炸范围ri和代价ci，花费ci可以引爆某个点，并且pi-ri到pi+ri范围内的点都会被引爆。q个询问，每次修改一个点的ci，每次输出引爆所有店的最小代价。题解：学了下线段树优化建立边。首先对于这些爆炸关系连边所点我们可以得到一个DAG，引爆所有点的代价就是所有入度为0的点的代价最小值之和。那么这题是区间操作，我们可以用线段树

2018-04-28 13:07:42 462

原创 bzoj 2460: [BeiJing2011]元素

Description 相传，在远古时期，位于西方大陆的 Magic Land 上，人们已经掌握了用魔法矿石炼制法杖的技术。那时人们就认识到，一个法杖的法力取决于使用的矿石。一般地，矿石越多则法力越强，但物极必反：有时，人们为了获取更强的法力而使用了很多矿石，却在炼制过程中发现魔法矿石全部消失了，从而无法炼制出法杖，这个现象被称为“魔法抵消” 。特别地，如果在炼制过程中使

2018-03-01 19:56:19 722

原创 bzoj 2115: [Wc2011] Xor

DescriptionInput第一行包含两个整数N和 M，表示该无向图中点的数目与边的数目。接下来M 行描述 M 条边，每行三个整数Si，Ti ，Di，表示 Si 与Ti之间存在一条权值为 Di的无向边。图中可能有重边或自环。Output仅包含一个整数，表示最大的XOR和（十进制结果）,注意输出后加换行回车。Sample Input

2018-03-01 19:54:45 224

原创 HDU 3949 XOR

Problem DescriptionXOR is a kind of bit operator, we define that as follow: for two binary base number A and B, let C=A XOR B, then for each bit of C, we can get its value by check the digit of co

2018-02-28 17:33:39 227

原创 hdu 6200 mustedge mustedge mustedge

Problem DescriptionGive an connected undirected graph with n nodes and m edges, (n,m≤105) which has no selfloops or multiple edges initially. Now we have q operations (q≤105): ⋅1 u

2017-09-21 16:50:45 408

原创 hdu 6209 The Intersection

Problem DescriptionA given coefficient K leads an intersection of two curves f(x) and gK(x). In the first quadrant, the curve f is a monotone increasing function that f(x)=x−−√. The curve

2017-09-18 20:54:59 1027 2

原创 2017多校训练Contest5: 1008 Rikka with Subset hdu6092

Problem DescriptionAs we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:Yuta has n positive A1−An and

2017-08-20 17:53:44 357

原创 2017多校训练Contest5: 1006 Rikka with Graph hdu6090

Problem DescriptionAs we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:For an undirected graph G with

2017-08-20 17:51:59 260

原创 2017多校训练Contest5: 1001 Rikka with Candies hdu6085

Problem DescriptionAs we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:There are n children and m ki

2017-08-20 17:48:22 341

原创 2017多校训练Contest4: 1007 Matching In Multiplication hdu6073

Problem DescriptionIn the mathematical discipline of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V (that is, U and V are each independ

2017-08-20 17:42:53 355

原创 2017多校训练Contest4: 1005 Lazy Running hdu6071

Problem DescriptionIn HDU, you have to run along the campus for 24 times, or you will fail in PE. According to the rule, you must keep your speed, and your running distance should not be less than

2017-08-20 17:39:39 401

原创 2017多校训练Contest4: 1004 Dirt Ratio hdu6070

Problem DescriptionIn ACM/ICPC contest, the ''Dirt Ratio'' of a team is calculated in the following way. First let's ignore all the problems the team didn't pass, assume the team passed Xproblems

2017-08-20 17:37:15 329

原创 2017多校训练Contest4: 1003 Counting Divisors hdu6069

Problem DescriptionIn mathematics, the function d(n) denotes the number of divisors of positive integer n.For example, d(12)=6 because 1,2,3,4,6,12 are all 12's divisors.In this prob

2017-08-20 17:31:33 271

原创 2017多校训练Contest4: 1012 Wavel Sequence hdu6078

Problem DescriptionHave you ever seen the wave? It's a wonderful view of nature. Little Q is attracted to such wonderful thing, he even likes everything that looks like wave. Formally, he defines

2017-08-20 17:26:33 356

原创 2017多校训练Contest4: 1011 Time To Get Up hdu6077

Problem DescriptionLittle Q's clock is alarming! It's time to get up now! However, after reading the time on the clock, Little Q lies down and starts sleeping again. Well, he has 5 alarms, and i

2017-08-20 17:20:46 245

原创 2017多校训练Contest4: 1009 Questionnaire hdu6075

Problem DescriptionIn order to get better results in official ACM/ICPC contests, the team leader comes up with a questionnaire. He asked everyone in the team whether to have more training.

2017-08-20 17:20:38 246

原创 2017多校训练Contest3: 1011 RXD's date hdu6066

Problem DescriptionAs we all know that RXD is a life winner, therefore he always goes out, dating with his female friends.Nevertheless, it is a pity that his female friends don't like extremely

2017-08-16 16:08:51 300

原创 2017多校训练Contest3: 1008 RXD and math hdu6063

RXD is a good mathematician.One day he wants to calculate:∑i=1nkμ2(i)×⌊nki−−−√⌋output the answer module 109+7.1≤n,k≤1018μ(n)=1(n=1)μ(n)=(−1)k(n=p1p2…pk)μ(n)=0(other

2017-08-16 16:05:44 275

原创 2017多校训练Contest3: 1005 RXD and dividing hdu6060

Problem DescriptionRXD has a tree T, with the size of n. Each edge has a cost.Define f(S) as the the cost of the minimal Steiner Tree of the set S on tree T. he wants to divide 2,3,4,5

2017-08-16 16:03:17 318

原创 2017多校训练Contest3: 1004 Kanade's sum hdu6059

Problem DescriptionGive you an array A[1..n]，you need to calculate how many tuples (i,j,k) satisfy that (ijk) and ((A[i] xor A[j])(A[j] xor A[k]))There are T test cases.1≤T≤201≤∑n≤

2017-08-16 16:01:20 251

原创 2017多校训练Contest3: 1003 Kanade's sum hdu6058

Problem DescriptionGive you an array A[1..n]of length n. Let f(l,r,k) be the k-th largest element of A[l..r].Specially , f(l,r,k)=0 if r−l+1k.Give you k , you need to calculate ∑

2017-08-16 15:57:49 230

原创 2017多校训练Contest2: 1006 Funny Function hdu6050

Problem DescriptionFunction Fx,ysatisfies:For given integers N and M,calculate Fm,1 modulo 1e9+7. InputThere is one integer T in the first line.The next T lines,each line

2017-08-16 15:53:44 237

原创 2017多校训练Contest2: 1011 Regular polygon hdu6055

Problem DescriptionOn a two-dimensional plane, give you n integer points. Your task is to figure out how many different regular polygon these points can make. InputThe input file con

2017-08-16 15:50:59 262

原创 2017多校训练Contest2: 1009 TrickGCD hdu6053

Problem DescriptionYou are given an array A , and Zhu wants to know there are how many different array B satisfy the following conditions?* 1≤Bi≤Ai* For each pair( l , r ) (1≤l≤r≤n) ,

2017-08-16 15:49:23 273

原创 2017多校训练Contest2: 1003 Maximum Sequence hdu6047

Problem DescriptionSteph is extremely obsessed with “sequence problems” that are usually seen on magazines: Given the sequence 11, 23, 30, 35, what is the next number? Steph always finds them too

2017-08-16 15:45:17 285

原创 2017多校训练Contest2: 1001 Captain is coding hdu6045

Problem DescriptionDerek and Alfia are good friends.Derek is Chinese,and Alfia is Austrian.This summer holiday,they both participate in the summer camp of Borussia Dortmund.During the summer

2017-08-16 15:42:06 275

原创 POJ2516 Minimum Cost

DescriptionDearboy, a goods victualer, now comes to a big problem, and he needs your help. In his sale area there are N shopkeepers (marked from 1 to N) which stocks goods from him.Dearboy has M s

2017-07-19 10:17:57 233

原创 bzoj 3572: [Hnoi2014]世界树

Description世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。世界树的形态可以用一个数学模型来描述：世界树中有n个种族，种族的编号分别从1到n，分别生活在编号为1到n的聚居地上，种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道

2017-07-19 09:33:26 246

原创 bzoj 3611: [Heoi2014]大工程

Description国家有一个大工程，要给一个非常大的交通网络里建一些新的通道。我们这个国家位置非常特殊，可以看成是一个单位边权的树，城市位于顶点上。在 2 个国家 a,b 之间建一条新通道需要的代价为树上 a,b 的最短路径。现在国家有很多个计划，每个计划都是这样，我们选中了 k 个点，然后在它们两两之间新建 C(k,2)条新通道。现在对于每个计划，我们想知道

2017-07-18 13:26:05 300

原创 bzoj 2286: [Sdoi2011]消耗战

Description在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希

2017-07-18 10:39:44 208

原创 bzoj 4196: [Noi2015]软件包管理器

Description Linux用户和OSX用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu使用的apt-get，Fedora/CentOS使用的yum，以及OSX下可用的homebrew都是优

2017-07-01 20:11:48 263

原创 bzoj 4198: [Noi2015]荷马史诗

Description追逐影子的人，自己就是影子。 ——荷马Allison 最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，Allison 想通过一种编码方式使得它变得短一些。一部《荷马史诗》中有 n 种不同的单词，从 1 到 n 进行编号。其中第 i 种单词出

2017-07-01 19:19:17 298

原创 4195: [Noi2015]程序自动分析

Description 在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本：假设x1,x2,x3,…代表程序中出现的变量，给定n个形如xi=xj或xi≠xj的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2，x2=x3，x3=x4，x1≠x4，

2017-07-01 18:56:17 221

原创 bzoj 3233: [Ahoi2013]找硬币

Description小蛇是金融部部长。最近她决定制造一系列新的货币。假设她要制造的货币的面值为x1,x2,x3… 那么x1必须为1，xb必须为xa的正整数倍（b>a）。例如 1，5，125，250就是一组合法的硬币序列，而1，5，100，125就不是。不知从哪一天开始，可爱的蛇爱上了一种萌物——兔纸！从此，小蛇便走上了遇上兔纸娃娃就买的不归路。某天，小蛇看到了N只可爱的兔纸，假设这N

2017-07-01 17:24:15 278

原创 bzoj 4831: [Lydsy2017年4月月赛]序列操作

Description给定一个长度为 n 的非负整数序列 a_1,a_2,...a_n 。你可以使用一种操作：选择在序列中连续的两个正整数，并使它们分别减一。当你不能继续操作时游戏结束，而你的得分等于你使用的操作次数。你的任务是计算可能的最小得分和最大得分。Input第一行包含一个正整数 T ，表示有 T 组数据，满足 T ≤ 200 。接下来依次给出每组测

2017-07-01 16:00:48 554

原创 bzoj 4289: PA2012 Tax

Description给出一个N个点M条边的无向图，经过一个点的代价是进入和离开这个点的两条边的边权的较大值，求从起点1到点N的最小代价。起点的代价是离开起点的边的边权，终点的代价是进入终点的边的边权NMInputOutputSample Input4 51 2 51 3 22 3 12 4

2017-07-01 13:27:58 379

原创 bzoj 2726: [SDOI2012]任务安排

Description机器上有N个需要处理的任务，它们构成了一个序列。这些任务被标号为1到N，因此序列的排列为1,2,3...N。这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和。注意，同一批任务将在同一时刻完成。每个任务的费用是它

2017-06-04 16:35:42 770

原创 codeforces #378C(733.C) Epidemic in Monstropolis

There was an epidemic in Monstropolis and all monsters became sick. To recover, all monsters lined up in queue for an appointment to the only doctor in the city.Soon, monsters became hungry and be

2017-05-20 19:30:30 361

原创 codeforces #378F(733.F) Drivers Dissatisfaction

F. Drivers Dissatisfactiontime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputIn one kingdom there are n citie

2017-05-20 19:14:48 438

空空如也

空空如也