首页 > 其他分享 >机试真题重点题目-2017

机试真题重点题目-2017

时间：2024-03-21 11:23:53浏览次数：32  
标签：std dist 真题 int sum 机试 2017 include const

A：连续字母

#include <iostream>
#include <string.h>
#include <algorithm>

using namespace std;

const int N = 110;
int n;
char str[N];

int main()
{
    cin >> n;
    while(n --) {
        scanf("%s", str + 1);
        
        int cnt = 0, MAX = 0;
        int len = strlen(str + 1);
        
        cnt ++;//第一个字符一定算一个 
        
        for(int i = 2; i<=len; i++) {
            if(str[i] == str[i - 1]){
                cnt ++;
                MAX = max(cnt, MAX);
            }
            else{
                cnt = 1; //从不同字符处重新开始计，肯定也包括它 
            }
        }
        cout << MAX << endl;
    }
    return 0;    
}
/*
3
AAAABBCDHHH
ISDHFSHFDAASDIAHSD
EEEEEEE
输出：
4
2
7 
*/
View Code

B：疯狂的快递哥

考察：单源最短路径

Dijkstra解决：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110, M = 10010, INF = 0x3f3f3f3f;
int n, m;//点，边
int g[N][N], dist[N];
bool st[N];
int pre[N]; //存储前驱结点 

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for(int i = 0; i<n; i++) {
        int t = -1;
        for(int j = 1; j<=n; j++) {
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        st[t] = true;
        
        for(int j = 1; j<=n; j++) {
            if(dist[j] >= dist[t] + g[t][j])
                pre[j] = t;
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    if(dist[n] == INF) return INF;
    else return dist[n];
}

void dfs(int u)
{
    if(u == 1) {
        cout << u << " ";
        return;
    }
    dfs(pre[u]);
    cout << u << " ";
}

int main()
{
    memset(g, 0x3f, sizeof g);
    cin >> n >> m;
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    
    //初始化前驱数组 
    for(int i = 1; i<=n; i++)
        pre[i] = i;
    
    int ans = dijkstra();
    dfs(n);
    
    return 0;
}
/*
5 6
1 2 1
2 3 5
3 4 5
3 5 10
1 3 2
4 5 4

输出：1 3 4 5

pre[n]:1 1 1 3 4 
*/
View Code

 

C：subrange_sum

与2019华为OD机试题类似，但华为是要求正整数，用滑动窗口解决，这里却有负数，似乎只能暴力解

华为OD版：

考察：滑动窗口

#include <iostream>

using namespace std;

const int N = 1000010;
int a[N];
int c, x;

int main()
{
    cin >> c >> x;
    for(int i = 0; i<c; i++) cin >> a[i]; 
    
    int l = 0, r = 0;
    long long count = 0;
    int sum = 0;
    
    while(r < c) {
        //从左边开始加 
        sum += a[r];
        while(sum >= x) { //只要sum大于x就符合要求，算作一个区间 
            if(sum >= x) {
                //当前sum已经大于x了，往后越大的数更成立 
                count += c - r;
            }
            sum -= a[l]; //保证区间是连续的，不会断开 
            l ++;
        }
        //当前sum不大于x时，r继续右移扩大区间 
        r ++;
    }
    cout << count << endl;
    return 0;
}
View Code

本题暴力版：

#include <iostream>

using namespace std;

const int N = 1000010;
int a[N];
int c, x;

int main()
{
    cin >> c >> x;
    int cnt = 0, sum = 0;
    
    for(int i = 0; i<c; i++) {
        cin >> a[i]; 
        if(a[i] >= x) //每个数自身就是一个区间 
            cnt ++;
    }
    
    for(int i = 0; i<c - 1; i++) {
        for(int j = i + 1; j<c; j++) {
            sum += a[i] + a[j];
            if(sum >= x) cnt ++;
        }
        sum = 0;
    }
    cout << cnt << endl;
    return 0;
}
View Code

 

D：进制转换

#include <iostream>

using namespace std;

long long x;

void Convert(int x, int n)
{
    if(n < 16)
    {
        if(x == 0) return;
        else {
            Convert(x / n, n);
            cout << x % n;
        }
    }
    else {
        if(x == 0) return;
        else {
            Convert(x / n, n);
            int re = x % n;
            if(re > 9) {
                char ch = re - 10 + 'A';
                cout << ch;
            } 
            else cout << re;
        }
    }
}

int main()
{
    cin >> x;
    Convert(x, 2);
    cout << endl;
    Convert(x, 8);
    cout << endl;
    Convert(x, 16);
    return 0;
}
View Code

 

E：疯狂的修路哥

考察：最小生成树

本题是用坐标形式给出的，可以先转换为点的编号，再用模板解决

#include <iostream>
#include <math.h>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;
const double INF = 1.0 / 0.0;
int n;

struct Point{
    int x, y, idx;
}points[N];

double g[N][N]; 
double dist[N] = {INF};
bool st[N];

double prim()
{
    for(int i = 1; i<=n; i++) dist[i] = INF;
    
    dist[1] = 0;
    double res = 0;
    
    for(int i = 0; i<n; i++) {
        int t = -1;
        for(int j = 1; j<=n; j++) {
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }
        st[t] = true;
        if(i && dist[t] == INF) return INF;
        if(i) res += dist[t];
        
        for(int j = 1; j<=n; j++)
            dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}


int main()
{
    cin >> n;
    
    //初始化 浮点型不能用memset! 
    for(int i = 1; i<=n; i++)
        for(int j = 1; j<=n; j++) 
            g[i][j] = INF;

    
    for(int i = 1; i<=n; i++)
    {
        double x, y;
        cin >> x >> y;
        points[i].x = x, points[i].y = y;
        points[i].idx = i; //每个点的编号 
    }
    
    //计算距离
    for(int i = 1; i<=n; i++) {
        for(int j = 1; j<=n; j++) {
            double dx = points[i].x - points[j].x;
            double dy = points[i].y - points[j].y;
            double c = sqrt(dx * dx + dy * dy);
            int a, b;
            //将坐标转换为编号表示 
            a = points[i].idx, b = points[j].idx;
            cout << "a = " << a << " b = " << b << " c = " << c << endl;
            g[a][b] = g[b][a] = min(g[a][b], c);
            cout << "a = " << a << " b = " << b << " g[a][b] = " << g[a][b] << endl;
        }
    } 
         
    double res = prim();
    if(res == INF) cout << "impossible" << endl;
    else printf("%.2lf", res);
    return 0;
}
/*
4
0 0
100 0
0 1
1 100
输出：200.01 
*/
View Code

 

F：最长回文子序列

考察：动态规划

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;

const int N = 310;
char str[N];
int dp[N][N];

int main()
{
    cin >> str + 1;
    int len = strlen(str + 1);
    //统一转为小写字母
    for(int i = 1; i<=len; i++)
        if(str[i] >= 'A' && str[i] <= 'Z' )
            str[i] += 32; //A与a相差32 
            
    //初始化dp状态数组
    //dp[i][j]:str[i ~ j]的最长回文子序列长度
    for(int i = 1; i<=len; i++) dp[i][i] = 1;
    /*
    i <= j
    str[i] == str[j]时：dp[i][j] = dp[i+1][j-1] + 2,掐头去尾
    str[i] != str[j]时：dp[i][j] = max(dp[i+1][j], dp[i][j-1]); 
    计算dp[i][j]时要计算dp[i + 1][]，即i处要用到i+1的数据，所以i要从大到小
    同理，j处要用到j-1的数据，故j要从小到大 
    */
    for(int i = len; i>=0; i--) {
        for(int j = i + 1; j<=len; j++) {
            if(str[i] == str[j])
                dp[i][j] = dp[i + 1][j - 1] + 2;
            else 
                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
        }
    } 
    cout << dp[1][len] << endl;
    return 0;
}
/*
ABCdca
输出：5 
*/
View Code

 

标签：std,dist,真题,int,sum,机试,2017,include,const
From： https://www.cnblogs.com/GeekDragon/p/18085941

相关文章

  • 2024. 1华为od机试C卷【传递悄悄话】Python
    题目给定一个二叉树，每个节点上站着一个人，节点数字表示父节点到该节点传递悄悄话需要花费的时间。初始时，根节点所在位置的人有一个悄悄话想要传递给其他人，求二叉树所有节点上的人都接收到悄悄话花费的时间。输入描述0920-1-1157-1-1-1-132注：-1表示空节点输出......
  • 复试C++15真题_程序设计2_递归_输入字符串倒序转整形
    编写一个递归函数，功能为：输入一个字符串，输出一个整数值。例如输入 "1a2xcz34,5a!6" , 输出654321。一开始想不明白怎么写递归，于是我写了迭代的函数。意识到，递归的过程就是实现了迭代的循环，而循环内的操作本质没有太大差别。于是就写出来了：#include<iostream>usingnam......
  • 复试C++14真题 看程序写结果5 虚函数、继承 易错？
    复试C++14真题 看程序写结果5  虚函数、继承#include<iostream>usingnamespacestd;classA{public:virtualvoidprint(){cout<<"A::print"<<endl;}//voidprint(){cout<<"A::print"<<endl;}};classB:public......
  • 计算机选择题真题(大全)
    计算机系统(132)计算机完成一条指令所花费的时间称为一个（指令周期）顺序程序不具有（并发性）总线带宽是指总线的（数据传输率）一进程已获得除CPU以外的所有所需运行资源，经调度分配CPU给它后，该进程将进入（运行状态）CPU芯片内部连接各元件的总线是（内部总线）如果一个进程在运行时因某种原因......
  • 华为OD机试真题-推荐多样性-2024年OD统一考试（C卷）
    题目描述：推荐多样性需要从多个列表中选择元素，一次性要返回N屏数据（窗口数量），每屏展示K个元素（窗口大小），选择策略：1. 各个列表元素需要做穿插处理，即先从第一个列表中为每屏选择一个元素，再从第二个列表中为每屏选择一个元素，依次类推2. 每个列表的元素尽量均分为N份，如果不够N个，也......
  • P3714 [BJOI2017] 树的难题
    fromxcs题意：给定一棵\(n\)个节点的树，树根为\(1\)，每个点有一个编号，每条边有一个边权。定义\(dep(x)\)表示一个点到根简单路径上边权的和，\(lca(x,y)\)表示\(x,y\)节点在树上的最近公共祖先。共\(m\)组询问，每次询问给出\(l,r\)，求对于所有点编号的二元组\((i,j)\)......
  • 【蓝桥杯选拔赛真题70】python最短路径和 第十五届青少年组蓝桥杯python选拔赛真题 算
    目录python最短路径和一、题目要求1、编程实现2、输入输出二、算法分析三、程序编写四、程序说明五、运行结果六、考点分析七、 推荐资料1、蓝桥杯比赛2、考级资料3、其它资料python最短路径和第十五届蓝桥杯青少年组python比赛选拔赛真题一、题目要求（注：i......
  • 分月饼【华为OD机试JAVA&Python&C++&JS题解】
    一.题目-分月饼中秋节，公司分月饼，m个员工，买了n个月饼，m<=n，每个员工至少分1个月饼，但可以分多个，单人分到最多月饼的个数是Max1，单人分到第二多月饼个数是Max2，Max1-Max2<=3，单人分到第n-1多月饼个数是Max(n-1)，单人分到第n多月饼个数是Max(n)，Max(n-1)–Max(n)<=3,问有多少......
  • 算法沉淀——贪心算法三（leetcode真题剖析）
    算法沉淀——贪心算法三01.买卖股票的最佳时机II02.K次取反后最大化的数组和03.按身高排序04.优势洗牌01.买卖股票的最佳时机II题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/给你一个整数数组prices，其中prices[i]表示某支股票......
  • 亲子游戏【华为OD机试JAVA&Python&C++&JS题解】
    题目描述宝宝和妈妈参加亲子游戏，在一个二维矩阵（NN）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99