ECNUOJ#4

ECNUOJ#4

Nth Largest Value

第N大数

单点时限: 2.0 sec

内存限制: 256 MB

For this problem, you will write a program that prints the Nth largest value in a fixed sized array of integers. To make things simple, N will be 3 and the array will always be have 10 decimal integer values.

输入格式
The first line of input contains a single integer §, ((1 leq P leq 1000)), which is the number of data sets that follow. Each data set consists of a single line containing the data set number, followed by a space, followed by 10 space separated decimal integers whose values are between 1 and 1000 inclusive.

输出格式
For each data set, generate one line of output with the following values: The data set number as a decimal integer, a space, and the 3rd largest value of the corresponding 10 integers.

样例
input
4
1 1 2 3 4 5 6 7 8 9 1000
2 338 304 619 95 343 496 489 116 98 127
3 931 240 986 894 826 640 965 833 136 138
4 940 955 364 188 133 254 501 122 768 408
output
1 8
2 489
3 931
4 768

#include<bits/stdc++.h>using namespace std;int sq[11];
int main()
{int number;cin>>number;while(number--){int number=10,ft;cin>>ft;int i=0;while(i<number){cin>>sq[i++];}nth_element(sq,sq+7,sq+10);cout<<ft<<" "<<sq[7]<<endl;}
}

5.特殊的子集

5. 特殊的子集
   单点时限: 2.0 sec

内存限制: 256 MB

集合 (M={1,2,3,ldots,n}) 的子集中，有一些是不含相邻自然数元素的。例如：(n=4) 时，集合 ({1,3}) 是满足要求的，而 ({1,3,4}) 是不满足的，因为它含有相邻自然数 (3) 和 (4)。把所有满足要求的子集记作 (S_i)，对于每一个 (S_i) 计算出它的所有元素的乘积 (T_i)，求 (sum {T_i}^2 )。

输入格式
仅一行，包括一个正整数 (n) ((n leq 100))。

输出格式
仅一行，即 (T_i) 的平方和，可能会超出长整型范围。

样例
input
4
output
119

#include<bits/stdc++.h>
using namespace std;/*
递归式
f(n)=f(n-1)+n^2f((n-2)+1)
得f(n)=(n+1)!-1
然后使用大数阶乘
*/
#define MAXLEN 10000
int main()
{int n;cin>>n;int i,j,up,tmp;char arr[MAXLEN+1]={1};for(i=2;i<=n+1;i++){for(up=0,j=0;j<=MAXLEN;j++){tmp=arr[j]*i+up;arr[j]=tmp%10;up=tmp/10;}}int key;if(arr[0]!=0){arr[0]--;	}else if(arr[0]==0){for(i=MAXLEN;i>=0;i--){if(arr[i]!=0){key=i;break;}}for(i=1;i<=key;i++){if(arr[i]!=0){arr[i]--;break;}else{arr[i]=9;}}arr[0]=9;		}for(i=MAXLEN;i>=0;i--)if(arr[i]!=0)for(i;i>=0;i--)printf("%d",arr[i]);return 0;
}这两道题固然有更直观的解法，但这里第4题直接调用c++内置函数；第5题入题较难，理清后明白即计算递归方程解得应是n+1的阶乘-1并且应用大数运算；python中有封包函数，这里用c理清逻辑.