比赛传送门：https://ac.nowcoder.com/acm/contest/52441
感觉整体难度有点偏大。
🎈 作者：Eriktse
🎈 简介：19岁，211计算机在读，现役ACM银牌选手🏆力争以通俗易懂的方式讲解算法！❤️欢迎关注我，一起交流C++/Python算法。（优质好文持续更新中……）🚀
🎈 个人博客：www.eriktse.com
A-蛋挞
签到题。
只需比较a / b和a % b的大小即可。注意开longlong。
#include
#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 less than others");
else printf("same");
return 0;
} B-玩具
排序贪心。
因为我们要将n个玩具全部买下，所以我们免单的玩具价格越高越好，我们将整个数组排升序后从后往前两个两个拿，且只付更高价格的玩具的钱。
#include
#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 = 1; -- i)
{
ans += a[i];
i --;
}
printf("%lldn", ans);
return 0;
} C-开题顺序
dfs。
题目数量比较小，我们可以枚举出所有的开题顺序，然后计算出最终分数取大即可，注意剪枝，当时间超过t的时候可以直接结束，此时的分数已经无效了。
#include
#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 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 D-旅游
最小生成树（并查集） + 二分。
首先我们知道要使得所有点互联，且边权尽可能小，应该建立一棵最小生成树，然后修复树中所有的边即可。
然后国家帮忙修复边权的部分，那么我们可以想到，当p较大时，牛牛的资金肯定可以足够修复剩下的，当p较小时，牛牛要修的路就比较多，就修不了。
所以“y=牛牛能否修复剩下的路”是随着p单调的，当p大时，y=1，当p小时，y=0，我们要做的就是找到那个交界处，二分即可。
#include
#define int long long
using namespace std;
const int maxn = 1e5 + 9;
map 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] vec;
//1.存边
for(int i = 1;i > 1;
if(check(mid))r = mid;
else l = mid;
}
printf("%lldn", r);
return 0;
} E-等腰三角形(easy)
暴力枚举。
枚举出所有三个点组成的三元组，注意不要重复。
可以通过海伦公式来求面积判断是否共线。
#include
#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 F-等腰三角形(hard)
这题肯定不能暴力枚举了。
我们可以发现，以整数点作为定点肯定无法构成等边三角形。
假如我们要构成一个等边三角形，那么就需要有60度的角，假如这个60度的角由两个角x,y相加而成，就有：
$$ tan60degree = tan(x+y)= frac{tanx + tany}{1-tanx times tany}$$
其中tan60是一个无理数，但是后面的tanx, tany都是有理数，一个无理数无法通过有理数的加减乘除算出，所以在整数点中构造不出60度的角。
我们枚举每一个点A，然后枚举其他点作为B，然后再查一下有多少C即可（也就是和A距离等于dist(AB)的点），这里只需保证C的下标小于B的下标，就保证了一个偏序关系，就不会重复计算。
接下来需要将“三点共线”的这样“特殊等腰三角形”减去，我们只需计算有多少这样的“线段”即可。
枚举每一个点A，再查一下A'是否存在即可，可以对点做一个桶来判断，因为地图并不大。
#include
#include
#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 vis[2005];
signed main()
{
int n;scanf("%lld", &n);
for(int i = 1;i 500 || ty 500)continue;
if(vis[tx + T][ty + T])cnt ++;
}
}
printf("%lldn", ans - cnt / 2);
return 0;
} 🎈 本文由eriktse原创，创作不易，如果对您有帮助，欢迎小伙伴们点赞👍、收藏⭐、留言💬
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
