C语言acm竞赛习题集锦.doc

杭州电子科技大学acm习题精选目录1、 数塔问题.22、 并查集类问题.43、 递推类问题.94、 动态规划系列.105、 概率类题型.136、 组合数学类题型.157、 贪心策略.168、 几何问题.19数塔类问题数塔Problem Description在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？已经告诉你了，这是个DP的题目，你能AC吗?Input输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 = N = 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间0,99内。Output对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。Sample Input1573 88 1 0 2 7 4 44 5 2 6 5Sample Output 30#include#include#define MAX 101int arrMAXMAX2;void res() int n; int i,j; memset(arr,0,MAX*MAX*sizeof(int); scanf(%d,&n); for(i=0;in;i+) /输入数塔 for(j=0;j=0;i-) for(j=0;jarri+1j+11) arrij1+=arri+1j1; else arrij1+=arri+1j+11; printf(%dn,arr001);int main() int num; scanf(%d,&num); while(num-) res(); return 0;免费馅饼Problem Description都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标：为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中期中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼） Input输入数据有多组。每组数据的第一行为以正整数n(0n100000)，表示有n个馅饼掉在这条小径上。在结下来的n行中，每行有两个整数x,T(0T100000),表示在第T秒有一个馅饼掉在x点上。同一秒钟在同一点上可能掉下多个馅饼。n=0时输入结束。Output每一组输入数据对应一行输出。输出一个整数m，表示gameboy最多可能接到m个馅饼。Sample Input65 14 16 17 27 28 30Sample Output4#include#include#define MAX 100001int arrMAX13;int Max(int n1,int n2,int n3) int max; max=(n1n2)?n1:n2; max=(maxn3)?max:n3; return max;void res(int num) int i,j; int n,m,count=-1; memset(arr,0,MAX*13*sizeof(int); for(i=0;inum;i+) scanf(%d%d,&n,&m); arrmn+1+; if(count=0;i-) for(j=1;j=11;j+) arrij+=Max(arri+1j-1,arri+1j,arri+1j+1); printf(%dn,arr06);int main() int num; scanf(%d,&num); while(num) res(num); scanf(%d,&num); return 0;并查集类问题畅通工程Problem Description某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？ Input测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 注意:两个城市之间可以有多条道路相通,也就是说3 31 21 22 1这种输入也是合法的当N为0时，输入结束，该用例不被处理。 Output对每个测试用例，在1行里输出最少还需要建设的道路数目。 Sample Input4 21 34 33 31 21 32 35 21 23 5999 00Sample Output102998#include #include #define MAX 2000int n,m;int arrMAX2;int resMAX;int set;void proc() int i,j; int rest; set=1; /用来统计集合个数 memset(res,0,(n+1)*sizeof(int); resarr00=resarr01=1; for(i=1;i=set;i+) for(j=0;jm;j+) if(resarrj0*resarrj1) continue; /当前数据已经归类，则不进行任何操作 if(resarrj0=i|resarrj1=i) resarrj0=resarrj1=i; /对数据进行集合划分 j=-1; /从第一组元素开始继续遍历 for(j=0;jm;j+) if(resarrj0*resarrj1=0) break; /遇到首或尾没有归类的情况的时候跳出 if(jm) set+; /如果当前还有没有归类的情况新增加一个集合 else break; /如果当前数据全部归类则跳出所有循环 for(j=0;jm;j+) if(resarrj0*resarrj1=0) resarrj0=resarrj1=set; break; rest=0; for(i=1;i=n;i+) if(resi=0) rest+; if(m=0) printf(%dn,n-1); else if(rest=0) if(set=1) printf(0n); else printf(%dn,set-1); else printf(%dn,rest+set-1);int main() int i; scanf(%d,&n); while(n) scanf(%d,&m); for(i=0;im;i+) scanf(%d %d,&arri0,&arri1); proc(); scanf(%d,&n); return 0;how many tablesProblem DescriptionToday is Ignatius birthday. He invites a lot of friends. Now its dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with strangers.One important rule for this problem is that if I tell you A knows B, and B knows C, that means A, B, C know each other, so they can stay in one table.For example: If I tell you A knows B, B knows C, and D knows E, so A, B, C can stay in one table, and D, E have to stay in the other one. So Ignatius needs 2 tables at least.InputThe input starts with an integer T(1=T=25) which indicate the number of test cases. Then T test cases follow. Each test case starts with two integers N and M(1=N,M=1000). N indicates the number of friends, the friends are marked from 1 to N. Then M lines follow. Each line consists of two integers A and B(A!=B), that means friend A and friend B know each other. There will be a blank line between two cases.OutputFor each test case, just output how many tables Ignatius needs at least. Do NOT print any blanks.Sample Input25 31 22 34 55 12 5Sample Output24#include #define MAX 2000int n,m;int startMAX,endMAX;int res;int arrMAX;int len;int Mempty() int i; for(i=0;im;i+) if(starti!=0) return 0; return 1;int inSet(int index) int i; for(i=0;ires;i+) if(arri=index) return 1; return 0;void deal() int i; int space=0; for(i=0;im;i+) if(starti=0) space+; else starti-space=starti; endi-space=endi; m=m-space;void proc() int i; int j; while(!Mempty() i=0; while(im) if(starti=0) i+; continue; if(i=0) if(starti!=endi) arrres+=starti; arrres+=endi; else arrres+=starti; starti=endi=0; else for(j=0;jres;j+) if(arrj=starti) if(!inSet(endi) arrres+=endi; starti=endi=0; i=-1; break; if(arrj=endi) if(!inSet(starti) arrres+=starti; starti=endi=0; i=-1; break; i+; len+; deal(); if(res=n) len-; else len+=n-res-1;int main() int i; int num; scanf(%d,&num); while(num-) scanf(%d%d,&n,&m); for(i=0;im;i+) scanf(%d %d,&starti,&endi); res=0; len=0; proc(); printf(%dn,len+1); return 0;递推类问题1、 RPG问题(简单的递推问题)有排成一行的个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色求全部的满足要求的涂法.输入为方格数N(0=N=50),输出为满足要求的涂法递推公式：f(n)=f(n-1)+2*f(n-2)#includeint main() _int64 i,arr51; _int64 num; arr0=0; arr1=3; arr2=6; arr3=6; for(i=4;i51;i+) arri=arri-1+2*arri-2; while(scanf(%d,&num)!=EOF) printf(%I64dn,arrnum); return 0;2、 考新郎(错排系列递推)国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做考新郎,具体的操作是这样的:首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个.最后,揭开盖头,如果找错了对象就要当众跪搓衣板.假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.输入数据的第一行是一个整数C,表示测试实例的个数，然后是C行数据，每行包含两个整数N和M(1M=N=20)。对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。错排类递推公式为：f(n)=(m-1)*f(n-1)+f(n-2),其中m表示错排的个数（即错排的新人对数），n表示全部的新人个数。#include int main(void) int i, m, n; _int64 a212 = 1,0,1,0,2,1,6,2; for (i = 4; i 21; i+) ai0 = i * ai-10; ai1 = (i-1) * (ai-11 + ai-21); scanf(%d, &i); while (i- & scanf(%d%d, &n, &m) printf(%I64dn, an0/am0/an-m0*am1); return 0;动态规划系列How to Type Problem DescriptionPirates have finished developing the typing software. He called Cathy to test his typing software. She is good at thinking. After testing for several days, she finds that if she types a string by some ways, she will type the key at least. But she has a bad habit that if the caps lock is on, she must turn off it, after she finishes typing. Now she wants to know the smallest times of typing the key to finish typing a string. InputThe first line is an integer t (t=100), which is the number of test case in the input file. For each test case, there is only one string which consists of lowercase letter and upper case letter. The length of the string is at most 100. OutputFor each test case, you must output the smallest times of typing the key to finish typing this string. 第 21 页 共 21 页Sample Input3PiratesHDUacmHDUACMSample Output888#include #include #define MAX 200int arrMAX4;char strMAX;int letter(char ch) if(ch=A&ch=Z) return 1; return 0;void proc() int i; int tmp,min; int len=strlen(str); for(i=0;iarri-12+1|!arri0) arri0=arri-12+1; if(arri3arri-12+3|!arri3) arri3=arri-12+3; if(arri-13) if(arri1arri-13+2|!arri1) arri1=arri-13+2; if(arri2arri-13+2|!arri2) arri2=arri-13+2; else if(arri-10) arri1=arri-10+2; arri2=arri-10+2; if(arri-11) arri0=arri-11+1; arri3=arri-11+3; if(arri-12) if(arri1arri-12+2|!arri1) arri1=arri-12+2; if(arri2arri-12+2|!arri2) arri2=arri-12+2; if(arri-13) if(arri0arri-13+1|!arri0) arri0=arri-13+1; if(arri3arri-13+3|!arri3) arri3=arri-13+3; min=3*MAX; if(letter(strlen-1) if(arrlen-10) tmp=arrlen-10+1; if(tmpmin) min=tmp; if(arrlen-11) tmp=arrlen-11; if(tmpmin) min=tmp; if(arrlen-12) tmp=arrlen-12+1; if(tmpmin) min=tmp; if(arrlen-13) tmp=arrlen-13; if(tmpmin) min=tmp; else if(arrlen-10) tmp=arrlen-10; if(tmpmin) min=tmp; if(arrlen-11) tmp=arrlen-11+1; if(tmpmin) min=tmp; if(arrlen-12) tmp=arrlen-12; if(tmpmin) min=tmp; if(arrlen-13) tmp=arrlen-13+1; if(tmpmin) min=tmp; printf(%dn,min);/Caps Shift:0-00;1-01;2-10;3-11int main() int num; scanf(%d,&num); while(num-) scanf(%s,str); memset(arr,0,strlen(str)*4*sizeof(int); proc(); return 0;最大连续子序列Problem Description给定K个整数的序列 N1, N2, ., NK ，其任意连续子序列可表示为 Ni, Ni+1, ., Nj ，其中 1 = i = j = K。最大连续子序列是所有连续子序列中元素和最大的一个， 例如给定序列 -2, 11, -4, 13, -5, -2 ，其最大连续子序列为 11, -4, 13 ，最大和 为20。 在今年的数据结构考卷中，要求编写程序得到最大和，现在增加一个要求，即还需要输出该 子序列的第一个和最后一个元素。Input测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K( 10000 )，第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。Output对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元 素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。 Sample Input6-2 11 -4 13 -5 -210-10 1 2 3 4 -5 -23 3 7 -2165 -8 3 2 5 01103-1 -5 -23-1 0 -20Sample Output20 11 1310 1 410 3 510 10 100 -1 -20 0 0#include#include#define MAX 20000int arrMAX;int main() int num,temp,i,flage; int sum,start,end,max=-32768; scanf(%d,&num); while(num!=0) memset(arr,0,MAX*sizeof(int); for(i=0;inum;i+) scanf(%d,&arri); sum=0; temp=0; max=-32768; flage=0; for(i=0;i=0) flage=1; sum+=arri; if(maxsum) max=sum; start=temp; end=i; if(sum0) sum=0; temp=i+1; if(flage) printf(%d %d %dn,max,arrstart,arrend); else printf(0 %d %dn,arr0,arrnum-1); scanf(%d,&num); return 0;概率类题型糖果大战Problem Description生日Party结束的那天晚上，剩下了一些糖果，Gandon想把所有的都统统拿走，Speakless于是说：“可以是可以，不过我们来玩24点，你不是已经拿到了一些糖果了吗？这样，如果谁赢一局，就拿走对方一颗糖，直到拿完对方所有的糖为止。”如果谁能算出来而对方算不出来，谁就赢，但是如果双方都能算出或者都不能，就算平局，不会有任何糖果的得失。 Speakless是个喜欢提前想问题的人，既然他发起了这场糖果大战，就自然很想赢啦（不然可就要精光了-_-）。现在他需要你的帮忙，给你他每局赢的概率和Gardon每局赢的概率，请你给出他可能获得这场大战胜利的概率。Input每行有四个数，Speakless手上的糖果数N、Gardon手上的糖果数M(0=N,M=50)、一局Speakless能解答出来的概率p、一个问题Gardon能解答出来的概率q(0=p,q=1)。Output每行一个数，表示Speakless能赢的概率（用百分比计算，保留到小数点后2位）。Sample Input50 50 0.5 0.510 10 0.51 0.550 50 0.51 0.5Sample Output0.500.600.88#include #include const double EPS = 1e-12;inline void solve(int n, int m, double p, double q) if(n=0) printf(0.00n); else if(m=0) printf(1.00n); else if(p=0.0|q=1.0) printf(0.00n); else double lamda = q*(1-p)/(p*(1-q); if(fabs(lamda-1.0)EPS) printf(%.2lfn, double(n)/(m+n); else double res = (1-pow(lamda, n)/(1-pow(lamda, m+n); printf(%.2lfn, res); int main() int n, m; double p, q; while(scanf(%d%d%lf%lf, &n, &m, &p, &q)!=EOF) solve(n, m, p, q); return 0;组合数学类题型新生晚会Problem Description开学了，杭电又迎来了好多新生。ACMer想为新生准备一个节目。来报名要表演节目的人很多，多达N个，但是只需要从这N个人中选M个就够了，一共有多少种选择方法？Input数据的第一行包括一个正整数T，接下来有T组数据，每组数据占一行。每组数据包含两个整数N（来报名的人数,1=N=30），M（节目需要的人数0=M=30）Output每组数据输出一个整数，每个输出占一行Sample Input53 25 34 43 68 0Sample Output310101这里用到的数学公式为：=+（注意用一维数组来计算此式的技巧）#include#include#define MAX 1000int arrMAX;long solve(int n,int m) int i,j;arr0=1; for(i=1;i-1;j-) if(j=0|i=j) arrj=1; else arrj+=arrj-1; return arrm;int main() int num; int n,m; scanf(%d,&num); memset(arr,0,MAX*sizeof(int); while(num-) scanf(%d%d,&n,&m); printf(%ldn,solve(n,m); return 0; 贪心策略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 Ji pounds of JavaBeans and requires Fi pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get Ji* a% pounds of JavaBeans if he pays Fi* 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 integers M and N. Then N lines follow, each contains two non-negative integers Ji and Fi respectively. The last test case is followed by two -1s. 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 Input5 37 24 35 220 325 1824 1515 10-1 -1Sample Output13.33331.500#include#include#define MAX 1000int main() int i,j,m,n,temp; int