【算法课OJ】作业三

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

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

链接：http://192.168.173.163/JudgeOnline/contest.php?cid=1111

密码：123654

问题 A: 单词排序

题目描述

小红学会了很多英文单词，妈妈为了帮小红加强记忆，拿出纸、笔，把 N 个单词写在纸上的一行里，小红看了几秒钟后，将这张纸扣在桌子上。妈妈问小红：“你能否将这 N 个单词按照字典排列的顺序，从小到大写出来？”小红按照妈妈的要求写出了答案。现在请你编写程序帮助妈妈检查小红的答案是否正确。注意：所有单词都由小写字母组成，开头字母全都不相同，单词两两之间用一个空格分隔。

输入

输入包含两行。

第一行仅包括一个正整数N(0<N≤26)。

第二行包含N个单词，表示妈妈写出的单词，两两之间用一个空格分隔。

单个单词长度不超过1010。

输出

输出仅有一行。针对妈妈写出的单词，按照字典排列的顺序从小到大排列成一行的结果，每个单词后带一个空格。

样例输入

4
city boy tree student

样例输出

boy city student tree

题意

如题目描述所示。

思路

Water，可以用string数组存储，sort函数一下输出即可。

代码

#include<iostream>
#include<stdio.h>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    string wo[30];
    scanf("%d",&n);
    for(int i = 0; i < n; i++) cin>>wo[i];
    sort(wo,wo+n);
    cout<<wo[0];
    for(int i = 1; i < n; i++) cout<<" "<<wo[i];
    cout<<endl;
    return 0;
}

问题 B: 求数组的最长递减子序列

题目描述

给定一个整数序列，输出它的最长递减（注意不是“不递增”）子序列。

输入

输入包括两行，第一行包括一个正整数N（N<=1000），表示输入的整数序列的长度。第二行包括用空格分隔开的N个整数，整数范围区间为[-30000,30000]。

输出

输入包括两行，第一行包括一个正整数N（N<=1000），表示输入的整数序列的长度。第二行包括用空格分隔开的N个整数，整数范围区间为[-30000,30000]。

样例输入

8
9 4 3 2 5 4 3 2

样例输出

9 5 4 3 2

题意

DP经典题，类似问题为最长递增子序列。

思路

代码

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn = 1005;
int dp[maxn],last[maxn];
int main()
{
    int n,a[maxn],ans = 0,ansp = 1,ansa[maxn];
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    dp[1] = 1;
    last[1] = -1;
    for(int i = 2; i <= n; i++)
    {
        dp[i] = 1;
        last[i] = -1;
        for(int j = 1; j < i; j++)
        {
            if(a[j] > a[i] && dp[j]+1 > dp[i])
            {
                dp[i] = dp[j]+1;
                last[i] = j;
            }
        }
    }
    for(int i = 1; i <= n; i++)
    {
        if(dp[i] > ans)
        {
            ans = dp[i];
            ansp = i;
        }
    }
    int j = ansp;
    for(int i = ans; ; i--)
    {
        ansa[i] = a[j];
        if(last[j] == -1) break;
        j = last[j];
    }
    for(int i = 1; i <= ans; i++) printf("%d ",ansa[i]);
    return 0;
}

问题 C: 矩形滑雪场

题目描述

zcb喜欢滑雪。他来到了一个滑雪场，这个滑雪场是一个矩形，为了简便，我们用r行c列的矩阵来表示每块地形。为了得到更快的速度，滑行的路线必须向下倾斜。 例如样例中的那个矩形，可以从某个点滑向上下左右四个相邻的点之一。例如24-17-16-1，其实25-24-23…3-2-1更长，事实上这是最长的一条。

输入

第1行:两个数字r，c(1 ≤ r, c ≤ 100)，表示矩阵的行列。第2..r+1行:每行c个数，表示这个矩阵。

输出

仅一行:输出1个整数，表示可以滑行的最大长度。

样例输入

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

样例输出

25

题意

沿着滑行路线，高度必须越来越低。滑行可以选择四个方向：上、下、左、右，求最长路线的长度。

思路

思路一：深搜。

先设三个二维数组：

  1. h[i][j]数组用于存储每个点的高度；
  2. l[i][j]数组用于存储从每一点出发可以得到的最长路线的长度；
  3. visited[i][j]数组用于判断第i行第j列的点是否走过。

我们可以开个4*2的数组dir[i][j]用来存储方向：

  1. 向右：1,0
  2. 向下：0,1
  3. 向左：-1,0
  4. 向上：0,-1

我习惯写一个bool check(int x,int y)函数用来判断当前的点是否在界内

  1. 若是，返回true；
  2. 否则，返回false。

显然，它的判断条件为if(x > 0 && x <= r && y > 0 && y <= c)。

关键，dfs()函数怎么写？

我们这里的dfs()函数和常规的dfs()函数稍有不同，它的流程大概如下：

  1. 假如该点已经访问过了，则不需要做下去了，直接return；
    • if(visited[x][y]) return;
  2. 把当前点的visited置为true；
    • visited[x][y] = true;
  3. 接下来就开始遍历周围的点(xx,yy)，递归调用dfs()，如果发现周围的点更矮，那就让当前l[x][y]和l[xx][yy]做一下max赋给l[x][y]。

最后，l[x][y]中存储的就是从(x,y)出发的最大滑行长度，我们遍历下就可以得到最终答案。

思路二：降维

二维数组，一看就很难的样子，那我们就把它降维打击一下。二维->一维。

怎么实现呢？

  1. 定义结构体node，存储坐标x，y和高度h；
    • 一般在定义后在}和;之间直接定义数组
  2. 写一个bool check(int i,int j)函数，用来判断两点是否为相邻点（上、下、左、右）；

以上为main()函数中的实现做铺垫。

  1. 输入时怎么处理？直接两层for：（比较巧妙）
    • a[n].x = i;
    • a[n].y = j;
    • scanf("%d",&a[n].h);
  2. 输入完后sort()一下，注意在结构体中重载下<，按h从大到小排；
  3. 这样就有点像DP：最长上升子序列问题了
    • 初始化dp[i] = 1
    • 此时，对于第i个结点，前面的结点j的h都更大，那就判断下每个点是否是相邻点（前面定义的check()函数），若是，则执行dp[i] = max(dp[i],dp[j]+1);
    • 最后的ans是dp[i]数组的最大值

代码1（深搜）

#include<iostream>
#include<stdio.h>
#include<string>
#include<algorithm>
using namespace std;
const int maxn = 105;

int r,c;
int h[maxn][maxn],l[maxn][maxn];
bool visited[maxn][maxn];
int dir[4][2] = {1,0, 0,1, -1,0, 0,-1};

bool check(int x,int y)
{
    if(x > 0 && x <= r && y > 0 && y <= c) return true;
    return false;
}
void dfs(int x,int y)
{
    if(visited[x][y]) return;
    visited[x][y] = true;
    for(int i = 0; i < 4; i++)
    {
        int xx = x+dir[i][0];
        int yy = y+dir[i][1];
        if(check(xx,yy) && h[x][y] > h[xx][yy])
        {
            dfs(xx,yy);
            l[x][y] = max(l[x][y],l[xx][yy]+1);
        }
    }
}
int main()
{

    scanf("%d %d",&r,&c);
    for(int i = 1; i <= r; i++)
    {
        for(int j = 1; j <= c; j++)
        {
            scanf("%d",&h[i][j]);
            l[i][j] = 1;
        }
    }
    int ans = -1;
    for(int i = 1; i <= r; i++)
    {
        for(int j = 1; j <= c; j++)
        {
            dfs(i,j);
            ans = max(ans, l[i][j]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

代码2（降维）

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int mod=1e9+7;
const int inf=0x7f7f7f7f;
const int maxn=5e4+50;

struct node
{
    int x,y,h;
    bool operator < (const node &c) const
    {
        return h > c.h;
    }
}a[maxn];
int dp[maxn];
int r,c;
bool check(int i,int j)
{
    if(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y) == 1)  //判断是否是相邻点
        return true;
    return false;
}
int main()
{
    scanf("%d%d",&r,&c);
    int n = 0;
    for(int i = 1; i <= r; i++)
    {
        for(int j = 1;j <= c; j++)
        {
            a[n].x = i;
            a[n].y = j;
            scanf("%d",&a[n].h);
            n++;
        }
    }
    sort(a,a+n);
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        dp[i] = 1;
        for(int j = 0; j < i; j++)
            if(check(i,j))
                dp[i] = max(dp[i],dp[j]+1);
        ans = max(ans,dp[i]);
    }
    printf("%d\n",ans);
    return 0;
}

问题 D: Homework

题目描述

临近开学了，大家都忙着收拾行李准 备返校，但 I_Love_C 却不为此担心!因为他的心思全在暑假作业上：目前为止还未开动。

暑假作业是很多张试卷，我们这些从试卷里爬出来的人都知道，卷子上的题目有选择题、填空题、简答题、证明题等。而做选择题的好处就在于工作量很少，但又因为选择题题目都普遍很长。如果有 55 张试卷，其中 44 张是选择题，最后一张是填空题，很明显做最后一张所花的时间要比前 44 张长很多。但如果你只做了选择题，虽然工作量很少，但表面上看起来也已经做了4/5的作业了。

I_Love_C决定就用这样的方法来蒙混过关，他统计出了做完每一张试卷所需的时间以及它做完后能得到的价值（按上面的原理，选择题越多价值当然就越高咯）。

现在就请你帮他安排一下，用他仅剩的一点时间来做最有价值的作业。

输入

测试数据包括多组。每组测试数据以两个整数 M,N(1<M<20,1<N<10000)开头，分别表示试卷的数目和 I_Love_C 剩下的时间。接下来有 M 行，每行包括两个整数 T,V(1<T<N,1<V<10000)分别表示做完这张试卷所需的时间以及做完后能得到的价值，输入以 0 0 结束。

输出

对应每组测试数据输出 I_Love_C 能获得的最大价值。保留小数点 22 位

提示：float 的精度可能不够，你应该使用 double 类型。

样例输入

4 20
4 10
5 22
10 3
1 2
0 0

样例输出

37.00

题意

就是背包问题。

思路

Greedy。先将所有按性价比（即v[i]/w[i]）排序，则每次选取性价比最高的，直到容量装满。

代码

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 20;
struct Hw
{
    double w,v;
    bool operator < (const Hw &c)const
    {
        return v/w > c.v/c.w;
    }
}hw[maxn];
int main()
{
    int n,c;
    while(~scanf("%d %d",&n,&c))
    {
        if(!n && !c) break;
        for(int i = 0; i < n; i++)
        {
            scanf("%lf %lf",&hw[i].w,&hw[i].v);
        }
        sort(hw,hw+n);
        double cur = double(c);
        double ans = 0;
        for(int i = 0; i < n; i++)
        {

            if(cur >= hw[i].w)
            {
                cur -= hw[i].w;
                ans += hw[i].v;
            }
            else
            {
                ans += cur/hw[i].w*hw[i].v;
                break;
            }
        }
        printf("%.2lf\n",ans);
    }
    return 0;
}

问题 E: 区间包含问题

题目描述

已知 n 个左闭右开区间 [a,b)，对其进行 m 次询问，求区间[l,r]最多可以包含 n 个区间中的多少个区间，并且被包含的所有区间都不相交。

输入

输入包含多组测试数据，对于每组测试数据：

第一行包含两个整数 n ,m (1≤n≤100000,1≤m≤100) 。

接下来 n 行每行包含两个整数 a ,b (0≤a9</sup>) 。

接下来 m 行每行包含两个整数 l ,r (0≤l9</sup>) 。

输出

对于每组测试数据，输出 m 行，每行包含一个整数。

样例输入

4 3
1 3
2 4
1 4
1 2
1 2
1 3
1 4

样例输出

1
1
2

题意

活动安排问题，n个活动，m次query。

思路

Greedy。

输入结束后，把所有活动按结束时间从小到大排序。

定义ans，先给它赋值1。

循环遍历所有活动，符合不相交、不越界就可选。

优化：

  1. 在结束时间超过r后跳出循环。
  2. 二分寻找第一个满足的活动（我没用）。

两种写法（本质上是一样的）：

  1. 用一个j来记录上一个被选的活动；

  2. 每次选活动后直接l = a[i].e;。

千万别写if(e == c.e) return b < c.b;否则必定WA，不知为何。

千万要在结束时间超过r后跳出循环，不然必定TLE。

千万不要用cin、cout，不然好像也是必定TLE。

代码1

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn = 1e5+5;
const int inf = 0x3f3f3f3f;

struct s
{
    int b,e;
    bool operator < (const s&c)const
    {
        //if(e == c.e) return b < c.b;
        return e < c.e;
    }
}a[maxn];
int main()
{
    int n,m,l,r;
    while(~scanf("%d %d",&n,&m))
    {
        for(int i = 0; i < n; i++)
        {
            scanf("%d %d",&a[i].b,&a[i].e);
        }
        sort(a,a+n);
        for(int cas = 0; cas < m; cas++)
        {
            scanf("%d %d",&l,&r);
            int j = 0,ans = 0;
            while(a[j].b < l) j++;
            for(int i = j; i < n && a[i].e <= r; i++)
            {
                if(a[i].b >= a[j].e || i == j)
                {
                    ans++;
                    j = i;
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

代码2

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
struct node
{
    int b,e;
    bool operator < (const node & c)const
    {
        return e < c.e;
    }
}a[maxn];
int main()
{
    int n,m,l,r;
    while(~scanf("%d %d",&n,&m))
    {
        for(int i = 0; i < n; i++)
        {
            scanf("%d %d",&a[i].b,&a[i].e);
        }
        sort(a,a+n);
        for(int cas = 0; cas < m; cas++)
        {
            scanf("%d %d",&l,&r);
            int ans = 0;
            for(int i = 0; i < n; i++)
            {
                if(a[i].b >= l)
                {
                    if(a[i].e <= r)
                    {
                        ans++;
                        l = a[i].e;
                    }
                    else break;
                }
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

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

Powered by Hexo
Theme - Material