【算法课OJ】作业一
决定程序优雅的人，而不是语言。
链接：http://192.168.173.163/JudgeOnline/contest.php?cid=1105
密码：123654
问题 A: 小雏鸟长大啦 2
题目描述
伟大的人民教育家，晓庄学院的创始人陶行知先生说：“晓庄是从爱里来的，没有了爱也便没有了晓庄。”
作为晓庄的小雏鸟们，一定对此话有深刻的理解。
虽然大白们这学期绞尽脑汁想方设法的折磨锻炼各位小雏鸟，但是回首看看学期初，想必各位柔弱的三角形翅膀也有了展翅翱翔的肌肉。
这就是爱吧。
事实上，肌肉是锻炼出来的。你们花了16周的时间，第i周进行了Mi道题的练习。所谓精通一个技能必然要付出一万小时的努力，你们也想算算这学期做了多少题吧？
输入
输入16个整数。代表每周训练的题目量
输出
输出一个整数，是这学期训练的总题量。
样例输入
5 7 8 10 9 8 9 8 9 8 9 8 9 8 9 8
样例输出
132
题意
输入16个数，求出它们的和，输出。
思路
Water，累加即可。
代码
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
int t,sum = 0;
for(int i = 0; i < 16; i++)
{
scanf("%d", &t);
sum += t;
}
printf("%d\n",sum);
return 0;
}
问题 B: 小雏鸟长大啦 3
题目描述
陶行知先生说：“行是知之始，知是行之成”。
大白铭记在心，所以，大白的教育方针就是，大胆试错。做就完事了，just do it！
但是小雏鸟们一定会遇到一些题，被卡住，格式错误，答案错误，编译错误等等。
大白决定考试结束之后，给最顽强拼搏的小雏鸟赠书以表敬意。所谓最顽强拼搏是指，所有小雏鸟里，wa错误次数最多的那位，便有资格获得大白赠书了。
给你若干个数，请你编程求出最大的那一个，并输出。
输入
第一行一个整数N，表示N只小雏鸟
接下来N行，每行一个整数x，表示N只小雏鸟wa的次数。
数据范围：N ≤ 310，x ≤ 600
输出
一个整数，最顽强拼搏获得者wa的次数。
样例输入
3
1
2
10
样例输出
10
题意
输入n个数，求出最大值。
思路
Water，用一个变量m存储最大值，每输入一个数，让其与m比较，若其大于m，则覆盖。
代码
#include<iostream>
#include<stdio.h>
using namespace std;
const int INF = 1<<30;
int main()
{
int n,m = -INF,t;
scanf("%d",&n);
for(int i = 0; i < n; i++)
{
scanf("%d",&t);
if(t>m) m = t;
}
printf("%d\n",m);
return 0;
}
问题 C: 小雏鸟长大啦 4
题目描述
陶行知先生说：”吃自己的饭，滴自己的汗，自己的事自己干”。
但是有些小雏鸟做作业喜欢抄别人的！
大白开发了代码自动查重功能。
已知有两个字符串，a和b，如果b串与a串的内容一模一样，那就是抄袭无误了。但是有些小雏鸟把心思用在了歪处。他们会在代码里加入一些干扰变量，使得上述判断方法失灵。
大白需要改进算法，帮他实现新的查重算法。
输入
两行字符串，分别代表字符串a和b。长度不超过100。
输出
输出b是否抄袭了a。
当b中存在去掉一些字符后和a字符串一致的数据(长度，顺序，内容都相等)的时候，输出yes，否则输出no
样例输入
int c;
int a,b,c=0;
样例输出
yes
题意
输入两行字符串，若b中包含a则输出yes，否则输出no
思路
可以使用两个下标i, j分别指向a, b字符串正在比较的字符。
- 若a[i] == b[j]，则i++（每次i++判断i是否>=lena，若是，则比较结束，输出yes）, j++；
- 否则j++（每次j++判断i是否>=lenb，若是，则比较结束，输出no）。
注意：由于要输入整行，故输入用gets()或getline()
代码
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAXN = 105;
int main()
{
char a[MAXN],b[MAXN];
gets(a);
gets(b);
int lena = strlen(a),lenb = strlen(b);
int i = 0,j = 0;
while(true)
{
if(a[i] == b[j])
{
i++;
if(i >= lena)
{
puts("yes");
return 0;
}
j++;
}
else j++;
if(j >= lenb)
{
puts("no");
return 0;
}
}
}
问题 D: 小雏鸟长大啦 5
题目描述
陶行知先生说：“教育不能创造什么，但它能启发学生创造力以从事于创造工作。”
所以大白在这学期的平时作业里一直在出一些启发小雏鸟创造思维的题。
但是很不幸，大多数的小雏鸟并没有被启发成功。当然主要怪高中僵化的培养训练模式。
郁闷的大白去喝矿泉水。最近大白喜欢的矿泉水在搞促销，两个瓶盖能够换一瓶新的矿泉水，而且这瓶水的盖子能继续使用。
大白把所有的水喝完了才会去换瓶盖。每次一定要喝完所有水才去换，若兑换的时候，有大于一的奇数个瓶盖，大白就会再买一瓶凑成偶数，如果最后只剩一个瓶子了，大白就喝撑了。
现在知道大白开始时有N瓶水，他想知道他喝撑了的时候一共喝掉了多少瓶。
输入
一个整数N，N≤10000（多组样例）
输出
一个整数，表示大白喝撑了的时候喝了多少瓶水。
样例输入
6
样例输出
13
提示
6->3(买一瓶)->2->1结束。总共喝了6+3+1+2+1=13瓶。
题意
如题目描述所示。
思路
模拟。注意多组输入。
代码
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
int n,sum;
while(~scanf("%d",&n))
{
sum = n;
while(n > 1)
{
if(n % 2)
{
n += 1;
sum += 1;
}
n /= 2;
sum += n;
}
printf("%d\n",sum);
}
return 0;
}
问题 E: 小雏鸟长大啦 7
题目描述
陶行知先生说：“千教万教教人求真”
大白对于科学问题上始终实事求是。比如，公元0年不存在就是不存在。
请你编写程序，判断给定的年份是否是闰年呢？
输入
输入多行，每行一个整数，表示年份。范围为[-1000,3000]负号表示公元前。注意没有公元0年
输出
对于每行输入，如果该年是闰年，则输出yes，否则输出no
样例输入
2018
100
4
-1
样例输出
no
no
yes
yes
题意
多组输入，判断是否为闰年，若是，则输出yes，否则输出no。
思路
首先明确判断某一年为闰年的条件：
这题和一般判闰年的题目不同，还要考虑负数情况，因为输入的可能值中最小为-1000，分析可知加上一个大于1000且可以被400整除的数再加1（因为没有公元0年，可选1201）可简化问题。
代码
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
int n;
while(~scanf("%d",&n))
{
if(n < 0)
{
n += 1201;
}
if(n%400 == 0 || (n%4 == 0 && n%100))
{
puts("yes");
}
else puts("no");
}
return 0;
}
问题 F: 小雏鸟的成人式 1
题目描述
陶行知先生说：“人有两件宝，双手和大脑”。
小雏鸟们经过磨练长大，不仅翅膀要变硬，脑子也要变得更聪明。
编程离不开键盘。敲键盘是有指法的。
以双手的十个手指的初始位置为基准，我们把打字需要移动手指的格数记为“键程”。打字标准指法见下图。
手指的初始键位是 asdf jkl; 每个手指控制的按键见上图，打完一个字符，手指要回到初始键位。 拇指初始键位为空格
我们记一根手指不移动就可以打出的字的键程为0,移动一格打出来的字的键程为1，需要移动两格及以上的键程记为2.打完字符的回位过程不重复计算键程。
比如，“asdf”的键程为0，“dfer”的键程为2.
请你编写程序，求要将指定的字符串打出来，总键程是多少。
输入
一行字符。可能包括大小写，数字，符号等。全部为半角字符。
输出
对于输入的字符串，求出总键程。请参阅提示部分的描述
样例输入
asdfg
样例输出
1
提示
对于左手小指而言，a的键程为0，键程为一的有q，z，大写键，小指区其他的字符都是键程为2。
题意
如题目描述所示。要注意大写字母是小写+1：题目把大写看成先按“大写锁定”（键程为1），再按那个键，而且不符合常理的事它按完字母不要把锁定给解除。
思路
坑题！模拟。可用map
代码
//这题简直有毒
#include<iostream>
#include<stdio.h>
#include<map>
using namespace std;
int main()
{
map<char,int> m;
//键程0
char a0[] = "asdf jkl\;";
for(int i = 0; a0[i] != '\0'; i++)
m[a0[i]] = 0;
//键程1
char a1[] = "qwerghuiop'zxcvm,.\/";
for(int i = 0; a1[i] != '\0'; i++)
m[a1[i]] = 1;
//键程2（不含大写字母）
char a2[] = "：`1234567890-=\\ty[]bn";
for(int i = 0; a2[i] != '\0'; i++)
m[a2[i]] = 2;
//大写字母统一处理：小写字母+1
for(int i = 0; i < 26; i++)
m['A'+i] = 1+m['a'+i];
//键程3（不含大写字母）：shift+键程1的键
m['\"'] = m['<'] = m['>'] = m['?'] = 3;
//键程4（不含大写字母）：shift+键程2的键
char a4[] = "~!@#$%^&*()_+|{}";
for(int i = 0; a4[i] != '\0'; i++)
m[a4[i]] = 4;
//初始化完毕，开始输入数据
char str[999999];
gets(str);
int len = strlen(str);
int sum = 0;
for(int i = 0; i < len; i++)
{
sum += m[str[i]];
}
printf("%d\n",sum);
return 0;
}
问题 G: 小雏鸟的成人式 2
题目描述
陶行知先生说：“我们要活的书，不要死的书 ”。
小雏鸟们从书上都是对的到现在能去伪存真的去使用书籍，证明你们长大了。总之就是要有自己的主见，自己的思考。
大白希望大家都能拿到一百分，所以对100这个数以及他的倍数很喜欢。
大白发现，从1开始，一定能找出一个序列从小到大排列，使得每一项都是 恰好能且仅能 被100整除D次。
请你编写程序，找到这个数列里第N个数。
输入
多行。每行输入两个整数，表示D和N，N范围[1,100]，D范围[0,2]
输出
每行对应输入，给出一个符合题意的整数
样例输入
0 5
1 11
2 85
样例输出
5
1100
850000
题意
如题目描述所示
思路
Water，要注意特殊情况：当n == 100时，可这样处理：n++。
代码
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
int d,n;
while(~scanf("%d %d",&d,&n))
{
if(n == 100) n++;
if(d == 1) n *= 100;
else if(d == 2) n *= 10000;
printf("%d\n",n);
}
return 0;
}
问题 H: 小雏鸟的成人式 3
题目描述
陶行知先生说：“因为道德是做人的根本。根本一坏，纵然使你有一些学问和本领，也无甚用处。”
小雏鸟们需要时刻铭记在心，不管你长成什么样的的攻城狮，都必须三观正确。
涛涛轰这一天带着爱美酱来到了一个风景如画的地方游玩。艳阳高照，他俩玩的很尽兴，但是现在他们口渴了。
涛涛轰：“我要买饮料！”
店主：“我们这里有三种饮料，矿泉水1.5元一瓶，可乐2元一瓶，橙汁3.5元一瓶。”
涛涛轰：“好的，给我一瓶矿泉水。”
说完他掏出一张N元的大钞递给店主。
店主：“我忘了提醒你了，我们这里没有找客人钱的习惯的，多的钱我们都当小费收了的，嘿嘿。”
涛涛轰：“……”
涛涛轰环顾四周，就这一家商店，况且实在太渴了，看着脸热的粉扑扑的一头汗的爱美酱，就决定在这买了。不过涛涛轰想，与其把钱当小费送给他还不如自己多买一点饮料，反正早晚都要喝，但是要尽量少让他赚小费。
现在涛涛轰希望你能帮他计算一下，最少他要给店主多少小费。
输入
输入数据的第一行是一个整数T(1<=T<=100)，代表测试数据的数量。然后是T行测试数据，每个测试数据只包含一个正整数N（1<=N<=10000），N代表小明手中钞票的面值，以分为单位。
注意：商店里只有题中描述的三种饮料。
输出
对于每组测试数据，请你输出小明最少要浪费多少钱给店主作为小费，以分为单位。
样例输入
2
900
250
样例输出
0
50
题意
有三种饮料，矿泉水1.5元/瓶，可乐2元/瓶，橙汁3.5元/瓶，黑心店家不找零，求用N元钱买饮品的最少亏损金额。（n <= 1e4）
思路
- 当n < 150，啥都买不了，钱全被黑心老板吞了，嘤嘤嘤~，直接输出n；
- 当150 <= n < 200时，对150取模输出，因为50|150，故也可对50取模；再考虑n >= 300时，列举几个数字观察发现也是直接对50取模即可；故可写成(n >= 300 || n <= 200)时，输出n%50；
- 200~300之间，输出n%200。
代码
#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
if(n < 150) printf("%d\n",n);
else if(n >= 300 || n <= 200) printf("%d\n",n%50);
else printf("%d\n",n-200);
}
return 0;
}
问题 I: 大白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
题意
m个关键词，n个借口，找出包含（子串）关键词种类最多的借口。（0<=n,m<=20,关键词、借口长度L<=4e4），注意不区分大小写。
思路
可以把主串和模式串都转成全大写（或全小写）。
注意，由于要输出原来的串，故所有主串都要保存原稿。
实现可用string类下的find()函数。
代码
#include<iostream>
#include<string>
using namespace std;
const int MAXN = 21;
int main()
{
int n,m,i,j;
string text[MAXN],pattern[MAXN];
string texx[MAXN],patterr[MAXN];
while(~scanf("%d %d",&n,&m))
{
for(i = 0; i < m; i++)
{
cin>>pattern[i];
patterr[i] = pattern[i];
for(j = 0; patterr[i][j] != '\0'; j++)
{
if(islower(patterr[i][j])) patterr[i][j] = patterr[i][j]+'A'-'a';
}
//cout<<patterr[i]<<endl;
}
for(i = 0; i < n; i++)
{
cin>>text[i];
texx[i] = text[i];
for(j = 0; texx[i][j] != '\0'; j++)
{
if(islower(texx[i][j])) toupper(texx[i][j]);
}
//cout<<texx[i]<<endl;
}
int maxx = -1,maxt = -1,cur;
for(i = 0; i < n; i++)
{
cur = 0;
for(j = 0; j < m; j++)
{
string::size_type idx = texx[i].find(patterr[j]);
if(idx != string::npos) cur++;
}
if(cur > maxx)
{
maxx = cur;
maxt = i;
}
}
cout<<text[maxt]<<endl;
}
return 0;
}
问题 J: 小雏鸟的计算
题目描述
小雏鸟们的三角形翅膀终于长出健壮的肌肉和丰满的羽毛，已经跃跃欲试的去准备尝试挑战新的难题了。
考虑以下的算法：
- 输入 n
- 印出 n
- 如果 n = 1 结束
- 如果 n 是奇数 那么 n=3*n+1
- 否则 n=n/2
- 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
题意
如题目描述所示，对任2个整数i、j，输出介于i、j（包含i，j）之间的数所产生的数列中最大的cycle length是多少。
思路
模拟，递归。
代码
#include<iostream>
#include<stdio.h>
using namespace std;
const int MAXN = 105;
int cnt;
void fun(int x)
{
if(x == 1) return;
if(x % 2) x = 3*x+1;
else x /= 2;
fun(x);
cnt++;
}
int solve(int n)
{
cnt = 1;
fun(n);
return cnt;
}
int main()
{
int l,r,ans,L,R;
while(~scanf("%d %d",&L,&R))
{
l = L;
r = R;
if(l > r) swap(l,r);
ans = 0;
for(int p = l; p <= r; p++)
ans = max(ans,solve(p));
printf("%d %d %d\n",L,R,ans);
}
return 0;
}
本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 ComyDream 。
本文链接：http://comydream.github.io/2018/09/10/algorithm-homework-1/