【牛客小白月赛69】题解与分析A-F【蛋挞】【玩具】【开题顺序】【旅游】【等腰三角形(easy)】【等腰三角形(hard)】

比赛传送门:https://ac.nowcoder.com/acm/contest/52441

感觉整体难度有点偏大。

? 作者:Eriktse
? 简介:19岁,211计算机在读,现役ACM银牌选手?力争以通俗易懂的方式讲解算法!❤️欢迎关注我,一起交流C++/Python算法。(优质好文持续更新中……)?
? 个人博客:www.eriktse.com

A-蛋挞

签到题。

只需比较a / ba % b的大小即可。注意开longlong。

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

signed main()
{
    int a, b;scanf("%lld %lld", &a, &b);
    if(a / b < a % b)printf("niuniu eats more than others");
    else if(a / b > a % b)printf("niuniu eats less than others");
    else printf("same");
    return 0;
}

B-玩具

排序贪心。

因为我们要将n个玩具全部买下,所以我们免单的玩具价格越高越好,我们将整个数组排升序后从后往前两个两个拿,且只付更高价格的玩具的钱

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

const int maxn = 1e6 + 9;
int a[maxn];
signed main()
{
    int n;scanf("%lld", &n);
    for(int i = 1;i <= n; ++ i)scanf("%lld", a + i);
    sort(a + 1,a + 1 + n);
    
    int ans = 0;
    for(int i = n;i >= 1; -- i)
    {
        ans += a[i];
        i --;
    }
    printf("%lld\n", ans);
    return 0;
}

C-开题顺序

dfs。

题目数量比较小,我们可以枚举出所有的开题顺序,然后计算出最终分数取大即可,注意剪枝,当时间超过t的时候可以直接结束,此时的分数已经无效了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 15;
int a[maxn], b[maxn], c[maxn], x[maxn], y[maxn];
int n, t, p;

bitset<maxn> vis;

//当前正在选第dep道题
int dfs(int dep, int ti, int sc)
{
    if(ti > t)return 0;//当累计做题时间已经超过了t说明比较已经结束了
    if(dep == n + 1)return sc;
    
    int res = sc;
    
    for(int i = 1;i <= n; ++ i)
    {
        if(vis[i])continue;
        //切了第i道题
        ti += x[i];
        vis[i] = true;
        res = max(res, dfs(dep + 1, ti, sc + max(c[i], a[i] - ti * b[i] - y[i] * p))); 
        vis[i] = false;
        ti -= x[i];
    }
    return res;
}

signed main()
{
    scanf("%lld %lld %lld", &n, &t, &p);
    for(int i = 1;i <= n; ++ i)
        scanf("%lld %lld %lld %lld %lld", a + i, b + i, c + i, x + i, y + i);

    printf("%lld\n", dfs(1, 0, 0));
    return 0;
}

D-旅游

最小生成树(并查集) + 二分。

首先我们知道要使得所有点互联,且边权尽可能小,应该建立一棵最小生成树,然后修复树中所有的边即可。

然后国家帮忙修复边权<=p的部分,那么我们可以想到,当p较大时,牛牛的资金肯定可以足够修复剩下的,当p较小时,牛牛要修的路就比较多,就修不了。

所以“y=牛牛能否修复剩下的路”是随着p单调的,当p大时,y=1,当p小时,y=0,我们要做的就是找到那个交界处,二分即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9;

map<int, int> mp[maxn];

struct Edge
{
    int x, y, w;
};

int pre[maxn];
//路径压缩的并查集
int root(int x){return pre[x] = (pre[x] == x ? x : root(pre[x]));}

int a[maxn];//a里面存放最小生成树的所有边权
int n, m, c, cnt;

bool check(int k)
{
    int res = 0;//贪心求最小代价,数组逆序点乘
    for(int i = cnt, j = 0;i >= 1; -- i)
    {
        if(a[i] <= k)break;//<=k的部分国家买单不用考虑了
        res += (++ j) * a[i];
    }
    return res <= c;
}

signed main()
{
    scanf("%lld %lld %lld", &n, &m, &c);
    /*最小生成树,共3步*/
    vector<Edge> vec;
    //1.存边
    for(int i = 1;i <= m; ++ i)
    {
        int x, y, w;scanf("%lld %lld %lld", &x, &y, &w);
        vec.push_back({x, y, w});//将边存入vec中
    }
    //2.将边升序
    sort(vec.begin(), vec.end(), [](const Edge &u, const Edge &v)
         {
             return u.w < v.w;
         });
    //3.贪心建树,并查集判断连通性
    for(int i = 1;i <= n; ++ i)pre[i] = i;//并查集初始化
    for(auto &i : vec)
    {
        int x = i.x, y = i.y, w = i.w;
        if(root(x) == root(y))continue;
        a[++ cnt] = w;//a自然是升序的
        pre[root(x)] = root(y);
    }
    
    /*生成树结束*/
    
    //以下为二分部分
    int l = -1, r = 2e9;
    
    while(l + 1 != r)
    {
        int mid = (l + r) >> 1;
        if(check(mid))r = mid;
        else l = mid;
    }
    printf("%lld\n", r);
    return 0;
}

E-等腰三角形(easy)

暴力枚举。

枚举出所有三个点组成的三元组,注意不要重复。

可以通过海伦公式来求面积判断是否共线。

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

const int maxn = 500;
const double eps = 1e-6;

struct Point
{
    int x, y;
}p[maxn];

int dist(const Point &u, const Point &v)
{
    int dx = u.x - v.x;
    int dy = u.y - v.y;
    return dx * dx + dy * dy;
}

double area(double a, double b, double c)
{
    double p = (a + b + c) / 2.0;
    return sqrt(p * (p - a) * (p - b) * (p - c));
}

signed main()
{
    int n;scanf("%lld", &n);
    for(int i = 1;i <= n; ++ i)
        scanf("%lld %lld", &p[i].x, &p[i].y);
    int ans = 0;
    for(int i = 1;i <= n; ++ i)
    {
        for(int j = i + 1;j <= n; ++ j)
        {
            for(int k = j + 1;k <= n; ++ k)
            {
                int d1 = dist(p[i], p[j]);
                int d2 = dist(p[i], p[k]);
                int d3 = dist(p[j], p[k]);
                if(area(sqrt(d1), sqrt(d2), sqrt(d3)) <= eps)continue;
                if(d1 == d2 || d1 == d3 || d2 == d3)ans ++;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

F-等腰三角形(hard)

这题肯定不能暴力枚举了。

我们可以发现,以整数点作为定点肯定无法构成等边三角形。

假如我们要构成一个等边三角形,那么就需要有60度的角,假如这个60度的角由两个角x,y相加而成,就有:

\[tan60\degree = tan(x+y)= \frac{tanx + tany}{1-tanx \times tany}
\]

其中tan60是一个无理数,但是后面的tanx, tany都是有理数,一个无理数无法通过有理数的加减乘除算出,所以在整数点中构造不出60度的角。

【牛客小白月赛69】题解与分析A-F【蛋挞】【玩具】【开题顺序】【旅游】【等腰三角形(easy)】【等腰三角形(hard)】

我们枚举每一个点A,然后枚举其他点作为B,然后再查一下有多少C即可(也就是和A距离等于dist(AB)的点),这里只需保证C的下标小于B的下标,就保证了一个偏序关系,就不会重复计算。

接下来需要将“三点共线”的这样“特殊等腰三角形”减去,我们只需计算有多少这样的“线段”即可。

【牛客小白月赛69】题解与分析A-F【蛋挞】【玩具】【开题顺序】【旅游】【等腰三角形(easy)】【等腰三角形(hard)】

枚举每一个点A,再查一下A'是否存在即可,可以对点做一个桶来判断,因为地图并不大。

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

const int maxn = 3009, T = 1000;
const double eps = 1e-6;

struct Point
{
    int x, y;
}p[maxn];

int dist(const Point &u, const Point &v)
{
    int dx = u.x - v.x;
    int dy = u.y - v.y;
    return dx * dx + dy * dy;
}

int cnt[2123456];
bitset<2005> vis[2005];

signed main()
{
    int n;scanf("%lld", &n);
    for(int i = 1;i <= n; ++ i)
    {
        scanf("%lld %lld", &p[i].x, &p[i].y);
        vis[p[i].x + T][p[i].y + T] = true;
    }
    
    
    int ans = 0;
    for(int i = 1;i <= n; ++ i)
    {
        for(int j = 1;j <= n; ++ j)
        {
            if(i == j)continue;
            
            ans += (cnt[dist(p[i], p[j])] ++);
        }
        for(int j = 1;j <= n; ++ j)
        {
            if(i == j)continue;
            
            cnt[dist(p[i], p[j])] = 0;
        }
    }
    int cnt = 0;
    for(int i = 1;i <= n; ++ i)
    {
        for(int j = 1;j <= n; ++ j)
        {
            if(i == j)continue;
            int tx = 2 * p[j].x - p[i].x;
            int ty = 2 * p[j].y - p[i].y;
            if(tx < -500 || tx > 500 || ty < -500 || ty > 500)continue;
            
            if(vis[tx + T][ty + T])cnt ++;
        }
    }
    printf("%lld\n", ans - cnt / 2);
    return 0;
}

? 本文由eriktse原创,创作不易,如果对您有帮助,欢迎小伙伴们点赞?、收藏⭐、留言?

原文链接:https://www.cnblogs.com/eriktse/p/17254354.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:【牛客小白月赛69】题解与分析A-F【蛋挞】【玩具】【开题顺序】【旅游】【等腰三角形(easy)】【等腰三角形(hard)】 - Python技术站

(0)
上一篇 2023年4月18日
下一篇 2023年4月18日

相关文章

  • python实现简单遗传算法

    Python实现简单遗传算法 遗传算法是一种基于自然选择和遗传学原理的优化算法,可以用于解决各种优化问题。本文将详细讲解Python中如何实现简单遗传算法,包括遗传算法的基本原理、编码方式、适应度函数、选择、交叉和变异等操作。 遗传算法的基本原理 遗传算法是一种基于自然选择和遗传学原理的优化算法,其基本原理是通过模拟自然界中的进化过程,从而寻找最优解。遗传算…

    python 2023年5月14日
    00
  • C语言学习之链表的实现详解

    下面我将详细讲解“C语言学习之链表的实现详解”的完整攻略。 1. 链表的定义 链表是一种数据结构,它由一系列节点组成。每个节点由一个数据部分和一个指向下一个节点的地址部分组成。链表可以有多种形式,例如单向链表、双向链表、循环链表等。 2. 链表的实现 2.1. 单向链表 单向链表是最简单的链表形式,一个节点只包含一个指向下一个节点的指针。在C语言中,我们可以…

    数据结构 2023年5月17日
    00
  • 带你了解Java数据结构和算法之哈希表

    带你了解Java数据结构和算法之哈希表 前言 哈希表是一种常用的数据结构,它可以高效地存储和查询数据。在计算机科学领域,哈希表广泛用于实现关联数组(Associative Array)和哈希集合(Hash Set)。本文将带领大家深入了解哈希表数据结构及常用算法实现。 哈希表的原理 哈希表是根据关键码值(Key Value)而直接进行访问的数据结构。也就是说…

    数据结构 2023年5月17日
    00
  • 线段树好题! P2824 [HEOI2016/TJOI2016]排序 题解

    题目传送门 前言 线段树好题!!!!咕咕了挺久的一道题目,很早之前就想写了,今天终于找了个时间A掉了。 题意 给定一个 \(1\) 到 \(n\) 的排列,有 \(m\) 次操作,分两种类型。1.0 l r表示将下标在 \([l, r]\) 区间中的数升序排序。2.1 l r表示将下标在 \([l, r]\) 区间中的数降序排序。给定一个数 \(q\) 询问…

    算法与数据结构 2023年4月17日
    00
  • 为什么说Python可以实现所有的算法

    Python是一种高级编程语言,它具有简单易学、易读易写、功能强大、可扩展性好等特点。Python有丰富的三方库和工具,可以实现各种算法和应用。下面我们将详细讲解为什么说Python可以实现所有的算法。 1. Python的优势 Python是一种高级编程语言,它具有以下优势: 简单易学:语法简单,易于学习和理解,适合初学者入门。 易读易写:Python代码…

    python 2023年5月13日
    00
  • 浅谈PHP链表数据结构(单链表)

    介绍 链表是一种常见的数据结构,它包括单链表和双链表,本文中我们将会介绍PHP的单链表数据结构实现,具体而言我们将会实现一个包括插入节点,删除节点,打印节点等基本操作的单链表,帮助读者深入理解PHP链表数据结构。 创建节点 链表数据结构是由一个个节点组成的,我们首先要实现一个节点的创建函数,这个函数接受两个参数,一个是节点数据,另一个是下一个节点的指针地址。…

    数据结构 2023年5月17日
    00
  • 基于sklearn实现Bagging算法(python)

    基于sklearn实现Bagging算法(python) Bagging算法是一种集成学习方法,它通过对多个基分类器的测结果进行平均或投票来提高模型的准确性。本文将详细介绍如何Python中的sklearn库实现Bagging算法提供两个示例说明。 Bagging算法简介 Bagging法是一种集成学习方法,它通过对多个基分类器的测结果进行平均或投票来提高模…

    python 2023年5月14日
    00
  • 一文教你用python编写Dijkstra算法进行机器人路径规划

    一文教你用Python编写Dijkstra算法进行机器人路径规划 Dijkstra算法是一种用于寻找图中最短路径的算法,它的基本思想是从起点开始逐步扩展到离起点越来越远的节点,直到到达终点为止。在这个过程中,我们维护一个距,用于记录每个节点到起点的距离,以及一个前驱数组用于记录每个节点的前驱节点。在算法结束后,可以通过前驱数组来重构最短路径。 在本文中,我们…

    python 2023年5月14日
    00
合作推广
合作推广
分享本页
返回顶部