Skip to content

Latest commit

 

History

History
257 lines (228 loc) · 6.36 KB

牛客网海外专场.md

File metadata and controls

257 lines (228 loc) · 6.36 KB

军训集合

给定 n 个学生，每个人的跑动速度为$v_i$。初始时学生分散在二维操场的各处，现要求学生到各自集合地点紧急集合，求集合的平均时间（存疑），保留三位小数。

  • 输入例
  • 第一行输入学生人数n，后续行每行输入5个整数，起始坐标$x_i$, $y_i$,集合坐标$a_i$, $b_i$,速度$v_i$
2
1 1 2 2 1
1 2 2 1 1
//output
1.414
  • 题解思路
  • 计算各自移动距离后，除以各自速度，加起来取平均
#include <iostream>
#include <cstdio>
#include <cmath>
#include <iomanip>
using namespace std;

int main(){
    int n;
    cin>>n;
    int** stu = new int*[n];
    for(int i = 0; i<n; i++){
        stu[i] = new int[5];
        for(int j = 0; j<5; j++){
            cin>>stu[i][j];
        }
    }

    double sum = 0;
    for(int i = 0; i<n; i++){
        double tmp = (stu[i][0]-stu[i][2])*(stu[i][0]-stu[i][2]) + (stu[i][1]-stu[i][3])*(stu[i][1]-stu[i][3]);
        sum += sqrt(tmp)/stu[i][4];
    }
    sum = sum/n;
    cout.setf(ios::fixed);
    cout<<setprecision(3)<<sum<<endl;
    return 0;
}

视线遮挡时刻

给定 n 个风扇，第$i$个风扇每隔$a_i$秒会挡住视线，初始状态0时刻所有风扇都处于遮挡视线的状态，求前两个视线不被遮挡的整数时刻。若不存在则输出Impossible。

  • 输入例
  • 第一行输入风扇个数n，后续每行输入第$i$个风扇遮挡视线的时刻$a_i$
3
1
2
3
//output
Impossible
2
2
3
//output
1 5
  • 题解思路
  • 接受输入后，对$a_i$排序，若存在1则一定Impossible，因为任何整数都是1的倍数；不存在1则一定存在t=1时所有风扇不遮挡视线，另一个则在$a_i$及后续自然数中寻找一个缺失的质数。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

bool isPrimeNumber(int m){
    int i = 2;
    for(i = 2; i<=m-1; i++){
        if(m%i == 0){
            return false;
        }
    }
    if(i == m){
        return true;
    }
}

int main(){
    int n;
    int ai;
    int result[2] = {0};
    cin>>n;
    if(n<=0){
        cout<<"Impossible"<<endl;
        return 0;
    }

    vector<int> a;
    for(int i = 0; i<n; i++){
        cin>>ai;
        a.push_back(ai);
    }
    sort(a.begin(), a.end());

    if(a[0] == 1){
        cout<<"Impossible"<<endl;
        return 0;
    }else{
        //a[0] != 1
        result[0] = 1;
        //在数组及其延长中找出另一个缺失的质数
        if(a[0] != 2){
            result[1] = 2;
        }else{
            //a[0] == 2 则所有的偶数都要排除
            int m = 3;
            while(result[1] == 0){
                //首先判断m是否为质数，其次判断m在a中是否存在
                if(isPrimeNumber(m)){
                    //m是质数
                    int flag = 0;
                    for(int i = 0; i<n; i++){ //查找可优化
                        if(a[i] == m){
                            flag = 1;
                            m = m+2;
                            break;
                        }
                    }
                    if(flag == 0){
                        result[1] = m;
                    }
                }else{
                    //m不是质数
                    m = m + 2;
                }
            }
        }
        //输出result
        cout<<result[0]<<" "<<result[1]<<endl;
    }

    return 0;
}

极限

$$ \frac{f(x)}{g(x)} = \frac{a_1x^{n-1}+a_2x^{n-2}+\cdots+a_n}{b_1x^{m-1}+b_2x^{m-2}+\cdots+b_m} $$

求$\lim_{n\rightarrow+\infty}\frac{f(x)}{g(x)}$

  • 输入例：第一行输入非负整数$n$, $m$，后续行输入$a_i$, $b_i$, 并确保$a_i$, $b_i$中至少有一个不为0
  • 输出例：若结果为0，则输出“0/1”；若结果为$\infty$，则输出“1/0”；其他结果则输出其最简分数形式；结果为负时需加上 “-” 号
2 2
1 1
2 2
//output
1/2
  • 题解思路
  • 查找$a_i$和$b_j$中第一个不为0的值，表示$f(x)$和$g(x)$中的实际最高阶项，然后比较$n-i$和$m-j$的大小，决定结果是0，$\infty$，分数
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

int calGCD(int a, int b){
    //求最大公约数
    int tmp;
    while(b){
        //辗转相除法
        tmp = b;
        b = a%b;
        a = tmp;
    }
    return a;
}

int main(){
    int n, m;
    cin>>n>>m;
    int* a = new int[n];
    int* b = new int[m];
    int a_i = -1;
    int b_j = -1;
    for(int i = 0; i<n; i++){
        cin>>a[i];
        if(a[i] != 0 && a_i == -1){
            a_i = i;
        }
    }
    for(int j = 0; j<m; j++){
        cin>>b[j];
        if(b[j] != 0 && b_j == -1){
            b_j = j;
        }
    }

    //根据题意a_i和b_j不可能同时为0
    if(a_i == -1 || n-a_i < m-b_j){
        //系数a全为0或分母阶数高，则结果为0/1
        cout<<"0/1"<<endl;
    }else if(b_j == -1 || n-a_i > m-b_j){
        //系数b全为0或分子阶数高，则结果为无穷，但需要判断正负
        if(a[a_i] > 0){
            cout<<"1/0"<<endl;
        }else{
            cout<<"-1/0"<<endl;
        }
    }else if(n-a_i == m-b_j){
        //系数a和系数b均有一项不为0，比较阶数
        //分子分母阶数相等，结果为最高阶系数的最简分数形式
        int gcd = calGCD(abs(a[a_i]), abs(b[b_j]));
        if(a[a_i] * b[b_j] > 0){
            //结果为正数
            cout<<abs(a[a_i])/gcd<<"/"<<abs(b[b_j])/gcd<<endl;
        }else{
            //结果为负数
            cout<<"-"<<abs(a[a_i])/gcd<<"/"<<abs(b[b_j])/gcd<<endl;
        }
    }
    return 0;
}

最短路径和

现有$n$个城市在一个$k$维空间中，规划最多$m$条路径，是城市两两连通，并使得所有路径之和最小，输出最短路径之和，结果保留3位小数

  • 输入例：第一行输入$n, m, k$, 后续每行输入第$i$个城市的坐标
2 100 1
1
2
//output
1.000
  • 题解思路
  • 暂时搁置

删边

节点为n的树，删除k条边后，图的连通块的问题