UVA 10038: Jolly Jumpers

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=12&problem=979&mosmsg=Submission+received+with+ID+8683259

题目大意:

      n长度数列中相邻的数之间的差的绝对值在1~n-1范围内且不一样,这样的数列叫 jolly jumper。

解题思路:

      用一个数组标记各个绝对值是否出现过,要是出现过就不是 jolly jumper,超出1~n-1的范围也不是 jolly jumper 。题目没看清楚错了一次。此题用到基础的hash算法思维。

解题代码:

#include<iostream>
using namespace std;
bool s[3001];
int a[3001];
int main(){
	int n;
	while(cin>>n){
		for(int i=1;i<=n;i++){
			cin>>a[i];			
			s[i]=true;
		}
		bool flag=true;
		for(int i=2;i<=n;i++){
				int x=(a[i]-a[i-1]>0)?(a[i]-a[i-1]):(a[i-1]-a[i]);
				if(x==0||x>n-1){
					flag=false;
					break;
				}
				else{
					if(s[x])
						s[x]=false;
					else{
						flag=false;
						break;
					}
				}
		}
		if(flag)
			cout<<"Jolly"<<endl;
		else
			cout<<"Not jolly"<<endl;
	}
}

扩展知识:http://blog.csdn.net/hqd_acm/archive/2010/09/23/5901955.aspx

UVA 136:Ugly Numbers

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=72

题目大意:

      素数因子只有2、3、5的数叫做丑数,求出第1500个丑数。

解题思路:

      因为指定要第1500个,我们先在我们机子上用暴力求出来然后直接输出,这种方法是比较投机取巧的,暴力花的时间非常久,要是提交暴力代码就TLE无疑啦。后来想到用优先队列(STL的priority_queue实现),从1开始放对队列,每次把最小的取出来然后乘以那三个数后放入队列,取到1500个数就结束。但是这样会有个问题,会有重复数据,后来保留上次取的数据,取出数据和上次取的数据判断一下,要是相同不做任何操作再取出下一个数据,要是不相同就保留这次的数据再取下一次。第1500次不相同的数据输出结果。

解题代码:

#include<iostream>
#include<queue>
using namespace std;
#define N 1500
typedef long long ll;
int s[3]={2,3,5};
priority_queue<ll,vector<ll>,greater<ll> > pq;
int main(){
	ll t,p=0,n=0;
	pq.push(1);
	while(n<N){
		t=pq.top();
		pq.pop();
		if(p!=t){
			p=t;
			n++;
			for(int i=0;i<3;i++){
				pq.push(t*s[i]);
			}
		}
	}
	cout<<"The 1500'th ugly number is "<<t<<'.'<<endl;
}

扩展知识:http://www.cppblog.com/CodeStream/archive/2011/03/25/142700.html

 

UVA 458:The Decoder

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=399

题目大意:

      这道题是最最基础的密码学知识,就是明文的每个字母加上一个数变成密文,现在给我们密文,转化为原文。

解题思路:

      找到密钥然后每个字母减去密钥。

解题代码:

#include<iostream>
#include<string>
using namespace std;
int main(){
	int t='1'-'*';
	string s;
	while(getline(cin,s)){
		int len=s.length();
		for(int i=0;i<len;i++)
			s[i]-=t;
		cout<<s<<endl;
	}
	return 0;
}

扩展知识:http://baike.baidu.com/view/25311.htm

UVA 272: TEX Quotes

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=4&page=show_problem&problem=208

题目大意:

      TEX是计算机界圣人Donald Knuth的作品,写论文的必备工具!现在题目要你把一对双引号("")的第一个变成(``)第二个变成('').

解题思路:

      看下题目想得太简单,遇到第一个(")就输出(``)第二个就输出(''),结果错啦,数据不是全给(")而是和(``和'')混用的吧。弄一个标记,遇到一次这三种符号之一就把标记取反,标记为1输出“``”,为0输出“''”,标记要为整篇文章的,不能是一行的,因为每行是相连的。

解题代码:

#include<iostream>
#include<string>
using namespace std;
int main(){
	string s;
	int flag=1;
	while(getline(cin,s)){
		int len=s.length();
		for(int i=0;i<len;i++)
			if(s[i]=='"'){
				if(flag)
					cout<<"``",flag^=1;
				else
					cout<<"''",flag^=1;
			}
			else{
				if(i+1<len&&(s[i]=='`'&&s[i+1]=='`')||(s[i]=='\''&&s[i+1]=='\''))
						cout<<s[i]<<s[i+1],i++,flag^=1;
				else
				cout<<s[i];
			}
		cout<<endl;
	}
}

扩展知识:http://zzg34b.w3.c361.com/index.htm

UVA 10055: Hashmat the brave warrior

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=996

题目大意:

      输入两个军队数量,输出之间的差。

解题思路:

      水的不能再水啊~我居然错了4次~没有注意数据范围是2^32,用int和unsinged都不行阿~只能用long long。

看题要细心阿~~

解题代码:

#include<iostream>
using namespace std;
int main(){
    long long a,b;
    while(cin>>a>>b){
        cout<<(a>b?a-b:b-a)<<endl;
    }
    return 0;
}

扩展知识:http://www.cnblogs.com/card323/archive/2009/06/18/1505794.html

UVA 10071: Back to High School Physics

题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=12&problem=1012&mosmsg=Submission+received+with+ID+8679275

题目大意:

      这是一道高中物理题,一个物体初速度为0,在t时间的速度为v,求在2t时刻这个物理走过的路程是多少。

解题思路:

      因为加速度a=v/t,路程s=(a*t^2)/2,所以2t时刻的路程为s=2*v*t.

解题代码:

#include<iostream>
using namespace std;
int main(){
    int v,t;
    while(cin>>v>>t){
        cout<<2*v*t<<endl;
    }
    return 0;
}

扩展知识:http://en.wikipedia.org/wiki/Acceleration