杭电OJ

发表于 | 分类于

#1001 Sum Problem

1
In this problem, your task is to calculate SUM(n) = 1 + 2 + 3 + ... + n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<stdio.h>
void main()
{
	int i,n,sum;
	while(scanf("%d",&n)!=EOF)
	{
		sum=0;
		for(i=1;i<=n;i++)
		{
			sum=sum+i;
		} 
		printf("%d\n\n",sum);
		sum=0;
	}
}

#1002 A + B Problem II

1
大数相加 cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<cstdio>
#include<cstring>
#include<stack>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    for(int x=1;x<=n;x++)
    {
        stack<int> s;
       char a[1000],b[1000];
       int sum=0;
       scanf("%s%s",a,b);
        int stra=strlen(a);
       int strb=strlen(b);
       int i,j;
       for(i=stra-1,j=strb-1;i>=0&&j>=0;i--,j--)
       {
            sum+=a[i]-'0'+b[j]-'0';
            s.push(sum%10);    //由于是由后面低位开始处理的，输出时要由高位到低位输出，故用栈处理
            sum/=10;    //记录上一位进位情况
       }
       if(i>=0)   //第一个数位数较多
       {
            for(;i>=0;i--)
            {
                sum+=a[i]-'0';
                s.push(sum%10);
                sum/=10;
            }
       }
       else   //第二个数位数较多
       {
            for(;j>=0;j--)
            {
                sum+=b[j]-'0';
                s.push(sum%10);
                sum/=10;
            }
       }
       if(x!=1)
        printf("\n");
       printf("Case %d:\n",x);
       printf("%s + %s = ",a,b);
       while(!s.empty())
       {
           printf("%d",s.top());
           s.pop();
       }
       printf("\n");
    }
    return 0;
}

#1003 Max Sum

1
最大连续子段和 cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
int main()
{
    int T,N,num,startP,endP;
    cin>>T;
    for(int k=0;k<T;k++)
    {
            cin>>N;
            int max=-1001,sum=0,temp=1;
            for(int i=0;i<N;i++)
            {
                            cin>>num;
                            sum+=num;
                            if(sum>max)
                            {
                                      max=sum;
                                      startP=temp;
                                      endP=i+1;
                            }
                            if(sum<0)
                            {
                                    sum=0;
                                    temp=i+2;
                            }
            }
            cout<<"Case "<<k+1<<":"<<endl<<max<<" "<<startP<<" "<<endP<<endl;
            if(k!=T-1) cout<<endl;
    
    }
}

#1004 Let the Balloon Rise

1
找出出现最多的颜色 cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <map>
#include <string>
using namespace std; 

int main(int argc, char *argv[])
{
    int  nCount=0; 
    string strTmp;
    while(cin>>nCount&&nCount!=0)
    {
        map<string,int> mapColor;//用map容器非常方便
        for(int i=0;i<nCount;++i)
        {
            cin>>strTmp;
            mapColor[strTmp]++;
        }
       map<string, int>::iterator iter;
       int max = -1;
       for(iter = mapColor.begin(); iter != mapColor.end(); iter++)
       {//第一次遍历标记最大次数所在位置
           if(iter->second>max)
           {
               max = iter->second;
           }
       }
       for(iter = mapColor.begin(); iter != mapColor.end(); iter++)
       {//第二次遍历找到标记的位置
           if(iter->second==max)
           {
               cout<<iter->first<<endl;
           }
       }  
    }
    return 0;
}

#1005 Number Sequence

1
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<stdio.h> 
int main() 
{ 
    int a,b,i; 
    long n,f[201]; 
    while (scanf("%d %d %ld",&a,&b,&n)!=EOF) 
    { 
        if(a==0 && b==0 && n==0) 
             break; 
        f[1]=1;
        f[2]=1; 
        if(n>=3) 
        { 
             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=i-2;
             n=n%i; 
             if(n==0) 
                  n=i; 
             printf("%d\n",f[n]); 
        } 
        else 
             printf("1\n");       
    } 
    return 0;
}

#1007Quoit Design

1
求任两点间距离最小的两点间的距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include<cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int N = 100005;
const double MAX = 10e100;
const double eps = 0.00001;
typedef struct TYPE
{
    double x, y;
    int index;
} Point;
Point a[N], b[N], c[N];
double closest(Point *, Point *, Point *, int, int);
double dis(Point, Point);
int cmp_x(const void *, const void*);
int cmp_y(const void *, const void*);
int merge(Point *, Point *, int, int, int);
inline double min(double, double);

int main()
{
    int n, i;
    double d;
    scanf("%d", &n);
    while (n)
    {
        for (i = 0; i < n; i++)
            scanf("%lf%lf", &(a[i].x), &(a[i].y));
        qsort(a, n, sizeof(a[0]), cmp_x);
        for (i = 0; i < n; i++)
            a[i].index = i;
        memcpy(b, a, n *sizeof(a[0]));
        qsort(b, n, sizeof(b[0]), cmp_y);
        d = closest(a, b, c, 0, n - 1);
        printf("%.2lf\n", d/2);
        scanf("%d", &n);
    }
    return 0;
}

double closest(Point a[], Point b[], Point c[], int p, int q)
{
    if (q - p == 1)
        return dis(a[p], a[q]);
    if (q - p == 2)
    {
        double x1 = dis(a[p], a[q]);
        double x2 = dis(a[p + 1], a[q]);
        double x3 = dis(a[p], a[p + 1]);
        if (x1 < x2 && x1 < x3)
            return x1;
        else if (x2 < x3)
            return x2;
        else
            return x3;
    }
    int m = (p + q) / 2;
    int i, j, k;
    double d1, d2;
    for (i = p, j = p, k = m + 1; i <= q; i++)
        if (b[i].index <= m)
            c[j++] = b[i];
    //数组c左半部保存划分后左部的点, 且对y是有序的.
    else
        c[k++] = b[i];
    d1 = closest(a, c, b, p, m);
    d2 = closest(a, c, b, m + 1, q);
    double dm = min(d1, d2);
    merge(b, c, p, m, q); //数组c左右部分分别是对y坐标有序的, 将其合并到b.
    for (i = p, k = p; i <= q; i++)
        if (fabs(b[i].x - b[m].x) < dm)
            c[k++] = b[i];
    //找出离划分基准左右不超过dm的部分, 且仍然对y坐标有序.
    for (i = p; i < k; i++)
    for (j = i + 1; j < k && c[j].y - c[i].y < dm; j++)
    {
        double temp = dis(c[i], c[j]);
        if (temp < dm)
            dm = temp;
    }
    return dm;
}

double dis(Point p, Point q)
{
    double x1 = p.x - q.x, y1 = p.y - q.y;
    return sqrt(x1 *x1 + y1 * y1);
}

int merge(Point p[], Point q[], int s, int m, int t)
{
    int i, j, k;
    for (i = s, j = m + 1, k = s; i <= m && j <= t;)
    {
        if (q[i].y > q[j].y)
            p[k++] = q[j], j++;
        else
            p[k++] = q[i], i++;
    }
    while (i <= m)
        p[k++] = q[i++];
    while (j <= t)
        p[k++] = q[j++];
    memcpy(q + s, p + s, (t - s + 1) *sizeof(p[0]));
    return 0;
}

int cmp_x(const void *p, const void *q)
{
    double temp = ((Point*)p)->x - ((Point*)q)->x;
    if (temp > 0)
        return 1;
    else if (fabs(temp) < eps)
        return 0;
    else
        return  - 1;
}

int cmp_y(const void *p, const void *q)
{
    double temp = ((Point*)p)->y - ((Point*)q)->y;
    if (temp > 0)
        return 1;
    else if (fabs(temp) < eps)
        return 0;
    else
        return  - 1;
}

inline double min(double p, double q)
{
    return (p > q) ? (q): (p);
}

#1008 电梯问题

1
2
花费6秒移动电梯一层,4秒移动到下一层。电梯将在每一站停留5秒。
3 2 3 1 === 41s

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
int main()
{ int a[100],i,j,k,n; 
  while(scanf("%d",&i)!=EOF && i) 
   {   n=0;a[0]=0; 
        for(j=1;j<=i;j++)   
        scanf("%d",&a[j]);  
           for(j=1;j<=i;j++)  
              {    if(a[j]>a[j-1])   
                 {     n+=(a[j]-a[j-1])*6;   
                   n+=5;    }  
                     else    {     n+=(a[j-1]-a[j])*4;  
                    n+=5;
    }  
     }  
     printf("%d\n",n);   }
 return 0;
 }

#

1
2
老鼠有很多的猫粮   要和看仓库的猫换java豆吃    每个仓库的java豆有不同的储量和价格
老鼠想你帮助他用自己猫粮换最多的java豆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct node{
    double gs;
    double jg;
    double dj;
}mat;
mat a[1002];
int cmp(mat a,mat b)
{
    return a.dj<b.dj;    
}
int main()
{
    int n,i;
    double m,count;
    while(scanf("%lf%d",&m,&n))
    {
        if(m==-1&&n==-1)break;
        count=0;
        for(i=0;i<n;i++)
        {
            scanf("%lf%lf",&a[i].gs,&a[i].jg);
            a[i].dj=a[i].gs/a[i].jg;
        }
        sort(a,a+n,cmp);
        i=n-1;
        while(m!=0.0)
        {
            if(a[i].jg>=m)
            {
                count+=a[i].dj*m;
                m=0;
            }
            else
            {
                count+=a[i].gs;
                m-=a[i].jg;
                i--;
            }
        }
        printf("%.3lf\n",count);
    }
    return 0;
}

#1024 dp 最大M籽椴和

1
2
3
4
5
6
7
8
9
10
11
12
问题： 
给定由n个整数(可能为负整数)组成的序列e1,e2,…,en,以及一个正整数m，要求确定序列的m个不相交子段，使这m个子段的总和达到最大。 
分析： 
设b(i，j)表示数组e的前j项中i个子段和的最大值，且第i个子段含e[j](1￡ i ￡m，i￡ j ￡n)。以下称b(i, j)为“最后一个元素属于第i子段的j元素i子段问题”。则n个元素中求i个子段的最优值显然为： 
best(i, n) = Max{ b(i, j) } (i <= j <= n) 
计算b(i，j)的最优子结构为： 
b(i，j) = Max{ b(i, j-1) + e[i], Max{ b(i-1, t) } + e[i] } (i <= t < j) 
这样，可以得到时间复杂度为O(m * n ^ 2)和空间复杂度为O(m * n)的MS相当漂亮而且容易理解的DP算法。当n不大的时候，这个算法足够优秀，然而，当n很大的时候，这个算法显然是不能让人满意的！ 
优化： 
观察上面的最优子结构，我们发现b(i, j)的计算只和b(i, j-1)和b(i-1, t)有关，也就是说只和最后一个元素属于第i子段的j-1元素i子段问题和前j-1个元素的最大i-1子段问题有关（可以分别理解为将e[j]作为最后一个元素而并入第i子段和将e[j]另起一段作为第i分段）。这样，我们只要分别用curr_best和prev_best两个一维数组保存当前阶段和前一阶段的状态值b(i, *)和b(i-1, *) 就行了，内存使用也就可以降为O(2 * n)。 
再来看看时间。分析发现，原算法低效主要是在求max_sum(i, t) = Max{b(i, t)} (i <= t < j)的时候用了O(n)的时间。其实，在求b(i, j)的过程中，我们完全可以同时计算出max_sum(i, t)，因为max_sum(i,j) = Max{b(i,j), max_sum(i,j-1)}，这个只花费O(1)的时间。而max_sum(i,t)不就是i+1阶段中要用到的吗？关键问题已经解决了！那如何保存max_sum呢？再开一个数组？我们可以在prev_best数组中保存！这个数组的任务相当艰巨，它既存放着i-1阶段的max_sum数值，又存放这供i+1阶段使用的i阶段的max_sum值。MS这有点矛盾？其实这是可行的。注意到我们在计算b(i,j)时只使用了prev_best[j-1]，使用完了再也没有用了，这样空闲着岂不浪费？其实我们可以将max_sum(i, j-1)存放到prev_best[j-1]里面——这个主意相当不错，它让所有问题迎刃而解。 
现在，我们得到了一个时间复杂度为O(m * n)、空间复杂度为(2 * n)的算法。这个算法相当优秀，以至于m为小常数，n = 1000000时，结果也是瞬间就出来了（此时算法的时间复杂度可以认为是O(n)的）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<stdio.h> 
#include<stdlib.h> 
#define MIN_SUM 0x80000000 

int max_sum(int e[], int n, int m) 
{ 
	int *curr_best; 
	int *prev_best; 
	int max_sum, i, j; 
	
	curr_best = (int*)malloc(sizeof(int) * (n + 1)); 
	prev_best = (int*)calloc(n + 1, sizeof(int)); 
	
	*curr_best = 0; 
	e--; 
	
	for(i = 1; i <= m; ++i) 
	{ 
		max_sum = MIN_SUM; 
		for(j = i; j <= n; ++j) 
		{ 
			if(curr_best[j - 1] < prev_best[j - 1]) 
				curr_best[j] = prev_best[j - 1] + e[j]; 
			else 
				curr_best[j] = curr_best[j - 1] + e[j]; 
			prev_best[j - 1] = max_sum; 
			if(max_sum < curr_best[j]) 
				max_sum = curr_best[j]; 
		} 
		prev_best[j - 1] = max_sum; 
	} 
	
	free(prev_best); 
	free(curr_best); 
	
	return max_sum; 
} 

int main() 
{ 
	int n, m, i, *data; 
	while(scanf("%d%d", &m, &n) == 2 && n > 0 && m > 0) 
	{ 
		data = (int*)malloc(sizeof(int) * n); 
		for(i = 0; i < n; ++i) 
			scanf("%d", &data[i]); 
		printf("%d\n", max_sum(data, n, m)); 
		free(data); 
	} 
	return 0; 
}

#

1
```

1
#
1
```