Contest3047 - 计科2101~2104算法设计与分析上机作业04

这篇具有很好参考价值的文章主要介绍了Contest3047 - 计科2101~2104算法设计与分析上机作业04。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

问题 A: 繁衍

问题 B: 平面分割 

问题 C: 二分查找(binary)

 问题 D: 求逆序对(deseq)

问题 E: 任务安排问题

 问题 F: 最长单调递增子序列的长度


问题 A: 繁衍

题目描述

有一种生物A,一天就能长大,长大的A每过一天就能生一个小A(刚长大的A会从下一天开始生小A),小A过一天后也会长大。。。以此往复。现在,我们有一个刚出生的小A,问n天后共有多少个长大的生物A

输入

输入仅一行,包含一个自然数 n,0<=n<=46.

输出

长大的A的个数

样例输入 

5

样例输出 

5

提示

sample 2
0
0

模拟一下就好啦

#include<bits/stdc++.h>
#define int long long
using namespace std;

void fun(int n){
    int all=0;
    int young=1;
    int old=0;
    for(int i=1;i<=n;i++){
        all=young+old;
        int temp=old;
        old+=young;
        young=temp;
    }
    cout<<all<<endl;
}

signed main(){
    int n;
    cin>>n;
    fun(n);
}

问题 B: 平面分割 

题目描述

同一平面内有 n(n≤500)条直线,已知其中 p(p≥2)条直线相交于同一点,则这 n 条直线最多能将 平面分割成多少个不同的区域? 

输入

两个整数 n(n≤500)和 p(2≤p≤n)。 

输出

一个正整数,代表最多分割成的区域数目。 

样例输入 

12 5

样例输出 

73

画个图,不难看出,要使分割的区域最大,必然相交的线要最多,

不难看出,当五条线交与一点时,再新增一条线,与之相交的线最多有五条,最多增加5+1块区域

#include<bits/stdc++.h>
#define int long long
using namespace std;

void fun(int n,int k){
    int ans=k*2;
    for(int i=k+1;i<=n;i++){
        ans+=i;
    }
    cout<<ans<<endl;
}

signed main(){
    int n,k;
    cin>>n>>k;
    fun(n,k);
}

问题 C: 二分查找(binary)

题目描述

  给出有 n 个元素的由小到大的序列,请你编程找出某元素第一次出现的位置。(n<=10^6)

输入

 第一行:一个整数,表示由小到大序列元素个数;下面 n 行,每行一个整数;最后一行 一个整数 x,表示待查找的元素;

输出

  如果 x 在序列中,则输出 x 第一次出现的位置,否则输出-1。

样例输入 

5
3
5
6
6
7
6

样例输出 

3

这里不是非得用二分,方法很多,像二维数组,map,甚至遍历,既然它叫我们用二分,那我们就用二分吧

注意判别不存在的情况

#include<bits/stdc++.h>
#define int long long
using namespace std;

vector<int>a;

void fun(int n,int t){
    int l=0,r=n-1;
    int mid=(l+r)/2;
    int ans=0;
    int flag=0;
    while(r-l>1){
        if(a[mid]>t){
            r=mid;
            mid=(l+r)/2;
        }
        else if(a[mid]<t){
            l=mid;
            mid=(l+r)/2;
        }
        else{
            ans=mid;
            flag=1;
            break;
        }
    }
    if(a[r]==t){
        ans=r;
    }
    else if(a[l]==t){
        ans=l;
    }
    else{
        if(!flag){
            cout<<-1<<endl;
            return ;
        }
    }
    while(a[ans]==t){
        ans--;
    }
    cout<<ans+2<<endl;
}

signed main(){
    int n;
    cin>>n;
    int temp;
    for(int i=0;i<n;i++){
        cin>>temp;
        a.push_back(temp);
    }
    int t;
    cin>>t;
    fun(n,t);
}

 问题 D: 求逆序对(deseq)

题目描述

给定一个序列 a1,a2,…,an,如果存在 i<j 并且 ai>aj,那么我们称之为逆序对,求逆序对 的数目。

输入

第一行为 n,表示序列长度,接下来的 n 行,第 i+1 行表示序列中的第 i 个数。

输出

所有逆序对总数。

样例输入 

4
3
2
3
2

样例输出 

3

提示

N<=10^5,Ai<=10^5

分治???太难了,不会,我用set试试

#include<bits/stdc++.h>
#define int long long
using namespace std;

class Mycompare{
    public:
        bool operator()(int v1, int v2){
            return v1 > v2;
        }
};

multiset<int,Mycompare>a;

signed main(){
    int n;
    cin>>n;
    int temp;
    int ans=0;
    for(int i=0;i<n;i++){
        cin>>temp;
        a.insert(temp);
        ans+=distance(a.begin(),a.find(temp));
    }
    cout<<ans<<endl;
}

我擦,时间超了,没道理呀,On*logn鸭。(可能是distance函数太慢了,我去,它的时间复杂度是On,你太baby了)

吐了,老老实实分治吧

有种归并排序的意思

#include<bits/stdc++.h>
#define int long long
using namespace std;

int a[100005];
int b[100005];

int fun(int l,int r){
    if(l==r){
        return 0;
    }
    int mid=(l+r)/2;
    int ans=fun(l,mid)+fun(mid+1,r);
    for(int i=l,j=l,k=mid+1;i<=r;i++){
        if(j>mid){ 
            b[i]=a[k++];
            continue;
        }
        if(k>r){
            b[i]=a[j++];
            continue;
        }
        if(a[j]>a[k]){
            b[i]=a[k++];
            ans+=mid-j+1;
        }
        else{
            b[i]=a[j++];
            continue;
        }
    }
    for(int i=l;i<=r;i++){
        a[i]=b[i];
    }
    return ans;
}

signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    cout<<fun(1,n)<<endl;
}

问题 E: 任务安排问题

题目描述

某个系统中有一个设备,该设备每次只能分配给一个任务使用,且只有当任务结束后才能再分配给另一个任务使用。 假设系统启动时间计为时间0点,预先有一份任务计划表,预定了每个任务的开始时间点和持续时间。 要求设计算法统计出该设备最多能够满足任务计划表中的多少个任务的使用请求。

输入

输入的第一行为一个整数m,表示要计算的用例的个数。 从第二行开始是m个测试用例的输入数据。 每个测试用例的第一行为一个整数n,表示任务计划表中的任务个数,n≤1000。 每个测试用例的第二行为2*n个整数,分别为每个任务的开始时间点和持续时间,整数之间用空格隔开。

输出

要求对每个测试用例输出一行结果,输出结果为该测试用例下,能够满足的最大任务数。

样例输入 

1
11
12 2 2 11 8 4 8 3 6 4 5 4 3 5 5 2 0 6 3 2 1 3

样例输出 

4

 结束时间早的优先

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct info{
    int s;
    int e;
};


bool mysort(info a,info b){
    return a.e<b.e;
}

signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<info>all(n);
        int temp;
        for(int i=0;i<n;i++){
            cin>>all[i].s>>temp;
            all[i].e=all[i].s+temp;
        }
        sort(all.begin(),all.end(),mysort);
        int ti=-1;
        int ans=0;
        for(int i=0;i<n;i++){
            if(ti<=all[i].s){
                ans++;
                ti=all[i].e;             
            }
        }
        cout<<ans<<endl;
    }
}

 问题 F: 最长单调递增子序列的长度

题目描述

请设计算法找出一个整数序列中最长单调递增子序列的长度。

输入

第一行为测试用例个数n,0<n≤1000。 第二行开始,每行为一个测试用例。每个测试用例由一组空格间隔的整数组成,第一个整数m为序列的长度,后面m个整数为序列内容,0<m≤1000。0≤ai≤1000

输出

对每个测试用例,输出其最长单调递增子序列的长度,每个输出占一行。

样例输入 

2
5 1 3 2 4 5
6 3 2 4 5 3 2

样例输出 

4
3

动态规划嘛。。。

注意:dp[i]是表示i之前的最大递增子序列,我们如何求dp[i]呢?

当然是遍历i之前的dp数组,如果a[i]>a[j],那么dp[i]=max(dp[j]+1,dp[i])

dp数组初始化为1嗷 文章来源地址https://www.toymoban.com/news/detail-434686.html

#include <bits/stdc++.h>
using namespace std;
#define int long long

int a[1005];

signed main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        int dp[1005];
        for(int i=0;i<1005;i++){
            dp[i]=1;
        }
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                if(a[i]>a[j]){
                    dp[i]=max(dp[j]+1,dp[i]);
                }
            }
            ans=max(ans,dp[i]);
        }
        cout<<ans<<endl;
    }
}

到了这里,关于Contest3047 - 计科2101~2104算法设计与分析上机作业04的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【多元统计分析】主成分分析——SPSS上机实验【过程+结果分析】

    题目来自何晓群《多元统计分析》(第五版)例题5-3 试利用主成分综合评价全国各地区水泥制造业规模以上企业的经济效益,原始数据来 源于2014 年《中国水泥统计年鉴》,如表5一5所示。 掌握主成分分析的使用方法,提取主成分,计算主成分得分及综合得分。 一、标准化

    2024年02月05日
    浏览(54)
  • 一位计科学长写给 2023 级计算机类和人工智能专业的同学们的程序设计入门指南

    本指南内容较多,但你们若能耐心读完,你们将收获很多…… 欢迎访问作者的主页:Xi Xu’s Home Page 什么是程序设计和程序设计语言? 程序设计 1 (programming),或称编程,是给程序解决出特定问题的过程,软件开发过程中的重要步骤。程序设计方法往往以某种程序设计语言

    2024年02月16日
    浏览(62)
  • 计算机专业考研复试上机算法学习

    这篇博客是博主在准备可能到来的线下上机复试基于王道机试指南的学习,将各道习题链接和代码记录下来,这篇博客权且当个记录。 ps:如果想咨询华南理工大学计算机考研复试的可以CSDN上私聊我,其他学校的我可以尝试?可以交个朋友 1.1 vector动态数组 vector是C加加语言中

    2023年04月09日
    浏览(52)
  • 【机器学习】机器学习上机作业聚类算法

    自编代码实现C均值聚类和FCM聚类,在“IRIS数据集(鸢尾花数据集)”上进行实验,验证所编代码是否正确,并计算准确率。 Iris鸢尾花数|据集:包含花萼长度、花萼宽度、花瓣长度、花瓣宽度四个属性,用于预测鸢尾花种类,标签0、1、2分别表示山鸢尾、变色鸢尾、维吉尼亚鸢

    2024年01月22日
    浏览(44)
  • Java程序设计2023-第三次上机练习

    这次的练习主要是一些类的高阶操作,像继承、接口和内部类这些,但其实还是挺简单的   目录 7-1 jmu-Java-03面向对象基础-04-形状-继承 前言 本题描述 思考 输入样例: 输出样例:  7-3 jmu-Java-04面向对象进阶-03-接口-自定义接口ArrayIntegerStack main方法说明 思考 输入样例 输出样例

    2024年02月05日
    浏览(48)
  • 上机实验四 哈希表设计 西安石油大学数据结构

    (1)实验目的:掌握哈希表的设计方法及其冲突解决方法。 (2)主要内容: 已知一个含有10个学生信息的数据表,为学生“姓名”的拼音,给出此表的一个哈希表设计方案。 要求: 1)建立哈希表:要求哈希函数采用除留余数法,解决冲突方法采用链表法。 2)编写

    2024年02月05日
    浏览(55)
  • 上机实验二 设计单循环链表 西安石油大学数据结构

    (1)实验目的:掌握线性表的链式存储结构;掌握单循环链表及其基本操作的实现。 (2)主要内容:实现单循环链表的初始化、求数据元素个数、插入、删除、取数据元素等操作;用插入法建立带头结点的单循环链表;设计一个测试主函数验证所设计单循环链表的正确性。 掌握线性

    2024年02月07日
    浏览(61)
  • 算法设计与分析--迭代算法

    一、迭代算法简介 二、设计工作步骤 三、迭代--递推法 题目及运行 四、迭代--倒推法 题目及运行 五、总结 算法语言--C语言 迭代算法也称 “辗转法” ,是一种不断用变量的 旧值递推出新值 的解决问题的方法。 迭代算法一般用于数值的计算,是读者早就熟悉的一种算法策

    2024年02月09日
    浏览(49)
  • 【算法分析与设计】算法概述

    数据结构+算法(+设计模式)=程序   理解算法的概念。   掌握算法的计算复杂性概念。   掌握算法复杂性的渐近性态的数学表述。   了解NP类问题的基本概念。   顾名思义,计算(求解)的方法   算法(Algorithm):对特定问题求解步骤的一种描述,是 指令的有

    2024年02月07日
    浏览(36)
  • 【算法分析与设计】贪心算法(下)

      给定带权有向图G =(V,E),其中 每条边的权是非负实数 。另外,还给定V中的一个顶点,称为源。现在 要计算从源到所有其它各顶点的最短路长度 。 这里路的长度是指路上各边权之和 。 这个问题通常称为单源最短路径问题 。   Dijkstra算法是解单源最短路径问题的贪心

    2024年02月08日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包