Jove's Blog

POJ 1080 Human Gene Functions C++版

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

不错的DP题，做了好多DP了，越做越觉得DP思路真的很开阔，以后还要加强，这题我参考的别人的解题报告，加以自己的想法。

解释下题意，两个字符串，通过增加空格来调整字符串，使得对应字符得到的数相加最大，比如题目中的
AGTGATG
-GTTA-G
第二列解释通过增加两个空格才和第一列对应的，一一对应关系参照

1080

可得到最大的得分(-3)+5+5+(-2)+5+(-1) +5=14

我们可以看到，相同的字符是得分最大的，那么我们可以想到LCS问题，这题也算是LCS的一种变形。
解释下DP思路，dp[i][j]记录第一列i个字符和第2列j个字符开始的最大得分，这个得分也就是前面可能的三种情况的最大值！我们来举个例子：
比如i和j分别指字符G，C
那么有三种情况：
GXXX
CXXX
那么dp[i][j]=dp[i-1][j-1]+getmatch(str1[i-1],str2[j-1])
-GXX
CXXX
那么dp[i][j]=dp[i][j-1]+getmatch(str2[j-1],’-‘)
GXXX
-CXX
那么dp[i][j]=dp[i-1][j]+getmatch(str1[i-1],’-‘)
这样由dp[0][0]开始动态规划下去就是了，其中还要注意i，j分别等于0的情况，一面i-1，j-1不存在。

代码种getnum函数将字符转换数字getmatch将组合转换成得分

具体见代码：

/***************************************
Problem: 1080		User: awq123
Memory: 292K		Time: 16MS
Language: C++		Result: Accepted
***************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int mymax(int a,int b,int c)
{
	int temp=a>b?a:b;
	return temp>c?temp:c;
}

int match[5][5]=
{
	{5,-1,-2,-1,-3},
	{-1,5,-3,-2,-4},
	{-2,-3,5,-2,-2},
	{-1,-2,-3,5,-1},
	{-3,-4,-2,-1,0}
};

int getnum(char ch)
{
	switch (ch)
	{
		case 'A':return 0;
		case 'C':return 1;
		case 'G':return 2;
		case 'T':return 3;
		case '-':return 4;
		default:return 5;
	}
}

int getmatch(char ch1,char ch2)
{
	return match[getnum(ch1)][getnum(ch2)];
}

int main()
{
	int t,len1,len2,dp[105][105],i,j;
	char str1[105],str2[105];
	cin>>t;
	while(t--)
	{
		cin>>len1>>str1>>len2>>str2;
		dp[0][0]=0;
		for(i=1;i<=len1;i++)
			dp[i][0]=dp[i-1][0]+getmatch(str1[i-1],'-');
		for(j=1;j<=len2;j++)
			dp[0][j]=dp[0][j-1]+getmatch(str2[j-1],'-');
		for(i=1;i<=len1;i++)
			for(j=1;j<=len2;j++)
				dp[i][j]=
				mymax(
					dp[i][j-1]+getmatch(str2[j-1],'-'),
					dp[i-1][j]+getmatch(str1[i-1],'-'),
					dp[i-1][j-1]+getmatch(str1[i-1],str2[j-1])
				);
		cout<<dp[len1][len2]<<endl;
	}
}

POJ 2244 Eeny Meeny Moo C++版

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

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

这个题简单约瑟夫问题，跟1012一个意思，不过比1012简单，方法一样，稍微调整一些细节就可以了。

题意是有n个城市，每隔m隔城市限电，1号第一个，问m为多少2号最后限电，我们可以这样看，就是n-1个城市从第一个开始数，保证第一个城市有电！

老样子利用公式：

p[i]=(p[i-1]+m-1)%(n-i);

代码如下：

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

int main()
{
	int n,m,i,p[155];
	while(cin>>n&&n;)
	{
		m=1;
		memset(p,0,sizeof(p));
		for(i=1;i<=n-2;i++)
		{
			p[i]=(p[i-1]+m-1)%(n-i);
			if(p[i]==0)
			{
				i=0;
				m++;
			}
		}
		cout<<m<<endl;
	}
}

POJ 2209 The King C++版

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

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

水题，就是求n个数的e次幂，如何加最大！必然是不加负数就是了！

代码如下：

/***************************************
Problem: 2209		User: awq123
Memory: 252K		Time: 16MS
Language: C++		Result: Accepted
***************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	int i,n,e,son[101],sum=0;
	cin>>n>>e;
	for(i=1;i<=n;i++)
	{
		cin>>son[i];
		if(e==1&&son;[i]>0)
			sum+=son[i];
		if(e==2)
			sum+=son[i]*son[i];
		if(e==3&&son;[i]>0)
			sum+=son[i]*son[i]*son[i];
	}
	cout<<sum<<endl;
}

POJ 1326 Mileage Bank C++版

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

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

题意就是要求我们计算飞机的总费用，地名只是眼子，不用管，头等舱两倍于路程的价格，商务舱1.5倍于路程的价格，经济舱，若路程小于500按500算，1倍于路程的价格！0结束一次飞行，#结束程序！

简单模拟题，不过有一点，我觉得学会了一些东西，就是：

Hint

When calculate bonus ,be sure you rounded x.5 up to x+1

当我们用int()强制转换时电脑会默认去掉小数，如何利用电脑去4舍5入，也算是这个题的一个考点了，我们巧妙的加上0.5就可能让电脑将尾数在5后的数识别到下一个整数里。

详细可以参见代码：

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

int main()
{
	char temp[20],c;
	float n;
	int sum=0;
	while(cin>>temp)
	{
		if(temp[0]=='#')
			break;
		else if(temp[0]=='0')
		{
			cout<<sum<<endl;
			sum=0;
			continue;
		}
		cin>>temp;
		cin>>n>>c;
		if(c=='F')
			sum+=int(2*n+0.5);
		else if (c=='B')
			sum+=int(1.5*n+0.5);
		else if (c=='Y')
		{
			if(n<500)
				sum+=500;
			else
				sum+=int(n+0.5);
		}
	}
}

POJ 1316 Self Numbers C++版

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

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

解释下题意，如果一个数可以写成另一个数及其个个位数的和，那么就不符合条件，比如39可以写成33+3+3那么不符合条件，要求输出所有符合条件的10000以内的数！

简单枚举，没什么算法，直接上代码：

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

int main()
{
	int a,b,c,d,n[10100]={0};
	for (int i = 1; i < 10000; i++)
	{
		if(n[i]==0)
			printf("%dn",i);
		a=i/1000;
		b=i%1000/100;
		c=i%100/10;
		d=i%10;
		n[i+a+b+c+d]=1;
	}

}

8-6 七夕了哦

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

转眼又是一年的七夕了，说实话，相对于外国的情人节我还是比较喜欢七夕这个属于我们自己的节日，说来惭愧，没有佳人相伴，七夕也没什么特别的。

有时在忧郁大学要不要谈个朋友，也是通过一些方面知道一个朋友的女友陪他一起泡图书馆，想来那感觉应该不错，值得羡慕，不过谈个朋友又怕纠结，小K很优秀，我也很喜欢她但是还是没有一个好的结果，懒得伤害别的女孩了，想想，大学混混也就过了，让充实的生活满足自己的无聊也是可以的，说实话，不像以前，慢慢知道就业压力大的，虽然总跟爸妈说不用他们操心，但是自己还是有点小无奈的！

虽然下学期也快到了，计划也还行，但是我是个按计划来的人吗？显然不是，顺其自然吧，不然就不是我风格了！

不过我没有忘记老段对我说的，既然你不愿意复读，那么大学就好好搞吧，一样有番作为，他说担心我会为一些东西分心，我说不会的，他说，如果大学真的碰到一个不错的女孩不要错过，那时一辈子的后悔，我深刻记得这句话，并且牢记在心！

POJ 1401 Factorial C++版

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

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

解释下题意，求n！后面有多少个0？比如10的阶乘是3628800那么就输出2！

有人说这个题是水题，其实只是题目简单，要在一个简单的题目里找到好的思路还是很有难度的！

分析下题目，有多少个0就是要求有多少含10的因式，也就是2*5的，但是其中含有的2绝对比5多，那么其实就是求，因式中有多少5

我现开始的思路就是将阶乘的每一个数都计算一次，每一个求因式5的数量，但是这样的方法在1000000000的数字下TLE了

贴下超时代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	int t,n,i,j,m=0;
	scanf("%d",&t;);
	while (t--)
	{
		m=0;
		scanf("%d",&n;);
		for(i=5;i<=n;i++)
		{
			j=i;
			while(j%5==0)
			{
				m++;
				j/=5;
			}
		}
		printf("%dn",m);
	}
}




```5 10 15 20 25 30 35 40 45 50 55 60  
他们一次除去本身的因式5得到  
1 2 3 4 5 6 7 8 9 10 11 12  
其中含有因式5的有：  
5 10  
除去5得：  
1 2  
结束  


这样得一个思路可以避免每个数都去求，每个阶段因式5的数量就是最大的数除以5（ps：12/5=2哦）

修改后代码如下：

```cpp
/***************************************
Problem: 1401		User: awq123
Memory: 136K		Time: 125MS
Language: C++		Result: Accepted
***************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	int t,n,m=0;
	scanf("%d",&t;);
	while (t--)
	{
		m=0;
		scanf("%d",&n;);
		while(n>=5)
		{
			n/=5;
			m+=n;
		}
		printf("%dn",m);
	}
}

POJ 1281 MANAGER C++版

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

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

解释下题意，先输入最大的数，再输入最后查询移出数的个数，依次输入查询移出数的位置，后面就是循环的操作了；

a：加入一个数
p：设置p的值
r：删除一个数，p为1删除最小的数，p为2删除最大的数！
e：结束一个输入

我们以给出的例子来分析

Sample Input
5
2
1 3
a 2
a 3
r
a 4
p 2
r
a 5
r
e

最大值设为5，后面要查询两个数，分别是第1个和第3个，然后开始循环
a2a3—现在列表为2，3
r——p为1，删除最小的，现在列表为3，移出列表为2
a4—–现在列表为3，4，移出列表为2
p2—–p设为2
r——p为2，删除最大的，现在列表为3，移出列表为2，4
a5—–现在列表为3，5，移出列表为2，4
r——p为2，删除最大的，现在列表为3，移出列表为2，4，5
e——结束

然后输出第1个和第3个移出的，既2，5。

模拟题没什么好说的，他说什么你就干什么，利用数组inum记录查询的位置，inow记录现在数列里的数，idel记录删除的数，用inumx，inowx，idelx分别记录每个数组里的数的个数。话不多说看代码，很好理解。

代码如下：

::cpp
/***************************************
Problem: 1281        User: awq123
Memory: 700K        Time: 0MS
Language: C++        Result: Accepted
***************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int cmp(int a,int b)
{
    return a>b;
}

int main()
{
    int inum[10000],inow[10000],idel[100000];
    int imax,i,p,inumx,inowx,idelx;
    char judge;
    while(cin>>imax>>inumx)
    {
        p=1,inowx=0,idelx=0;
        for(i=0;i<inumx;i++)
            cin>>inum[i];
        while(1)
        {
            cin>>judge;
            if (judge=='e')
                break;
            else if (judge=='a')
            {
                cin>>inow[inowx];
                inowx++;
            }
            else if (judge=='r')
            {
                if(p==1)
                    sort(inow,inow+inowx,cmp);
                else if(p==2)
                    sort(inow,inow+inowx);
                inowx--;
                idel[idelx]=inow[inowx];
                idelx++;
            }
            else if (judge=='p')
            {
                cin>>p;
            }

        }
        for (i = 0; i < inumx; i++)
        {
            if(inum[i]>idelx)
                cout<<-1<<endl;
            else
                cout<<idel[inum[i]-1]<<endl;
        }
        cout<<endl;
    }
}

POJ 1218 THE DRUNK JAILER C++版

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

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

做了才知道为什么说这题式用来调节心情的，呵呵，话不多说，直接开方就是了。

不过第一次提交CE没办法，现在都用g++，还是有点区别的，c++里sqrt直接开int会编译错误，后来改成double，AC！

代码如下：

/***************************************
Problem: 1218		User: awq123
Memory: 224K		Time: 0MS
Language: C++		Result: Accepted
***************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	int t;
	double n;
	cin>>t;
	while(t--)
	{
		cin>>n;
		cout<<(int)sqrt(n)<<endl;
	}
}

POJ 1046 Color Me Less C++版

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

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

水题，解释下题意，其中讲到了RGB颜色，给了个公式：

1046

其中D越小说明，颜色越接近，输入16个点，在后面每组数据求最接近的颜色，也就是最近的坐标点。

暴力枚举就是了，没什么好解释的，还有其实不用开根号的！

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

int main()
{
	int i,d[16][3],r,g,b;
	for (i = 0; i < 16; i++)
		scanf("%d%d%d",&d;[i][0],&d;[i][1],&d;[i][2]);
	while(scanf("%d%d%d",&r;,&g;,&b;)==3&&!(r==-1&&g;==-1&&b;==-1))
	{
		int min=100000,len,n;
		for (i = 0; i < 16; i++)
		{
			len=(r-d[i][0])*(r-d[i][0])+(g-d[i][1])*(g-d[i][1])+(b-d[i][2])*(b-d[i][2]);
			if (len<min)
			{
				min=len;
				n=i;
			}
		}
		printf("(%d,%d,%d) maps to (%d,%d,%d)n",r,g,b,d[n][0],d[n][1],d[n][2]);
	}
}