比赛传送门:https://ac.nowcoder.com/acm/contest/52441
感觉整体难度有点偏大。
? 作者:Eriktse
? 简介:19岁,211计算机在读,现役ACM银牌选手?力争以通俗易懂的方式讲解算法!❤️欢迎关注我,一起交流C++/Python算法。(优质好文持续更新中……)?
? 个人博客:www.eriktse.com
A-蛋挞
签到题。
只需比较a / b
和a % 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
是一个无理数,但是后面的tanx, tany
都是有理数,一个无理数无法通过有理数的加减乘除算出,所以在整数点中构造不出60
度的角。
我们枚举每一个点A
,然后枚举其他点作为B
,然后再查一下有多少C
即可(也就是和A
距离等于dist(AB)
的点),这里只需保证C
的下标小于B
的下标,就保证了一个偏序关系,就不会重复计算。
接下来需要将“三点共线”的这样“特殊等腰三角形”减去,我们只需计算有多少这样的“线段”即可。
枚举每一个点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技术站