acm期末考试之我解

Problem A
感觉哪里做到过。。

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
int main()
{
    int n;
    scanf("%d",&n);
    while(n!=0)
    {
        int max=INT_MIN,min=INT_MAX;
        int i;
        for(i=1;i<=n;i++)
        {
            int a;
            scanf("%d",&a);
            if(a>max)
                max=a;
            if(a<min)
                min=a;
        }
        printf("%d\n",2*(max-min));
        scanf("%d",&n);
    }
return 0;
}

Problem B
简单nim游戏

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,i,sum=0;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            int a;
            scanf("%d",&a);
            sum=sum^a;
        }
        if(sum==0)
            printf("JiJi Brother\n");
        else
            printf("WeiWei Brother\n");
    }
return 0;
}

Problem C
开始result[n]<1 || result[n]>500000的||写成了&&,检查很久,WA多次。。

#include<stdio.h>
#include<stdlib.h>
__int64 result[500005];
int main()
{
    int t,i,j;
    result[1]=0;
    for(i=1;i<=(500000/2);i++)
    {
        for(j=i*2;j<=500000;j+=i)
        {
            result[j]+=i;
        }
    }
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        __int64 b=result[n];
        if(result[n]==n||(result[n]<1 || result[n]>500000))
            printf("注定单身\n");
        else if(n==result[b])
        {
            printf("缘分已定\n");
        }
        else
            printf("缘分未到\n");
    }
return 0;
}

Problem D
五题之中最后做出来的,推了好久,开始用一个数组,最后改变策略,对每个量进行递推,总算推出来了,不过感觉做复杂了。。

#include<stdio.h>
#include<stdlib.h>
int main()
{
    __int64 a[50],b[50],r[50];
    a[1]=1,b[1]=0,r[1]=1;
    a[2]=0,b[2]=0,r[2]=1;
    a[3]=4,b[3]=0,r[3]=5;
    a[4]=4,b[4]=0,r[4]=9;
    int i;
    for(i=5;i<=50;i++)
    {
        b[i]=a[i-4];
        a[i]=4*(r[i-1]-b[i-1]-a[i-1]);
        r[i]=r[i-1]-b[i-1]+a[i];
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        printf("%I64d\n",r[n]);
    }
return 0;
}

Problem E
简单数学

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int t;
    int a[14]={366,365,365,365,366,365,365,365,366,365,365,365,366,365};
    int b[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
    scanf("%d",&t);
    while(t--)
    {
        int i,y,m,d;
        scanf("%d/%d/%d",&y,&m,&d);
        int sum=0;
        for(i=0;i<=y-2000-1;i++)
        {
            sum+=a[i];
        
        }
        if(m==1)
            sum+=d;
        else if(m==2)
            sum+=b[1]+d;
        else if(m>=3)
        {
            int j;
            for(j=1;j<=m-1;j++)
                sum+=b[j];
            if(a[y-2000]==366)
                sum+=1;
            sum+=d;
        }
        int result=sum%5;
        if(result>=1 && result<=3)
            printf("Fishing\n");
        else
            printf("Resting\n");
        

    
    }
return 0;
}

hdoj1250——Hat’s Fibonacci

传送门:题目链接
这题记一下,很明显,斐波那契+大数,数值最长达到2005位,果断套大数模板,开了个10000左右的大数数组,结果MLE,经过尝试,减小到7100,依然MLE,无奈。。
于是只好想其他办法,发现n的值其实并不大,索性开个只有5个元素的大数数组,用f[0]保存结果,循环滚动,这样MLE肯定是解决了,但是如果n较大的话就可能TLE,提交了一下,还好,这回AC了~~。下面贴出代码

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 9999
#define MAXSIZE 2100
#define DLEN 4
using namespace std;
class BigNum;
ostream& operator<<(ostream&,  BigNum&);
class BigNum
{
public:
	int a[MAXSIZE];
	int len;
public:
	BigNum(){len = 1;memset(a,0,sizeof(a));}
	BigNum(const int);
	BigNum(const BigNum &);  
	BigNum &operator=(const BigNum &);
	friend ostream& operator<<(ostream&,  BigNum&);
	BigNum operator+(const BigNum &) const;
};
ostream& operator<<(ostream& out,  BigNum& b)
{
	int i;  
	cout << b.a[b.len - 1];
	for(i = b.len - 2 ; i >= 0 ; i--)
	{
		cout.width(DLEN);
		cout.fill('0');
		cout << b.a[i];
	}
	return out;
}
BigNum::BigNum(const int b)
{
	int c,d = b;  
	len = 0;
	memset(a,0,sizeof(a));
	while(d > MAXN)
	{
		c = d - (d / (MAXN + 1)) * (MAXN + 1);
		d = d / (MAXN + 1);  a[len++] = c;
	}
	a[len++] = d;
}
BigNum::BigNum(const BigNum & T) : len(T.len)
{
	int i;
	memset(a,0,sizeof(a));
	for(i = 0 ; i < len ; i++)  a[i] = T.a[i];
}
BigNum & BigNum::operator=(const BigNum & n)
{
	len = n.len;
	memset(a,0,sizeof(a));
	for(int i = 0 ; i < len ; i++)
		a[i] = n.a[i];
	return *this;
}
BigNum BigNum::operator+(const BigNum & T) const
{
	BigNum t(*this);
	int i,big;  
	big = T.len > len ? T.len : len;
	for(i = 0 ; i < big ; i++)
	{
		t.a[i] +=T.a[i];
		if(t.a[i] > MAXN)
		{
			t.a[i + 1]++;
			t.a[i] -=MAXN+1;
		}
	}
	if(t.a[big] != 0) t.len = big + 1;
	else t.len = big;  
	return t;
}
int main()
{
	int n,i;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==1||n==2||n==3||n==4)
		{
			printf("1\n");
			continue;
		}
		BigNum f[5];
		f[1]=f[2]=f[3]=f[4]=1;
		f[0]=4;
		for(i=5;i<=n;i++)
		{
			f[0]=f[1]+f[2]+f[3]+f[4];
			f[1]=f[2];
			f[2]=f[3];
			f[3]=f[4];
			f[4]=f[0];
		}
		cout<<f[0]<<endl;
	}
	//system("pause");
	return 0;
}

写个stl程序

明天就要acm课考试了,可是一学期几乎没去上过课(感觉有点对不住lcy老师啊。、、),肿么办。。没办法,只能临时抱抱佛脚,于是拿出了尘封已久的《算法竞赛入门经典》,话说当初刚接触acm的时候真心挺佩服刘汝佳的,大神啊,大二是就是世界第四了。可一年多过去后发现自己对这个没多少兴趣了。。

闲话不多说,切入正题,翻书的时候看到这样一道小题:

移动小球

你有一些小球,从左到右依次编号为1,2,3,……,n。指令A x y表示把小球x移动到小球y左边,B x y表示把小球x移动到小球y右边。指令保证合法(x不等于y)。输入小球个数n和指令条数m及m条指令,从左至右输出最后的序列。n可高达500000,m可高达100000.

样例输入:

6 2

A 1 4

B 3 5

样例输出:

2 1 4 5 3 6

 

这道题时间规模很大,因此书上采用数组模拟链表的方式实现。详见书。。

这里给出我的一个解法,用stl的list容器。

代码如下:

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
int main()
{
int n,m,x,y;
char type[3];
list<int> ball;
list<int>::iterator it;
while(scanf(“%d%d”,&n,&m)!=EOF)
{
for(int i=1;i<=n+1;i++)
ball.push_back(i);
for(int j=1;j<=m;j++)
{
scanf(“%s%d%d”,type,&x,&y);
if(type[0]==’A')
{
it=find(ball.begin(),ball.end(),y);
ball.remove(x);
ball.insert(it,x);
}
else
{
it=find(ball.begin(),ball.end(),y);
ball.remove(x);
ball.insert(++it,x);
}
}
ball.pop_back();
for(it=ball.begin();it!=ball.end();it++)
{
cout<<*it<<’ ‘;
}
cout<<endl;
ball.clear();
}
return 0;
}

这里有一点值得注意,因为list的迭代器不能实现+1等随机遍历(list实质是链表),所以只好用++操作替代,因而可能造成迭代器越界(find()返回ball.end()时)。所以这里我多创建一个元素,在输出前删除。由于使用while(scanf()!=EOF),所以每组数据结束后都要清空ball。