Dash's Blog

Problem You are listening to your music collection using the shuffle function to keep the music surprising. You assume that the shuffle algorithm of your music player makes a random permutation of the songs in the playlist and plays the songs in that order until all songs have been played. Then it reshuffles and starts playing the list again.   You have a history of the songs that have been played. However, your record of the history of played songs is not complete, as you started recording song ...

Problem 描述起来很麻烦，大家还是直接去OJ站看吧。我之后也会解释一下题目的意思 题目链接： 1607 - Gates Input The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 ≤ d ≤ 20. The data sets follow.   Each data set consists of two consecutive lines. The rst of those lines contains exactly two positive integers n and m separated by single space, 1 ≤ n ≤ 100.000, 1 ≤ m ≤ 200.000. Integer n is the number of the net inputs and integer m is the number of the gates in the net.   The second of th ...

Problem Along a circular track, there are N gas stations, which are numbered clockwise from 1 up to N. At station i, there are pi gallons of petrol available. To race from station i to its clockwise neighbor one need qi gallons of petrol. Consider a race where a car will start the race with an empty fuel tank. Your task is to find whether the car can complete the race from any of the stations or not. If it can then mention the smallest possible station i from which the lap can be completed. Inpu ...

昨天做题时无意间得知了<functional>这个头文件，之后自己也稍微地了解了一下相关的一些知识。 内容比较多，叙述方面可能不是很详尽，大家如果看完还有不是很理解的地方，建议进文末的链接看看。 <functional>头文件 关于这个头文件，在cppreference.com中是这样定义的: This header is part of the function objects library and provides the standard hash function. 这个头文件定义了许多函数对象类型和支持函数对象的功能。 函数对象 关于函数对象这里就来比较详细的讲一下，也为后面的内容做一个铺垫。 先来看看cplusplus.com中关于函数对象（Function object）的定义： Function objects are objects specifically designed to be used with a syntax similar to that of functions. In C++, this is achieved b ...

Problem 这个问题要带图才能方便理解题意，这里为了节省时间，大家自己去网站看题目就好。我真是太懒了 :p Input The first line of input is an integer T (T < 1000) that indicates the number of test cases. Each case contains 3 integers K, A and B. The meanings of these variables are mentioned above. K will be in the range [0, 30] and 1 ≤ A ≤ B ≤ 2K. Output For each case, output the case number followed by the total number of red balloons in rows [A, B] after K-th hour. Sample Input 123430 1 13 1 83 3 7 Sample Output 123Case 1: 1Case 2: 27Case ...

Problem 有n（n≤5000）个数的集合S，每次可以从S中删除两个数，然后把它们的和放回集合， 直到剩下一个数。每次操作的开销等于删除的两个数之和，求最小总开销。所有数均小于 105。 Input Each test case will start with a positive number, N (2 ≤ N ≤ 5000) followed by N positive integers (all are less than 100000). Input is terminated by a case where the value of N is zero. This case should not be processed. Output For each case print the minimum total cost of addition in a single line. Sample Input 1234531 2 341 2 3 40 Sample Output 12919 Solution 题目很简单，就是最小的两个数相加，用优先队列只要几行代码就能完成。 ...

Problem 把一个包含m个正整数的序列划分成k个（1≤k≤m≤500）非空的连续子序列，使得每个正 整数恰好属于一个序列。设第i个序列的各数之和为S(i)，你的任务是让所有S(i)的最大值尽 量小。例如，序列1 2 3 2 5 4划分成3个序列的最优方案为1 2 3 | 2 5 | 4，其中S(1)、S(2)、S(3) 分别为6、7、4，最大值为7；如果划分成1 2 | 3 2 | 5 4，则最大值为9，不如刚才的好。每个 整数不超过107。如果有多解，S(1)应尽量小。如果仍然有多解，S(2)应尽量小，依此类推 Input The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly two lines. At the first line, there are two integers m and k, 1 ≤ k ≤ m ≤ 500. At the ...

Problem 给定一个长度为n的01串，选一个长度至少为L的连续子串，使得子串中数字的平均值最 大。如果有多解，子串长度应尽量小；如果仍有多解，起点编号尽量小。序列中的字符编号 为1～n，因此[1,n]就是完整的字符串。1≤n≤100000，1≤L≤1000。 例如，对于如下长度为17的序列00101011011011010，如果L=7，最大平均值为6/8（子 序列为[7,14]，其长度为8）；如果L=5，子序列[7,11]的平均值最大，为4/5。 Input Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing two integers n (1 ≤ n ≤ 100, 000) and L (1 ≤ L ≤ 1, 000) which are the l ...

Problem After the last war devastated your country, you - as the king of the land of Ardenia - decided it was high time to improve the defense of your capital city. A part of your fortification is a line of mage towers, starting near the city and continuing to the northern woods. Your advisors determined that the quality of the defense depended only on one factor: the length of a longest contiguous tower sequence of increasing heights. (They gave you a lengthy explanation, but the only thing you ...

Problem 输入一个长度为n（n≤106）的序列A，找到一个尽量长的连续子序列AL～AR，使得该序 列中没有相同的元素。 Input The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing an integer n, the number of snowflakes processed by the machine. The following n lines each contain an integer (in the range 0 to 109, inclusive) uniquely identifying a snowflake. Two snowflakes are identified by the same integer if and only if they are identical.   The input will contain no m ...