-
-
[求助]请教三道很简单的算法题。。。我没有KX了，只好发在这里了o(︶︿︶)o
-
发表于: 2012-6-16 01:22
-
这些题是南京邮电大学第四届大学生程序设计竞赛之预赛的题。说白了就是大一新生选拔的题。很简单。求C的源码，如果用C++做的话，很简单，用sort就行了。但是如果用C的话，我总是超时
，实在不知道该怎么办了，麻烦大家都做一下好吗？然后http://acm.njupt.edu.cn/acmhome/contest.do?&method=contestDetail&contestId=158
在这里提交一下源码，看看答案通过了没有，如果答案通过了，麻烦你把源码贴上来好吗？谢谢了。
第一题：
A. Sorting Problem I
题目描述：
openxxx喜欢一切有序的事物，现在有一串数字，openxxx希望以最小的代价对这串数字从小到大进行排序（实现非递减序）。
openxxx只会交换任意两个相邻的数字，每做一次交换，就要消耗openxxx一格的体力值，当然openxxx希望消耗的体力值越少越好，你能计算出openxxx至少要消耗多少格体力值吗？
输入格式：
多组测试数据，每组数据第一行包含一个正整数N（1<=N<=500）表示这串数字的个数，第二行包含N个正整数x1 x2 x3 …… xN（1<=xi<=N，1<=i<=N）用来描述这串原始数字序列，任意两个相邻数字之间用一个空格隔开。
输出格式：
每组测试数据对应一行输出，仅包含一个整数p，表示最少需要消耗的体力值数。
样例输入：
2
1 2
3
3 1 2
2
1 1
样例输出：
0
2
0
第二题：
B. Sorting Problem II
题目描述：
openxxx喜欢一切有序的事物，现在有一串数字，openxxx希望对这串数字从小到大进行排序（实现非递减序）。
openxxx可以交换任意两个数字，每做一次交换，就要消耗openxxx一格体力值，openxxx希望恰好在消耗了K格体力值的情况下完成排序，请你判断是否可能存在这样的情况。
输入格式：
多组测试数据，每组数据第一行包含一个正整数N（1<=N<=500）表示这串数字的个数，第二行包含N个正整数恰好是1~N的某一排列，相邻数字之间用一个空格隔开。第三行包含一个正整数M（1<=M<=500），接下来M行，每行包含一个非负整数K（0<=K<=50000），其含义见题目描述。
输出格式：
每组测试数据对应M行输出，每行输出一个字符串 “YES”或者“NO”(不包括双引号)，存在恰好消耗了K格体力值的情况下完成排序则输出“YES”，否则输出“NO”。
样例输入：
2
2 1
2
0
1
样例输出：
NO
YES
第三题
C. Arithmetic Progression
题目描述：
如果一个数列从第二项起，每一项与它的前一项的差等于同一个常数，这个数列就叫做等差数列，这个常数叫做等差数列的公差。 十分喜欢等差数列，他给你一个数列 ， ,他想知道有多少个子序列是等差数列，且公差的绝对值不超过 。所谓子序列为：在这个数列里，任取若干多项，不改变它们在原来数列中的先后次序，得到的数列称为是原来数列的一个子数列。(注意：等差数列至少2项)。
输入格式：
输入第一行为一个正整数 , 组测试数据，每组测试数据第一行为两个正整数 和 ，第二行为 个整数 。
输出格式：
对于每组测试数据输出一行，仅包含一个整数，为满足条件的子序列的个数，答案对1000000007取模。
样例输入：
1
3 3
1 2 3
样例输出：
4
，实在不知道该怎么办了，麻烦大家都做一下好吗？然后http://acm.njupt.edu.cn/acmhome/contest.do?&method=contestDetail&contestId=158在这里提交一下源码，看看答案通过了没有，如果答案通过了，麻烦你把源码贴上来好吗？谢谢了。
第一题：
A. Sorting Problem I
题目描述：
openxxx喜欢一切有序的事物，现在有一串数字，openxxx希望以最小的代价对这串数字从小到大进行排序（实现非递减序）。
openxxx只会交换任意两个相邻的数字，每做一次交换，就要消耗openxxx一格的体力值，当然openxxx希望消耗的体力值越少越好，你能计算出openxxx至少要消耗多少格体力值吗？
输入格式：
多组测试数据，每组数据第一行包含一个正整数N（1<=N<=500）表示这串数字的个数，第二行包含N个正整数x1 x2 x3 …… xN（1<=xi<=N，1<=i<=N）用来描述这串原始数字序列，任意两个相邻数字之间用一个空格隔开。
输出格式：
每组测试数据对应一行输出，仅包含一个整数p，表示最少需要消耗的体力值数。
样例输入：
2
1 2
3
3 1 2
2
1 1
样例输出：
0
2
0
第二题：
B. Sorting Problem II
题目描述：
openxxx喜欢一切有序的事物，现在有一串数字，openxxx希望对这串数字从小到大进行排序（实现非递减序）。
openxxx可以交换任意两个数字，每做一次交换，就要消耗openxxx一格体力值，openxxx希望恰好在消耗了K格体力值的情况下完成排序，请你判断是否可能存在这样的情况。
输入格式：
多组测试数据，每组数据第一行包含一个正整数N（1<=N<=500）表示这串数字的个数，第二行包含N个正整数恰好是1~N的某一排列，相邻数字之间用一个空格隔开。第三行包含一个正整数M（1<=M<=500），接下来M行，每行包含一个非负整数K（0<=K<=50000），其含义见题目描述。
输出格式：
每组测试数据对应M行输出，每行输出一个字符串 “YES”或者“NO”(不包括双引号)，存在恰好消耗了K格体力值的情况下完成排序则输出“YES”，否则输出“NO”。
样例输入：
2
2 1
2
0
1
样例输出：
NO
YES
第三题
C. Arithmetic Progression
题目描述：
如果一个数列从第二项起，每一项与它的前一项的差等于同一个常数，这个数列就叫做等差数列，这个常数叫做等差数列的公差。 十分喜欢等差数列，他给你一个数列 ， ,他想知道有多少个子序列是等差数列，且公差的绝对值不超过 。所谓子序列为：在这个数列里，任取若干多项，不改变它们在原来数列中的先后次序，得到的数列称为是原来数列的一个子数列。(注意：等差数列至少2项)。
输入格式：
输入第一行为一个正整数 , 组测试数据，每组测试数据第一行为两个正整数 和 ，第二行为 个整数 。
输出格式：
对于每组测试数据输出一行，仅包含一个整数，为满足条件的子序列的个数，答案对1000000007取模。
样例输入：
1
3 3
1 2 3
样例输出：
4
|
|
|---|---|
|
|
|
|
|
|
|
|
哪有刀塔。。。你自己去看那个网址啦，这是早都过去了的比赛啦，我只是自己想做一做罢了，但就是做不出来。。。
恩人，明早你能贴一份C的代码吗
|
|
|
|
|
|
|
|
|
额，这是我的解法，似乎看起来很长……
我只给关键过程。输入输出自己去搞吧。 #include <stdlib.h> unsigned int SortCount(unsigned int numElements,unsigned int *pArray) { unsigned int nCount,i,j; nCount=0; for (i=0;i<=numElements;i++) { for (j=i;j<=numElements;j++) { if(*(pArray+i)>*(pArray+j)) { nCount++; *(pArray+i)^=*(pArray+j)^=*(pArray+i)^=*(pArray+j); } } } return nCount; } int SortCountK(unsigned int numElements,unsigned int *pArray,unsigned int k) { unsigned int i,minCount,maxCount,*pArrayb,*pMinElement,*pElement; int return_value=0; pArrayb=(unsigned int *)(malloc(numElements*sizeof(unsigned int))); for (i=0;i<numElements;i++) *(pArrayb+i)=*(pArray+i); maxCount=SortCount(numElements,pArray); minCount=0; i=0; do { pElement=pArray+i; pMinElement=pElement; while(pElement<(pArrayb+numElements)) { if (*pMinElement>*pElement) pMinElement=pElement; pElement++; } if (pMinElement!=pArray+i) { minCount++; *pMinElement^=*pElement^=*pMinElement^=*pElement; } }while(i<=numElements); if (k>=minCount && k<=maxCount) return_value=1; return return_value; } unsigned int ArithmeticProgression(int numElements,int *pArray) { //结果在debug模式编译的程序是正确的，Release模式出错，不管了。 int min,max,i,j,subArrayCount,*pElement,Dvalue; min=*pArray; max=min; i=1; do { if(min>*(pArray+i)) min=*(pArray+i); if(max<*(pArray+i)) max=*(pArray+i); i++; }while(i<numElements); i=max-min; max=i; min=0-i; subArrayCount=0; for (i=0;i<numElements;i++) { pElement=pArray+i; Dvalue=0; for (j=1;pElement<(pArray+numElements);j++) { if((*pElement-*(pElement+j))>=min && (*pElement-*(pElement+j))<=max) { if (!Dvalue) { Dvalue=*pElement-*(pElement+j); } else { if ((*pElement-*(pElement+j))==Dvalue) { subArrayCount++; pElement+=j; j=0; } } } } } return subArrayCount; } |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
