Jove's Blog

POJ 1573 Robot Motion C++版

发表于 2013-04-07 更新于 2022-03-12

题目的意思很容易从图中看出，题目要求机器人根据每个字母的方向行走，直到走出矩阵，或者进入循环，我的思路是利用map数组记录矩阵字母，用getv函数和step数组配合找出此时该怎么走，利用mapnum数组给经过的路标号，因为我初始化时所有的数都是0再遇到不是0的数则说明循环，而且利用这个路标号可以很方便的求出循环长度。

做题完成了后完美显示给出的两个例子，但是一直WA我就郁闷了，当时的代码其实只有一点区别，就是

1
2
3

t=0;

1
2
3

cout<<t<<" step(s) to exit"<<endl;

1
2
3

cout<<mapnum[y][x]<<" step(s) before a loop of "<<t-mapnum[y][x]<<" step(s)"<<endl;

代码如下：

/*Problem: 1573		User: awq123
**Memory: 260K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstring>
using namespace std;

int getv(char ch)
{
	switch(ch)
	{
	case 'N': return 0;
	case 'E': return 2;
	case 'S': return 4;
	case 'W': return 6;
	}
}

int main()
{
	int step[8]={0,-1,1,0,0,1,-1,0};
	char map[50][50];
	int mapnum[50][50];
	int x,y,n,i,j,r,c,t,temp;
	while(cin>>r>>c>>n&&r;!=0&&c;!=0&&n;!=0)
	{
		x=n;
		y=1;
		t=1;
		memset(map,0,sizeof(map));
		memset(mapnum,0,sizeof(mapnum));
		for(j=1;j<=r;j++)
			for(i=1;i<=c;i++)
				cin>>map[j][i];
		while(1)
		{
			if(x==0||x==c+1||y==0||y==r+1)
			{
				cout<<t-1<<" step(s) to exit"<<endl;
				break;
			}
			else if(mapnum[y][x]!=0)
			{
				cout<<mapnum[y][x]-1<<" step(s) before a loop of "<<t-mapnum[y][x]<<" step(s)"<<endl;
				break;
			}
			mapnum[y][x]=t++;
			temp=getv(map[y][x]);
			x+=step[temp];
			y+=step[temp+1];
		
		}

	}

}

POJ 2586 Y2K Accounting Bug C++版

发表于 2013-04-07 更新于 2022-03-12

题目链接：http://poj.org/problem?id=2586

这个题目要求我们分析公司盈亏，题目有点麻烦，盈利和亏损的钱是固定的，公司每5个月汇总一次，全年都是亏的，问一年最多盈利多少钱，s表示盈利，d表示亏损，5个月统计一次都亏空，那么有5种情况：

1、若SSSSD亏空，那么全年最优情况为SSSSDSSSSDSS
2、若SSSDD亏空，那么全年最优情况为SSSDDSSSDDSS
3、若SSDDD亏空，那么全年最优情况为SSDDDSSDDDSS
4、若SDDDD亏空，那么全年最优情况为SDDDDSDDDDSD
5、若DDDDD亏空，那么全年最优情况为DDDDDDDDDDDD

先令num为最坏测情况也就是第五种，然后一次分析，注意越前面的盈利越大，但是要满足在五个月内是亏损的，所以一次由上到下分析，简单if语句解决，如果有最大的盈利时替换num

代码如下：

/*Problem: 2586		User: awq123
**Memory: 248K		Time: 32MS
**Language: C++		Result: Accepted
*/
#include <iostream>
using namespace std;
#define max(a,b) (a>b)?a:b

int main()
{
	int s, d, num;
	while(cin>>s>>d)
	{
		num=-12*d;
		if(4*s<d)
			num=max(num,10*s-2*d);
		else if(3*s<2*d)
			num=max(num,8*s-4*d);
		else if(2*s<3*d)
			num=max(num,6*s-6*d);
		else if(1*s<4*d)
			num=max(num,3*s-9*d);
		if(num>0)
			cout<<num<<endl;
		else 
			cout<<"Deficit"<<endl;
	}
}

POJ 2109 Power of Cryptography C++版

发表于 2013-04-07 更新于 2022-03-12

题目链接：http://poj.org/problem?id=2109

本题要求，求出所给k和p的幂次n，虽然题目给出的范围很大，但是查阅了下double的精度

然而精度已经够高了，关于求幂次的函数pow在cmath里有具体用法查阅MSDN是这样说的

Calculates x raised to the power of y.
也就是说求x^y，这里利用的1/n实现求幂次，学习了

代码如下：

/*Problem: 2109		User: awq123
**Memory: 272K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include<iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main()
{
	double n,p;
	while(cin>>n>>p)
	{
		double k=pow(p,1/n);
		cout<<setprecision(0)<<k<<endl;
	}
}

POJ 1068 Parencodings C++版

发表于 2013-04-07 更新于 2022-03-12

题目链接：http://poj.org/problem?id=1068

解释下题意，对于一个括号组合，有两种括号代码，一种是P代码，一种是W代码，英语不好看了半天，还是要提升下，为CCNA准备，下面解释下两种代码：
P代码就是每一个反括号前面的正括号数
W代码就是每一个好括号与其对应的正括号之间的正括号数，算上他本身的那个

题目要求通过P代码，求W代码，典型的模拟题。

我的代码原理就是，先翻译每一个P代码前方的S字符串，用0表示（，用1表示），在通过这个前方的字符串，求该反括号的W代码

具体实现利用

temp=p[i]+i;

具体代码如下：

/*Problem: 1068		User: awq123
**Memory: 248K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
	int s[41],p[21],w[21];
	int i,j,t,n,temp,num,flag;
	cin>>t;
	while(t--)
	{
		cin>>n;
		memset(s,0,sizeof(s));
		memset(w,0,sizeof(w));
		for(i=0;i<n;i++)
		{
			cin>>p[i];
			temp=p[i]+i;
			s[temp]=1;
			num=1,flag=0;
			for(j=temp-1;j>=0;j--)
			{	
				if(s[j]==0&&flag;==0)
				{
					w[i]=num;
					break;
				}
				else if(s[j]==1)
				{
					flag++;
					num++;
				}
				else if(s[j]==0)
					flag--;
			}
		}
		for(i=0;i<n;i++)
			cout<<w[i]<<" ";
		cout<<endl;
	}
}

POJ 1328 Radar Installation c++版

发表于 2013-04-07 更新于 2022-03-12

题目链接：http://poj.org/problem?id=1328

题意要求我们根据所给的坐标的点，选出最少得雷达安装数，若超出范围则为-1。

参考解题报告，应该利用贪心算法，先排出每个点的雷达安装范围，也就是结构体中的left和right，由左到右摆放雷达，用std表示雷达的最远安装范围，在范围不够的时候加设一台，然后更新雷达覆盖范围，这样就能够求出雷达的最小值，其中的细节还需好好研究下，更新标准点的算法是重点！
代码如下：

#include <iostream>
#include <cmath>

typedef struct
{
	double left;
	double right;
}point;

point p[1001];
int n, d, sum;

void Solve()
{
	int i;
	sum = 1;
	point temp;
	double std;
	//对岛坐标进行排序
	for (int m=0;m<n;m++)
		for(int j=m+1;j<n;j++)
			if (p[m].left>p[j].left)
			{
				temp=p[m];
				p[m]=p[j];
				p[j]=temp;
			}
	std = p[0].right;
	//第一个点的右坐标作为起始参考
	for (i = 1; i < n; i++)
	{
		if (p[i].left > std)
		{
			std = p[i].right;
			//更新参考
			sum++;
		}
		else
		{
			//某点右坐标比标准值小，更新标准值为该点右坐标
			if (p[i].right < std)
			{
				std = p[i].right;
			}
		}
	}
}

int main()
{
	int x, y, i, t, fail;
	t = 1;
	while(1)
	{
		fail = 0;
		scanf("%d%d", &n;, &d;);
		if(n + d == 0) break;
		for (i = 0; i < n; i++)
		{
			scanf("%d%d", &x;, &y;);
			if (y > d)
				fail = 1;
			else
			{
				//求出这个点最远的雷达点
				p[i].left = x - sqrt((double)(d * d - y * y));
				p[i].right = x + sqrt((double)(d * d - y * y));
			}
		}
		if (fail)
		{
			printf("Case %d: -1n", t++);
		}
		else
		{
			Solve();
			printf("Case %d: %dn", t++, sum);
		}
	}
}

POJ 1163 The Triangle C++版

发表于 2013-04-07 更新于 2022-03-12

题目链接：http://poj.org/problem?id=1163

这个题目一个数字金字塔，求由上到下，经过的数字和最大为多少，其实本身看着简单的很，第一想法肯定是递归，必定这样的题目我以前做过，老师也是教的递归做法，由上到下，将问题分解为若干个小问题，这样利用一个求值型函数既可解决问题。代码如下：

#include <iostream>
using namespace std;

int n,num[100][100];

int DFS(int i, int j)
{
	if(i==n)
		return num[i][j];
	else if (DFS(i+1,j)>DFS(i+1,j+1))
		return DFS(i+1,j)+num[i][j];
	else
		return DFS(i+1,j+1)+num[i][j];
}
int main()
{
	cin>>n;
	for(int i=1; i<=n; i++)
		for(int k=1; k<=i; k++)
			cin>>num[i][k] ;
	cout<<DFS(1,1)<<endl;
}

/*Problem: 1163		User: awq123
**Memory: 292K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include <iostream>
using namespace std;

int main()
{
	int i,j,n,num[100][100];
	cin>>n;
	for(i=0; i<n; i++)
		for(j=0; j<=i; j++)
			cin>>num[i][j] ;
	for(i=n-2;i>=0;i--)
		for(j=0;j<=i;j++)
			num[i][j]+=(num[i+1][j]>num[i+1][j+1])?num[i+1][j]:num[i+1][j+1];
	cout<<num[0][0]<<endl;
}

POJ 1154 LETTERS C++版

发表于 2013-04-07 更新于 2022-03-12

题目链接：http://poj.org/problem?id=1154

这个题目就是要求你从左上角开始在不经过同样字母的前提下能走的最大路程。
查阅了别人的解题报告，可以穷举四条线路，但是我发现了一个不错的思路，代码是这样的：

int step[8] = {1,0,-1,0,0,1,0,-1}; 

for( int k=0; k<8; k+=2)


```先开始错了一只不知道什么问题，当时num数组定义的num[26]后来发现其实A对应的是num[1]不是num[0]导致Z无法识别，后来改了通过
代码如下：

```cpp
/*Problem: 1154		User: awq123
**Memory: 268K		Time: 47MS
**Language: C++		Result: Accepted
*/
#include <iostream>
using namespace std;

int x,y,temp,tempmax,str[100][100],num[27];
int step[8] = {1,0,-1,0,0,1,0,-1}; 

void DFS(int i, int j)
{
	for( int k=0; k<8; k+=2)
	{
		int a = i+step[k];  
		int b = j+step[k+1];  
		if(a>=1&&a;<=y&&b;>=1&&b;<=x&&!num[str[a][b]] )  
		{  
			num[str[a][b]] = 1;  
			temp++;  
			DFS(a,b);  
			if( temp > tempmax )  
				tempmax = temp;  
			temp--;  
			num[str[a][b]] = 0;  
		}  
	}
}
int main()
{
	char s[100];

	while( cin >> y >> x )
	{
		temp=1,tempmax=1;
		memset(num,0,sizeof(num)); 
		getchar(); 
		/*这条getchar我还是不理解但是不加就会造成数据少输入一行， */
		for(int i=1; i<=y; i++)
		{
			gets(s);
			for(int k=1; k<=x; k++)
				str[i][k] = s[k-1] -'A' + 1;
		}
		num[str[1][1]] = 1;
		DFS(1,1);
		cout<<tempmax<<endl;
	}

}

和小Z聊了下，虽然不是无故去找她聊天，但是顺便看看她的小计划怎么样了，她好像知道我的目的，第一句话就说出来了，没意思，我这么容易被看透，后来真的发现，连百度也能看透我，想想百度自己的名字还是高中的时候的事，当时无聊，后来才知道自己名字稀有，百度的几个好多就是我，真的觉得我好有意思，这个说出去，“去百度我的名字吧”哈哈，本来仅仅是一个聊天而看到他想起了过去的我，虽然聊了很多但是，感觉还是看不透她，小K啊难道我还要再学学吗。聊天间不经意回想很多，整个高中的生活，和小K的开始，尽管这个开始不是那么光明磊落，我知道小K不会来这个网站，也不怕什么，她担心的事我自然知道，一个不完美的开始配上的就是一个不完美的结局，我不是一个好孩子，也不算很差吧，如果有机会，我还会追小K的这点我不会忘记。

但是我不是个简单的人，每一个自认为看透我的人，后来都失望了，不知道是好还是坏，简单就是美，我一直信奉的一句话。

刚才还顺便开导了下小Q，看她纠结的我都想哭啊，爱情这个东西我能看清但说不清，我还就真不理解了，她见个男朋友干嘛那么害羞，躲躲藏藏的，我当时也害羞啊，多亏了有个主动的女孩，我擦，谈话间对她的MR.Right有了点兴趣，她一再强调这是她托付终身的人，想想当初我也这么想过后来还是换成泡沫了，我的坚持也只能化作学习的力量了吧！大学不谈朋友，我的承诺，也不知道能不能保持，但是现在应该没有这个心境接受另一个吧！

一个心情贴，不应该在这里出现，或者该加个密码，算了反正也没人看这网站，只当记录生活了，原名被我改了！

7-9 随笔

发表于 2013-04-07 更新于 2022-03-12

妈妈总烦着我去找事，以前不想去是嫌麻烦，但真正找起来的时候，才发现真的不容易找啊，要么就说不要短工，要么就说没学历，好吧现在知道现实生活的残酷了，不过说实话我不觉我很差啊，至少我有自己的爱好，本来放假就有学习计划的，既然你不给我机会做事，那我就去学习了。

上学期也是玩的多了点，搞得我居然挂科了，那天逸凡q我说我c语言考了92，他骂我考试前一天晚上还说不会，怕过不了，我本来心里就没底嘛，至少我认真学的东西觉得没差过，下学期别的课也要加油了，还要该死的重修，我了个去啊。

还有答应彪的事一定要办到，我也觉得图书馆是个不错的环境，想大学期间把CCNA考了，但是仅仅是计划，还要看具体情况，我真是没办法做到像彪一样说我明年一定要考了，想想很有意思，我妈也是这个习惯，把自己逼到绝路上，慢慢来吧，我向往的自由学习，呵

一个暑假完了我就大二了，还要学更多我不懂的东西，自己的小站慢慢也定性了还是选择了这个标准blog形式，那样的小窝形式还是不适合我，以后等这个小站有名了，有人来看了，在换个精致点的主题，必定简洁才是美。

POJ 1047 Round and Round We Go C++版

发表于 2013-04-07 更新于 2022-03-12

题目链接：http://poj.org/problem?id=1047

这题不算个简单的题，主要在于算法，但是还是多谢别人总结的：
对于数N，若N为循环的则有N*(length(N)+1)=99….99， (length(N)个9)，length(N)为N的位数，含前导0。
代码调用一个judge函数判断是否成功，水题。
代码如下：

/*Problem: 1047		User: awq123
**Memory: 212K		Time: 0MS
**Language: C++		Result: Accepted
*/
#include<iostream>
#include<string>
using namespace std;
int judge(string str)
{
	int n=str.length()+1;
	int i,up=0,temp=0;
	for(i=n-2;i>=0;i--)
	{
		temp=(int)(str[i]-'0');
		if((temp*n+up)%10!=9) return 0;
		up=(temp*n+up)/10;
	}
	return 1;
}
int main()
{
	string str;
	while(cin>>str)
	{
		if(judge(str))
		{
			cout<<str<<" is cyclic"<<endl; 
		}
		else
		{
			cout<<str<<" is not cyclic"<<endl;
		}
	}
	return 0;
}