CUMTOJ算法作业一

算法 C++ 算法

发布时间 : 2019-10-23 21:15

阅读 :

问题 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>
using namespace std;
int main()
{
    long long D, N;
    while(cin >> D, cin >> N)
    {
    	if(D == 0)
    		if(N == 100)
				cout << 101 << endl;
			else
				cout << N << endl;
    	else if(D == 1)
    		if(N == 100)
				cout << 10100 << endl;
			else
				cout << (N * 100) << endl;
    	else if(D == 2)
    		if(N == 100)
				cout << 1010000 << endl;
			else
				cout << (N * 10000) << endl;
	}
    return 0;
}

问题 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>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int m, i, j, k;
    for(m = 0; m < n; m++)
    {
        int max = 0;
        int s;
        cin >> s;
        for(i = s / 350; i >= 0; i--)
        {
            for(j = (s - i * 350) / 200; j >= 0; j--)
            {
                for(k = (s - i * 350 - j * 200) / 150; k >= 0; k--)
                {
                    int p = i * 350 + j * 200 + k * 150;
                    if(p > max)
                    max = p;
                }
            }
        }
        cout << s - max << endl;
    }
    return 0;
}

问题 E: 进制转换

题目描述

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

输入

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

输出

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

样例输入

10

样例输出

12

代码

#include <iostream>
using namespace std;
int main()
{
	int a, b, i[100], n = 1, k = 0;
	cin >> a;
	if(a >= 8)
	{
		while(a > 0)
		{
			i[n] = a % 8;
			a = a / 8;
			n++;
			k++;
		}
		while(k >= 1)
		{
			cout << i[k];
			k--;
		}
	} 
	else
	{
		b = a;
		cout << b;
	}
	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>
using namespace std;
int a[1000001];
int main()
{
	void swap(int &a,int &b);
	void select(int a[],int p,int r);
	int partition(int a[], int p, int r);
	int n, k;
	cin >> n;
	cin >> k; 
	for(int i = 0; i < n; i++)
		cin >> a[i];
	select(a, 0, n-1);
	cout << a[k - 1] << endl;
	return 0;	
}
void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}
 
int partition(int a[], int p, int r)
{
	int x = a[r];
	int middle = p;
	int j;
	for(j = p; j < r; j++)
	{
		if(a[j] < x)
		{
			if(j != middle)
			  swap(a[middle], a[j]);
			middle++;
		} 
	}
	swap(a[middle], a[j]);
	return middle;
}
 
void select(int a[],int p,int r)
{
	if(p < r)
	{
		int q = partition(a, p, r);
	    select(a, p, q - 1);
		select(a, q + 1, r);	
	}
}

问题 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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <stdlib.h>
using namespace std;
const int maxn = 305;
int dp[maxn][maxn], sum[maxn], n;
int main()
{
	int dfs(int l, int r);
	cin >> n;
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i <= n; ++i)
	{
		int x;
		cin >> x;
		sum[i] = sum[i - 1] + x;
	}
	cout << dfs(1, n) << endl;
	return 0;
}
int dfs(int l, int r)
{
	int min(int x, int y);
	if(l == r)
	    return 0;
	if(l + 1 == r)
	    return sum[r] - sum[l - 1];
	if(dp[l][r] != -1)
	    return dp[l][r];
	int ans = 2e9;
	for(int i = l; i < r; ++i)
		ans = min(ans, dfs(l, i) + dfs(i + 1, r));
	ans += sum[r] - sum[l - 1];
	dp[l][r] = ans;
	return ans;
}
int min(int x, int y)
{
	return x > y ? y : x;
}

问题 J: 最长公共子序列

题目描述

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

输入

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

输出

最长子串的长度。

样例输入

abccd aecd

样例输出

3

代码

#include <iostream>
#include <string>
using namespace std;
const int max_num = 2000;
int main()
{
	int max(int x, int y);
    string s1, s2;
    int m, n, i, j;
    cin >> s1;
	cin >> s2;
    m = s1.length();
	n = s2.length();
    int c[max_num][max_num] = { 0 };
    for(i = 1; i <= m; i++)
    {
        for(j = 1; j <= n; j++)
        {
            if(s1[i - 1] == s2[j - 1])
                c[i][j] = c[i - 1][j - 1] + 1;
            else
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
        }
    }
    cout << c[m][n] << endl;
    return 0;
}
int max(int x, int y)
{
	return x > y ? x : y;
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达，可以邮件至 xingshuaikun@163.com。