【算法课OJ】作业二

Author Avatar
source. 9月 15, 2018
  • 在其它设备中阅读本文章

决定程序优雅的是人，而不是语言。

链接：http://192.168.173.163/JudgeOnline/contest.php?cid=1107
密码：123654

问题 A: 进制转换

题目描述

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

输入

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

输出

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

样例输入

10

样例输出

12

题意

输入十进制，输出八进制。

思路

Water，可直接用cout<<oct<<n<<endl;，也可以printf("%o\n",n);，也可以自己写一个转换进制的递归函数。

代码1

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    printf("%o\n",n);
    //cout<<oct<<n<<endl;
    return 0;
}

代码2

#include<iostream>
using namespace std;
char* tbl="0123456789ABCDEF";
void f(int dec,int base)
{
    if(dec)
    {
        f(dec/base,base);
        cout<<tbl[dec%base];
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    f(n,8);
    printf("\n");
    return 0;
}

问题 B: 排列问题

题目描述

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

输入

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

输出

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

样例输入

abc,

样例输出

abc acb bac bca cab cba

题意

去掉,后打印字符串的全排列（有可能有重复字符）。

思路

递归。

  1. （TLE）用一个set（去重+排序）保存结果，递归交换第i位和第j位（递归后还得把它们换回去，有点像dfs）。

c++中的std::set，是基于红黑树的平衡二叉树的数据结构实现的一种容器，因为其中所包含的元素的值是唯一的，因此主要用于去重和排序。

  1. 但是，研表究明，上述代码会超时！原因可能是后台数据量过大、存在太多冗余计算、用了cin、cout。后来，惊奇发现语言自带这种函数，叫做next_permutation()，震惊！后来为了避免重复造轮子（其实是懒得自己模拟捂脸），就用了这函数。

注意：这题用cin、cout好像一定TLE，所以用stdio吧！

代码1（TLE）

//set消重
#include<iostream>
#include<stdio.h>
#include<set>
using namespace std;

string str;
int len;
set<string> s;

void f(int i)
{
    if(i != len)
    {
        s.insert(str);
        for(int j = i; j < len; j++)
        {
            swap(str[i],str[j]);
            f(i+1);
            swap(str[i],str[j]);
        }
    }
}
int main()
{
    cin>>str;
    len = str.length() - 1;
    str.resize(len);
    f(0);
    set<string>::iterator it = s.begin();
    cout<<*it;
    it++;
    for(;it != s.end(); it++)
        cout<<" "<<*it;
    cout<<endl;
    return 0;
}

代码2

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

int main()
{
    char str[15];
    scanf("%s",str);
    int len = strlen(str)-1;
    str[len] = '\0';
    sort(str,str+len);
    printf("%s",str);
    while(next_permutation(str,str+len))
    {
        printf(" %s",str);
    }
    printf("\n");
    return 0;
}

问题 C: 快速幂

题目描述

img

输入

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

输出

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

样例输入

3
4
5

样例输出

33
289
3414

题意

如题目描述所示，就是输入x求

的结果输出。

思路

开一个足够大的数组存储

输出的时候+1即可。

既然题目是“快速幂”，那就愉快地用快速幂模板吧！

初始化：

f[0] = 0；

f[i] = f[i-1] + poww(i,i)

注意，这样可能会溢出，所以要利用数论知识

改写成

f[0] = 0;

f[i] = (f[i-1]%mod+poww(i,i)%mod)%mod;

注意：最后输出+1后还要再% mod！

代码

#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
const ll mod = 1e8 + 7;
const int MAXN = 25005;
ll f[MAXN];
ll poww(ll x,ll n)
{
    ll ans = 1;
    while(n)
    {
        if(n & 1)
            ans = ans * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return ans%mod;
}
int main()
{
    f[0] = 0;
    for(ll i = 1; i < MAXN; i++)
    {
        f[i] = (f[i-1]%mod+poww(i,i)%mod)%mod;
    }
    ll n;
    while(~scanf("%lld",&n))
        printf("%lld\n",(f[n]+1)%mod);
    return 0;
}

问题 D: 求第k小

题目描述

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

输入

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

输出

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

样例输入

5 2
1 5 3 2 4

样例输出

2

题意

如题目描述所示。

思路

最简单的代码：sort()函数排序后输出a[k-1]。

注意：数组太大，不应该在main()中开，而应在全局开。

代码

#include<iostream>
#include<stdio.h>
#include<algorithm>
const int MAXN = 1000000;
using namespace std;
int n,k,a[MAXN];
int main()
{

    cin>>n>>k;
    for(int i = 0; i < n; i++) scanf("%d",&a[i]);
    sort(a,a+n);
    printf("%d\n",a[k-1]);
    return 0;
}

问题 E: 沙子的质量

题目描述

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

题意

合并时由于选择的顺序不同，合并的总代价也不相同，找出总代价小的方案。

思路

dp。

开一个一维数组sum，用于存储前缀和。

开一个二维数组dp，dp[j][i]代表合并j到i的代价，一开始把它全部置为足够大的数，dp方程：

  1. dp[i][i] = 0;
  2. dp[j][i] = min(dp[j][i],dp[j][k]+dp[k+1][i]+sum[i]-sum[j-1]);

解释：

  1. 只有一堆沙子，则不需要合并，故代价为0；
  2. 三重循环：
    • i（从 2 到 n）：合并右界
    • j（从 i 到 1，逆序）：合并左界
      • 为什么要逆序呢？
      • 比如说，求出(2,3)才能求(1,3)
    • k（从 j 到 i）：分界点
  3. dp[j][k]表示合并从 j 到 k 的沙子所需要的代价；
  4. dp[j][k]表示合并从 k 到 i 的沙子所需要的代价；
  5. sum[i]-sum[j-1]前缀和相减代表从j到i堆的沙子数量之和；

这样子，最后的答案就是dp[1][n]，输出即可。

代码1

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAXN = 305;
int dp[MAXN][MAXN];
int main()
{
    int n,i,j,k,a[MAXN],sum[MAXN] = {0};
    memset(dp,1,sizeof(dp));
    cin>>n;
    for(i = 1; i <= n; i++)
    {
        scanf("%d",&a[i]);
        sum[i] = sum[i-1]+a[i];
        dp[i][i] = 0;
    }
    for(i = 2; i <= n; i++)
    {
        for(j = i; j >= 1; j--)
        {
            for(k = j; k <= i; k++)
                dp[j][i] = min(dp[j][i],dp[j][k]+dp[k+1][i]+sum[i]-sum[j-1]);
        }
    }
    printf("%d\n",dp[1][n]);
    return 0;
}

代码2

按课本MatrixChain的代码修改了下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 305;
int dp[maxn][maxn];
int sum[maxn];
int main()
{
    int n,a[maxn];
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d",&a[i]);
        dp[i][i] = 0;
        sum[i] = sum[i-1]+a[i];
    }
    for(int r = 2; r <= n; r++)
    {
        for(int i = 1; i <= n-r+1; i++)
        {
            int j = i+r-1;
            dp[i][j] = dp[i+1][j]+sum[j]-sum[i-1];
            for(int k = i; k < j; k++)
            {
                int t = dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
                dp[i][j] = min(dp[i][j],t);
            }
        }
    }
    printf("%d\n",dp[1][n]);
    return 0;
}

建议参见

【CSDN】动态规划-区间最值问题-沙子合并

问题 F: 最长公共子序列

题目描述

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

输入

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

输出

最长子串的长度。

样例输入

abccd aecd

样例输出

3

题意

输入两个字符串a和b，求它们最长公共子序列长度。

思路

dp经典题。

开一个二维数组dp，然后双重循环，dp方程：

  1. 如果a[i-1] == b[j-1]的话，dp[i][j] = dp[i-1][j-1]+1;
  2. 否则（不一样，取大的），dp[i][j] = max(dp[i-1][j],dp[i][j-1]);

这样子，最后的答案就是dp[lena][lenb]，输出即可。

代码

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int MAXN = 2005;
int dp[MAXN][MAXN];
int main()
{
    int lena,lenb,i,j;
    char a[MAXN],b[MAXN];
    cin>>a>>b;
    lena = strlen(a);
    lenb = strlen(b);
    for(i = 1; i <= lena; i++)
    {
        for(j = 1; j <= lenb; j++)
        {
            if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1]+1;
            else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
        }
    }
    printf("%d\n",dp[lena][lenb]);
    return 0;
}

结语

dp真的难呀。

居然没有原以为有的二分、归并、快排的题，出乎意料。

可能教学进度不一样，所以出现了2题dp题，然而我们dp才开始了个头。

本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 ComyDream 。
本文链接：http://comydream.github.io/2018/09/15/algorithm-homework-2/

Powered by Hexo
Theme - Material