题意： 给定起点和终点，中间有n个站点，给定m条边，每条边有两个边权分别为w1和w2，给定约束条件B，求从起点开始到达终点的最短w1权值和为多少且要满足w2权值和小于等于B？ 题解： 即为有条件限制的dijkstra算法 代码：
#include <bits/stdc++.h> using namespace std; typedef long long LL; int const N = 1100, M = 110; LL const INF = 0x3f3f3f3f3f3f3f3f; // dis[i][j]:走到i点限制条件为j时的最小距离，st[i][j]：在i点且限制条件为j是否走到过， w1:边权，w2:限制条件 LL C[M], e[N * N], ne[N * N], w1[N * N], w2[N * N], idx, h[N], dis[N][110], st[N][110]; struct NODE { LL point, distance, strict; // point:点，distance:最小距离，strict:限制条件 bool operator<(const NODE &w) const { // 按照距离的排序，小的排在前面 return distance > w.distance; } }node[N]; // 放在优先队列内的数据结构 struct POINT { int id, x, y; }point[N]; // 0~n-1为中间站点，n为起点，n+1为终点 struct PATH { int id1, id2, c; }; // 记录id1->id2的边权需要乘上c int sx, sy, ex, ey, B, m, n; // (sx, sy)为起点, (ex, ey)为终点，B为限制条件，m为边类型数目，n为站点数 void add(int a, int b, LL c1, LL c2) { // c1为边权，c2为限制条件 e[idx] = b, w1[idx] = c1, w2[idx] = c2, ne[idx] = h[a], h[a] = idx++; } // 计算id1和id2之间的距离 LL getdis(int id1, int id2) { int x1 = point[id1].x, x2 = point[id2].x, y1 = point[id1].y, y2 = point[id2].y; return (LL)ceil(sqrt((x2 - x1) * 1ll * (x2 - x1) + (y2 - y1) * 1ll * (y2 - y1))); } // 有条件限制的dijkstra算法 LL dijkstra() { priority_queue<NODE> q; // 定义一个按照距离从小到大排序的优先队列 memset(dis, 0x3f, sizeof dis); // 距离初始化 q.push({n, 0, 0}); // 把起点放入队列 dis[n][0] = 0; // 记录源点的距离 while (q.size()) { auto t = q.top(); q.pop(); LL ver = t.point, distance = t.distance, strict = t.strict; // 点、距离、限制条件 if (st[ver][strict]) continue; // 如果走过 st[ver][strict] = 1; for (int i = h[ver]; ~i; i = ne[i]) { // 遍历ver的所有出边 int j = e[i]; if (strict + w2[i] > B) continue; // 如果超过限制条件，跳过 if (dis[j][strict + w2[i]] > distance + w1[i]) { // 如果能够更新 dis[j][strict + w2[i]] = distance + w1[i]; // 更新 q.push({j, dis[j][strict + w2[i]], strict + w2[i]}); // 放入优先队列 } } } LL res = INF; // 记录到终点点的最小距离 for (int i = 0; i <= B; ++i) res = min(res, dis[n + 1][i]); // 遍历每一个限制条件 return res == INF? -1: res; } int main() { memset(h, -1, sizeof h); cin >> sx >> sy >> ex >> ey >> B >> C[0] >> m; // 读入起点、终点、限制条件、初始边类型参数、边类型数目 for (int i = 1; i <= m; ++i) scanf("%lld", &C[i]); // 读入不同类型的边参数 cin >> n; vector<PATH> path; // 记录所有的连边 for (int i = 0, t; i < n; ++i) { scanf("%d%d", &point[i].x, &point[i].y); point[i].id = i; cin >> t; for (int j = 1, obj, c; j <= t; ++j) { scanf("%d%d", &obj, &c); path.push_back({i, obj, c}); } } // 记录起点和终点 point[n].x = sx, point[n].y = sy, point[n + 1].x = ex, point[n + 1].y = ey; point[n].id = n, point[n + 1].id = n + 1; // 起点和终点能够连到所有的站点 for (auto p: path) { add(p.id1, p.id2, C[p.c] * (LL)getdis(p.id1, p.id2), (LL)getdis(p.id1, p.id2)); add(p.id2, p.id1, C[p.c] * (LL)getdis(p.id1, p.id2), (LL)getdis(p.id1, p.id2)); } for (int i = 0; i < n; ++i) { add(n, i, C[0] * (LL)getdis(n, i), (LL)getdis(n, i)); add(i, n, C[0] * (LL)getdis(n, i), (LL)getdis(n, i)); add(n + 1, i, C[0] * (LL)getdis(n + 1, i), (LL)getdis(n + 1, i)); add(i, n + 1, C[0] * (LL)getdis(n + 1, i), (LL)getdis(n + 1, i)); } add(n, n + 1, C[0] * (LL)getdis(n, n + 1), (LL)getdis(n, n + 1)); add(n + 1, n, C[0] * (LL)getdis(n, n + 1), (LL)getdis(n, n + 1)); // 计算有条件的dijkstra算法 cout << dijkstra(); return 0; }题意： 统计是否有的动物的个数比其他的动物个数总和都多 题解： unordered_map计数，签到 代码：
#include <bits/stdc++.h> using namespace std; int n; char name[21]; unordered_map<string, int> mp; int main() { // freopen("in.txt", "r", stdin); cin >> n; string s; for (int i = 1; i <= n; ++i) { cin >> s; // scanf("%s", name); mp[s]++; } int flg = 1; for (auto m: mp) { auto cur = m.second; auto res = n - m.second; if (cur > res) { cout << m.first; flg = 0; break; } } if (flg) cout << "NONE\n"; return 0; }题意： 给定n个数字，然后做mex运算，注意每个数字的长度可能最长为100 题解： 按照离散化的思想，大于1e6的数字可以直接舍去，然后mex运算即可 代码：
#include <bits/stdc++.h> using namespace std; int n; char name[21]; unordered_set<long long> mp; int main() { // freopen("in.txt", "r", stdin); cin >> n; for (int i = 1, t; i <= n; ++i) { string s; cin >> s; if (s[0] == '-') continue; if (s.size() >= 7) continue; mp.insert(atoll(s.c_str())); } for (int i = 0; ; ++i) { if (!mp.count(i)) { cout << i << endl; break; } } return 0; }题意： 计算几何 题解： sloved by l 代码：
#include <bits/stdc++.h> using namespace std; typedef long long LL; int T, n; struct point{ LL x,y; point(){} point(LL _x, LL _y):x(_x), y(_y){} double operator * (point b){ return x * b.y - y * b.x; } point operator + (point b){ return point(x + b.x, y + b.y); } void input(){scanf("%lld%lld", &x, &y);} }; typedef vector<point>Polygon; typedef point Vector; LL rev(LL x){ if(x > 0)return x; else return -x; } LL Square(Polygon poly){ int num = poly.size(); LL res = 0; for(int i = 0; i < num - 1; i++){ res += (poly[i] * poly[i + 1]); } return rev(res); } int main(){ cin >> T; LL ans = 0; while(T--){ Polygon poly; poly.clear(); scanf("%d", &n); for(int i = 0; i < n; i++) { point x; x.input(); poly.push_back(x); } poly.push_back(poly[0]); LL res = Square(poly); ans += res; } printf("%lld\n", ans / 2); return 0; }题意： 按照公式计算 题解： 签到 代码：
#include <bits/stdc++.h> using namespace std; int n; char name[21]; unordered_map<string, int> mp; int main() { // freopen("in.txt", "r", stdin); double n1, n2, n12; cin >> n1 >> n2 >> n12; cout << floor((n1 + 1) * (n2 + 1) / (n12 + 1) - 1); return 0; }