算法分析与设计(一)

http://192.168.173.163/JudgeOnline/contest.php?cid=1245

密码:123654

算法作业1

小雏鸟的成人式 2

问题描述

从1开始,一定能找出一个序列从小到大排列,使得每一项都是恰好能且仅能被100整除D次。

请你编写程序,找到这个数列里第N个数。

输入

多行。每行输入两个整数,表示D和N,N范围[1,100],D范围[0,2]

输出

每行对应输入,给出一个符合题意的整数

样例输入

1
2
3
0 5
1 11
2 85

样例输出

1
2
3
5
1100
850000

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;
int main(){
int k;
int num;
while (cin >> k >> num) {
if (num % 100 == 0) {
num++;
}
if (k == 0) {
cout << num << endl;
}
else if (k == 1) {
cout << num * 100 << endl;
}
else {
cout << num * 10000 << endl;
}
}
return 0;
}

小雏鸟的成人式 3

问题描述

店主:“我们这里有三种饮料,矿泉水1.5元一瓶,可乐2元一瓶,橙汁3.5元一瓶。”

涛涛轰:“好的,给我一瓶矿泉水。”

说完他掏出一张N元的大钞递给店主。

店主:“我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿。”

涛涛轰:“……”

涛涛轰环顾四周,就这一家商店,况且实在太渴了,看着脸热的粉扑扑的一头汗的爱美酱,就决定在这买了。不过涛涛轰想,与其把钱当小费送给他还不如自己多买一点饮料,反正早晚都要喝,但是要尽量少让他赚小费。

现在涛涛轰希望你能帮他计算一下,最少他要给店主多少小费。

输入

输入数据的第一行是一个整数T(1<=T<=100),代表测试数据的数量。然后是T行测试数据,每个测试数据只包含一个正整数N(1<=N<=10000),N代表小明手中钞票的面值,以分为单位。
注意:商店里只有题中描述的三种饮料。

输出

对于每组测试数据,请你输出小明最少要浪费多少钱给店主作为小费,以分为单位。

样例输入

1
2
3
2
900
250

样例输出

1
2
0
50

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<algorithm>
using namespace std;

int T;
int n;
int money[3] = { 150,200,350 };
int dp[10005];

int main() {
cin >> T;
for (int i = 0; i < 3; i++) {
for (int j = money[i]; j < 10005; j++) {
dp[j] = max(dp[j], dp[j - money[i]] + money[i]);
}
}
while (T--) {
cin >> n;
cout << n - dp[n] << endl;
}
return 0;
}

大白just大白

问题描述

大家都知道,大白对学术要求是很严格的。抄作业、考试作弊神马的在大白这简直不能忍。

这不刚刚过去的期末考试。有n个学生被查出来有问题。

大白给了他们申辩的机会,每个学生可以提交一段文字,作为申辩理由。但是大白发现来的人总会有一些奇怪的理由。

大白提前列了m个常见借口关键字。他想看看来申辩的学生中最烂的申辩理由是什么。

所谓最烂申辩理由就是,申辩里,含有常见借口关键字最多的。

含有关键字,指的是,理由中出现了一串和关键字完全匹配的字符串,如果出现大写小写不同,也认为匹配。比如,关键字是 bed 理由中出现Bedroom算含有一个关键字。

输入

一个输入可能有多个case,每个case第一行两个数。分别代表n 和 m

接下来m行,每行一个关键字(字符串)

再接下来n行字符串。m和n都不大于20

每一个借口和借口关键字只会包含大小写字母,长度不会超过4000个字符。

输出

对于每个case输出一行字符串,表示最烂的理由。若有多个理由包含相同数目的关键字,按输入顺序输出靠前的那个。

样例输入

1
2
3
4
5
6
7
8
9
10
11
2 3
love
cumt
ACM
ILoveCUMTACM
cumtAACM
2 2
A
b
Ab
bA

样例输出

1
2
ILoveCUMTACM
Ab

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;
int countStr(char*t, char*s) {
char *cp = NULL;
if (NULL != (cp = strstr(t, s))) {
return 1;
}
return 0;
}

int main() {
int n, m;
char s[21][4002], t[21][4002];
char s1[21][4002], t1[21][4002];
int num;
int maxx = 0;
int p = 0;

while (cin >> n >> m) {
num = 0;
maxx = 0;
p = 0;
for (int i = 0; i < n; i++) {
cin >> s[i];
for (int k = 0; s[i][k] != '\0'; k++) {
if (s[i][k] >= 'A'&&s[i][k] <= 'Z') {
s1[i][k] = s[i][k] + 32;
}
else {
s1[i][k] = s[i][k];
}
s1[i][k + 1] = '\0';
}
}
for (int j = 0; j < m; j++) {
cin >> t[j];
for (int k = 0; t[j][k] != '\0'; k++) {
if (t[j][k] >= 'A'&&t[j][k] <= 'Z') {
t1[j][k] = t[j][k] + 32;
}
else {
t1[j][k] = t[j][k];
}
t1[j][k + 1] = '\0';
}
}
for (int i = 0; i < m; i++) {
num = 0;
for (int j = 0; j < n; j++) {
num = num + countStr(t1[i], s1[j]);
}
if (num > maxx) {
p = i;
maxx = num;
}
}
cout << t[p] << endl;
}
return 0;
}

小雏鸟的计算

问题描述

考虑以下的算法:

  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
2
3
4
5
1 10
10 1
100 200
201 210
900 1000

样例输出

1
2
3
4
5
1 10 20
10 1 20
100 200 125
201 210 89
900 1000 174

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int cycle(int x){
int res = 1;
while(x != 1){
if(x % 2 == 1)
x = 3 * x + 1;
else
x /= 2;
res++;
}
return res;
}

int main(){
int x, y;
while(cin >> x >> y){
cout << x << " " << y << " ";
if(x > y)
swap(x, y);
int Max = 0;
for(int i = x; i <= y; ++i)
Max = max(Max, cycle(i));
cout << Max << endl;
}
return 0;
}

进制转换

问题描述

输入一个十进制正整数,然后输出它所对应的八进制数。

输入

输入一个十进制正整数n(1≤n≤106) 。

输出

输出n对应的八进制数,输出在一行。

样例输入

1
10

样例输出

1
12

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;

int main() {
int n;
while (cin >> n) {
int q = n;
int r;
int k = 0;
int num = 0;
while (q >= 8) {
r = q % 8;
q = q / 8;
num = num + r * pow(10, k);
//cout << r<<" "<<pow(8, k) << endl;
k++;
}
cout <<fixed<<setprecision(0)<< num + q * pow(10, k) << endl;
}
return 0;
}

排列问题

问题描述

输入一个可能含有重复字符的字符串,打印出该字符串中所有字符的全排列。

输入

单组测试数据,输入数据是一个长度不超过10个字符的字符串,以逗号结尾

输出

打印出该字符串中所有字符的全排列。以字典序顺序输出,用空格分隔。

样例输入

1
abc,

样例输出

1
abc acb bac bca cab cba

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<string>
#include <algorithm>
#include<iomanip>
using namespace std;

int main() {
char a[12];
char s;
int k;
for (k = 0; k < 12; k++) {
cin >> s;
if (s != ',') {
a[k] = s;
}
else {
break;
}
}
sort(a, a + k);
for (int i = 0; i < k; i++) {
cout << a[i];
}
cout << " ";
while (next_permutation(a, a + k)) {
for (int i = 0; i < k; i++) {
cout << a[i];
}
cout << " ";
}
cout << endl;
return 0;
}

快速幂

问题描述

给定x,求f(x)对100000007取余的结果。

输入

多组测试样例,最多50组。每组测试样例给定一个整数x(1<=x<=25000)

输出

对每个样例,输出一行,代表f(x)对100000007取余的结果。

样例输入

1
2
3
3
4
5

样例输出

1
2
3
33
289
3414

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;

long long binaryPow(long long a, long long b, long long m){
if(b == 0)
return 1;
else if(b % 2 == 1)
return a * binaryPow(a, b - 1, m) % m;
else{
long long num = binaryPow(a, b/2, m) % m;
return num * num % m;
}
}

int main() {
long long x;
while (cin >> x) {
long long sum = 1;
for (int i = 1; i <= x; i++) {
sum = sum + binaryPow(i, i, 100000007);
}
cout << sum % 100000007 << endl;
}
return 0;
}

求第k小

问题描述

给定n(1<=n<=1000000)个元素,求第k小数(1<=k<=n)。

输入

一组样例。第一行输入两个整数n和k。第二行输入n个不同的int范围内的数。

输出

输出一行,输出第k小数。

样例输入

1
2
5 2
1 5 3 2 4

样例输出

1
2

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<string>
#include <algorithm>
#include<iomanip>
using namespace std;
int main() {
int *a;
int n, k;
while (cin >> n >> k) {
a = new int[1000001];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
cout << a[k - 1] << endl;
delete a;
}
return 0;
}

沙子的质量

问题描述

设有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。

输出

合并的最小代价。

样例输入

1
2
4
1 3 5 2

样例输出

1
22

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f;

int n, dp[1001][1001], sum[1001][1001], stone[1001];
int main() {
int i, j, k, t;
cin >> n;
for (i = 1; i <= n; i++) {
cin >> stone[i];
dp[i][i] = 0;
}

for (i = 1; i <= n; i++) {
sum[i][i] = stone[i];
for (j = i + 1; j <= n; j++)
sum[i][j] = sum[i][j - 1] + stone[j];
}

for (int r = 2; r <= n; r++) {
for (i = 1; i <= n - r + 1; i++) {
j = i + r - 1;
dp[i][j] = INF;
for (k = i; k < j; k++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[i][j]);
}
}
}
cout << dp[1][n] << endl;
return 0;
}

最长公共子序列

问题描述

一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad” ,顺次选1,3,5个字符就构成子串” cad” ,现给定两个字符串,求它们的最长共公子串。

输入

第一行两个字符串用空格分开。两个串的长度均小于2000 。

输出

最长子串的长度。

样例输入

1
abccd aecd

样例输出

1
3

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
string s, t;
int m[2001][2001];
int main(){
cin >> s >> t;
s = '0' + s;
t = '0' + t;
int result = 0;
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j < t.length(); j++) {
if (s[i] != t[j]) m[i][j] = max(m[i - 1][j], m[i][j - 1]);
else m[i][j] = max(m[i][j], m[i - 1][j - 1] + 1);
result = max(result, m[i][j]);
}
}
cout << result;
return 0;
}

算法实验1

http://192.168.173.163/JudgeOnline/contest.php?cid=1247

密码:123654

判断字符串是否是手机号码

题目描述

手机号码是一串数字,长度为11位,并且第一位必须是1,现在给出一个字符串,我们需要判断这个字符串是否符合手机格式。

输入

多组测试数据。每组数据输入一个字符串。

输出

若该字符串符合手机号码格式,输出1,否则输出0。

样例输入

1
12345612345

样例输出

1
1

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include<string>
#include<string.h>
using namespace std;
bool judge(string s) {
for (int i = 0; s[i] != '\0'; i++) {
if (s[i]<'0' || s[i]>'9') {
return 0;
}
}
return 1;
}
int main(){
string s;
while (cin >> s) {
bool flag = judge(s);
if (flag==1 && s.length() == 11 && s[0] == '1') {
cout << "1" << endl;
}
else {
cout << "0" << endl;
}
}
return 0;
}

内部收益率

题目描述

在金融中,我们有时会用内部收益率IRR来评价项目的投资财务效益,它等于使得投资净现值NPV等于0的贴现率。换句话说,给定项目的期数$\mathsf{\scriptsize T}$、初始现金流$\mathsf{\scriptsize CF_{0}}$和项目各期的现金流$\mathsf{\scriptsize CF_{1}}$,$\mathsf{\scriptsize CF_{2}}$,$\mathsf{\scriptsize CF_{3}}$….$\mathsf{\scriptsize CF_{T}}$。IRR是下面方程的解:

为了简单起见,本题假定:除了项目启动时有一笔收入(即初始现金流$\mathsf{\scriptsize CF_{0}<0}$)之外,其余各期均能赚钱(即对于所有$\mathsf{\scriptsize i=1,2,…T,CF_{i}}$)。根据定义,IRR可以是负数,但必须大于-1。

输入

输入文件最多包含25组测试数据,每个数据占两行,第一行包含一个正整数$\mathsf{\scriptsize T(1\leq T \leq 10)}$,表示项目的期数。第二行包含$\mathsf{\scriptsize T+1}$个整数:$\mathsf{\scriptsize CF_{0}}$,$\mathsf{\scriptsize CF_{1}}$,$\mathsf{\scriptsize CF_{2}}$,$\mathsf{\scriptsize CF_{3}}$….$\mathsf{\scriptsize CF_{T}}$,其中$\mathsf{\scriptsize CF_{0}<0,0<CF_{i}<10000(i=1,2,…T)}$。$\mathsf{\scriptsize T=0}$表示输入结束,你的程序不应当处理这一行。

输出

对于每组数据,输出仅一行,即项目的IRR,四舍五入保留小数点后两位。

样例输入

1
2
3
4
5
1
-1 2
2
-8 6 9
0

样例输出

1
2
1.00
0.50

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const double esp=1e-6;
int main() {
int n,cf[20];
while(cin >> n) {
for(int i = 0; i <= n; i++){
cin >> cf[i];
}
double l = -1.0, r = 1e6, m;
while(fabs(r-l)>eps) {
m = (r + l)/2;
double f = 1.0, s = 0;
for(int j = 1; j <= n; j++) {
f /= (1+m);
s += cf[j]*f;
}
if(s < -cf[0]) r = m;
else l = m;
}
printf("%.2lf\n", m);
}
return 0;
}

跳台阶

题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

输入

多组测试样例。每组测试样例包含一个整数n。(1<=n<=100)

输出

每组测试样例输出一行,表示青蛙跳上n级台阶的跳法数量.

所得到的结果模1000000007

样例输入

1
2
3
4

样例输出

1
2
3
5

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include<string>
#include<string.h>

using namespace std;
int main() {
int n;
while (cin >> n) {
long long * dp = new long long[n + 1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2])%1000000007;
}
cout << dp[n]<< endl;
delete[] dp;
}
return 0;
}

奶牛的聚会

题目描述

农历新年马上就要到了,奶牛们计划举办一次聚会庆祝新年的到来。但是,奶牛们并不喜欢走太远的路,这会给他们的聚会带来消极情绪,当一头奶牛的消极指数为Wi,他参加聚会所需行走的距离为si,那么他就会给聚会带来Si3*Wi的消极情绪。所有奶牛所在位置都在一条直线上,已知所有奶牛的坐标和消极指数,求如何确定聚会地点,使得所有奶牛给聚会带来的消极情绪之和最小,输出消极情绪之和的最小值。

输入

第一行包含一个整数 Ca(Ca<=20) ,表示有 Ca 组测试数据。对于每组测试数据:第一行包含一个整数n(1<=n<=50000) ,表示奶牛的数量。接下来 n 行每行包含两个浮点数Si和Wi (-106<=Si<=106, 0<Wi<15)。

输出

对于每组测试数据,输出 “Case #c: ans” ,其中c表示测试数据编号,ans表示消极情绪之和的最小值,结果四舍五入为一个整数。

样例输入

1
2
3
4
5
6
7
1
5
0.9 2
1.4 4
3.1 1
6.2 1
8.3 2

样例输出

1
Case #1: 300

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include<string>
#include<string.h>
#include<algorithm>

using namespace std;
double si[50001];
double wi[50001];
int Ca;
int n;
double value(double pos) {
double sum = 0;
for (int i = 0; i < n; i++) {
double d = fabs(si[i] - pos);
sum = sum + d * d * d * wi[i];
}
return sum;
}

int main() {
cin >> Ca;
for (int i = 0; i < Ca; i++) {
cin >> n;
double l=1000001, r=-1000001;
for (int j = 0; j < n; j++) {
cin >> si[j] >> wi[j];
l = min(l, si[j]);
r = max(r, si[j]);
}
while (r - l > 0.0000001) {
double m1 = (l + r) / 2;
double m2 = (m1 + r) / 2;
if (value(m1) > value(m2)) {
l = m1;
}
else {
r = m2;
}
}
long long result = value(l) + 0.5;
cout << "Case #" << i + 1 << ": " << result << endl;

}
return 0;
}

光合作用

题目描述

蒜头是个爱学习的孩子,他总喜欢在生活中做一些小实验,这次蒜头想研究一下光合作用。蒜头的实验材料有如下几样:神奇的种子,普通的纸箱和一些光源。一开始,蒜头将种子均匀的种在了箱子底部,你可以将其看成 X 轴,种子的位置为 X 轴上的点。然后蒜头用纸板将箱子盖住,并在纸板上安装了一些光源(具体见图,顶上的为光源,光源两边与顶部的夹角都为45度,黄色部分为光照,绿色的为植物。)。神奇的种子会在有光的情况下一直向上生长直到没光为止。现在蒜头想知道当实验结束时每颗种子的高度是多少?

20180914132714_44771.png

输入

第一行输入一个整数 T,表示测试数据的组数。

每组数据的第一行是三个整数 n,m,h(1<=n,m<=1e5,0<=m<=1e5,1<=h<=1e4),n表示种子数(编号为1,2…n),m表示光源数,h 表示箱子的高度。

接下来m行,每行一个整数Xi表示第i个光源在顶部的位置。

输出

对于每组测试数据,请输出n行,每行一个数表示第i颗种子的最终高度。

样例输入

1
2
3
4
5
6
7
8
2
7 1 2
4
4 4 1
1
2
3
4

样例输出

1
2
3
4
5
6
7
8
9
10
11
0
0
1
2
1
0
0
1
1
1
1

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;

int light[10010];
int hight[10010];

int main() {
int t;
cin >> t;
while (t--) {
memset(hight, 0, sizeof(hight));
int n, m, h;
cin >> n >> m >> h;
for (int i = 1; i <= m; i++) {
cin >> light[i];
for (int j = h; j > 0; j--) {
int r = light[i] + h - j;
int l = light[i] - h + j;
if (r <= n && hight[r] < j)
hight[r] = j;
if (l >= 0 && hight[l] < j)
hight[l] = j;
}
}
for (int i = 1; i <= n; i++) {
cout << hight[i] << endl;
}
}
return 0;
}
-------------end ♥-------------