下载文档原格式
程序设计比赛试题主办方：迅翔计算机协会最少钱币数：【问题描述】这是一个古老而又经典的问题。
用给定的几种钱币凑成某个钱数，一般而言有多种方式。
例如：给定了6种钱币面值为2、5、10、20、50、100，用来凑15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。
显然，最少需要2个钱币才能凑成15元。
你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。
【要求】【数据输入】输入可以有多个测试用例。
每个测试用例的第一行是待凑的钱数值M（1 <= M <= 2000，整数），接着的一行中，第一个整数K（1 <= K <= 10）表示币种个数，随后是K 个互不相同的钱币面值Ki(1 <= Ki <= 1000)。
输入M=0时结束。
【数据输出】每个测试用例输出一行，即凑成钱数值M最少需要的钱币个数。
如果凑钱失败，输出“Impossible”。
你可以假设，每种待凑钱币的数量是无限多的。
【样例输入】156 2 5 10 20 50 10011 2【样例输出】2ImpossibleFeli 的生日礼物【问题描述】Felicia 的生日是11月1日（和Kitty是同一天生的哦）。
于是Feli请来Kitty一起过生日。
Kitty带来了最新款的“Kitty猫”玩具准备送给Feli，不过她说，这份礼物可不是白送的。
Feli要帮她一个忙，才能够得到心仪已久的玩具。
Kitty说，“Kitty猫”玩具已经卖出了n!个，n<=10^100 *_*，Kitty想知道确切的数字，而不是无聊的“一个数加个感叹号”。
Feli 听了大吃一惊。
要知道，算出n!是一个无比艰巨的任务。
Feli告诉Kitty，就算Feli算出n!，Kitty也看不下去，因为当n=20 时，计算机的长整型已经存不下了（Kitty只能接受1-9之间的数字）。
CDOJ第七届ACM趣味程序设计竞赛第三场（正式赛）题解宝贵资源题⽬连接：题意平⾯上给n个点（n<=1000)，要求找⼀个⾯积最⼩的正⽅形，将所有的点都囊括进去。
要求正⽅形的边必须平⾏于坐标轴。
题解：对于这道题，我们可以⾸先找⼀个满⾜题意的，并且⾯积是最⼩的矩形。
假设矩形的长为L，宽为W，那么很显然:L = (MaxX - MinX)W = (MaxY - MinY)MaxX，MaxY 指题⽬中输⼊的最⼤横、纵坐标的值，MinX，MinY 指题⽬中输⼊的最⼩横，纵坐标的值。
因为我们需要得到正⽅形，那么正⽅形的边长L 取 max(L,W)即可。
这道题就结束了~代码如下：#include<iostream>#include<stdio.h>using namespace std;unsigned long long x1=99999999999LL,x2=0,y1=99999999999LL,y2=0;int main(){int n;scanf("%d",&n);for(int i=1;i<=n;i++){unsigned long long X ,Y;cin>>X>>Y;x1 = min(x1,X);x2 = max(x2,X);y1 = min(y1,Y);y2 = max(y2,Y);}unsigned long long l = max(x2-x1,y2-y1);cout<<l*l<<endl;}The Desire of Asuna题⽬连接：题意给你n条链，每条链的长度为a[i]每次操作你可以选择⼀条链，使得这条链的长度减1，然后使得任意两条链连接在⼀起，连接之后的长度要加1。
询问最少操作次数。
题解：贪⼼。
我们选择长度减⼩的链，⼀定是可选的，并且长度最⼩的链。
我们选择合并的链，⼀定是当前长度最⼤的两条链。
acm竞赛试题及答案ACM（Association for Computing Machinery）竞赛是一项全球性计算机科学竞赛，旨在锻炼参赛者的问题解决能力和编程技巧。
每年都有数千名来自不同学校的学生参加这一挑战。
本文将提供一些最近的ACM竞赛试题以及相应的答案，帮助读者了解和学习竞赛题目的类型和解题思路。
1. 问题描述给定一个由N个整数组成的数组A，请编写一个程序，找出数组中两个不同元素的差的最小值。
2. 输入格式- 第一行包含一个整数N，表示数组A的长度。
- 第二行包含N个以空格分隔的整数，表示数组A中的元素。
3. 输出格式输出一个整数，表示数组中两个不同元素的差的最小值。
4. 示例输入：51 52 9 12输出：15. 解题思路该问题可以通过对数组进行排序，并比较相邻两个数的差值来求解。
首先，将数组A进行升序排序。
然后，遍历排序后的数组，依次计算相邻两个数的差值，并记录其中的最小值。
最后，返回这个最小差值即可。
6. 代码实现```pythondef min_difference(nums):nums.sort() # 对数组进行升序排序min_diff = float('inf') # 初始化最小差值为正无穷大for i in range(len(nums)-1):diff = abs(nums[i] - nums[i+1]) # 计算相邻两个数的差值min_diff = min(min_diff, diff) # 更新最小差值return min_diff# 输入处理N = int(input())A = list(map(int, input().split()))# 调用函数并输出结果result = min_difference(A)print(result)```7. 答案解析对给定的数组进行排序后，遍历数组计算相邻两个数的差值，并记录其中的最小值。
上述代码中，首先将数组A进行升序排序，然后使用一个变量`min_diff`来记录最小差值。
1000 A + B ProblemProblem DescriptionCalculate A + B .InputEach line will contain two integers A and B. Process to end of file.OutputFor each case, output A + B in one line.Sample Input1 1Sample Output2AuthorHDOJ代码：#include<stdio.h>int main(){int a , b;while( scanf ( "%d %d" ,& a,& b)!= EOF)printf( "%d\n" , a+b);}1001 Sum ProblemProblem DescriptionHey, welcome to HDOJ(Hangzhou Dianzi University Online Judge).In this problem, your task is to calculate SUM(n) = 1 + 2 + 3 + ... + n.InputThe input will consist of a series of integers n, one integer per line.OutputFor each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit signed integer.Sample Input1100Sample Output15050AuthorDOOM III解答：#include<stdio.h>main (){int n , i , sum;sum =0;while (( scanf ( "%d" ,& n)!=- 1)) {sum for =0;( i =0; i <= n; i ++)sum +=i ;printf( "%d\n\n" , sum);}}1002 A + B Problem IIProblem DescriptionI have a very simple problem for you. Given two integers A and B, your job is to calculate the Sum of A + B. InputThe first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000.OutputFor each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line is the an equation "A + B = Sum", Sum means the result of A + B. Note there are some spaces int the equation. Output a blank line between two test cases.Sample Input21 2Sample OutputCase 1:1+2=3Case 2:Author代码：#include <stdio.h>#include <string.h>int main (){char str1 [ 1001 ], str2 [ 1001 ];int t , i , len_str1 , len_str2 , len_max , num = 1 , k ; scanf ( "%d" , & t );getchar ();while ( t --){int a [ 1001 ] = { 0}, b [1001]={ 0}, c [1001]={ 0};scanf ( "%s" , str1 );len_str1 = strlen ( str1 );for ( i = 0 ; i <= len_str1 - 1;++ i )a [ i ] = str1 [ len_str1 - 1 - i ] - '0' ;scanf ( "%s" , str2 );len_str2 = strlen ( str2 );for ( i = 0 ; i <= len_str2 - 1;++ i )b [ i ] = str2 [ len_str2 - 1 - i ] - '0' ;if ( len_str1 > len_str2 )len_max = len_str1 ;elselen_max = len_str2 ;k = 0 ;for ( i = 0 ; i <= len_max - 1 ;++ i ){c [ i ] = ( a[ i ] + b [ i ] + k ) % 10 ;k = ( a[ i ] + b [ i ] + k ) / 10 ;}if ( k != 0 )c [ len_max ] = 1 ;printf ( "Case %d:\n" , num );num ++;printf ( "%s + %s = " , str1 , str2 );if ( c[ len_max ] == 1 )printf ( "1" );for ( i = len_max - 1 ; i >= 0 ;-- i ){printf ( "%d" , c [ i ]);}printf ( "\n" );if ( t >= 1 )printf ( "\n" );}return 0 ;}1005 Number Sequence Problem DescriptionA number sequence is defined as follows:f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.Given A, B, and n, you are to calculate the value of f(n).InputThe input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.OutputFor each test case, print the value of f(n) on a single line.Sample Input1 1 312100 0 0Sample Output25AuthorCHEN, ShunbaoSourceRecommendJGShining代码：#include<stdio.h>int f [ 200 ];int main (){int a , b, n, i ;while ( scanf ( "%d%d%d" ,& a,& b,& n)&& a&&b&&n){if ( n>= 3){f [ 1]= 1; f [ 2]= 1;for ( i =3; i <= 200 ; i ++){f [ i ]=( a* f [ i - 1]+ b* f [ i - 2])% 7;if ( f [ i - 1]== 1&&f [ i ]== 1)break ;}i -= 2;n =n%i ;if ( n== 0)printf ( "%d\n" , f [ i ]);elseprintf ( "%d\n" , f [ n]);}elseprintf ( "1\n" );}return 0 ;}1008 ElevatorProblem DescriptionThe highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6 seconds to move the elevatorup one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop.For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.InputThere are multiple test cases. Each case contains a positive integer N, followed by N positive numbers. All the numbers in the input are less than 100. A test case with N = 0 denotes the end of input. This test case is not to be processed.OutputPrint the total time on a single line for each test case.Sample Input1 23231Sample Output1741AuthorZHENG, JianqiangSourceRecommendJGShining代码：#include<stdio.h>int a [ 110 ];int main(){int while { sum , i , n;( scanf ( "%d" ,& n)&& n!= 0)forscanf ( i =1; i <= n; i ++)( "%d" ,& a[ i ]);sum a for=0;[ 0]= 0;( i =1; i <= n; i ++){ifsum ( a[ i ]> a[ i - 1])+=6*( a[ i ]- a[ i - 1]);elsesum +=4*( a[ i - 1]- a[ i ]);sum +=5;printf ( "%d\n" , sum);}return 0 ;}1009 FatMouse' TradeProblem DescriptionFatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean.The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]* a% pounds of JavaBeans if he pays F[i]* a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.InputThe input consists of multiple test cases. Each test case begins with a line containing two non-negative integersM and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test caseis followed by two -1's. All integers are not greater than 1000.OutputFor each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain.Sample Input53724352203251824151510-1-1Sample OutputAuthorCHEN, YueSourceRecommendJGShining代码：#include<stdio.h>#include<string.h>#define MAX 1000int main(){int i,j,m,n,temp;int J[MAX],F[MAX];double P[MAX];double sum,temp1;scanf("%d%d",&m,&n);while(m!=-1&&n!=-1){sum=0;memset(J,0,MAX*sizeof(int));memset(F,0,MAX*sizeof(int));memset(P,0,MAX*sizeof(double));for(i=0;i<n;i++){ scanf("%d%d",&J[i],&F[i]); P[i]=J[i]*1.0/((double)F[i]); }for(i=0;i<n;i++){for(j=i+1;j<n;j++){if(P[i]<P[j]){temp1=P[i];P[i]=P[j];P[j]=temp1;temp=J[i]; J[i]=J[j]; J[j]=temp; temp=F[i];F[i]=F[j]; F[j]=temp;} }}for(i=0;i<n;i++) { if(m<F[i]){ else{sum+=m/((double)F[i])*J[i];sum+=J[i];break;m-=F[i];} }}printf("%.3lf\n",sum); scanf("%d%d",&m,&n); }return 0; }1021 Fibonacci AgainProblem DescriptionThere are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2).InputInput consists of a sequence of lines, each containing an integer n. (n < 1,000,000).OutputPrint the word "yes" if 3 divide evenly into F(n). Print the word "no" if not.Sample Input0 1 2 3 4 5Sample Outputno no yes no no noAuthorLeojayRecommendJGShining#include<stdio.h> int main () { long while if printfn ;( scanf ( "%ld" ,& n) !=( n%8==2 || n %8==6) ( "yes\n" ); EOF ) elseprintf ( "no\n");return0 ;}1089 A+B for Input-Output Practice (I)Problem DescriptionYour task is to Calculate a + b.Too easy?! Of course! I specially designed the problem for acm beginners.You must have found that some problems have the same titles with this one, yes, all these problems were designed for the same aim.InputThe input will consist of a series of pairs of integers a and b, separated by a space, one pair of integers per line.OutputFor each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input.Sample Input151020Sample Output630AuthorlcyRecommendJGShining解答：#include<stdio.h>main (){int a , b;while( scanf ( "%d%d" ,& a,& b)!=EOF)printf( "%d\n" , a+b);}1090 A+B for Input-Output Practice (II)Problem DescriptionYour task is to Calculate a + b.InputInput contains an integer N in the first line, and then N lines follow. Each line consists of a pair of integers a and b, separated by a space, one pair of integers per line.OutputFor each pair of input integers a and b you should output the sum of a and b in one line, and with one line of output for each line in input.Sample Input2151020Sample Output630AuthorlcyRecommendJGShining解答：#include<stdio.h>#define M 1000void main (){int a , b, n, j [ M], i ;//printf("please input n:\n");scanf( "%d" ,& n);for( i =0; i <n; i ++){scanf( "%d%d" ,& a,& b);//printf("%d %d",a,b);j[ i ]= a+b;}i=0;while( i <n){printf( "%d" , j [ i ]);i++;printf( "\n" );}}1091 A+B for Input-Output Practice(III) Problem DescriptionYour task is to Calculate a + b.InputInput contains multiple test cases. Each test case contains a pair of integers a and b, one pair of integers per line.A test case containing 0 0 terminates the input and this test case is not to be processed.OutputFor each pair of input integers a and b you should output the sum of a and b in one line, and with one line ofoutput for each line in input.Sample Input15102000Sample Output630AuthorlcyRecommendJGShining解答：#include<stdio.h>main (){int a , b;scanf( "%d %d" ,& a,& b);while(!( a== 0&&b==0)){printf( "%d\n" , a+b);scanf( "%d %d" ,& a,& b);}}1092 A+B for Input-Output Practice(IV) Problem DescriptionYour task is to Calculate the sum of some integers.InputInput contains multiple test cases. Each test case contains a integer N, and then N integers follow in the same line. A test case starting with 0 terminates the input and this test case is not to be processed.OutputFor each group of input integers you should output their sum in one line, and with one line of output for each line in input.。
acm试题及答案pythonACM试题及答案（Python）1. 问题描述：给定一个整数数组，请编写一个Python函数，找出数组中第二大的数。
2. 输入格式：一个包含整数的列表。
3. 输出格式：一个整数，表示数组中第二大的数。
4. 示例：- 输入：[10, 5, 8, 20, 15]- 输出：155. 答案：```pythondef find_second_max(nums):first_max = float('-inf')second_max = float('-inf')for num in nums:if num > first_max:second_max = first_maxfirst_max = numelif num > second_max and num != first_max:second_max = numreturn second_max if second_max != float('-inf') else None# 示例测试nums = [10, 5, 8, 20, 15]print(find_second_max(nums)) # 输出应为15```6. 分析：此题要求找出数组中第二大的数。
我们可以通过遍历数组，使用两个变量分别记录当前找到的最大值和第二大值。
在遍历过程中，如果当前元素比第一大的元素大，则更新第二大的元素为当前第一大的元素，并将当前元素设为第一大的元素。
如果当前元素小于第一大的元素但大于第二大的元素，则更新第二大的元素。
最后返回第二大的元素。
7. 注意：如果数组中只有一个元素或所有元素都相等，则返回`None`。
ACM竞赛试题集锦（2020年九⽉整理）.doc取⽯⼦游戏Time Limit:1S Memory Limit:1000KTotal Submit:505 Accepted:90Description有两堆⽯⼦，数量任意，可以不同。
游戏开始由两个⼈轮流取⽯⼦。
游戏规定，每次有两种不同的取法，⼀是可以在任意的⼀堆中取⾛任意多的⽯⼦；⼆是可以在两堆中同时取⾛相同数量的⽯⼦。
最后把⽯⼦全部取完者为胜者。
现在给出初始的两堆⽯⼦的数⽬，如果轮到你先取，假设双⽅都采取最好的策略，问最后你是胜者还是败者。
Input输⼊包含若⼲⾏，表⽰若⼲种⽯⼦的初始情况，其中每⼀⾏包含两个⾮负整数a 和b，表⽰两堆⽯⼦的数⽬，a和b都不⼤于1,000,000,000。
Output输出对应也有若⼲⾏，每⾏包含⼀个数字1或0，如果最后你是胜者，则为1，反之，则为0。
Sample Input2 18 44 7Sample Output1跳蚤Time Limit:1S Memory Limit:1000KTotal Submit:198 Accepted:44DescriptionZ城市居住着很多只跳蚤。
在Z城市周六⽣活频道有⼀个娱乐节⽬。
⼀只跳蚤将被请上⼀个⾼空钢丝的正中央。
钢丝很长，可以看作是⽆限长。
节⽬主持⼈会给该跳蚤发⼀张卡⽚。
卡⽚上写有N+1个⾃然数。
其中最后⼀个是M，⽽前N个数都不超过M，卡⽚上允许有相同的数字。
跳蚤每次可以从卡⽚上任意选择⼀个⾃然数S，然后向左，或向右跳S个单位长度。
⽽他最终的任务是跳到距离他左边⼀个单位长度的地⽅，并捡起位于那⾥的礼物。
⽐如当N=2，M=18时，持有卡⽚(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。
⽽持有卡⽚(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边⼀个单位长度的地⽅。
注：两个题目可选做一个，也可两个都做。
难度不一定按顺序排列。
题目1：核电站问题题目描述一个核电站有N个放核物质的坑，坑排列在一条直线上。
如果连续M个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质。
任务：对于给定的N和M，求不发生爆炸的放置核物质的方案总数输入格式输入文件只一行，两个正整数N，M( 1<N<50，2≤M≤5)输出格式输出文件只有一个正整数S，表示方案总数。
样例输入题目2：小t的游戏Problem Description小t有点神经质，喜欢发明一些稀奇古怪的游戏，比如说左手和右手打架就是他发明的。
这个周末，小t又发明了一个有趣的硬币游戏：小t手里有6枚硬币，他把硬币分成了两堆，一左一右并排堆放，一堆2个，一堆4个。
然后他开始从这两个堆中各取出1个硬币，再组成一个新的堆放在最右边。
用(2,4)表示初始两堆，于是作下抽象，第一次操作后(2,4)变成了(1,3,2)。
小t继续操作，他从这三堆中继续各取出1个硬币，组成新堆放到最右边。
于是(1,3,2)变成了(0,2,1,3)，去掉空堆，变成(2,1,3)。
小t继续进行以上操作并去除空堆，(2,1,3)变成了(1,2,3)。
这时，小t发现如果继续做同样的动作，分堆的硬币不会再有变化了，一直都是(1,2,3)状态，也就是陷入了循环节为1的循环。
小t突发奇想，他想知道：如果知道硬币的分堆数，和每堆硬币的个数，执行“每次从已有的每一堆硬币中取出1个硬币，凑成新堆”的操作，用(a,b,c,d,….)表示分堆状态（其中a,b,c,d…每个字母都是正整数），分堆状态是否会陷入循环，如果陷入循环，循环节又是多少呢。
Input输入有很多组case，每组case第一行一个正整数n (n<65536)，表示硬币分为多少堆第二行有n个整数，每个数k<65536，表示每堆有多少个硬币，每个数后面都有一个空格。
Output如果分堆状态陷入循环，输出分两行，第一行输出yes，第二行输出一个整数表示循环节长度。
acm选拔试题及答案# acm选拔试题及答案1. 问题描述：编写一个程序，计算给定整数序列中，连续子序列的最大和。
2. 输入格式：第一行包含一个整数 \( n \)，表示序列的长度。
第二行包含 \( n \) 个整数，表示序列中的元素。
3. 输出格式：输出一个整数，表示连续子序列的最大和。
4. 示例：输入：```51 -234 -1```输出：```6```5. 问题分析：这个问题可以通过动态规划的方法来解决。
定义一个数组 `dp[i]` 来表示以第 `i` 个元素结尾的连续子序列的最大和。
6. 算法逻辑：- 初始化 `dp[0]` 为序列的第一个元素。
- 对于每个 `i`（从 1 到 `n-1`），`dp[i]` 可以通过 `dp[i-1] + nums[i]` 来更新，如果 `dp[i-1]` 是负数，则 `dp[i]` 应该等于`nums[i]`。
- 遍历序列，更新 `dp` 数组，同时记录最大和。
7. 代码实现：```pythondef max_subarray_sum(nums):n = len(nums)max_sum = nums[0]current_sum = nums[0]for i in range(1, n):current_sum = max(nums[i], current_sum + nums[i]) max_sum = max(max_sum, current_sum)return max_sum```8. 测试用例：- 输入：`[-2, 1, -3, 4, -1, 2, 1, -5, 4]`- 输出：`6`9. 答案解析：- 该测试用例中，连续子序列 `[4, -1, 2, 1]` 的和为 `6`，是所有可能子序列中的最大值。
10. 注意事项：- 考虑边界条件，如序列中所有元素都是负数的情况。
- 优化算法以处理大数据量的情况。
11. 附加说明：- 该问题也可以通过分治法或贪心算法来解决，但动态规划提供了一个更简洁且易于理解的解决方案。
//missing_趣题、1.歌唱王国（Modified）字母表中有若干个字母，从空串出发每次等概率随机选择一个字母添加在当前串的末尾。
另给若干停止串，若当前串中出现了这些停止串则停止扩展。
求串扩展的期望长度~！2.水管局长SC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。
嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。
在处理每项送水任务之前，路径上的水管都要进行一系列的准备操作，如清洗、消毒等等。
嘟嘟在控制中心一声令下，这些水管的准备操作同时开始，但由于各条管道的长度、内径不同，进行准备操作需要的时间可能不同。
供水公司总是希望嘟嘟能找到这样一条送水路径，路径上的所有管道全都准备就绪所需要的时间尽量短。
嘟嘟希望你能帮助他完成这样的一个选择路径的系统，以满足供水公司的要求。
另外，由于MY市的水管年代久远，一些水管会不时出现故障导致不能使用，你的程序必须考虑到这一点。
-----------------------------------------------最小生成森林LCA + 反向加边优化。
3.Frequent values给一个有序序列，你的任务是对于每个询问Q(i, j)，输出[i, j]中出现频率最高的次数。
-1 -1 1 1 1 1 3 10 10 10-----------------------------------------------转换为：2 4 1 3，辅助sum数组二分查找：2 6 7 10。
RMQ4.与众不同A是某公司的CEO，每个月都会有员工把公司的盈利数据送给A，A是个与众不同的怪人，A 不注重盈利还是亏本，而是喜欢研究“完美序列”：连续的互不相同的序列。
A想知道区间[L,R] 之间最长的完美序列。
-----------------------------------------------st[i]:=max(st[i-1],last[a[i]]+1)len[i]:=i-st[i]+1由st的非递减性对于[L, R]可二分找到一个最大M使得st[M]<=L，则Q(i, j) = max(M-L+1, RMQ(M+1, R));5.程序复杂度（模拟）给出一段程序，计算它的时间复杂度。
这段程序只有三种语句：–OP <x>：执行一条时间耗费为x 的指令。
这里的x 为不超过100 的正整数。
–LOOP <x>：与END 配套，中间的语句循环x 次，其中x 可以为规模n，也可以是不超过100 的正整数。
–END：与LOOP 配套，循环终止。
注意：OP 语句的参数不能为变量n，而LOOP 语句的参数可以为变量n，但不允许有其他名字的变量。
这样，整个程序的时间复杂度应为n 的多项式。
你的任务就是计算并显示出这个多项式。
Sample InOP 1LOOP nLOOP 10LOOP n OP 7 ENDOP 1ENDENDSample Out70n^2+10n+16.序列和的前n小元素给你两个长度为n的数组A,B，从A，B中任选一个元素，可得到n*n个和，回答询问Q(i)，表示第i小和的值(1<=i<=n)。
-----------------------------------------------n路归并、heap7.轮廓线a).每一个建筑物用一个三元组(L, H, R), 表示左边界, 高度和右边界。
轮廓线如此给出：x1-H1-x2-H2-x3-H3-x4-0(x1<x2<x3<x4....，0代表结束)。
求轮廓线……b).求总面积。
-----------------------------------------------离散化，每个区间找最大值。
与求矩形面积相似，a)快排后线性heap求解区间最大值。
b)线段树……8.赛车有n辆赛车从各不相同的地方以各种速度(0<vi<10000)开始向右行驶，不断有超车现象发生。
给出n辆赛车的描述(位置xi, 速度vi)。
输出超车总数以及按时间顺序的前m个超车事件(ti, ai, bi->ti 时间ai超过bi)。
------------------------------------------------注意时间是浮点型，用heap模拟过程保存每辆车的前车与后车及超越时间。
超越时间的比较用整数乘法……9.可怜的奶牛农夫John有n（n≤100000）头奶牛，可是由于它们产的奶太少，农夫对它们很不满意，决定每天把产奶最少的一头做成牛肉干吃掉。
但还是有一点舍不得，John打算如果不止有一头奶牛产奶最少，当天就大发慈悲，放过所有的牛。
由于John的奶牛产奶是周期性的，John在一开始就能可以了解所有牛的最终命运，不过他的数学很差，所以请你帮帮忙，算算最后有多少头奶牛可以幸免于难。
每头奶牛的产奶周期Ti可能不同，但不会超过10。
在每个周期中，奶牛每天产奶量不超过200。
（输入一个T，表示John想知道T天后的奶牛数(T<=10^5)。
待测试）-------------------------------------------------按周期分组，然后对每个周期中的每天维护一个heap，模拟天数。
10.黑匣子我们使用黑匣子的一个简单模型。
它能存放一个整数序列和一个特别的变量i。
在初始时刻，黑匣子为空且i等于0。
这个黑匣子执行一序列的命令。
有两类命令：ADD(x)：把元素x放入黑匣子；GET +/-：（+:i增1的同时，-:i减1的同时）输出黑匣子内所有整数中第i小的数。
牢记第i小的数是当黑匣子中的元素以非降序排序后位于第i位的元素。
（如果i超出整数序列的个数范围，你应该输出NoElement。
）-------------------------------------------------两个heap，一个大根堆维护输出的第i小值，一个小根堆，维护下一个将添加到大根堆里的元素值。
11.代码等式由元素0和1组成的非空的序列称为一个二进制代码。
一个代码等式就是形如x1x2..xl=y1y2..yr,这里xi和yj是二进制的数字（0或1）或者是一个变量（如英语中的小写字母）。
每一个变量都是一个有固定长度的二进制代码，它可以在代码等式中取代变量的位置。
我们称这个长度为变量的长度。
对于每一个给出的等式，计算一共有多少组解。
例: a,b,c,d,e的长度分别是4,2,4,4,2, 则1bad1 = acbe有16组解--------------------------------------------------并查集求解。
先解析等式，把字母代表的二进制位用一个整数表示，即a,b,c,d,e的二进制位可从2标号到17。
然后并查集求解变量集合个数n。
答案为2^n。
12.如下定义：朋友的朋友是朋友，敌人的敌人是敌人~！给你若干关系，判断最多有多少关系是正确的，如果一个关系与前面的关系矛盾，我们认为它是错误的，就不要。
--------------------------------------------------有问题，值得思考。
想到了，感觉是个好东西……还是并查集。
对每个人有两个集合：朋友集合及敌人集合。
先确认一个事实：在（a,b,c）关系中，如果a,b为朋友而a,c为敌人则b,c的关系只能是陌生人。
所以对于每个输入(a,b)应该先判断没有一个c使得a,c为朋友，b,c为敌人，或者相反。
为了快速的进行上面的判断，我的策略是将每个人的朋友集合代表元和敌人代表元hash成一个整数，由上面的关系知，如果F(a)+E(b)或F(b)+E(a)可以在hash表中找到就说明(a, b)应该是陌生人，不能有任何关系。
然后对于每次合并都需要修改hash表。
我是先初始化a的敌人和朋友都是a，则hash表中有n个值F(i)+E(i) = i+i。
每次合并必然是删除一个值和添加一个值，所以可以在内存不增加的情况下保存不可能的值。
hash 查找近似O(1)。
13.合并队列初始时n个数1~n各在单独的一列中, 需要执行两个操作–Move(i, j): 把i所在列接到j所在列的尾部–Check(i, j): 询问i和j是否在同一列, 如果是, 输出二者之间的元素个数---------------------------------------------------并查集....14.数字序列给定一个整数序列 a1 , a2 , … , an，求一个不下降序列 b1≤b2≤…≤bn，使得数列 {ai} 和 {bi} 的各项之差的绝对值之和|a1 - b1| + |a2 - b2| + … + |an - bn| 最小。
（数据规模：1≤n≤106, 0≤ai≤2*10^9 ）----------------------------------------------------假设数列 a1,a2, … ,ak 的最优解为 b1,b2, … ,bk。
合并 {bi} 中相同的项，得到 m 个区间和数列 s1,s2, … ,sm显然，si 为数列 a 中，下标在第 i 个区间内的各项的中位数。
若ak+1>sm，直接令sm+1＝ak+1，得到前k+1项的最优解；否则，将ak+1并入第m个区间，并更新sm不断检查最后两个区间的解 sm-1和 sm，若sm-1≥sm，合并最后两个区间，并令新区间的解为该区间内的中位数。
左偏堆实现。
aco Jan09 Safe Travel格雷姆林最近在农场里泛滥，这些丑陋的东西会阻止牛从农庄(牛棚1)走到其他的牛棚(第i 头牛的目的是牛棚i)，每个格雷姆林i都只认识牛i并且知道牛i一般走到牛棚i的最短路径(时间最少的路径)。
所以每个格雷姆林i都会在牛i到牛棚i的最短路径的最后一条路上等牛i。
当然牛不愿意遇到格雷姆林，所以准备找一条稍微不同的路径从牛棚1走到牛棚i。
所以，请你为每一头牛i找出避免格雷姆林的最短路径的长度。
农场中有M条双向道路，N个编号1..N的牛棚。
第i条路连接牛棚ai、bi,且需要ti时间通过(两点间最多存在一条路)。
牛i到牛棚i的最短路唯一且存在。
N<=100,000;M<=200,000图论，难题。
