域名备案终于过审了2
测试一下代码与 latex
第二题手抖把
70 + 40 + 100,rk 7
A 赛艇表演
给出一个边权,点权无向连通图,对于每个
图论建模,最短路
考虑建模
先将所有边权乘
时间复杂度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
const int maxn = 4e5 + 10, maxm = 4e5 + 10;
int n, m, s;
int cnt, head[maxn];
struct edge { int nxt, to; ll w; } e[maxm << 2];
void add(int u, int v, int w) { e[++cnt].to = v, e[cnt].w = w, e[cnt].nxt = head[u], head[u] = cnt; }
ll w[maxn], dis[maxn];
bool vis[maxn];
void dij() {
priority_queue<pii, vector<pii>, greater<pii> > f;
for (int i = 1; i <= n + 1; ++i) dis[i] = LONG_LONG_MAX;
dis[s] = 0, f.push(make_pair(0, s));
while (!f.empty()) {
int now = f.top().second; f.pop();
if (vis[now]) continue;
vis[now] = true;
for (int i = head[now]; i; i = e[i].nxt) { int v = e[i].to;
if (dis[v] > dis[now] + e[i].w) dis[v] = dis[now] + e[i].w, f.push(make_pair(dis[v], v));
}
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1, u, v; i <= m; ++i) { ll w;
scanf("%d %d %lld", &u, &v, &w);
add(u, v, w << 1), add(v, u, w << 1);
}
for (int i = 1; i <= n; ++i) scanf("%lld", &w[i]);
for (int i = 1; i <= n; ++i) add(n + 1, i, w[i]), add(i, n + 1, w[i]);
s = n + 1;
dij();
for (int i = 1; i <= n; ++i) printf("%lld ", dis[i]);
return 0;
}
如果多次最短路会导致错误的复杂度,就考虑建模
B 逮虾户
求解关于
二分答案
单调性显然
二分即可
时间复杂度
#include <bits/stdc++.h>
using namespace std;
typedef long double db;
const int maxn = 1000 + 10;
const db eps = 1e-9;
const db inf = 1e17;
int n;
db f, s[maxn], t[maxn], mx = -0x7fffffff, ans;
db check(db x) {
db res = 0;
for (int i = 1; i <= n; ++i) res += s[i] / (t[i] + x);
return res;
}
int main() {
scanf("%d %llf", &n, &f);
db l = -1e9, r = 1e9;
for (int i = 1; i <= n; ++i) scanf("%llf %llf", &s[i], &t[i]), l = max(l, -t[i]);
l += eps;
while (r - l > eps) {
db mid = (l + r) / 2;
if (check(mid) > f) l = mid;
else r = mid;
}
printf("%.10f", (double)l);
return 0;
}
C 战略威慑
求树上两条不交链的长度乘积最大值
直径
一定可以通过断掉一条边,使得树分成两个部分,分别求出两个树的直径即可
时间复杂度
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200 + 10;
typedef long long ll;
int n;
ll ans;
int cnt, head[maxn];
struct edge { int nxt, fr, to, num; } e[maxn << 1];
void add(int u, int v) { e[++cnt].to = v, e[cnt].nxt = head[u], e[cnt].fr = u, head[u] = cnt; }
int mx, tmp;
void dfs(int u, int fa, int dep, int& num) {
if (mx < dep) { mx = dep, tmp = u; }
for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to;
if (v == fa || (i + 1 == num || i == num)) continue;
dfs(v, u, dep + 1, num);
}
}
ll work(int num) {
mx = -1;
int u = e[num].fr, v = e[num].to;
dfs(u, 0, 0, num);
mx = -1;
dfs(tmp, 0, 0, num);
int len1 = mx;
mx = -1;
dfs(v, 0, 0, num);
mx = -1;
dfs(tmp, 0, 0, num);
int len2 = mx;
return 1ll * len1 * len2;
}
int main() {
scanf("%d", &n);
for (int i = 1, u, v; i < n; ++i) {
scanf("%d %d", &u, &v);
add(u, v), add(v, u);
}
for (int i = 2; i <= cnt; i += 2) {
ll tmp = work(i);
ans = max(ans, tmp);
}
printf("%lld\n", ans);
return 0;
}
这种不相交的问题往往可以化为断边枚举
总结
做的好的地方
- 先写了暴力
做的不好的地方
- 二分写假了,熟练度不够
递推公式:
求和公式:
彩色表达式:
计算:
计算:
算法表达示例:
for
颜色:
集合:
向量:
多行表达式:
test2
您太强啦!
orz orz
ssss