算法作业一。
问题 A: 小雏鸟的成人式 2
题目描述
陶行知先生说：“我们要活的书，不要死的书 ”。
小雏鸟们从书上都是对的到现在能去伪存真的去使用书籍，证明你们长大了。总之就是要有自己的主见，自己的思考。
大白希望大家都能拿到一百分，所以对100这个数以及他的倍数很喜欢。
大白发现，从1开始，一定能找出一个序列从小到大排列，使得每一项都是 恰好能且仅能 被100整除D次。
请你编写程序，找到这个数列里第N个数。
输入
多行。每行输入两个整数，表示D和N，N范围[1,100]，D范围[0,2]
输出
每行对应输入，给出一个符合题意的整数
样例输入
0 5
1 11
2 85
样例输出
5
1100
850000
提示
代码
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int d,n;
while(cin>>d>>n)
{
if(n>=1&&n<100&&d>=0&&d<=2)
cout<<n*int(pow(100,d))<<endl;
else if(n==100)
cout<<101*int(pow(100,d))<<endl;
else
continue;
}
}
问题 B: 小雏鸟的成人式 3
题目描述
陶行知先生说：“因为道德是做人的根本。根本一坏，纵然使你有一些学问和本领，也无甚用处。”
小雏鸟们需要时刻铭记在心，不管你长成什么样的的攻城狮，都必须三观正确。
涛涛轰这一天带着爱美酱来到了一个风景如画的地方游玩。艳阳高照，他俩玩的很尽兴，但是现在他们口渴了。
涛涛轰：“我要买饮料！”
店主：“我们这里有三种饮料，矿泉水1.5元一瓶，可乐2元一瓶，橙汁3.5元一瓶。”
涛涛轰：“好的，给我一瓶矿泉水。”
说完他掏出一张N元的大钞递给店主。
店主：“我忘了提醒你了，我们这里没有找客人钱的习惯的，多的钱我们都当小费收了的，嘿嘿。”
涛涛轰：“……”
涛涛轰环顾四周，就这一家商店，况且实在太渴了，看着脸热的粉扑扑的一头汗的爱美酱，就决定在这买了。不过涛涛轰想，与其把钱当小费送给他还不如自己多买一点饮料，反正早晚都要喝，但是要尽量少让他赚小费。
现在涛涛轰希望你能帮他计算一下，最少他要给店主多少小费。
输入
输入数据的第一行是一个整数T(1<=T<=100)，代表测试数据的数量。然后是T行测试数据，每个测试数据只包含一个正整数N（1<=N<=10000），N代表小明手中钞票的面值，以分为单位。
注意：商店里只有题中描述的三种饮料。
输出
对于每组测试数据，请你输出小明最少要浪费多少钱给店主作为小费，以分为单位。
样例输入
2
900
250
样例输出
0
50
提示
代码
#include<iostream>
#include<cmath>
using namespace std;
void test(int x)
{
if(x<150)
cout<<x<<endl;
else if(x<=200||x>300)
cout<<(x%50)<<endl;
else
cout<<x-200<<endl;
}
int main()
{
int n,x;
cin>>n;
while(n--)
{
cin>>x;
test(x);
}
}
问题 C: 大白just大白
题目描述
大家都知道，大白对学术要求是很严格的。抄作业、考试作弊神马的在大白这简直不能忍。
这不刚刚过去的期末考试。有n个学生被查出来有问题。
大白给了他们申辩的机会，每个学生可以提交一段文字，作为申辩理由。但是大白发现来的人总会有一些奇怪的理由。
大白提前列了m个常见借口关键字。他想看看来申辩的学生中最烂的申辩理由是什么。
所谓最烂申辩理由就是，申辩里，含有常见借口关键字最多的。
含有关键字，指的是，理由中出现了一串和关键字完全匹配的字符串，如果出现大写小写不同，也认为匹配。比如，关键字是 bed 理由中出现Bedroom算含有一个关键字。
输入
一个输入可能有多个case，每个case第一行两个数。分别代表n 和 m
接下来m行，每行一个关键字（字符串）
再接下来n行字符串。m和n都不大于20
每一个借口和借口关键字只会包含大小写字母，长度不会超过4000个字符。
输出
对于每个case输出一行字符串，表示最烂的理由。若有多个理由包含相同数目的关键字，按输入顺序输出靠前的那个。
样例输入
2 3
love
cumt
ACM
ILoveCUMTACM
cumtAACM
2 2
A
b
Ab
bA
样例输出
ILoveCUMTACM
Ab
提示
代码
#include<iostream>
#include<string>
#include<string.h>
#include <algorithm>
using std::string;
using namespace std;
bool search(string str,string sub)
{
int i;
if((i = str.find(sub, i)) != std::string::npos)
return true;
else
return false;
}
int main()
{
int m,n,k=0,local=0;
while(cin>>n>>m)
{
string key[m],ca[n],key1[m],ca1[n];
for(int i=0;i<m;i++)
{
cin>>key[i];
key1[i]=key[i];
transform(key1[i].begin(),key1[i].end(),key1[i].begin(),::tolower);
}
for(int i=0;i<n;i++)
{
cin>>ca[i];
ca1[i]=ca[i];
transform(ca1[i].begin(),ca1[i].end(),ca1[i].begin(),::tolower);
}
for(int i=0;i<n;i++)
{
int num=0;
for(int j=0;j<m;j++)
{
if(search(ca1[i],key1[j]))
num++;
//cout<<search(ca1[i],key1[j])<<endl;
}
if(num>k)
{
k=num;
local=i;
}
}
//cout<<local<<endl;
//cout<<k<<endl;
cout<<ca[local]<<endl;
}
}
问题 D: 小雏鸟的计算
题目描述
小雏鸟们的三角形翅膀终于长出健壮的肌肉和丰满的羽毛，已经跃跃欲试的去准备尝试挑战新的难题了。
考虑以下的算法：
\1. 输入 n
\2. 印出 n
\3. 如果 n = 1 结束
\4. 如果 n 是奇数 那么 n=3*n+1
\5. 否则 n=n/2
\6. GOTO 2
例如输入 22 得到的数列： 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
据推测此算法对任何整数而言会终止 (当打印出 1 的时候)。虽然此算法很简单，但以上的推测是否真实却无法知道。然而对所有的n ( 0 < n < 1000000 )来说，以上的推测已经被验证是正确的。
给一个输入 n 透过以上的算法我们可以得到一个数列（1作为结尾）。此数列的长度称为n的cycle length。上面提到的例子 22的 cycle length为 16.
问题来了：对任2个整数i，j我们想要知道介于i，j（包含i，j）之间的数所产生的数列中最大的cycle length是多少。
输入
输入可能包含了好几行测试数据，每一行有一对整数 i，j 。
0< i，j < 1000000
输出
对每一对输入 i j你应该要输出 i j和介于i j之间的数所产生的数列中最大的cycle length。
样例输入
1 10
10 1
100 200
201 210
900 1000
样例输出
1 10 20
10 1 20
100 200 125
201 210 89
900 1000 174
提示
代码
#include<iostream>
using namespace std;
int test(int n)
{
int count=0;
while(n!=1)
{
count++;
if(n%2!=0)
n=3*n+1;
else
n=n/2;
}
count++;
return count;
}
int main()
{
int i,j;
while(cin>>i>>j)
{
cout<<i<<" "<<j<<" ";
int max=0;
if(i>j)
{
int m;
m=i;
i=j;
j=m;
}
for(int k=i;k<=j;k++)
{
if(test(k)>max)
max=test(k);
}
cout<<max<<endl;
}
}
问题 E: 进制转换
题目描述
输入一个十进制正整数，然后输出它所对应的八进制数。
输入
输入一个十进制正整数n(1≤n≤106) 。
输出
输出n对应的八进制数，输出在一行。
样例输入
10
样例输出
12
提示
代码
#include<iostream>
#include<stack>
using namespace std;
void transform(int x)
{
stack <int> stk;
while(x!=0)
{
stk.push(x%8);
x=x/8;
}
while(!stk.empty())
{
cout<<stk.top();
stk.pop();
}
cout<<endl;
}
int main()
{
int n;
cin>>n;
transform(n);
}
问题 F: 排列问题
题目描述
输入一个可能含有重复字符的字符串，打印出该字符串中所有字符的全排列。
输入
单组测试数据，输入数据是一个长度不超过10个字符的字符串，以逗号结尾。
输出
打印出该字符串中所有字符的全排列。以字典序顺序输出，用空格分隔。
样例输入
abc,
样例输出
abc acb bac bca cab cba
提示
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
int main()
{
string str;
cin >> str;
str = str.substr(0, str.length() - 1);
sort(str.begin(),str.end());
do
{
cout << str <<" ";
}while(next_permutation(str.begin(),str.end()));
return 0;
}
问题 G: 快速幂
题目描述
输入
多组测试样例，最多50组。每组测试样例给定一个整数x(1<=x<=25000)
输出
对每个样例，输出一行，代表f(x)对100000007取余的结果。
样例输入
3
4
5
样例输出
33
289
3414
提示
代码
#include<iostream>
#include<cmath>
using namespace std;
long long n=100000007;
long long poww(long long a, long long b) {
long long ans = 1;
while (b)
{
if (b & 1 != 0)
ans=ans*a%n;
a=a*a%n;
b >>= 1;
}
return ans;
}
int main()
{
long long n=100000007;
int x;
while(cin>>x)
{
long long sum=0;
for(int i=1;i<=x;i++)
{
sum+=(poww(i,i));
}
cout<<(sum+1)%n<<endl;
}
return 0;
}
问题 H: 求第k小
题目描述
给定n(1<=n<=1000000)个元素，求第k小数(1<=k<=n)。
输入
一组样例。第一行输入两个整数n和k。第二行输入n个不同的int范围内的数。
输出
输出一行，输出第k小数。
样例输入
5 2
1 5 3 2 4
样例输出
2
提示
代码
#include<iostream>
#include<algorithm>
using namespace std;
int a[1000010];
int main()
{
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
cout<<a[k-1]<<endl;
}
问题 I: 沙子的质量
题目描述
设有N堆沙子排成一排，其编号为1，2，3，…，N（N< =300）。每堆沙子有一定的数量，可以用一个整数来描述，现在要将N堆沙子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆沙子的数量之和，合并后与这两堆沙子相邻的沙子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，如有4堆沙子分别为1 3 5 2我们可以先合并1、2堆，代价为4，得到4 5 2又合并1，2堆，代价为9，得到9 2，再合并得到11，总代价为4+9+11=24，如果第二步是先合并2，3堆，则代价为7，得到4 7，最后一次合并代价为11，总代价为4+7+11=22；问题是：找出一种合理的方法，使总的代价最小。输出最小代价。
输入
第一行一个数N表示沙子的堆数N。 第二行N个数，表示每堆沙子的质量。 a[i]< =1000。
输出
合并的最小代价。
样例输入
4
1 3 5 2
样例输出
22
提示
代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int num[305];
int f[305][305]; //合并a堆到b堆的最小代价
int main()
{
cin>>n;
memset(f,127/3,sizeof(f)); //初始化为一个较大值，注意memset的用法！
for(int i=1; i<=n; i++)
{
cin>>num[i];
num[i]+=num[i-1];
f[i][i]=0;
}
for(int i=2; i<=n; i++) //求1到i堆的最小代价
{
for(int j=i-1; j>=1; j--) //求j到i堆的最小代价
{
for(int k=j; k<=i; k++) //找到j到i堆的最小代价
{
f[j][i]=min(f[j][i],f[j][k]+f[k+1][i]+num[i]-num[j-1]);
}
}
}
cout<<f[1][n];
return 0;
}
问题 J: 最长公共子序列
题目描述
一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad” ,顺次选1，3，5个字符就构成子串” cad” ,现给定两个字符串，求它们的最长共公子串。
输入
第一行两个字符串用空格分开。两个串的长度均小于2000 。
输出
最长子串的长度。
样例输入
abccd aecd
样例输出
3
提示
代码
#include<iostream>
#include<string.h>
using namespace std;
int maxx(int a,int b)
{
if (a>=b) return a;
return b;
}
int main()
{
string a,b;
cin>>a>>b;
int n,m,max=0;
n=a.size();
m=b.size();
int lcm[n+1][m+1];
for(int i = 0; i <= n; ++i)
lcm[i][0] = 0;
for(int i = 0; i <= m; ++i)
lcm[0][i] = 0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i-1]==b[j-1])
{
lcm[i][j]=lcm[i-1][j-1]+1;
}
else
{
lcm[i][j]=maxx(lcm[i][j-1],lcm[i-1][j]);
}
}
}
cout<<lcm[n][m];
}
