hdu1708(C++)

这个题目明确说了不涉及大数，假设第i个为b[i]：

b[0]=s1;

b[1]=s2;

b[3]=s1+s2;

b[4]=s1+2*s2;

b[5]=2*s1+3*s2；

b[6]=3*s1+5*s2;

b[7]=5*s1+8*s2;

………………

于是s1和s2的系数从某一项开始分别成斐波那契数列，于是只要算出b[k]中有多少个s1和多少个s2即可解决问题

#include<iostream>
#include<string>
using namespace std;
int main()
{
int i,j,p,c,k,T;
cin>>T;
string s1,s2;
while(T--){
cin>>s1>>s2>>k;
int a[51];
int b[26],c[26];
a[0]=1,a[1]=1; //初始化斐波那契数列
for(i=0;i<26;i++)
c[i]=b[i]=0; //每一项都设置为0
for(i=2;i<k;i++)
a[i]=a[i-1]+a[i-2];
for(i=0;i<s1.size();i++)
b[s1[i]-'a']++;
for(i=0;i<s2.size();i++)
c[s2[i]-'a']++;
if(k==0)
{
for(char ch='a';ch<='z';ch++)
cout<<ch<<":"<<b[ch-'a']<<endl;
cout<<endl;
continue;
}
if(k==1)
{
for(char ch='a';ch<='z';ch++)
cout<<ch<<":"<<c[ch-'a']<<endl;
cout<<endl;
continue;
}
for(i=0;i<26;i++)
{
b[i]=b[i]*a[k-2]; //注意对应关系
c[i]=c[i]*a[k-1];
c[i]=c[i]+b[i];
}
for(char ch='a';ch<='z';ch++)
cout<<ch<<":"<<c[ch-'a']<<endl;
cout<<endl;
}
return 0;
}

如果涉及大数，将上述代码做一个改进·也可以做出来，下面还有一个涉及大数的版本

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
typedef vector<vector<int>>vt;
class letter //将每一个字母看为对象
{
public:
vt v; //二维向量来储存大数
letter(){ vt v1(51); v = v1;};
char ch;
};
int main()
{
int T,i,k,j,t,p,c;
cin >> T;
string s1, s2;
while (T--)
{
cin >> s1 >> s2 >> k;
letter L[26]; //定义a-z 26个对象
for (i = 0; i < 26; i++)
{
L[i].ch = 'a' + i;
L[i].v[0].push_back(0);
L[i].v[1].push_back(0); //初始化前两项
}
for (i = 0; i < s1.size(); i++)
L[s1[i] - 'a'].v[0][0]++;
for (i = 0;i<s2.size();i++)
L[s2[i] - 'a'].v[1][0]++;
for (i = 0; i < 26;i++)
for (j =2; j <=k;j++)
{
c = 0;
if (L[i].v[j - 1].size()>L[i].v[j - 2].size())
L[i].v[j - 2].insert(L[i].v[j - 2].begin(),0);
for (t = L[i].v[j - 2].size() - 1; t >= 0; t--)
{
p = L[i].v[j - 1][t] + L[i].v[j - 2][t] + c;
L[i].v[j].push_back(p % 10);
c = p / 10;
}
if (c>0)
L[i].v[j].push_back(c);
reverse(L[i].v[j].begin(), L[i].v[j].end());
}

//-----------------------------------以上实现大数相加

for (i = 0; i < 26; i++)
{
cout << L[i].ch << ":";
for (j = 0; j < L[i].v[k].size(); j++)
cout << L[i].v[k][j];
cout << endl;
}
cout << endl;
} //控制输出
return 0;
}

巴特西

hdu1708(C++)

最新文章

热门文章