周赛题解
Description
When Teddy was a child , he was always thinking about some simple math problems ,such as “What it’s 1 cup of water plus 1 pile of dough ..” , “100 yuan buy 100 pig” .etc..One day Teddy met a old man in his dream , in that dream the man whose name was“RuLai” gave Teddy a problem :
Given an N , can you calculate how many ways to write N as i * j + i + j (0 < i <= j) ?
Teddy found the answer when N was less than 10…but if N get bigger , he found it was too difficult for him to solve.
Well , you clever ACMers ,could you help little Teddy to solve this problem and let him have a good dream ?
Input
The first line contain a T(T <= 2000) . followed by T lines ,each line contain an integer N (0<=N <= 10 10).Output
For each case, output the number of ways in one line.Sample Input
2 1 3Sample Output
0 1 代码; 1 #include<stdio.h> 2 #include<math.h> 3 const int MAXN=100010; 4 int main(){ 5 __int64 N,ans; 6 int T; 7 scanf("%d",&T); 8 while(T--){ 9 ans=0; 10 scanf("%I64d",&N); 11 N++; 12 int flot=0; 13 for(int i=2;i<=sqrt(N);i++)if(N%i==0)ans++; 14 printf("%I64d\n",ans); 15 } 16 return 0; 17 } C - 最少拦截系统 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64uDescription
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
Input
输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)Output
对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.Sample Input
8 389 207 155 300 299 170 158 65Sample Output
2 代码： 1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<vector> 4 #include<algorithm> 5 using namespace std; 6 const int MAXN=30010; 7 vector<int>vec; 8 int main(){ 9 int N,x; 10 while(~scanf("%d",&N)){ 11 int top=0; 12 vec.clear(); 13 for(int i=0;i<N;i++){ 14 scanf("%d",&x); 15 if(lower_bound(vec.begin(),vec.end(),x)==vec.end())vec.push_back(x); 16 else *lower_bound(vec.begin(),vec.end(),x)=x; 17 } 18 printf("%d\n",vec.size()); 19 } 20 return 0; 21 } G - Ignatius and the Princess III Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64uDescription
"Well, it seems the first problem is too easy. I will let you know how foolish you are later." feng5166 says."The second problem is, given an positive integer N, we define an equation like this:
N=a[1]+a[2]+a[3]+...+a[m];
a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"
Input
The input contains several test cases. Each test case contains a positive integer N(1<=N<=120) which is mentioned above. The input is terminated by the end of file.Output
For each test case, you have to output a line contains an integer P which indicate the different equations you have found.Sample Input
4 10 20Sample Output
5 42 627 代码： 1 #include<stdio.h> 2 #include<string.h> 3 int main(){ 4 int N,a[150],b[150]; 5 while(~scanf("%d",&N)){ 6 for(int i=0;i<=N;i++)a[i]=1,b[i]=0; 7 for(int i=2;i<=N;i++){ 8 for(int j=0;j<=N;j++){ 9 b[j]+=a[j]; 10 for(int k=i;j+k<=N;k+=i){ 11 b[j+k]+=a[j]; 12 } 13 } 14 for(int j=0;j<=N;j++) 15 a[j]=b[j],b[j]=0; 16 } 17 printf("%d\n",a[N]); 18 } 19 return 0; 20 } H - Charm Bracelet Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64uDescription
Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).
Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di
Output
* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
Sample Input
4 6 1 4 2 6 3 12 2 7Sample Output
23代码： 1 #include<stdio.h> 2 #include<string.h> 3 const int MAXN=200000; 4 int bag[MAXN]; 5 #define MAX(x,y)(x>y?x:y) 6 struct Node{ 7 int w,v; 8 }; 9 Node dt[5000]; 10 int main(){ 11 int N,M; 12 while(~scanf("%d%d",&N,&M)){ 13 memset(bag,0,sizeof(bag)); 14 for(int i=0;i<N;i++)scanf("%d%d",&dt[i].w,&dt[i].v); 15 for(int i=0;i<N;i++){ 16 for(int j=M;j>=dt[i].w;j--){ 17 bag[j]=MAX(bag[j],bag[j-dt[i].w]+dt[i].v); 18 } 19 } 20 printf("%d\n",bag[M]); 21 } 22 return 0; 23 }
转载于:https://www.cnblogs.com/handsomecui/p/4841362.html
总结
- 上一篇： 还呗还信用卡审核容易通过吗？审核要多久？
- 下一篇： （原创）对某国的一次渗透