搜索
您的当前位置：首页正文

6.12-6.14刷题总结

来源：二三娱乐

H - Sale

这个问题要求我们找到Bob能够通过购买电视机销售中获得的最大金额。Bob最多可以携带m台电视机，并希望最大化收益。

解题思路：

对数组进行升序排序，以获取价格按升序排列的顺序。

初始化一个变量"earnedMoney"为0，用于记录总共赚取的金额。

遍历排序后数组的前m个元素：

  • 如果价格为负数，则表示Bob通过购买该电视机可以赚取金额。将价格的绝对值加到"earnedMoney"中。
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> prices(n);
    for (int i = 0; i < n; i++) {
        cin >> prices[i];
    }

    sort(prices.begin(), prices.end());

    int earnedMoney = 0;
    for (int i = 0; i < m; i++) {
        if (prices[i] >= 0) {
            break;
        }
        earnedMoney -= prices[i];
    }

    cout << earnedMoney << endl;

    return 0;
}

I - Laptops

题目要求判断是否存在两台笔记本电脑，其中第一台电脑的价格低于第二台电脑，但第一台电脑的质量高于第二台电脑。

解决这个问题的思路是，首先将输入的笔记本电脑按照价格进行排序，然后遍历排序后的笔记本电脑列表，比较相邻两台电脑的质量。如果存在一对相邻电脑，第一台电脑的质量高于第二台电脑，则满足Alex的观点，输出"Happy Alex"；否则，输出"Poor Alex"。

AC代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<pair<int, int>> laptops;

    for (int i = 0; i < n; i++) {
        int price, quality;
        cin >> price >> quality;
        laptops.push_back(make_pair(price, quality));
    }

    sort(laptops.begin(), laptops.end());

    for (int i = 1; i < n; i++) {
        if (laptops[i].second < laptops[i - 1].second) {
            cout << "Happy Alex" << endl;
            return 0;
        }
    }

    cout << "Poor Alex" << endl;

    return 0;
}

使用一个vector,laptops存储笔记本电脑的价格和质量。接下来，将每台笔记本电脑的价格和质量添加到laptops中。之后，我们对laptops进行排序，按照价格从低到高排序。排序后，我们遍历排序后的laptops列表，从第二台电脑开始，比较相邻两台电脑的质量。如果存在一对相邻电脑，第一台电脑的质量高于第二台电脑，则输出"Happy Alex"表示Alex的观点成立。否则，输出"Poor Alex"表示Alex的观点不成立。

题目大意：

给定一组人，其中一些人可能是撒谎者，总是说谎。其他人总是说实话。每个人都说：“我们中至少有li个撒谎者”。判断人们的陈述是否存在矛盾，如果可能存在，输出撒谎者的数量。如果存在多个可能的答案，则输出其中任意一个。

解题思路：

对于每个测试用例，我们需要找到满足条件的撒谎者数量。我们可以使用一个循环来尝试不同的撒谎者数量，并检查是否存在满足条件的情况。

    • 读取人数n。
    • 读取每个人的陈述li，并将其存储在向量nums中。
    • 初始化变量val为-1，表示尚未找到满足条件的撒谎者数量。
    • 对于撒谎者数量i从0到n进行循环：
      • 初始化变量s为0，表示满足条件的陈述数量。
      • 对于每个人的陈述nums[j]，如果nums[j]大于i，则增加s的值。
      • 如果s等于i，则更新val的值为i，表示找到了满足条件的撒谎者数量。

AC代码：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }

        int val = -1;
        for (int i = 0; i <= n; i++) {
            int s = 0;
            for (int j = 0; j < n; j++) {
                if (nums[j] > i) {
                    s++;
                }
            }
            if (s == i) {
                val = i;
            }
        }

        cout << val << endl;
    }

    return 0;
}

题目要求计算不大于N的正整数中，能表示为a^2 * b^2 * c^2的数量，其中a、b、c是三个不同的质数，且满足a < b < c。

解决这个问题的思路是首先生成一些质数，然后遍历所有可能的组合，计算它们的乘积并判断是否符合条件。

题解：计算满足条件的正整数数量

首先，我们需要一个函数来生成一些质数。可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）来生成不大于INF的所有质数。该算法的基本思想是从小到大遍历每个数，将其所有的倍数标记为非质数。我们使用生成的质数列表来计算满足条件的正整数数量。

#include <stdio.h>

#define INF 300010

int c, prime[INF];
char f[INF];
long long n, ans;

int main() {
    scanf("%lld", &n);
    f[1] = 1;

    for (int i = 2; i < INF; i++) {
        if (!f[i]) {
            prime[++c] = i;
        }
        for (int j = 1; j <= c && (long long)prime[j] * i < INF; j++) {
            f[prime[j] * i] = 1;
        }
    }

    for (int i = 1; i <= c; i++) {
        int x = prime[i];
        if ((long long)x * x * x * x * x > n) {
            break;
        }
        for (int j = i + 1; j <= c; j++) {
            int y = prime[j];
            if ((long long)x * x * y * y * y > n) {
                break;
            }
            for (int k = j + 1; k <= c; k++) {
                int z = prime[k];
                if ((long long)x * x * y * z * z > n) {
                    break;
                } else {
                    ans++;
                }
            }
        }
    }

    printf("%lld\n", ans);

    return 0;
}

题目大意：

给定n个程序员和m个选择选项，每轮投票中，每个程序员选择剩余选项中的一个进行投票。投票结束后，只有得票最多的选项会保留下来，直到只剩下一个选项。判断是否无论程序员如何投票，最终都能选择出唯一的选项，或者投票过程会无限继续下去。

思路：

  1. ，首先判断边界情况，即当人数n为1或选项数m为1时，一定能选择出唯一选项，因为只有一个人或一个选项时必然如此。输出"YES"，。
  2. 如果选项数m大于等于人数n，无论如何投票，最终都无法选择出唯一选项，因为剩下的选项都会得到相同数量的票数。输出"NO"，。
  3. 对于剩下的情况，遍历从2到min(m, sqrt(n) + 1)的数字，判断是否存在n的因子。如果存在因子，则无法选择出唯一选项，因为该因子的倍数会得到相同数量的票数。输出"NO"，
  4. 如果没有找到因子，说明无论如何投票，最终都能选择出唯一选项。输出"YES"。

AC代码：

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, m;
        cin >> n >> m;

        if (n == 1 || m == 1) {
            cout << "YES" << endl;
            continue;
        }
        
        if (m >= n) {
            cout << "NO" << endl;
            continue;
        }

        bool flag = true;
        for (int i = 2; i <= min(m, (int)sqrt(n) + 1); i++) {
            if (n % i == 0) {
                cout << "NO" << endl;
                flag = false;
                break;
            }
        }

        if (flag) {
            cout << "YES" << endl;
        }
    }

    return 0;
}

题目大意：给定一个非负整数数组a，定义函数f(a,x)=[a1 mod x, a2 mod x, ..., an mod x]，其中x为正整数。找出最大的x，使得f(a,x)是一个回文序列。

解题思路：回文序列要求序列正向和反向读取结果相同。为了使得f(a,x)是回文序列，我们需要考虑序列的前半部分和后半部分对应位置的元素的差值。我们遍历数组的前半部分，计算每个位置上的元素差值的最大公约数，最终得到的最大公约数即为满足条件的x。

AC代码：

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> l(n);
        for (int i = 0; i < n; i++) {
            cin >> l[i];
        }

        int s = 0;
        for (int x = 0; x < n / 2; x++) {
            s = gcd(abs(l[x] - l[n - x - 1]), s);
        }

        cout << s << endl;
    }

    return 0;
}

题目大意：这个好难写唉

给定一个无向图，判断该图是否符合克苏鲁（Cthulhu）的定义。符合定义的图应该由三个或更多的以简单环连接起来的有根树组成。

解题思路：

首先，我们需要读取图的顶点数n和边数m，以及图的边信息。然后，我们使用深度优先搜索（DFS）算法遍历图，统计能够访问到的顶点数量。最后，通过判断访问到的顶点数量是否等于图的顶点数n，以及边数m是否等于n，来确定图是否符合克苏鲁的定义。

  1. 定义一个bool数组vis[105]，用于标记顶点是否已访问过，初始时所有顶点均未访问过。
  2. 定义一个邻接表adj[105]，用于存储图的边信息。
  3. 实现一个递归的深度优先搜索函数dfs，用于遍历与当前顶点相连的顶点，并标记访问过的顶点。
    • 在dfs函数中，首先将当前顶点u标记为已访问（vis[u] = true）。
    • 然后，遍历与顶点u相连的所有顶点v，若顶点v未被访问过，则递归调用dfs(v)。
  1. 然后，使用循环读取m行输入，每行包含两个整数x和y，表示存在一条边连接顶点x和顶点y。
    • 在读取边的信息时，需要将边同时添加到x和y对应的邻接表中（adj[x].push_back(y)，adj[y].push_back(x)）。
  1. 调用dfs(1)，从顶点1开始进行深度优先搜索，统计访问到的顶点数量。
  2. 最后，判断访问到的顶点数量t是否等于图的顶点数n，并且边数m是否等于n，根据判断结果输出"NO"或"FHTAGN!"。

AC代码：

#include <iostream>
#include <vector>
using namespace std;

int n, m, t;
bool vis[105];
vector<int> a[105];

void dfs(int u)
{
    vis[u] = true;
    ++t;
    for (int i = 0; i < a[u].size(); i++)
    {
        int v = a[u][i];
        if (!vis[v])
            dfs(v);
    }
}

int main()
{
    int x, y;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    dfs(1);
    if (t == n && m == n)
        cout << "FHTAGN!" << endl;
    else
        cout << "NO" << endl;
}

H - Roadwork

题目大意：

这是一个无限长的街道，从西到东延伸，我们将其视为一个数轴。

在这条街道上有N个道路工程安排。第i个道路工程将从时间Si-0.5到时间Ti-0.5期间阻塞坐标Xi。

有Q个人站在坐标0处。第i个人将在时间Di开始从坐标0出发，以单位速度向正方向行走，并在到达阻塞点时停止行走。

找出每个人行走的距离。

解题思路：

首先，将道路工程的信息存储在结构体数组stus中。每个结构体包含起始时间s、结束时间t和阻塞点坐标x。

然后，按照起始时间和阻塞点坐标的差值对道路工程进行排序，以便后续处理时按照顺序处理。

创建一个优先队列pq，用于存储按照结束时间升序排列的阻塞点坐标和结束时间。

接下来，对于每个人的查询，根据查询时间限制，将满足起始时间和阻塞点坐标差值小于等于查询时间的道路工程信息加入优先队列。

然后，从优先队列中移除结束时间小于等于查询时间的道路工程信息。

最后，判断优先队列是否为空。如果不为空，则输出队列中最小的阻塞点坐标，表示该人的行走距离；如果为空，则输出-1，表示该人行走无限远。

代码实现如下：

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

const int Nx = 2e5+5;

struct Stu {
    int s, t, x;
};

Stu stus[Nx];

struct CompareStu {
    bool operator()(const int& i, const int& j) const {
        return stus[i].s - stus[i].x < stus[j].s - stus[j].x;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    cin >> N >> Q;

    for (int i = 0; i < N; i++) {
        cin >> stus[i].s >> stus[i].t >> stus[i].x;
    }

    int queries[Nx];
    for (int i = 0; i < Q; i++) {
        cin >> queries[i];
    }

    int I[Nx];
    for (int i = 0; i < N; i++) {
        I[i] = i;
    }


    sort(I, I + N, CompareStu());


    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    int idx = 0;

    for (int i = 0; i < Q; i++) {
        int d = queries[i];
        //在第i个人的到达时间之前开始并且在其到达时间之后结束的所有道路工程加入到优先队列pq中。
        while (idx < N && stus[I[idx]].s - stus[I[idx]].x <= d) {
            pq.push(make_pair(stus[I[idx]].x, stus[I[idx]].t - stus[I[idx]].x));
            idx++;
        }
        //将已经结束的道路工程从优先队列中移除。
        while (!pq.empty() && pq.top().second <= d) {
            pq.pop();
        }
        if (!pq.empty()) {
            cout << pq.top().first << endl;
        } else {
            cout << -1 << endl;
        }
    }

    return 0;
}

H - 题目8

思路：首先找到最小生成树权值最大的边S，然后去构建所有权值不超过S的最大生成树

AC

#include <iostream>
#include <vector>
using namespace std;

const int mod = 1000000007;

long long powMod(long long base, long long exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

long long nCk(int n, int k) {
    long long under = 1;
    for (int x = 1; x <= k; x++) {
        under = (under * x) % mod;
    }
    long long over = 1;
    for (int x = n; x >= n - k + 1; x--) {
        over = (over * x) % mod;
    }
    long long invUnder = powMod(under, mod - 2);
    return (invUnder * over) % mod;
}

vector<int> primeFactors(int num) {
    vector<int> exps;
    int pushval = 0;
    while (num % 2 == 0) {
        pushval += 1;
        num = num / 2;
    }
    exps.push_back(pushval);

    int i = 3;
    while (i * i <= num) {
        pushval = 0;
        while (num % i == 0) {
            pushval += 1;
            num = num / i;
        }
        if (pushval > 0) {
            exps.push_back(pushval);
        }
        i += 2;
    }

    if (num > 2) {
        exps.push_back(1);
    }

    return exps;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> exps = primeFactors(M);
    long long ans = 1;
    for (int i = 0; i < exps.size(); i++) {
        int e = exps[i];
        ans = (ans * nCk(e + N - 1, N - 1)) % mod;
    }
    cout << ans << endl;

    return 0;
}

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

Copyright © 2019-2025 yule263.com 版权所有
湘ICP备2023023988号-1

Top