zsybupt的博客
zsybupt · 共 59 篇文章
leetcode - gas station
There are N gas stations along a circular route, where the amount of gas at station i is gas[i] . You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station ( i +1). You begin the journey with an empty tank at one of the gas stations. Return t…
2014-10-02 21:45 · leetcode · 评论(0)
51nod-1050 循环最大字段和
N个整数组成的循环序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的连续的子段和的最大值(循环序列是指n个数围成一个圈,因此需要考虑a[n-1],a[n],a[1],a[2]这样的序列)。当所给的整数均为负数时和为0。 例如:-2,11,-4,13,-5,-2,和最大的子段为:11,-4,13。和为20。 Input 第1行:整数序列的长度N(2 <= N <= 50000) 第2 - N+1行:N个整数 (-10^9 <= S[i] <= 10^9) Output 输出循环数组的最大子段和。 解题思路:就是最大字段和的变形,设整个序列和为sum…
2014-04-12 23:42 · oj · 评论(0)
51nod-1101 换零钱
时间限制:1 秒 空间限制:65536 KB 分值: 20 N元钱换为零钱,有多少不同的换法?币值包括1 2 5分,1 2 5角,1 2 5 10 20 50 100元。 例如:5分钱换为零钱,有以下4种换法: 1、5个1分 2、1个2分3个1分 3、2个2分1个1分 4、1个5分 (由于结果可能会很大,输出Mod 10^9 + 7的结果) Input 输入1个数N,N = 100表示1元钱。(1 <= N <= 100000) Output 输出Mod 10^9 + 7的结果 Input 示例 5 Output 示例 4 话不多说,直接上代码。。。 #include<iostream> #…
2014-04-12 23:32 · oj · 评论(0)
boj 11
Description We are familiar with the game called “Counting 24”. Now it comes a problem that we want to know whether we can figure out the exact answer with given 4 numbers only using +,-,*,/ and (,). Input There are several cases in a test. Each case contains only 5 integers, a1, a2, a3, a4 and req…
2013-05-07 16:27 · oj · 评论(0)
boj 342
Description xiaoming实在太好管闲事了.有一天他去参加一个舞会,这里聚集了一大堆帅哥美女,但是舞会却不是那么顺利,虽然帅哥和美女的人数都是相同的,但并不是每一位帅哥都能找到他的舞伴,原因就是有些女生只愿意接受某些男生的邀请.小明为了舞会的顺利进行,xiaoming只好厚着脸皮去和这些女生搭话,了解到了这些女生就都愿意接受哪些男生的邀请,那么剩下的工作就是要小明给这些帅哥美女们搭搭线,小明只希望能找到舞伴的人尽量多. Input 多组数据测试 每行一个偶数n(n<=1000) ,表示参加舞会的人数,其中男生和女生一样多。 接下来n/2行,每一行先是一个正整数m,然后是m个整数…
2013-05-07 00:30 · oj · 评论(0)
boj 343
Description Tradia最近去了趟超市,采购了好多好吃的东西,其中花花绿绿的巧克力最是诱人。为了感谢Jim前段时间对自己的帮助,Tradia决定把自己的巧克力分一些给Jim。但是Tradia也爱吃巧克力,她不想把自己全部的巧克力都给Jim,而是把巧克力平均分配,使得给Jim的总量和留给自己的总量之差最小。聪明的你能帮助她吗? Input 输入包含多组测试数据。 首先第一行输入一个数T(T<=50),表示总共有T组测试数据。 接下来是每组测试数据,第一行是一个数N(N<=20),表示一共有N个巧克力。接着是这N个巧克力的描述,用一个正数M(M<=10000)表示巧克力的质量。 Ou…
2013-05-06 13:19 · oj · 评论(0)
boj 347
Description Tradia对数据结构很感兴趣,她懂得很多有用的数据结构,比如链表、二叉树、图等等。最近她在学习堆的有关知识,并对堆能够在log2N的时间复杂度内返回当前集合的最值感到十分的满意。可是我们都知道,Tradia是一个求知欲很强的学生,她并不满足于得到集合的最值(最大、最小值),同时她还想获得集合当前的第K小数,并且要求每次查询的复杂度要与log2N相当,如果复杂度比log2N还低的话,她或许会以此来申请明年的图灵奖。 然而Tradia自己能力有限,没能想出什么好的解决办法,这时她想到了Jim,希望他能帮帮忙。但是Jim现在正忙着给大家出题呢,所以这个光荣的任务只能拜托聪…
2013-05-06 00:10 · oj · 评论(0)
boj 586
[Description] Teoy最近迷上了阿里巴巴面向网商和中小企业主开发的BNS(Business Network Service)网站“来往”( www.laiwang.com ),在那里他可以结交生意上的朋友,包括上游供应商以及下游的客户。随着业务的 扩大,Teoy迫切想认识自己好友列表之外的更多的同行。他提出这样一个问题,给出任意的A和B,他想知 道在“来往”上A能不能间接认识到B。 [Input] 一共有 T 组测试数据。每组数据第一行为三个整数 n,m 和 q,表示人数,给出的关系数和询问数。 接下来共 n 行,每行 2 个整数 x 和 y。表示 x 和 y 认识。 接下来 …
2013-05-06 00:08 · oj · 评论(0)
boj 437
Description 校内赛马上开始了,选手们比赛时,需要打印代码,但是912的打印机被wangkun弄坏了,无法进行打印。wangkun的钱都上交给wmz了,他只有想办法让912的小盆友们手抄代码,然后送给选手们。这里共有n份代码 ,编号1,2,…,n。每份代码有pi页。全部分给m个小盆友。每人分到顺序连续的若干份,每份代码只分给一人。 为了和谐,wangkun需要你,求一种方案,使每人分到的页数总和的最大值为最小. Input 每行输入两个n,m (1<=n<=200) 接下来有n个数,是每份代码的页数。 m < n 当 n = 0 并且 m=0时结束。 Output 输出一行,为每人…
2013-05-06 00:07 · oj · 评论(0)
boj 164
Description 古老的原始部落ACElite的居民们一直过着日出而做,日落而出的简单生活。酋长dalong为了改善大家的生活,研究出了一种新的无线通讯工具,便于大家之间相互交流。这需要架设多个基站进行通信。但由于各种原因,他无法保证这项技术是否成功,所以决定和champ测试一下。 现在我们知道ACElite部落有n(n<=10000)个山头,每个山头都可以架设基站。但如果山头间的距离大于c,基站间便无法通信。 在测试时dalong在s山头,champ在t山头,他们需要架设一些基站以进行通信。于是dalong希望YesXdogdog购买一些材料来架设基站,为了节约资源,YesXdogd…
2013-05-06 00:03 · oj · 评论(0)
boj 158
Description 为了准备期末考试了,laprovence正被讨厌的数字逻辑搞的头昏脑胀,尤其后面的一堆乱七八糟的概念,简直不知所云@#~!*&~ 这不有道简单的题就把他给难住了,题目大意是这样的:给出n个发光二极管,每个二极管都有两种状态,亮(on)与灭(off),然后给出一组每两个二极管之间的约束关系, 约束关系有以下3 种 1)a and b 表示第a个与第b个二极管必须同时亮 2)a or b表示第a个与第b个二极管至少有一个亮 3)a xor b 表示第a个与第b个二极管必须是一个亮,一个灭 Input 第一行两个整数n(二极管的个数,n<=10),m(m组约束关系,m<=5…
2013-04-28 00:07 · oj · 评论(0)
boj 268
Description A brand new sapper robot is able to neutralize mines in a rectangular region having integer height and width (N and M respectively). Before the robot begins its work it is placed near the top leftmost cell of the rectangle heading right. Then the robot starts moving and neutralizing min…
2013-04-27 21:21 · oj · 评论(0)
boj 237
Description Greetings, Libras. 一个不透明的袋子里装有若干个重量是1的小球, 袋子的重量忽略不计. 只知道小球的数量至少是1, 至多是N. 现在给你一架天平, 你可以自己设计一套砝码, 即砝码的个数与每个砝码的重量都可以自由定义(每个砝码的重量必须是正整数). 要求不管袋子里有多少个小球, 都可以用这套砝码称出小球的确切数量. 称的次数不限. 每次使用天平只能获得下列三种信息之一: 左边比右边重; 两边等重; 右边比左边重. 给你已知的N, 请问设计方案至少需要多少个砝码? Input 多组CASE(不超过50000组). 每组CASE一行, 一个正整数N. 1…
2013-04-27 21:09 · oj · 评论(0)
boj 378
Description 对于一个集合S={1,2,3,...N}的任一排列a1、a2、a3、... aN,我们定义ai的逆序数为∑(aj>ai | j<i),即排在ai前的所有比ai大的数的个数。我们把每个数的逆序数按下标排出就构成排列a1、a2、a3、... aN的一个逆序排列。比如排列 3 1 2的逆序排列为1 1 0(从左往右依次是1的逆序数、2的逆序数、3的逆序数)。 现在我们给出一个排列的逆序排列,请求出原排列。 Input 输入包含多组测试数据。 首先第一行输入一个数T(T<=10),表示总共有T组测试数据。 接下来是每组测试数据,第一行是一个数N(N<=100000),表示是N…
2013-04-27 00:39 · oj · 评论(0)
boj 447
Description Let’s play a stone removing game. Initially, n stones are arranged on a circle and numbered 1, …, n clockwise (Figure 1). You are also given two numbers k and m. From this state, remove stones one by one following the rules explained below, until only one remains. In step 1, remove ston…
2013-04-24 21:31 · oj · 评论(0)