较量传送门：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 longusing 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 longusing 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 longusing 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 longusing 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 longusing 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度的角。
咱们枚举每一个点A，而后枚举其余点作为B，而后再查一下有多少C即可（也就是和A间隔等于dist(AB)的点），这里只需保障C的下标小于B的下标，就保障了一个偏序关系，就不会反复计算。
接下来须要将“三点共线”的这样“非凡等腰三角形”减去，咱们只需计算有多少这样的“线段”即可。
枚举每一个点A，再查一下A'是否存在即可，能够对点做一个桶来判断，因为地图并不大。
#include <bits/stdc++.h>#include <bits/extc++.h>#define int long longusing 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原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞、珍藏⭐、留言